Related Experiment Video
Updated: May 15, 2026
10:36
Optimization of An Air-Based Heat Management System for Dusty Particulate Matter-Covered Lithium-Ion Battery Packs
Published on: November 3, 2023
A deterministic annealing algorithm for approximating a solution of the linearly constrained nonconvex quadratic
Chuangyin Dang1, Jianqing Liang, Yang Yang
1Department of Systems Engineering & Engineering Management, City University of Hong Kong, Kowloon, Hong Kong. mecdang@cityu.edu.hk
Summary
This study introduces a deterministic annealing algorithm for solving nonconvex quadratic minimization problems with linear constraints. The novel approach effectively handles box and linear equality constraints, demonstrating efficiency and effectiveness in preliminary tests.
Area of Science:
- Optimization
- Numerical Analysis
- Operations Research
Background:
- Nonconvex quadratic minimization problems with linear constraints are common in various fields.
- Existing algorithms may face challenges with box and linear equality constraints simultaneously.
- Deterministic annealing offers a potential framework for addressing these complexities.
Purpose of the Study:
- To propose a novel deterministic annealing algorithm for linearly constrained nonconvex quadratic minimization.
- To develop an algorithm that effectively handles both box and linear equality constraints.
- To assess the efficiency and effectiveness of the proposed algorithm.
Main Methods:
- The algorithm utilizes a Hopfield-type barrier function for box constraints.
- Lagrange multipliers are employed to manage linear equality constraints.
- A sequence of barrier problems with descending barrier parameters is solved iteratively.
- Feasible descent directions are determined using a globally convergent procedure for updating Lagrange multipliers.
Main Results:
- The algorithm converges to a stationary point of the barrier problem for any given barrier parameter value.
- Box constraints are automatically satisfied within a step length of zero to one.
- Preliminary numerical results indicate the algorithm is effective and efficient.
Conclusions:
- The proposed deterministic annealing algorithm provides a viable method for solving linearly constrained nonconvex quadratic minimization problems.
- The integration of barrier functions and Lagrange multipliers offers a robust approach to constraint handling.
- The algorithm shows promise for practical applications due to its demonstrated effectiveness and efficiency.
Related Concept Videos
01:29Mechanistic Models: Compartment Models in Algorithms for Numerical Problem Solving
Mechanistic models play a crucial role in algorithms for numerical problem-solving, particularly in nonlinear mixed effects modeling (NMEM). These models aim to minimize specific objective functions by evaluating various parameter estimates, leading to the development of systematic algorithms. In some cases, linearization techniques approximate the model using linear equations.
In individual population analyses, different algorithms are employed, such as Cauchy's method, which uses a...
In individual population analyses, different algorithms are employed, such as Cauchy's method, which uses a...
01:26Linearization and Approximation
Linearization is a mathematical technique used to approximate complex, nonlinear functions with simpler linear models in the vicinity of a chosen reference point. The method is based on the idea that, although a function may be difficult to evaluate exactly, its behavior near a specific input value can often be closely approximated by the tangent line at that point. This approach is particularly useful when small deviations from a known value are involved.Consider the square root function, for...
01:29Application of Linearization and Approximation
A drone flying through complex terrain often relies on more than one sensing method to estimate small changes in altitude. Along with direct measurements, air pressure provides a useful indirect indicator of vertical movement. Atmospheric pressure decreases as altitude increases, and this relationship is commonly described using an exponential model. Although accurate, converting pressure measurements into altitude values requires calculations that are too complex to perform repeatedly during...
01:21Linear Approximation in Time Domain
Nonlinear systems often require sophisticated approaches for accurate modeling and analysis, with state-space representation being particularly effective. This method is especially useful for systems where variables and parameters vary with time or operating conditions, such as in a simple pendulum or a translational mechanical system with nonlinear springs.
For a simple pendulum with a mass evenly distributed along its length and the center of mass located at half the pendulum's length, the...
For a simple pendulum with a mass evenly distributed along its length and the center of mass located at half the pendulum's length, the...
01:29Application of Nonlinear Inequalities
A nonlinear inequality describes a comparison involving an expression that curves or behaves more complexly than a straight line. These inequalities often appear in forms that include squares, products, or variables in the denominator.To solve such an inequality, one starts by rewriting it so that zero appears on one side. For example, the inequality: can be factored as: This form makes it easier to identify the values that cause the expression to equal zero. In this case, the key values are 3...
01:30Newton’s Method
Newton’s Method is a powerful iterative technique for approximating the roots of real-valued, differentiable functions, particularly when analytical solutions are impractical. This approach is widely used in scientific computing, engineering, and finance, where equations may be too complex for traditional algebraic methods to handle. The method relies on an iterative process that refines an initial estimate using the function’s derivative to approach the true solution progressively.