基于拉格朗日对偶的一类全局优化算法

Global Optimization Algorithm Based on Lagrangian Dual

针对带有非凸二次函数约束的非凸二次规划问题(NQP),提出了一个基于拉格朗日对偶的确定型全局优化算法,这类优化算法可广泛应用于工程设计和非线性系统的鲁棒稳定性分析等实际问题中.为求解此问题,首先,应用拉格朗日对偶对原问题进行下界估计.其次,为克服拉格朗日对偶问题的非凸性,利用线性化方法,得到拉格朗日对偶问题的线性下界估计,并且由此建立了NQP拉格朗日对偶问题的松弛线性规划(RLP).如此通过对RLP可行域的细分和一系列RLP的求解过程,从理论上证明了算法收敛到NQP的全局最优解.数值算例应用结果表明,该方法是可行的.

A deterministic global optimization algorithm based on Lagrangian dual is proposed for solving the nonconvex quadratic programming with nonconvex quadratic constraints, which is often encountered in technical design and operational research. By utilizing a linearized method the difficulty that the Lagrangian dual problem is nonconvex is solved and the linearization relaxation of the Lagrangian is obtained. The proposed branch and bound algorithms are convergent to the global minimum via successive refinement of the linear relaxation of the Lagrangian dual problem and the solutions to a series of the relaxation of linear programming. Interval Newton method is used to accelerate the convergence of the algorithm. Numerical experiments are given to verify the feasibility of the proposed algorithm.