强次可行方法与序列二次约束二次规划算法的研究
|
摘要
最优化在工程设计、生产管理、交通运输、政府决策等重要领域日益得到广泛的应用,因此更加快速有效的最优化算法成为迫切需求。序列二次规划(SQP)算法是求解非线性约束优化最有效的算法之一,而可行SQP算法又是其中一类重要的算法,因为它能产生可行迭代点序列,故在工程设计和实时控制等方面有着十分重要的实际应用。然而可行SQP算法的较大缺陷就是需要一个可行初始迭代点,而通常计算一个可行点不是一个容易的工作。为此,简金宝教授近年提出了一个强次可行方向法,并成功应用于可行SQP算法。该方法能从任意初始点开始,能保证迭代的可行性单调增加,且一旦迭代点落入可行域即变成可行方向法。然而,强次可行方向法中仍然有一些问题亟待解决,如:能否在理论上保证在经过有限次迭代之后迭代点落入可行域;在理论分析当中一些较强的假设条件能否去掉或者减弱;数值计算量能否进一步减少等。
在过去三四十年里SQP方法的研究得到了极大的完善,然而当要求解的问题非线性程度比较高时,如人造卫星轨道问题,SQP方法可能进程较为缓慢,甚至会失败。于是近年来一些学者专门针对该类问题提出了一种有效的方法,称为序列二次约束二次规划(SQCQP)方法。与SQP方法相比,SQCQP方法每步迭代只需求解一个二次约束二次规划(QCQP)子问题,并且在不需要任何方向修正的情况下可以克服Maratos效应,达到超线性收敛性。由于QCQP子问题是原问题的二次近似,因此相对于SQP方法中的二次规划(QP)子问题而言,QCQP子问题对原问题的近似程度要好,从而SQCQP方法预期的数值效果要比SQP方法好。
本学位论文首先结合强次可行方向法,SQP方法和SQCQP方法的思想,分别给了一个强次可行SQP算法和一个强次可行SQCQP算法。然后专门针对目前SQCQP方法中存在的缺陷,提出了两个新的SQCQP算法。本论文共分为六章,各章内容简要介绍如下。
第一章主要介绍了强次可行方向法的思想,可行SQP方法和SQCQP方法的研究进展,以及QCQP子问题的求解方法。
第二章结合强次可行方向法和可行SQP方法的思想,提出了一个新的强次可行SQP算法。通过构造新的修正方向和设计新的Armijio型曲线搜索,提出的算法弥补了传统强次可行SQP算法的多个缺陷。首先能在理论上保证算法经过有限次迭代之后,迭代点落入可行域,之后自动变为可行SQP算法,并由此克服了一个较强的假设条件(即最大约束违背函数是QP子问题解的高阶)。其次,去掉了严格互补条件。最后,由于两个修正方向均由简单的显式产生,而且包含的逆矩阵是一样的,从而极大减少了计算量。算法具备全局和超线性收敛性。初步的数值试验说明该算法是稳定有效的。
第三章结合强次可行方向法和可行模松弛SQCQP方法的思想,提出了一个强次可行模松弛SQCQP算法。通过对线搜索和QCQP子问题精心的构造,算法能从任意初始点开始,并保证有限步之后迭代点落入可行域。算法每次迭代只需求解一个凸QCQP子问题,且无需任何修正方向就能得到算法的全局、超线性及拟二次收敛性。数值试验说明算法的数值效果与测试的SQP算法相比有一定的优越性。
第四章提出了一个新的罚函数型SQCQP算法。算法引入了一个简单的非单调罚参数调整技术,该技术仅利用QCQP子问题中有界约束的KKT乘子来更新罚参数,因为当把QCQP转化为二阶锥规划求解时,对应于二次约束的乘子往往比较难获取。该技术还允许罚参数在早期迭代减小,从而缓解了因罚参数增大过快而导致罚函数及子问题性态变差的问题。此外,我们利用了工作集技术剔除了QCQP子问题中局部不相关的约束,从而极大地减少了计算量。在不需要假设目标和约束函数为凸的情况下,算法是全局、超线性及二次收敛性的。初步的数值试验表明算法对测试的算例要比SQP方法优越。
第五章结合增广Lagrange函数线搜索技术和SQCQP方法的思想,提出了一个增广Lagrange函数型SQCQP算法。算法中构造了一个新型的凸QCQP子问题,该子问题不仅始终有可行解,而且通过应用积极约束集技术避免了那些局部不相关的梯度和(近似)Hesse阵的计算,从而减少了计算量。步长由Armijio型线搜索产生,罚参数允许减小。在适当的假设下,算法不需要任何修正方向就具有全局、超线性及二次收敛性。此外,与以往SQCQP算法不同的是,该算法还能简单地推广到求解混合等式与不等式的一般约束优化,以及推广到非单调线搜索。
第六章总结了本文的主要工作,并引出了一些需要进一步研究的问题。
最后,值得指出的是,我们对本文中提出的两个SQCQP算法做了比较充分和完整的数值试验,而以往给出的SQCQP算法中,除了一个局部收敛的算法给出了一些初步的数值试验结果(而且当中还是把QCQP子问题当成一个一般的非线性规划问题来求解)外,其余算法都没有做数值试验,其主要原因可能在于QCQP子问题求解上的困难。
Optimization plays more and more important roles in many areas,such as engineering design,production management,transportation,government decisionmaking. So more faster and efficient optimization algorithms are urgently demanded. Sequential quadratic programming(SQP) algorithms are among the most efficient algorithms for solving nonlinear constrained optimization.As an important kind of SQP algorithms,feasible SQP algorithms have many important applications in practice,such as engineering design and real-time control,since they can generate feasible iterations.However,a major disadvantage of feasible SQP is that a feasible starting point is required in advance,while computing such a point is generally a nontrivial work.Recently,in order to overcome this shortcoming,Prof.Jian has proposed a strongly sub-feasible direction method,and then successfully applied it to feasible SQP algorithms.This method allows arbitrary starting points,and guarantees that the feasibility of constraints is monotonously increasing.Furthermore, once a certain iterate gets into the feasible set,the corresponding algorithm will become feasible direction algorithm.However,there are still some problems in strongly sub-feasible direction method that needed to be resolved:ensuring theoretically the iterates getting into the feasible set after a finite number of iterations, removing some strong assumptions,reducing the computational cost and so on.
During the past several decades,the researches of SQP methods have been greatly improved,but when the problems we solved are highly nonlinear,SQP methods usually show slow convergence,even fail.For this,in recent years,a so-called sequential quadratically constrained quadratic programming(SQCQP) method has been proposed. Compared with SQP methods,at each iteration SQCQP methods only need to solve a quadratically constrained quadratic programming(QCQP) subproblem, and without any correctional directions the Maratos effect will not occur and there- fore the superlinear convergence can obtained.QCQP subproblem is a quadratic approximation of the original problem,so it is a better approximation than the quadratic programming(QP) subproblem solved in SQP methods,and therefore the expected numerical performance of SQCQP will be better than SQP.
Combining the ideas of strongly sub-feasible direction methods,SQP methods and SQCQP methods,this dissertation firstly proposed a strongly sub-feasible SQP algorithm and a strongly sub-feasible SQCQP algorithm.Secondly,with the motivation of overcoming the shortcomings of the existing SQCQP algorithms,two new SQCQP algorithms are proposed.The dissertation is divided into six chapters as follows.
Chapter 1 mainly introduces the ideas of strongly sub-feasible direction methods and feasible SQP methods,recent developments of SQCQP methods,and the solution method of QCQP subproblem.
Combining the ideas of strongly sub-feasible direction methods and feasible SQP methods,chapter 2 presents a new strongly sub-feasible SQP algorithm.By constructing new correctional directions and new Armijio-type curve search,the new algorithm overcomes several shortcomings of the traditional strongly sub-feasible SQP algorithm.At first,the algorithm theoretically ensures that the iterates get into the feasible set after a finite number of iterations,and then automatically becomes feasible SQP algorithm,as a result,a strong assumption(the order of the maximal constraint violation function is higher than the solution of the QP subproblem) is removed.Secondly,the strict complementarity condition is removed. At last,two correctional directions are generated by explicit formulas that contain the same inverse matrix,so the computational cost is reduced.The algorithm is proved to be globally and superlinearly convergent.Some preliminary numerical results show that the proposed algorithm is stable and efficient.
Combining the ideas of strongly sub-feasible direction methods and feasible normrelaxed SQCQP methods,chapter 3 presents a strongly sub-feasible norm-relaxed SQCQP algorithm.By constructing new QCQP subproblem and new line search, the algorithm can start from arbitrary initial point,and ensure that the iterates get into the feasible set after a finite number of iterations.Only one convex QCQP subproblem needs to be solved at each iteration,and without any other correctional directions,the global,superlinear and quasi-quadratic convergence properties are obtained.Preliminary numerical results show that the proposed SQCQP algorithm is superior to a related SQP algorithm for the test problems.
Chapter 4 presents a new penalty function type SQCQP algorithm,in which a simple nonmonotone penalty parameter updating technique is introduced.This technique only uses the KKT multiplier corresponding to the bounded constraint of the QCQP subproblem,since the multipliers corresponding to the quadratic con-straints are usually hard to be obtained when QCQP is cast and then solved as an second-order cone programming.This technique allows penalty parameters to be decreasing, which prevents the penalty parameters from increasing too fast and therefore prevents the penalty function and QCQP subproblem from being ill-conditioned. In addition,by using the working set technique,we remove the constraints of the QCQP subproblem that are locally irrelevant,so the computational cost is greatly reduced.Without assuming the convexity of the objective or constraints,the algorithm is globally,superlinearly and quadratically convergent.Preliminary numerical results show that the algorithm is superior to the tested SQP algorithms for the test problems.
Combining the augmented Lagrange function line search technique and the idea of SQCQP methods,chapter 5 presents an augmented Lagrange function SQCQP algorithm, in which a new consistent convex QCQP subproblem is proposed.The active set strategy used in this subproblem can avoid calculating the unnecessary gradients and(approximate) Hessian matrices.The step size is generated by Armijio-type line search,and the penalty parameters can be reduced.Under suitable assumptions, the algorithm is proved to be globally,superlinearly,and quadratically convergent. Compared with previous SQCQP algorithms,the proposed algorithm can be easily extended to general problems with inequality and equality constraints,and to nonmonotone line search.
Chapter 6 summarizes the main contributions of this dissertation,and raises some problems needed to be further studied.
Finally,we should point out that sufficient and full numerical experiments were done for two SQCQP algorithms proposed in this dissertation,whereas except for a local convergent one(in which the QCQP subproblem is treated and solved as a general nonlinear programming),the previous SQCQP algorithms have not reported numerical experiments,mainly due to the difficulty of solving the QCQP subproblem.
在过去三四十年里SQP方法的研究得到了极大的完善,然而当要求解的问题非线性程度比较高时,如人造卫星轨道问题,SQP方法可能进程较为缓慢,甚至会失败。于是近年来一些学者专门针对该类问题提出了一种有效的方法,称为序列二次约束二次规划(SQCQP)方法。与SQP方法相比,SQCQP方法每步迭代只需求解一个二次约束二次规划(QCQP)子问题,并且在不需要任何方向修正的情况下可以克服Maratos效应,达到超线性收敛性。由于QCQP子问题是原问题的二次近似,因此相对于SQP方法中的二次规划(QP)子问题而言,QCQP子问题对原问题的近似程度要好,从而SQCQP方法预期的数值效果要比SQP方法好。
本学位论文首先结合强次可行方向法,SQP方法和SQCQP方法的思想,分别给了一个强次可行SQP算法和一个强次可行SQCQP算法。然后专门针对目前SQCQP方法中存在的缺陷,提出了两个新的SQCQP算法。本论文共分为六章,各章内容简要介绍如下。
第一章主要介绍了强次可行方向法的思想,可行SQP方法和SQCQP方法的研究进展,以及QCQP子问题的求解方法。
第二章结合强次可行方向法和可行SQP方法的思想,提出了一个新的强次可行SQP算法。通过构造新的修正方向和设计新的Armijio型曲线搜索,提出的算法弥补了传统强次可行SQP算法的多个缺陷。首先能在理论上保证算法经过有限次迭代之后,迭代点落入可行域,之后自动变为可行SQP算法,并由此克服了一个较强的假设条件(即最大约束违背函数是QP子问题解的高阶)。其次,去掉了严格互补条件。最后,由于两个修正方向均由简单的显式产生,而且包含的逆矩阵是一样的,从而极大减少了计算量。算法具备全局和超线性收敛性。初步的数值试验说明该算法是稳定有效的。
第三章结合强次可行方向法和可行模松弛SQCQP方法的思想,提出了一个强次可行模松弛SQCQP算法。通过对线搜索和QCQP子问题精心的构造,算法能从任意初始点开始,并保证有限步之后迭代点落入可行域。算法每次迭代只需求解一个凸QCQP子问题,且无需任何修正方向就能得到算法的全局、超线性及拟二次收敛性。数值试验说明算法的数值效果与测试的SQP算法相比有一定的优越性。
第四章提出了一个新的罚函数型SQCQP算法。算法引入了一个简单的非单调罚参数调整技术,该技术仅利用QCQP子问题中有界约束的KKT乘子来更新罚参数,因为当把QCQP转化为二阶锥规划求解时,对应于二次约束的乘子往往比较难获取。该技术还允许罚参数在早期迭代减小,从而缓解了因罚参数增大过快而导致罚函数及子问题性态变差的问题。此外,我们利用了工作集技术剔除了QCQP子问题中局部不相关的约束,从而极大地减少了计算量。在不需要假设目标和约束函数为凸的情况下,算法是全局、超线性及二次收敛性的。初步的数值试验表明算法对测试的算例要比SQP方法优越。
第五章结合增广Lagrange函数线搜索技术和SQCQP方法的思想,提出了一个增广Lagrange函数型SQCQP算法。算法中构造了一个新型的凸QCQP子问题,该子问题不仅始终有可行解,而且通过应用积极约束集技术避免了那些局部不相关的梯度和(近似)Hesse阵的计算,从而减少了计算量。步长由Armijio型线搜索产生,罚参数允许减小。在适当的假设下,算法不需要任何修正方向就具有全局、超线性及二次收敛性。此外,与以往SQCQP算法不同的是,该算法还能简单地推广到求解混合等式与不等式的一般约束优化,以及推广到非单调线搜索。
第六章总结了本文的主要工作,并引出了一些需要进一步研究的问题。
最后,值得指出的是,我们对本文中提出的两个SQCQP算法做了比较充分和完整的数值试验,而以往给出的SQCQP算法中,除了一个局部收敛的算法给出了一些初步的数值试验结果(而且当中还是把QCQP子问题当成一个一般的非线性规划问题来求解)外,其余算法都没有做数值试验,其主要原因可能在于QCQP子问题求解上的困难。
Optimization plays more and more important roles in many areas,such as engineering design,production management,transportation,government decisionmaking. So more faster and efficient optimization algorithms are urgently demanded. Sequential quadratic programming(SQP) algorithms are among the most efficient algorithms for solving nonlinear constrained optimization.As an important kind of SQP algorithms,feasible SQP algorithms have many important applications in practice,such as engineering design and real-time control,since they can generate feasible iterations.However,a major disadvantage of feasible SQP is that a feasible starting point is required in advance,while computing such a point is generally a nontrivial work.Recently,in order to overcome this shortcoming,Prof.Jian has proposed a strongly sub-feasible direction method,and then successfully applied it to feasible SQP algorithms.This method allows arbitrary starting points,and guarantees that the feasibility of constraints is monotonously increasing.Furthermore, once a certain iterate gets into the feasible set,the corresponding algorithm will become feasible direction algorithm.However,there are still some problems in strongly sub-feasible direction method that needed to be resolved:ensuring theoretically the iterates getting into the feasible set after a finite number of iterations, removing some strong assumptions,reducing the computational cost and so on.
During the past several decades,the researches of SQP methods have been greatly improved,but when the problems we solved are highly nonlinear,SQP methods usually show slow convergence,even fail.For this,in recent years,a so-called sequential quadratically constrained quadratic programming(SQCQP) method has been proposed. Compared with SQP methods,at each iteration SQCQP methods only need to solve a quadratically constrained quadratic programming(QCQP) subproblem, and without any correctional directions the Maratos effect will not occur and there- fore the superlinear convergence can obtained.QCQP subproblem is a quadratic approximation of the original problem,so it is a better approximation than the quadratic programming(QP) subproblem solved in SQP methods,and therefore the expected numerical performance of SQCQP will be better than SQP.
Combining the ideas of strongly sub-feasible direction methods,SQP methods and SQCQP methods,this dissertation firstly proposed a strongly sub-feasible SQP algorithm and a strongly sub-feasible SQCQP algorithm.Secondly,with the motivation of overcoming the shortcomings of the existing SQCQP algorithms,two new SQCQP algorithms are proposed.The dissertation is divided into six chapters as follows.
Chapter 1 mainly introduces the ideas of strongly sub-feasible direction methods and feasible SQP methods,recent developments of SQCQP methods,and the solution method of QCQP subproblem.
Combining the ideas of strongly sub-feasible direction methods and feasible SQP methods,chapter 2 presents a new strongly sub-feasible SQP algorithm.By constructing new correctional directions and new Armijio-type curve search,the new algorithm overcomes several shortcomings of the traditional strongly sub-feasible SQP algorithm.At first,the algorithm theoretically ensures that the iterates get into the feasible set after a finite number of iterations,and then automatically becomes feasible SQP algorithm,as a result,a strong assumption(the order of the maximal constraint violation function is higher than the solution of the QP subproblem) is removed.Secondly,the strict complementarity condition is removed. At last,two correctional directions are generated by explicit formulas that contain the same inverse matrix,so the computational cost is reduced.The algorithm is proved to be globally and superlinearly convergent.Some preliminary numerical results show that the proposed algorithm is stable and efficient.
Combining the ideas of strongly sub-feasible direction methods and feasible normrelaxed SQCQP methods,chapter 3 presents a strongly sub-feasible norm-relaxed SQCQP algorithm.By constructing new QCQP subproblem and new line search, the algorithm can start from arbitrary initial point,and ensure that the iterates get into the feasible set after a finite number of iterations.Only one convex QCQP subproblem needs to be solved at each iteration,and without any other correctional directions,the global,superlinear and quasi-quadratic convergence properties are obtained.Preliminary numerical results show that the proposed SQCQP algorithm is superior to a related SQP algorithm for the test problems.
Chapter 4 presents a new penalty function type SQCQP algorithm,in which a simple nonmonotone penalty parameter updating technique is introduced.This technique only uses the KKT multiplier corresponding to the bounded constraint of the QCQP subproblem,since the multipliers corresponding to the quadratic con-straints are usually hard to be obtained when QCQP is cast and then solved as an second-order cone programming.This technique allows penalty parameters to be decreasing, which prevents the penalty parameters from increasing too fast and therefore prevents the penalty function and QCQP subproblem from being ill-conditioned. In addition,by using the working set technique,we remove the constraints of the QCQP subproblem that are locally irrelevant,so the computational cost is greatly reduced.Without assuming the convexity of the objective or constraints,the algorithm is globally,superlinearly and quadratically convergent.Preliminary numerical results show that the algorithm is superior to the tested SQP algorithms for the test problems.
Combining the augmented Lagrange function line search technique and the idea of SQCQP methods,chapter 5 presents an augmented Lagrange function SQCQP algorithm, in which a new consistent convex QCQP subproblem is proposed.The active set strategy used in this subproblem can avoid calculating the unnecessary gradients and(approximate) Hessian matrices.The step size is generated by Armijio-type line search,and the penalty parameters can be reduced.Under suitable assumptions, the algorithm is proved to be globally,superlinearly,and quadratically convergent. Compared with previous SQCQP algorithms,the proposed algorithm can be easily extended to general problems with inequality and equality constraints,and to nonmonotone line search.
Chapter 6 summarizes the main contributions of this dissertation,and raises some problems needed to be further studied.
Finally,we should point out that sufficient and full numerical experiments were done for two SQCQP algorithms proposed in this dissertation,whereas except for a local convergent one(in which the QCQP subproblem is treated and solved as a general nonlinear programming),the previous SQCQP algorithms have not reported numerical experiments,mainly due to the difficulty of solving the QCQP subproblem.
引文
[1]F.Alizadeh and D.Goldfarb.Second-order cone programming,Mathematical Programming,Ser.B,95:3-51,2003.
[2]Le Tiff Hoai An.An efficient algorithm for globally minimizing a quadratic function under convex quadratic constraints,Mathematical Programming,Ser.A,87:401-426,2000.
[3]E.D.Andersen,C.Roos,and T.Terlaky.On implementing a primal-dual interiorpoint method for conic quadratic optimization,Mathematical Programming,Ser.B,95:249-277,2003.
[4]M.Anitescu.A Superlinearly convergent sequential quadratically constrained quadratic programming algorithm for degenerate nonlinear programming,SIAM Journal on Optimization,12:949-978,2002.
[5]C.Audet,P.Hansen,B.Jaumard,and G.Savard.A branch and cut algorithm for nonconvex quadratically constrained quadratic programming,Mathematical Programming,Ser.A,87:131-152,2000.
[6]D.P.Bertsekas.Nonlinear Programming,2nd Edition,Athena Scientific,Belmont,MA,1999.
[7]P.T.Boggs and J.W.Tolie.Sequential quadratic programming,Acta Numerica,Cambridge Univ.Press,Cambridge,1-51,1995.
[8]I.Bongartz,A.R.Conn,N.I.Gould,PH.L.Toint.CUTE:Constrained and unconstrained testing environment,ACM Tras.Math.Software,21:123-160,1995.
[9]J.F.Bonbons,E.R.Panier,A.L.Tits,and J.L.Zhou.Avoiding the Maratos effect by means of a nonmonotone line search.Ⅱ.Inequality constrained problems-feasible iterates,SIAM J.Numer.Anal.,29:1187-1202,1992.
[10]S.Boyd and L.Vandenberghe.Convex Optimization,Cambridge University Press,2004.
[11]M.E.Cawood and M.M.Kostreva.Norm-relaxed method of feasible directions for solving nonlinear programming problems,Journal of Optimization Theory and Applications,83:311-320,1994.
[12]R.M.Chamberlain,M.J.D.Powell,C.Lemarechal,and H.C.Pederson.The watchdog technique for forcing convergence in algorithms for constrained optimization,Mathematical Programming Study,16:1-17,1982.
[13]T.F.Coleman and A.Verma.ADMIT-1:Automatic differentiation and MATLAB interfacetoolbox,ACM Transactions on Mathematical Software,26:150-175,2000.
[14]Y.-H.Dai and K.Schittkowski.A sequential quadratic programming algorithm with non-monotone line search,http://www.math.uni-bayreuth,de/～kschittkowski,submitted for publication,2005.
[15]L.C.W.Dixon,S.E.Hersom,and Z.A.Maany.Initial experience obtained solving the low thrust satellite trajectory optimization problem,Technical Report T.R.152,The Hatfield Polytechnic Numerical Optimization Center,1984.
[16]F.Facchinei and S.Lucidi.Quadratically and superlinearly convergent algorithms for the solution of inequality constrained minimization problems,Journal of Optimization Theory and Applications,85:265-289,1995.
[17]F.Facchinei.Robust recursive quadratic programming algorithm model with global and superlinear convergence properties,Journal of Optimization Theory and Applications,92:543-579,1997.
[18]F.Facchinei,A.Fischer,and C.Kanzow.On the accurate identification of active constraints,SIAM Journal on Optimization,9:14-32,1998.
[19]D.Fernandez and M.Solodov.On local convergence of sequential quadraticallyconstrained quadratic-programming type methods,with an extension to variational problems,Computational Optimization and Applications,39:143-160,2008.
[20]R.Fletcher and S.Leyffer.User manual for filterSQP,Numerical Analysis Report NA/181,Department of Mathematics,University of Dundee,Dundee,Scotland,1998.
[21]R.Fletcher and S.Leyffer.Nonlinear programming without a penalty function,Mathematical Programming,Ser.A,91:239-269,2002.
[22]M.Fukushima,Z.-Q.Luo,and P.Tseng.A sequential quadratically constrained quadratic programming method for differentiable convex minimization,SIAM Journal on Optimization,13:1098-1119,2003.
[23]Z.Y.Gao and F.Wu.A superlinearly feasible method for nonlinear constraints,Acta Mathematica Sinica,Ser.A,40:895-900,1997.
[24]P.E.Gill,W.Murray,M.A.Saunders,and M.H.Wright.User's Guide for NPSOL (Version 4.0):a Fortran package for nonlinear programming,Report SOL 86-2,Systems Optimization Laboratory,Stanford University,1986.
[25]P.E.Gill,W.Murray,M.A.Saunders,and M.H.Wright.Some theoretical properties of an augmented Lagrangian merit function,in:P.M.Pardalos(ed.),Advances in Optimization and Parallel Computing,North-Holland,Amsterdam,101-128,1992.
[26]P.E.Gill,W.Murray,and M.A.Sannders.SNOPT:An SQP algorithm for large-scale constrained optimization,Numerical Analysis Report 97-2,Department of Mathematics,University of California,San Diego,La Jolla,CA,1997.
[27]N.I.M.Gould and Ph.L.Toint.SQP methods for large-scale nonlinear programming,Report 99/05,Dept of Mathematics,FUNDP,Namur(B),1999.
[28]L.Grippo,F.Lampariello,and S.Lucidi.A nonmonotone line search technique for Newton's method,SIAM Journal on Numerical Analysis,23:707-716,1986.
[29]S.P.Han.A globally convergent method for nonlinear programming,Journal of Optimization Theory and Applications,22:297-309,1977.
[30]W.Hock and K.Schittkowski.Test examples for nonlinear programming codes,lecture notes in economics and mathematical systems,Springer-Verlag,Berlin Heidelberg New York,187,1981.
[31]Z.H.Huang,D.Sun,and G.Zhao.A smoothing Newton-type algorithm of stronger convergence for the quadratically constrained convex quadratic programming,Computational Optimization and Applications,35:199-237,2006.
[32]简金宝.次可行与强次可行方向法的研究,见:越民义.最优化理论与应用,西安电子科技大学出版社,100-106,1994.
[33]简金宝.非线性约束最优化的广义强次可行方向法,运筹学杂志,16:57,1997.
[34]J.B.Jian.A superlinearly convergent directly strongly subfeasible directions method for nonlinear inequality constrained optimization-A generalized projection variable metric method,Journal of Systems Science and Systems Engineering,6:418-429,1997.
[35]简金宝.一般约束最优化的拟乘子强次可行方向法,数学杂志,18:179-186,1998.
[36]J.B.Jian.Researches on superlinearly and quadratically convergent algorithms for nonlinearly constrained optimization,Ph.D.Thesis,School of Science,Xi'an Jiaotong University,Xi'an,China,2000.
[37]J.B.Jian,K.C.Zhang,and S.J.Xue.A superlinearly and quadratically convergent SQP type feasible method for constrained optimization,Appl.Math.J.Chinese Univ.,Ser.B,15:319-331,2000.
[38]J.B.Jian.A feasible descent algorithm combining SQP with generalized projection for optimization problems without strict complementarity,Applied Mathematics and Computation,162:1065-1081,2005.
[39]J.B.Jian and C.M.Tang.An SQP feasible descent algorithm for nonlinear inequality constrained optimization without strict complementarity,Computer and Mathematics with Applications,49:223-238,2005.
[40]J.B.Jian,C.M.Tang,Q.J.Hu,and H.Y.Zheng.A feasible descent algorithm for general constrained optimization without strict complementarity,Journal of Computational and Applied Mathematics,180:391-412,2005.
[41]J.B.Jian.New sequential quadratically constrained quadratic programming normrelaxed method of feasible directions,Journal of Optimization Theory and Applications,129:109-130,2006.
[42]M.M.Kostreva.Applications of MFD in engineering design optimization,http://www.math.clemson.edu/～flstgla/mfdapp.ps,Department of Mathematical Sciences,Clemson University.
[43]S.Kruk and H.Wolkowicz.SQ2P,Sequential quadratic constrained quadratic programming,in Advances in Nonlinear Programming,Yuan,Y.X.,Kluwer Academic Publishers,Dordrecht,177-204,1998.
[44]S.Kruk and H.Wolkowicz.Sequential,quadratic constrained quadratic programming for general nonlinear programming,in Handbook Of Semidefinite Programming,H.Wolkowicz,R.Saigal,and L.Vandenberghe,Kluwer Academic Publishers,Boston,MA,563-575,2000.
[45]C.T.Lawrence.A computationally efficient feasible sequential quadratic programming algorithm,Ph.D.thesis,University of Maryland,College Park,MD,1998.
[46]C.T.Lawrence and A.L.Tits.A computationally efficient feasible sequential quadratic programming algorithm,SIAM Journal on Optimization,11:1092-1118,2001.
[47]M.S.Lobo,L.Vandenberghe,and S.Boyd.SOCP:Software for second-order cone programming,user's guide(Beta version),April,1997.
[48]M.S.Lobo,L.Vandenberghe,S.Boyd,and H.Lebret.Applications of second-order cone programming,Linear Algebra and Its Appl.,284:193-228,1998.
[49]S.Lucidi.Recursive quadratic programming algorithm that uses an exact augmented Lagrangian function,Journal of Optimization Theory and Applications,67:227-245,1990.
[50]S.Lucidi.New results on a continuously differentiable exact penalty function,SIAM J.Optimization,2:558-574,1992.
[51]N.Maratos.Exact penalty function algorithm for finite dimensional and control optimization problems,Ph.D.thesis,Imperial College Science,Technology,University of London,1978.
[52]D.Q.Mayne and E.Polak.Feasible direction algorithm for optimization problems with equality and inequality constraints,Mathematical Programming,11:67-80,1976.
[53]R.D.C.Monteiro and T.Tsuchiya.Polynomial convergence of primal-dual algorithms for the second-order cone programs based on the MZ-family of directions,Mathematical Programming,88:61-83,2000.
[54]MOSEK 5.0,http://www.mosek.com/.
[55]The MOSEK optimization toolbox for MATLAB manual,Version 5.0(Revision 79),http://www.mosek.com/.
[56]C.Oberlin and S.J.Wright.Active set identification in nonlinear programming,SIAM Journal on Optimization,17:577-605,2006.
[57]E.R.Partier and A.L.Tits.A superlinearly convergent feasible method for the solution of inequality constrained optimization problems,SIAM Journal on Control and Optimization,25:934-950,1987.
[58]E.R.Panier and A.L.Tits.On combining feasibility,descent and superlinear convergence in inequality constrained optimization,Mathematical Programming,59:261-276,1993.
[59]E.R.Partier,A.L.Tits and J.N.Herskovits.A QP-free,globally convergent,locally superlinearly convergent algorithm for inequality constrained optimization,SIAM J.Control and Optimization,26:788-811,1988.
[60]V.M.Panin.A second-order method for the discrete min-max problem,USSR Comput.Math.Math.Phys,19:90-100,1979.
[61]V.M.Panin.Some methods of solving convex programming problems,USSR Comput.Math.Math.Phys,21:57-72,1981.
[62]J.F.A.De O.Pantoja and D.Q.Mayne.Exact penalty function algorithm with simple updating of the penalty parameter,Journal of Optimization Theory and Applications,69:441-467,1991.
[63]Y.H.Peng,B.C.Shi,and S.B.Yao.An SQP algorithm without penalty function for inequality constrained optimization problems with arbitrary initial point,Mathematica Applicata,supplement,15:125-129,2002.
[64]E.Polak,R.Trahan,and D.Q.Mayne.Combined phase Ⅰ-phase Ⅱ methods of feasible directions,Mathematical Programming,17,pp.61-73,1979.
[65]E.Polak,D.Q.Mayne,and J.E.Higgins.On the extension of Newton's method to semiinfinite minimax problems,SIAM J.Control Optim.,30:367-389,1992.
[66]M,J.D.Powell.A fast algorithm for nonlinearly constrained optimization calculations,In:G.A.Waston,Editor,Numerical Analysis,Springer,Berlin,144-157,1978.
[67]R.T.Rockafellar.The multiplier method of Hestenes and Powell applied to convex programming,Journal of Optimization Theory and Applications,12:555-562,1973.
[68]P.Spellucci.An SQP method for general nonlinear programs using only equality constrained subproblems,Mathematical Programming,82:413-448,1998.
[69]K.Schittkowski.The nonlinear programming method of Wilson,Han and Powell.Part 1:Convergence analysis.Part 2:An efficient implementation with linear least squares subproblems,Numerische Mathematik,38:83-127,1981.
[70]K.Schittkowski.On the convergence of a sequential quadratic programming method with an augmented Lngrangian line search function,Mathematische Operationsforschung und Statistik,Series Optimization,14:197-216,1983.
[71]K.Schittkowski.NLPQL:A Fortran subroutine solving constrained nonlinear programming problems,Annals of Operations Research,5:485-500,1985/86.
[72]K.Schittkowski.QLD:A FORTRAN code for quadratic programming,user's guide,Mathematisches institut,Universitat Bayreuth,Germany,1986.
[73]K.Schittkowski.More test examples for nonlinear programming codes,Spring-Verlag,1987.
[74]K.Schittkowski.NLPQLP:A Fortran implementation of a sequential quadratic programming algorithm with distributed and non-monotone line search-user's guide,version 2.2,Report,Department of Computer Science,University of Bayreuth,2006.
[75]M.V.Solodov.On the sequential quadratically constrained quadratic programming methods,Mathematics of Operations Research,29:64-79,2004.
[76]C.M.Tang and J.B.Jian.Sequential quadratically constrained quadratic programming method with an augmented Lagrangian line search function,Journal of Computational and Applied Mathematics,Available online 22 October 2007.
[77]D.M.Topkis and A.F.Veinott,Jr..On the convergence of some feasible direction algorithms for nonlinear programming,SIAM J.Control,5:268-279,1967.
[78]E.J.Wiest and E.Polak.A generalized quadratic programming-based phase-Ⅰ-phase-Ⅱmethod for inequality-constrained optimization,Appl.Math.Optim.,26:223-252,1992.
[79]R.B.Wilson.A simplicial algorithm for concave programming,Ph.D.Thesis,Graduate School of Business Administration,Harvard University,1963.
[80]S.J.Wright and M.J.Tenny.A feasible trust-region sequential quadratic programming algorithm,SIAM Journal on Optimization,14:1074-1105,2004.
[81]G.Zoutendijk.Methods of feasible directions,Elsevier Science,Amsterdam,the Netherlands,1960.
[2]Le Tiff Hoai An.An efficient algorithm for globally minimizing a quadratic function under convex quadratic constraints,Mathematical Programming,Ser.A,87:401-426,2000.
[3]E.D.Andersen,C.Roos,and T.Terlaky.On implementing a primal-dual interiorpoint method for conic quadratic optimization,Mathematical Programming,Ser.B,95:249-277,2003.
[4]M.Anitescu.A Superlinearly convergent sequential quadratically constrained quadratic programming algorithm for degenerate nonlinear programming,SIAM Journal on Optimization,12:949-978,2002.
[5]C.Audet,P.Hansen,B.Jaumard,and G.Savard.A branch and cut algorithm for nonconvex quadratically constrained quadratic programming,Mathematical Programming,Ser.A,87:131-152,2000.
[6]D.P.Bertsekas.Nonlinear Programming,2nd Edition,Athena Scientific,Belmont,MA,1999.
[7]P.T.Boggs and J.W.Tolie.Sequential quadratic programming,Acta Numerica,Cambridge Univ.Press,Cambridge,1-51,1995.
[8]I.Bongartz,A.R.Conn,N.I.Gould,PH.L.Toint.CUTE:Constrained and unconstrained testing environment,ACM Tras.Math.Software,21:123-160,1995.
[9]J.F.Bonbons,E.R.Panier,A.L.Tits,and J.L.Zhou.Avoiding the Maratos effect by means of a nonmonotone line search.Ⅱ.Inequality constrained problems-feasible iterates,SIAM J.Numer.Anal.,29:1187-1202,1992.
[10]S.Boyd and L.Vandenberghe.Convex Optimization,Cambridge University Press,2004.
[11]M.E.Cawood and M.M.Kostreva.Norm-relaxed method of feasible directions for solving nonlinear programming problems,Journal of Optimization Theory and Applications,83:311-320,1994.
[12]R.M.Chamberlain,M.J.D.Powell,C.Lemarechal,and H.C.Pederson.The watchdog technique for forcing convergence in algorithms for constrained optimization,Mathematical Programming Study,16:1-17,1982.
[13]T.F.Coleman and A.Verma.ADMIT-1:Automatic differentiation and MATLAB interfacetoolbox,ACM Transactions on Mathematical Software,26:150-175,2000.
[14]Y.-H.Dai and K.Schittkowski.A sequential quadratic programming algorithm with non-monotone line search,http://www.math.uni-bayreuth,de/～kschittkowski,submitted for publication,2005.
[15]L.C.W.Dixon,S.E.Hersom,and Z.A.Maany.Initial experience obtained solving the low thrust satellite trajectory optimization problem,Technical Report T.R.152,The Hatfield Polytechnic Numerical Optimization Center,1984.
[16]F.Facchinei and S.Lucidi.Quadratically and superlinearly convergent algorithms for the solution of inequality constrained minimization problems,Journal of Optimization Theory and Applications,85:265-289,1995.
[17]F.Facchinei.Robust recursive quadratic programming algorithm model with global and superlinear convergence properties,Journal of Optimization Theory and Applications,92:543-579,1997.
[18]F.Facchinei,A.Fischer,and C.Kanzow.On the accurate identification of active constraints,SIAM Journal on Optimization,9:14-32,1998.
[19]D.Fernandez and M.Solodov.On local convergence of sequential quadraticallyconstrained quadratic-programming type methods,with an extension to variational problems,Computational Optimization and Applications,39:143-160,2008.
[20]R.Fletcher and S.Leyffer.User manual for filterSQP,Numerical Analysis Report NA/181,Department of Mathematics,University of Dundee,Dundee,Scotland,1998.
[21]R.Fletcher and S.Leyffer.Nonlinear programming without a penalty function,Mathematical Programming,Ser.A,91:239-269,2002.
[22]M.Fukushima,Z.-Q.Luo,and P.Tseng.A sequential quadratically constrained quadratic programming method for differentiable convex minimization,SIAM Journal on Optimization,13:1098-1119,2003.
[23]Z.Y.Gao and F.Wu.A superlinearly feasible method for nonlinear constraints,Acta Mathematica Sinica,Ser.A,40:895-900,1997.
[24]P.E.Gill,W.Murray,M.A.Saunders,and M.H.Wright.User's Guide for NPSOL (Version 4.0):a Fortran package for nonlinear programming,Report SOL 86-2,Systems Optimization Laboratory,Stanford University,1986.
[25]P.E.Gill,W.Murray,M.A.Saunders,and M.H.Wright.Some theoretical properties of an augmented Lagrangian merit function,in:P.M.Pardalos(ed.),Advances in Optimization and Parallel Computing,North-Holland,Amsterdam,101-128,1992.
[26]P.E.Gill,W.Murray,and M.A.Sannders.SNOPT:An SQP algorithm for large-scale constrained optimization,Numerical Analysis Report 97-2,Department of Mathematics,University of California,San Diego,La Jolla,CA,1997.
[27]N.I.M.Gould and Ph.L.Toint.SQP methods for large-scale nonlinear programming,Report 99/05,Dept of Mathematics,FUNDP,Namur(B),1999.
[28]L.Grippo,F.Lampariello,and S.Lucidi.A nonmonotone line search technique for Newton's method,SIAM Journal on Numerical Analysis,23:707-716,1986.
[29]S.P.Han.A globally convergent method for nonlinear programming,Journal of Optimization Theory and Applications,22:297-309,1977.
[30]W.Hock and K.Schittkowski.Test examples for nonlinear programming codes,lecture notes in economics and mathematical systems,Springer-Verlag,Berlin Heidelberg New York,187,1981.
[31]Z.H.Huang,D.Sun,and G.Zhao.A smoothing Newton-type algorithm of stronger convergence for the quadratically constrained convex quadratic programming,Computational Optimization and Applications,35:199-237,2006.
[32]简金宝.次可行与强次可行方向法的研究,见:越民义.最优化理论与应用,西安电子科技大学出版社,100-106,1994.
[33]简金宝.非线性约束最优化的广义强次可行方向法,运筹学杂志,16:57,1997.
[34]J.B.Jian.A superlinearly convergent directly strongly subfeasible directions method for nonlinear inequality constrained optimization-A generalized projection variable metric method,Journal of Systems Science and Systems Engineering,6:418-429,1997.
[35]简金宝.一般约束最优化的拟乘子强次可行方向法,数学杂志,18:179-186,1998.
[36]J.B.Jian.Researches on superlinearly and quadratically convergent algorithms for nonlinearly constrained optimization,Ph.D.Thesis,School of Science,Xi'an Jiaotong University,Xi'an,China,2000.
[37]J.B.Jian,K.C.Zhang,and S.J.Xue.A superlinearly and quadratically convergent SQP type feasible method for constrained optimization,Appl.Math.J.Chinese Univ.,Ser.B,15:319-331,2000.
[38]J.B.Jian.A feasible descent algorithm combining SQP with generalized projection for optimization problems without strict complementarity,Applied Mathematics and Computation,162:1065-1081,2005.
[39]J.B.Jian and C.M.Tang.An SQP feasible descent algorithm for nonlinear inequality constrained optimization without strict complementarity,Computer and Mathematics with Applications,49:223-238,2005.
[40]J.B.Jian,C.M.Tang,Q.J.Hu,and H.Y.Zheng.A feasible descent algorithm for general constrained optimization without strict complementarity,Journal of Computational and Applied Mathematics,180:391-412,2005.
[41]J.B.Jian.New sequential quadratically constrained quadratic programming normrelaxed method of feasible directions,Journal of Optimization Theory and Applications,129:109-130,2006.
[42]M.M.Kostreva.Applications of MFD in engineering design optimization,http://www.math.clemson.edu/～flstgla/mfdapp.ps,Department of Mathematical Sciences,Clemson University.
[43]S.Kruk and H.Wolkowicz.SQ2P,Sequential quadratic constrained quadratic programming,in Advances in Nonlinear Programming,Yuan,Y.X.,Kluwer Academic Publishers,Dordrecht,177-204,1998.
[44]S.Kruk and H.Wolkowicz.Sequential,quadratic constrained quadratic programming for general nonlinear programming,in Handbook Of Semidefinite Programming,H.Wolkowicz,R.Saigal,and L.Vandenberghe,Kluwer Academic Publishers,Boston,MA,563-575,2000.
[45]C.T.Lawrence.A computationally efficient feasible sequential quadratic programming algorithm,Ph.D.thesis,University of Maryland,College Park,MD,1998.
[46]C.T.Lawrence and A.L.Tits.A computationally efficient feasible sequential quadratic programming algorithm,SIAM Journal on Optimization,11:1092-1118,2001.
[47]M.S.Lobo,L.Vandenberghe,and S.Boyd.SOCP:Software for second-order cone programming,user's guide(Beta version),April,1997.
[48]M.S.Lobo,L.Vandenberghe,S.Boyd,and H.Lebret.Applications of second-order cone programming,Linear Algebra and Its Appl.,284:193-228,1998.
[49]S.Lucidi.Recursive quadratic programming algorithm that uses an exact augmented Lagrangian function,Journal of Optimization Theory and Applications,67:227-245,1990.
[50]S.Lucidi.New results on a continuously differentiable exact penalty function,SIAM J.Optimization,2:558-574,1992.
[51]N.Maratos.Exact penalty function algorithm for finite dimensional and control optimization problems,Ph.D.thesis,Imperial College Science,Technology,University of London,1978.
[52]D.Q.Mayne and E.Polak.Feasible direction algorithm for optimization problems with equality and inequality constraints,Mathematical Programming,11:67-80,1976.
[53]R.D.C.Monteiro and T.Tsuchiya.Polynomial convergence of primal-dual algorithms for the second-order cone programs based on the MZ-family of directions,Mathematical Programming,88:61-83,2000.
[54]MOSEK 5.0,http://www.mosek.com/.
[55]The MOSEK optimization toolbox for MATLAB manual,Version 5.0(Revision 79),http://www.mosek.com/.
[56]C.Oberlin and S.J.Wright.Active set identification in nonlinear programming,SIAM Journal on Optimization,17:577-605,2006.
[57]E.R.Partier and A.L.Tits.A superlinearly convergent feasible method for the solution of inequality constrained optimization problems,SIAM Journal on Control and Optimization,25:934-950,1987.
[58]E.R.Panier and A.L.Tits.On combining feasibility,descent and superlinear convergence in inequality constrained optimization,Mathematical Programming,59:261-276,1993.
[59]E.R.Partier,A.L.Tits and J.N.Herskovits.A QP-free,globally convergent,locally superlinearly convergent algorithm for inequality constrained optimization,SIAM J.Control and Optimization,26:788-811,1988.
[60]V.M.Panin.A second-order method for the discrete min-max problem,USSR Comput.Math.Math.Phys,19:90-100,1979.
[61]V.M.Panin.Some methods of solving convex programming problems,USSR Comput.Math.Math.Phys,21:57-72,1981.
[62]J.F.A.De O.Pantoja and D.Q.Mayne.Exact penalty function algorithm with simple updating of the penalty parameter,Journal of Optimization Theory and Applications,69:441-467,1991.
[63]Y.H.Peng,B.C.Shi,and S.B.Yao.An SQP algorithm without penalty function for inequality constrained optimization problems with arbitrary initial point,Mathematica Applicata,supplement,15:125-129,2002.
[64]E.Polak,R.Trahan,and D.Q.Mayne.Combined phase Ⅰ-phase Ⅱ methods of feasible directions,Mathematical Programming,17,pp.61-73,1979.
[65]E.Polak,D.Q.Mayne,and J.E.Higgins.On the extension of Newton's method to semiinfinite minimax problems,SIAM J.Control Optim.,30:367-389,1992.
[66]M,J.D.Powell.A fast algorithm for nonlinearly constrained optimization calculations,In:G.A.Waston,Editor,Numerical Analysis,Springer,Berlin,144-157,1978.
[67]R.T.Rockafellar.The multiplier method of Hestenes and Powell applied to convex programming,Journal of Optimization Theory and Applications,12:555-562,1973.
[68]P.Spellucci.An SQP method for general nonlinear programs using only equality constrained subproblems,Mathematical Programming,82:413-448,1998.
[69]K.Schittkowski.The nonlinear programming method of Wilson,Han and Powell.Part 1:Convergence analysis.Part 2:An efficient implementation with linear least squares subproblems,Numerische Mathematik,38:83-127,1981.
[70]K.Schittkowski.On the convergence of a sequential quadratic programming method with an augmented Lngrangian line search function,Mathematische Operationsforschung und Statistik,Series Optimization,14:197-216,1983.
[71]K.Schittkowski.NLPQL:A Fortran subroutine solving constrained nonlinear programming problems,Annals of Operations Research,5:485-500,1985/86.
[72]K.Schittkowski.QLD:A FORTRAN code for quadratic programming,user's guide,Mathematisches institut,Universitat Bayreuth,Germany,1986.
[73]K.Schittkowski.More test examples for nonlinear programming codes,Spring-Verlag,1987.
[74]K.Schittkowski.NLPQLP:A Fortran implementation of a sequential quadratic programming algorithm with distributed and non-monotone line search-user's guide,version 2.2,Report,Department of Computer Science,University of Bayreuth,2006.
[75]M.V.Solodov.On the sequential quadratically constrained quadratic programming methods,Mathematics of Operations Research,29:64-79,2004.
[76]C.M.Tang and J.B.Jian.Sequential quadratically constrained quadratic programming method with an augmented Lagrangian line search function,Journal of Computational and Applied Mathematics,Available online 22 October 2007.
[77]D.M.Topkis and A.F.Veinott,Jr..On the convergence of some feasible direction algorithms for nonlinear programming,SIAM J.Control,5:268-279,1967.
[78]E.J.Wiest and E.Polak.A generalized quadratic programming-based phase-Ⅰ-phase-Ⅱmethod for inequality-constrained optimization,Appl.Math.Optim.,26:223-252,1992.
[79]R.B.Wilson.A simplicial algorithm for concave programming,Ph.D.Thesis,Graduate School of Business Administration,Harvard University,1963.
[80]S.J.Wright and M.J.Tenny.A feasible trust-region sequential quadratic programming algorithm,SIAM Journal on Optimization,14:1074-1105,2004.
[81]G.Zoutendijk.Methods of feasible directions,Elsevier Science,Amsterdam,the Netherlands,1960.