非线性不等式约束优化的强次可行原始对偶内点算法
|
摘要
在本文中,我们考虑非线性不等式约束优化问题。我们知道,原始对偶内点算法是求解这类问题的重要的可行方向法之一。这种方法每步迭代不用求解QP子问题,而是求解线性方程组来得到可行下降方向。工作集技术经常被用来减少计算量。同时,对于初始点任意的问题,强次可行方向法是行之有效的解法之一。
本文结合原始对偶内点法的性质和强次可行方向法的思想,利用一种新的确定积极约束的“工作集”技术,提出了一个解决不等式约束优化的原始对偶内点算法。新算法的主要性质如下:(ⅰ)在每步迭代中,该算法只需要求解两到三个含有相同系数矩阵的简约线性方程组;(ⅱ)初始迭代点可以任意选取,系数矩阵都是可逆的。在有限次迭代后,迭代点成为一个严格内点,搜索方向是可行下降的,目标函数单调下降;(ⅲ)在适当的假设下,算法具有全局收敛性和超线性收敛性。特别地,此算法放松了对于修正矩阵的正定性约束。最后,我们给出了一些数值试验结果。
In this thesis, we consider the nonlinear inequality constrained optimization problems. We know that primal-dual interior point methods are one of the important methods of feasible directions for solving this kind of problems. At each iteration, the methods only need to solve linear equation systems in stead of QP subproblem to obtain feasible and descent direction. And "working set" technique for determining the active set is often used to reduce computational cost. At the same time, strongly sub-feasible direction methods are one of effective methods for solving the problems starting with an infeasible initial point.
In this work, combining the properties of primal-dual interior point methods and the strongly sub-feasible method, by means of a new "working set" technique, we present a new primal-dual interior point algorithm for inequality constrained optimization. The main properties of the new algorithm are described as follows: (i) At each iteration, the algorithm solves only two or three reduced systems of linear equations with a common coefficient matrix; (ii) The initial iteration point can be chosen arbitrarily and the coefficient matrix is uniformly nonsingular. After finite iterations, the iterate becomes an interior point of the feasible set, then the searching direction is feasible and the objective function is monotone decreasing; (iii) Under suitable assumptions, the proposed algorithm possesses global and superlinear convergence. In particular, the positive definiteness assumption on the Hessian estimate is relaxed. Finally, promising numerical results are reported.
本文结合原始对偶内点法的性质和强次可行方向法的思想,利用一种新的确定积极约束的“工作集”技术,提出了一个解决不等式约束优化的原始对偶内点算法。新算法的主要性质如下:(ⅰ)在每步迭代中,该算法只需要求解两到三个含有相同系数矩阵的简约线性方程组;(ⅱ)初始迭代点可以任意选取,系数矩阵都是可逆的。在有限次迭代后,迭代点成为一个严格内点,搜索方向是可行下降的,目标函数单调下降;(ⅲ)在适当的假设下,算法具有全局收敛性和超线性收敛性。特别地,此算法放松了对于修正矩阵的正定性约束。最后,我们给出了一些数值试验结果。
In this thesis, we consider the nonlinear inequality constrained optimization problems. We know that primal-dual interior point methods are one of the important methods of feasible directions for solving this kind of problems. At each iteration, the methods only need to solve linear equation systems in stead of QP subproblem to obtain feasible and descent direction. And "working set" technique for determining the active set is often used to reduce computational cost. At the same time, strongly sub-feasible direction methods are one of effective methods for solving the problems starting with an infeasible initial point.
In this work, combining the properties of primal-dual interior point methods and the strongly sub-feasible method, by means of a new "working set" technique, we present a new primal-dual interior point algorithm for inequality constrained optimization. The main properties of the new algorithm are described as follows: (i) At each iteration, the algorithm solves only two or three reduced systems of linear equations with a common coefficient matrix; (ii) The initial iteration point can be chosen arbitrarily and the coefficient matrix is uniformly nonsingular. After finite iterations, the iterate becomes an interior point of the feasible set, then the searching direction is feasible and the objective function is monotone decreasing; (iii) Under suitable assumptions, the proposed algorithm possesses global and superlinear convergence. In particular, the positive definiteness assumption on the Hessian estimate is relaxed. Finally, promising numerical results are reported.
引文
[1]P.T.Boggs,J.W.Tolle,Sequential quadratic programming[M],Acta No.4,Cambridge University Press,Cambridge,UK,1995,1-51.
[2]P.E.Gill,W.Murray,M.A Saunders,SNOPT:An SQP algorithm for large-scale constrained optimization[J],SIAM Review,2005,47(1),99-131.
[3]E.R.Panier,A.L.Tits,A superlinearly convergent feasible method for the solution of inequality constrained optimization problems[J],SIAM J.on Control and Optimization,1987,25,934-950.
[4]E.R.Panier,A.L.Tits,On combining feasibility,descent and superlinear convergence in inequality constrained optimization[J],Mathematical Programming,1993,59,261-276.
[5]J.B.Jian,C.M.Tang,An SQP feasible descent algorithm for nonlinear inequality constrained optimization without strict complementarity[J],Computers and Mathematics with Applications,2005,49,223-238.
[6]C.T.Lawrence,A.L.Tits,A computationally efficient feasible sequential quadratic programming algorithm[J],SIAM J.Optimization,2001,11(4),1092-1118.
[7]J.B.Jian,H.Y.Zheng,Q.J.Hu,et al,A new norm-relaxed method of strongly sub-feasible direction for inequality constrained optimization[J],Applied Mathematics and Computation,2005,168,1-28.
[8]A.S.El-Bakry,R.A.Tapia,T.Tsuchiya,et al,On the formulation and theory of the Newton interior-point method for Nonlinear programming[J],Journal of Optimization Theory and Applications,1996,189(3),507-541.
[9]E.R.Panier,A.L.Tits,J.N.Herskovits,A QP-free,globally convergent,locally superlinearly convergent algorithm for inequality constrained optimization[J],SIAM J.Control and Optimization,1988,26(4),788-811.
[10]Z.Y.Gao,G.P.He,F.Wu,Sequential systems of linear equations algorithm for nonlinear optimization problems with general constraints[J],Journal of Optimization Theory and Application,1997,95,371-397.
[11]S.Bakhtiari,A.L.Tits,A simple primal-dual feasible interior-point method for nonlinear programming with monotone descent[J],Computational Optimization and Applications,2003,25,17-38.
[12]Z.Zhu,An interior point type QP-free algorithm with superlinear convergence for inequality constrained optimization[J],Applied Mathematical Modelling,2007,31,1201-1212.
[13]J.B.Jian,Strong combined phase Ⅰ-Phase Ⅱ methods of sub-feaisible directions[J],Mathematics in Economics(A Chinese Journal),1995,12,64-70.
[14]J.B.Jian,Sub-feasible direction method with strong convergence for inequlity constrained optimization[J],Journal of Xi'An Jiao Tong University,1999,33(8),88-91.
[15]F.Facchinei,A.Fischer,C.Kanzow,On the accurate identification of active constraints[J],SIAM J.Optimization,1998,9(1),14-32.
[16]P.Spellucci,An SQP method for general nonlinear programs using only equality constrained subproblem[J],Math.Programming,1998,82,413-448.
[17]Y.F.Yang,D.H.Qi,L.Q.Qi,A feasible sequnetial system of linear equations method for inequality constrained optimization[J],SIAM Journal of Optimization,2003,13(4),1222-1244.
[18]L.f.Chen,Y.Wang,G.P.Guo,A feasible active set QP-free method for nonlinear programming [J],SIAM Journal of Optimization,2006,17,401-429.
[19]C.Kanzow,H.D.Qi,A QP-free constrained Newton-type method for variational inequality problems[J],Math.Program.,1999,85,81-106.
[20]S.M.Robinson,Strongly regular generalized equations[J],Math.Oper.Res.,1980,5,43-62.
[21]J.B.Jian,H.Y.Zheng,C.M.Tang,et al,A new superlinearly convergent norm-relaxed method of strongly sub-feasible direction for inequality constrained optimization[J],Applied Mathematics and Computation,2006,182,955-976.
[22]M.J.D.Powell,The convergence of variable metric methods for nonlinearly constrained optimization calculations[M],Nonlinear Promgramming 3,Edited by R.R.Meyer,S.M.Robinson,Academic Press,New York,1978.
[23]W.Hock,K.Schittkowski,Test examples for nonlinear programming codes,lecture notes in economics and mathematical systems[M],Springer-Verlag,Belin Heidelberg,1981.
[24]I.Bongartz,A.R.Coun,N.I.Gould,et al,Cute:Constrained and unconstrained testing environment[J],ACM Tras.Math.Software,1995,21,123-160.
[25]A.L.Tits,A.Wachter,S.Bakhtiari,T.J.Urban and C.T.Lawrence,A primal-dual interiorpoint method for nonlinear programming with strong global and local convergence properties[J],SIAM J.Optimization,2003,14,173-199.
[26]M.J.Todd,Dual versus primal-dual interior-point methods for linear and conic programming[J],Math.Program,2008,Ser.B,301-313.
[27]J.M.Peng,C.Roos and T.Terlaky,A new class of polynomial primal-dual methods for linear and semidefinite optimization[J],European Journal of Operational Research,2002,143(2),234-256.
[28]J.Sun,G.Y.Zhao,Quadratic convergence of a long-step interior-point for nonlinear monotone variational inequality problems[J],Journal of Optimization Theory and Applications,1998,97(2),471-491.
[29]M.E.Cawood,M.M.Kostreva,Norm-relaxed method of feasible direction for solving the nonlinear programming problems[J],Journal of Optimization Theory and Application,1994,83,311-320.
[30]J.L.Zhou,A.L.Tits,Nonmonotone line search for minimax problems[J],Journal of Optimization Theorey and Applications[J],1995,76(3),455-476.
[31]Y.H.Yu,L.Gao,Nonmonotone line search algorithm for constrained minimax problems[J],Journal of Optimization Theory and Applications,2002,115(2),419-446.
[32]S.Zakovic,C.Pantelides,An interior point algorithm for computing saddle points of constrained continous minmax[J],Annals of Operations Research 99,2000,59-77.
[2]P.E.Gill,W.Murray,M.A Saunders,SNOPT:An SQP algorithm for large-scale constrained optimization[J],SIAM Review,2005,47(1),99-131.
[3]E.R.Panier,A.L.Tits,A superlinearly convergent feasible method for the solution of inequality constrained optimization problems[J],SIAM J.on Control and Optimization,1987,25,934-950.
[4]E.R.Panier,A.L.Tits,On combining feasibility,descent and superlinear convergence in inequality constrained optimization[J],Mathematical Programming,1993,59,261-276.
[5]J.B.Jian,C.M.Tang,An SQP feasible descent algorithm for nonlinear inequality constrained optimization without strict complementarity[J],Computers and Mathematics with Applications,2005,49,223-238.
[6]C.T.Lawrence,A.L.Tits,A computationally efficient feasible sequential quadratic programming algorithm[J],SIAM J.Optimization,2001,11(4),1092-1118.
[7]J.B.Jian,H.Y.Zheng,Q.J.Hu,et al,A new norm-relaxed method of strongly sub-feasible direction for inequality constrained optimization[J],Applied Mathematics and Computation,2005,168,1-28.
[8]A.S.El-Bakry,R.A.Tapia,T.Tsuchiya,et al,On the formulation and theory of the Newton interior-point method for Nonlinear programming[J],Journal of Optimization Theory and Applications,1996,189(3),507-541.
[9]E.R.Panier,A.L.Tits,J.N.Herskovits,A QP-free,globally convergent,locally superlinearly convergent algorithm for inequality constrained optimization[J],SIAM J.Control and Optimization,1988,26(4),788-811.
[10]Z.Y.Gao,G.P.He,F.Wu,Sequential systems of linear equations algorithm for nonlinear optimization problems with general constraints[J],Journal of Optimization Theory and Application,1997,95,371-397.
[11]S.Bakhtiari,A.L.Tits,A simple primal-dual feasible interior-point method for nonlinear programming with monotone descent[J],Computational Optimization and Applications,2003,25,17-38.
[12]Z.Zhu,An interior point type QP-free algorithm with superlinear convergence for inequality constrained optimization[J],Applied Mathematical Modelling,2007,31,1201-1212.
[13]J.B.Jian,Strong combined phase Ⅰ-Phase Ⅱ methods of sub-feaisible directions[J],Mathematics in Economics(A Chinese Journal),1995,12,64-70.
[14]J.B.Jian,Sub-feasible direction method with strong convergence for inequlity constrained optimization[J],Journal of Xi'An Jiao Tong University,1999,33(8),88-91.
[15]F.Facchinei,A.Fischer,C.Kanzow,On the accurate identification of active constraints[J],SIAM J.Optimization,1998,9(1),14-32.
[16]P.Spellucci,An SQP method for general nonlinear programs using only equality constrained subproblem[J],Math.Programming,1998,82,413-448.
[17]Y.F.Yang,D.H.Qi,L.Q.Qi,A feasible sequnetial system of linear equations method for inequality constrained optimization[J],SIAM Journal of Optimization,2003,13(4),1222-1244.
[18]L.f.Chen,Y.Wang,G.P.Guo,A feasible active set QP-free method for nonlinear programming [J],SIAM Journal of Optimization,2006,17,401-429.
[19]C.Kanzow,H.D.Qi,A QP-free constrained Newton-type method for variational inequality problems[J],Math.Program.,1999,85,81-106.
[20]S.M.Robinson,Strongly regular generalized equations[J],Math.Oper.Res.,1980,5,43-62.
[21]J.B.Jian,H.Y.Zheng,C.M.Tang,et al,A new superlinearly convergent norm-relaxed method of strongly sub-feasible direction for inequality constrained optimization[J],Applied Mathematics and Computation,2006,182,955-976.
[22]M.J.D.Powell,The convergence of variable metric methods for nonlinearly constrained optimization calculations[M],Nonlinear Promgramming 3,Edited by R.R.Meyer,S.M.Robinson,Academic Press,New York,1978.
[23]W.Hock,K.Schittkowski,Test examples for nonlinear programming codes,lecture notes in economics and mathematical systems[M],Springer-Verlag,Belin Heidelberg,1981.
[24]I.Bongartz,A.R.Coun,N.I.Gould,et al,Cute:Constrained and unconstrained testing environment[J],ACM Tras.Math.Software,1995,21,123-160.
[25]A.L.Tits,A.Wachter,S.Bakhtiari,T.J.Urban and C.T.Lawrence,A primal-dual interiorpoint method for nonlinear programming with strong global and local convergence properties[J],SIAM J.Optimization,2003,14,173-199.
[26]M.J.Todd,Dual versus primal-dual interior-point methods for linear and conic programming[J],Math.Program,2008,Ser.B,301-313.
[27]J.M.Peng,C.Roos and T.Terlaky,A new class of polynomial primal-dual methods for linear and semidefinite optimization[J],European Journal of Operational Research,2002,143(2),234-256.
[28]J.Sun,G.Y.Zhao,Quadratic convergence of a long-step interior-point for nonlinear monotone variational inequality problems[J],Journal of Optimization Theory and Applications,1998,97(2),471-491.
[29]M.E.Cawood,M.M.Kostreva,Norm-relaxed method of feasible direction for solving the nonlinear programming problems[J],Journal of Optimization Theory and Application,1994,83,311-320.
[30]J.L.Zhou,A.L.Tits,Nonmonotone line search for minimax problems[J],Journal of Optimization Theorey and Applications[J],1995,76(3),455-476.
[31]Y.H.Yu,L.Gao,Nonmonotone line search algorithm for constrained minimax problems[J],Journal of Optimization Theory and Applications,2002,115(2),419-446.
[32]S.Zakovic,C.Pantelides,An interior point algorithm for computing saddle points of constrained continous minmax[J],Annals of Operations Research 99,2000,59-77.