非凸二次规划问题的一个全局优化方法
|
摘要
考虑的问题是线性约束下极小化二次目标函数的数学规划问题(QP)。在可行域是非空紧集假设下,利用KKT条件,将原问题等价转化为带线性互补约束、线性目标函数的问题(LPC),对(LPC)提出了一个全局优化算法。该方法的主要思想是生成一个点对序列,使它或在有限步迭代后终止于(LPC)的最优解或收敛于(LPC)的最优解。证明了算法的收敛性,并通过求解构造的实例说明了此方法的有效性。
Considering the problem QP is that minimum quadratic objective function with linear constraints.Under the hypothesis of the feasible region is non-empty compact set,using the KKT conditions of the problem,to bring the original problem is transformed into the problem of linear objective function with complementarity's constraints LPC.On a global optimization algorithm is proposed.The main idea of the method is to generate a sequence of points either ending at a global optimal solution within a finite number of iterations or converging to a global optimal solution of the LPC.To prove the finite convergence of the algorithm and by solving construction example is given to illustrate the effectiveness of this method.
Considering the problem QP is that minimum quadratic objective function with linear constraints.Under the hypothesis of the feasible region is non-empty compact set,using the KKT conditions of the problem,to bring the original problem is transformed into the problem of linear objective function with complementarity's constraints LPC.On a global optimization algorithm is proposed.The main idea of the method is to generate a sequence of points either ending at a global optimal solution within a finite number of iterations or converging to a global optimal solution of the LPC.To prove the finite convergence of the algorithm and by solving construction example is given to illustrate the effectiveness of this method.
引文
[1]Horst R,Pardalos P M,Thoai N V.全局优化引论[M].黄红选译.北京:清华大学出版社,2003.Horst R,Pardalos P M,Thoai N V.Introduction to global optimization[M].Huang H X translation.Beijing:Tshinghua University Press,2003.
[2]Pardlos P M,Vavasis S A.Quadratic programming with one negative eigenvalue is NP-hard[J].Global Optim,1991,1(1):15-22.
[3]Vandenbusscite D,Nemhauser G.A branch-and-cut algorithmn for nonconvex quadratic programs with box constraints[J].Math Program,2005,102(3):559-575.
[4]Sherali H D,Tuncbilek C H.A reformulation-convexification approach for solving nonconvex quadratic programmi-ng problems[J].Global Optim,1995,7:1-31.
[5]Burer S,Vandenbussche D.A finite branch-and-bound algorithm for nonconvex quadratic programming via semidifinite relaxations[J].Math Program,2008,113(2):259-282.
[6]吴至友.求解全局优化问题的一种新方法[J].重庆师范大学学报:自然科学版,2009,26(4):1-8.Wu Z Y.A New Method for Global Optimization Problems[J].Journal of Chongqing Normal University:NaturalScience,2009,26(4):1-8.
[7]Thoai N V,Yamamoto Y,Yoshise A.Global optimization method for solving mathematical programs with linear complementarity constraints[J].Journal of Optimization Theory and Applications,2005,124(2):467-490.
[8]Fukushima M,Luo Z Q,Pang J S.A Global convergent sequential quadratic programming algorithm for mathem-atical programs with linear complementarity constraints[J].Computational Optimization and Applications,1998,10:5-34.
[2]Pardlos P M,Vavasis S A.Quadratic programming with one negative eigenvalue is NP-hard[J].Global Optim,1991,1(1):15-22.
[3]Vandenbusscite D,Nemhauser G.A branch-and-cut algorithmn for nonconvex quadratic programs with box constraints[J].Math Program,2005,102(3):559-575.
[4]Sherali H D,Tuncbilek C H.A reformulation-convexification approach for solving nonconvex quadratic programmi-ng problems[J].Global Optim,1995,7:1-31.
[5]Burer S,Vandenbussche D.A finite branch-and-bound algorithm for nonconvex quadratic programming via semidifinite relaxations[J].Math Program,2008,113(2):259-282.
[6]吴至友.求解全局优化问题的一种新方法[J].重庆师范大学学报:自然科学版,2009,26(4):1-8.Wu Z Y.A New Method for Global Optimization Problems[J].Journal of Chongqing Normal University:NaturalScience,2009,26(4):1-8.
[7]Thoai N V,Yamamoto Y,Yoshise A.Global optimization method for solving mathematical programs with linear complementarity constraints[J].Journal of Optimization Theory and Applications,2005,124(2):467-490.
[8]Fukushima M,Luo Z Q,Pang J S.A Global convergent sequential quadratic programming algorithm for mathem-atical programs with linear complementarity constraints[J].Computational Optimization and Applications,1998,10:5-34.