几类二次约束二次优化问题的全局最优性条件
|
摘要
二次约束条件下的二次规划是很值得研究的一类问题,一方面它频繁地出现在科学研究、工程技术等应用领域,另一方面许多非线性问题也可转化为此类模型进行求解。本文主要利用求非凸规划全局最优性条件的新方法—L-次微分方法(与凸分析中的概念不同,一个函数在某点的L-次微分是一个函数集,该函数集可能是一些非线性函数所组成的集合。),考察和研究了几类特殊的带二次约束二次规划问题的全局最优性条件。
在第一章我们首先简要介绍了研究全局最优性条件的必要性和研究现状,然后引入了函数的L-次微分和集合的L-正则锥的概念,在此基础上根据文[1]给出了一般带二次约束二次规划问题的全局最优性的拉格朗日乘子条件。第二章主要讨论无约束0-1二次规划的全局最优性条件。首先在文[2]结论基础上做简单变换后得到了无约束0-1二次规划问题的充分条件和必要条件,然后又把结论进一步推广至更一般的情形,最后又考虑选取不同的函数集L给出了一个充分必要条件。在第三章主要考虑了两类有箱约束的二次约束二次规划问题的全局最优性条件。第四章研究了带二次等式约束二次规划问题的全局优化问题。第五章是总结和进一步要做的工作。
Quadratically constrained quadratic programming problems are worthy of study both because they frequently appear in many applied field of science and technology, and many other nonlinear problems are converted into this form. This paper present a new approach which make use of a global subdifferential: L- subdifferentail. Unlike local or convex subdifferential,an L-subdifferential is defined by functions which are not necessarily linear functions. We consided global optimality conditions of some quadratically constrained quadratic programming problems.
In the first chapter of this paper, we first introduce the recent developments in global optimality conditions, then we introduce the definitions of L-subdifferential and L-normal cone. Finally, we obtain some global optimality conditions for non-convex quadratic minimization problems with quadratic constraints. The global optimality conditions of 0-1 programming problems are discussed in chaper two. In chaper three,we establish conditions which endure that a feasible point is a global minimization problem subject to box constraints and quadratic intger minimization problem subject to box constraints. In chaper four, we consider the constrained optimization problem with a quadratic cost functional and two quadratic equality constraints. A necessary and sufficient condition to characterize a local optimal solution to be global is established.
在第一章我们首先简要介绍了研究全局最优性条件的必要性和研究现状,然后引入了函数的L-次微分和集合的L-正则锥的概念,在此基础上根据文[1]给出了一般带二次约束二次规划问题的全局最优性的拉格朗日乘子条件。第二章主要讨论无约束0-1二次规划的全局最优性条件。首先在文[2]结论基础上做简单变换后得到了无约束0-1二次规划问题的充分条件和必要条件,然后又把结论进一步推广至更一般的情形,最后又考虑选取不同的函数集L给出了一个充分必要条件。在第三章主要考虑了两类有箱约束的二次约束二次规划问题的全局最优性条件。第四章研究了带二次等式约束二次规划问题的全局优化问题。第五章是总结和进一步要做的工作。
Quadratically constrained quadratic programming problems are worthy of study both because they frequently appear in many applied field of science and technology, and many other nonlinear problems are converted into this form. This paper present a new approach which make use of a global subdifferential: L- subdifferentail. Unlike local or convex subdifferential,an L-subdifferential is defined by functions which are not necessarily linear functions. We consided global optimality conditions of some quadratically constrained quadratic programming problems.
In the first chapter of this paper, we first introduce the recent developments in global optimality conditions, then we introduce the definitions of L-subdifferential and L-normal cone. Finally, we obtain some global optimality conditions for non-convex quadratic minimization problems with quadratic constraints. The global optimality conditions of 0-1 programming problems are discussed in chaper two. In chaper three,we establish conditions which endure that a feasible point is a global minimization problem subject to box constraints and quadratic intger minimization problem subject to box constraints. In chaper four, we consider the constrained optimization problem with a quadratic cost functional and two quadratic equality constraints. A necessary and sufficient condition to characterize a local optimal solution to be global is established.
引文
[1]Strekalovsky,A.:Global Optimality Conditions for nonconvex optimization[J].J.Global Optim.1998,12,4:415-434.
[2]Jeyakumar,V.,Rubinov,A.M.,Wu Z.Y.:Non-convex quadratic minimization problems with quadratic constraints:global optimality conditions[J].Math Program.2007,110,3:521-541
[3]Jeyakumar,V.,Rubinov,A.M.,Wu Z.Y.:Sufficient global optimality conditions for Non-convex quadratic minimization problems with box constraints.[J].J.Global optim.2006,36:471-481
[4]Ye Y.Y.:Approximation Quadratic Programming with Bound and Quadratic Constraints.Math.Prog.1999,84:216-226.
[5]Beck,A.,Teboulle,M.:Global Optimality Conditions for Quadratic Optimization Problems with Binary Constraints[J].SIAM J.optim.2002,11:179-188.
[6]吴至友,白富生.:一种新的求全局优化最优性条件的方法[J].重庆大学学报(自然科学版).2006,23:1-5.
[7]Goemans,M.X.,Williamson,D.P.:Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems using Semidef'mite Programming[J].ACM,1995,42:1115-1145.
[8]Beck,A.and Teboulle,M.:Global Optimality Conditions for Quadratic with Binar Constraints[J].SIAM Journal on Optimization,2000,11:179-188.
[9]Hansen,E.R.:Global Optimization Using Interval Analysis-the One dimensional Case,[J]Numerische Mathematik.1980,34:247-270.
[10]Rockafellar,R.T.:Convex Analysis[M].Princeton University Press,Princeton,New Jersey,1970.
[11]Nesterov,Y.,Nemirovski,A.:Interior-Point Polynomial Algorithms in Convex Programming[M].SIAM,Philadelphia,Pennsylvania,1993.
[12]Hiriart-Urruty,J.B.:Conditions for Global Optimality,Handbook for Global Optimization[M].Kluwer Academic Publishers,Dordrecht,Holland,1999,1-26.
[13]Hiriart-Urruty,J.B.:Conditions for Global Optimality 2[J].Journal of Global Optimization,1998,13:349-367.
[14]Kuhn,H.W.,Tucker,A.W.:Nonlinear Programming.[M]Neyman,editor,Proc.of the second Berkeley Symposium on Math.Stat,and Prob.,page 481-492.U.of California Press,Berkeley,California,1951.
[15]Swarup,K.:Indefinite Quadratic Programming with a Quadratic Constraint[J].Ekonomickomatem.Obzor.1966,4:69-75.
[16]More,J.J.:Generalizations of The Region Problem[J].Optimization Methods and Software 2,1993,189-209.
[17]Carraresi,P.,Farinaccio,F.and Malucelli,F.:Testing Optimality for Quadratic 0-1Problems[J].Mathematical Programming,1999,85:407-421.
[18]Nstreicher,K.,Chen,X.,Wolkowicz,H.and Yuan Y.:Strong Duality for a Trust Region Type Relaxation of the Quadratic Assignment Problem[J].Linear Algebra and Its Applications,1999,301:121-136.
[19]Horst,R.and Pardalos,P.M.and Thoai,N.V.著,黄红选 译.全局优化引论[M].清华大学出版社,北京,2003.
[20]史树中.:凸分析[M].上海科学技术出版社,1990.
[21]Hiriart-Urruty,J.B.:Global Optimality Conditions in Maximizing a Convex Quadratic Function under Convex Quadratic Constraints[J].J.of Global Optimization 2001,21:445-455.
[22]Nstreicher,K.,Wolkowicz,H.:On Lagrangian Relaxation of Quadrtic Matrix Constraints[J].SIAM Journal on Matrix Analysis and Applications,2000,22:41-55.
[23]Peng,J.M.,Yuan,Y.X.:Optimality Condtions for The Minimization of A Quadratic With Two Quadrtic Constraints[J].OPTIAI.,1997,3:579-594.
[24]Nstreicher,K.,Brixius,N.W.:A New Bound for the Quadratic Assignment Problem Based on Convex Quadratic Programming[J]Mathematical Programming.2001,89:341-357.
[25]Bazaraa,M.S.,Sherali,H.D.and Shetty,G.M.:Nonlinear programming-Theory and Algorithms[M].John Wiley & Sons,Inc,1993.
[26]Beck,A.,Teboulle,M.:Global optimality conditions for quadratic optimization problems with binary constraints[J].SIAM.,2000,1:179-188.
[27]Chen,W.,Zhang,L.S.:Global optimality conditions for quadratic 0-1 Optimization Problems[J].J.of Global Optimization.
[28]Bar-on,J.R.,Grasse,K.:A.Global Optimization of a Quadratic Functional with Quadratic Equality Constraints[J].Journal of Optimization Theory and Applications.1994,2:379-386.
[29]Bar-on,J.R.,Grasse,K.:A.Global Optimization of a Quadratic Functional with Quadratic Equality Constraints,Part 2[J],.Journal of Optimization Theory and Applications,1997,3:547-556.
[30]Shi Kuiran and Wang Cheng.:On a Class of Quadratic Programming Problem with Equality Constraints[J].Jonrnal of NanJing University Mathematical Biquarterly.2006,1:98-105.
[31]申培萍.:全局优化方法[M].科学出版社.北京,2006
[32]谢政,李建平,汤泽滢.:非线性最优化[M].国防科技大学出版社.湖南,长沙,2002.
[33]Strang,G.:Linear Algebra and Its Applications[M],Harcourt Brace Jovanovich,Orlando,Florida,1986.
[34]王杉林.:一类混合二次规划问题的全局最优性充分条件[J].兰州大学学报(专辑),2008,44.
[2]Jeyakumar,V.,Rubinov,A.M.,Wu Z.Y.:Non-convex quadratic minimization problems with quadratic constraints:global optimality conditions[J].Math Program.2007,110,3:521-541
[3]Jeyakumar,V.,Rubinov,A.M.,Wu Z.Y.:Sufficient global optimality conditions for Non-convex quadratic minimization problems with box constraints.[J].J.Global optim.2006,36:471-481
[4]Ye Y.Y.:Approximation Quadratic Programming with Bound and Quadratic Constraints.Math.Prog.1999,84:216-226.
[5]Beck,A.,Teboulle,M.:Global Optimality Conditions for Quadratic Optimization Problems with Binary Constraints[J].SIAM J.optim.2002,11:179-188.
[6]吴至友,白富生.:一种新的求全局优化最优性条件的方法[J].重庆大学学报(自然科学版).2006,23:1-5.
[7]Goemans,M.X.,Williamson,D.P.:Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems using Semidef'mite Programming[J].ACM,1995,42:1115-1145.
[8]Beck,A.and Teboulle,M.:Global Optimality Conditions for Quadratic with Binar Constraints[J].SIAM Journal on Optimization,2000,11:179-188.
[9]Hansen,E.R.:Global Optimization Using Interval Analysis-the One dimensional Case,[J]Numerische Mathematik.1980,34:247-270.
[10]Rockafellar,R.T.:Convex Analysis[M].Princeton University Press,Princeton,New Jersey,1970.
[11]Nesterov,Y.,Nemirovski,A.:Interior-Point Polynomial Algorithms in Convex Programming[M].SIAM,Philadelphia,Pennsylvania,1993.
[12]Hiriart-Urruty,J.B.:Conditions for Global Optimality,Handbook for Global Optimization[M].Kluwer Academic Publishers,Dordrecht,Holland,1999,1-26.
[13]Hiriart-Urruty,J.B.:Conditions for Global Optimality 2[J].Journal of Global Optimization,1998,13:349-367.
[14]Kuhn,H.W.,Tucker,A.W.:Nonlinear Programming.[M]Neyman,editor,Proc.of the second Berkeley Symposium on Math.Stat,and Prob.,page 481-492.U.of California Press,Berkeley,California,1951.
[15]Swarup,K.:Indefinite Quadratic Programming with a Quadratic Constraint[J].Ekonomickomatem.Obzor.1966,4:69-75.
[16]More,J.J.:Generalizations of The Region Problem[J].Optimization Methods and Software 2,1993,189-209.
[17]Carraresi,P.,Farinaccio,F.and Malucelli,F.:Testing Optimality for Quadratic 0-1Problems[J].Mathematical Programming,1999,85:407-421.
[18]Nstreicher,K.,Chen,X.,Wolkowicz,H.and Yuan Y.:Strong Duality for a Trust Region Type Relaxation of the Quadratic Assignment Problem[J].Linear Algebra and Its Applications,1999,301:121-136.
[19]Horst,R.and Pardalos,P.M.and Thoai,N.V.著,黄红选 译.全局优化引论[M].清华大学出版社,北京,2003.
[20]史树中.:凸分析[M].上海科学技术出版社,1990.
[21]Hiriart-Urruty,J.B.:Global Optimality Conditions in Maximizing a Convex Quadratic Function under Convex Quadratic Constraints[J].J.of Global Optimization 2001,21:445-455.
[22]Nstreicher,K.,Wolkowicz,H.:On Lagrangian Relaxation of Quadrtic Matrix Constraints[J].SIAM Journal on Matrix Analysis and Applications,2000,22:41-55.
[23]Peng,J.M.,Yuan,Y.X.:Optimality Condtions for The Minimization of A Quadratic With Two Quadrtic Constraints[J].OPTIAI.,1997,3:579-594.
[24]Nstreicher,K.,Brixius,N.W.:A New Bound for the Quadratic Assignment Problem Based on Convex Quadratic Programming[J]Mathematical Programming.2001,89:341-357.
[25]Bazaraa,M.S.,Sherali,H.D.and Shetty,G.M.:Nonlinear programming-Theory and Algorithms[M].John Wiley & Sons,Inc,1993.
[26]Beck,A.,Teboulle,M.:Global optimality conditions for quadratic optimization problems with binary constraints[J].SIAM.,2000,1:179-188.
[27]Chen,W.,Zhang,L.S.:Global optimality conditions for quadratic 0-1 Optimization Problems[J].J.of Global Optimization.
[28]Bar-on,J.R.,Grasse,K.:A.Global Optimization of a Quadratic Functional with Quadratic Equality Constraints[J].Journal of Optimization Theory and Applications.1994,2:379-386.
[29]Bar-on,J.R.,Grasse,K.:A.Global Optimization of a Quadratic Functional with Quadratic Equality Constraints,Part 2[J],.Journal of Optimization Theory and Applications,1997,3:547-556.
[30]Shi Kuiran and Wang Cheng.:On a Class of Quadratic Programming Problem with Equality Constraints[J].Jonrnal of NanJing University Mathematical Biquarterly.2006,1:98-105.
[31]申培萍.:全局优化方法[M].科学出版社.北京,2006
[32]谢政,李建平,汤泽滢.:非线性最优化[M].国防科技大学出版社.湖南,长沙,2002.
[33]Strang,G.:Linear Algebra and Its Applications[M],Harcourt Brace Jovanovich,Orlando,Florida,1986.
[34]王杉林.:一类混合二次规划问题的全局最优性充分条件[J].兰州大学学报(专辑),2008,44.