BFGS方法及其在求解约束优化问题中的应用
|
摘要
本文研究求解无约束非凸问题的BFGS方法以及求解非线性约束问题的序列二次规划(SQP)方法，既约Hessian SQP方法，序列二次约束二次规划(SQCQP)方法．我们首先在第1章简单介绍将要研究的问题的背景和已有结果．
在第2章，我们研究BFGS方法在求解无约束非凸问题时的收敛问题．众所周知，BFGS方法是求解无约束优化问题的拟牛顿法中最有效的方法之一，它具有很好的数值效果及快速的收敛性，然而采用精确线性搜索或非精确的Wolfe型线性搜索或Armijo线性搜索的BFGS方法在求解非凸函数的极小化问题时并不一定全局收敛．本文通过在拟牛顿方程中使用扰动策略提出了一种扰动BFGS方法．我们证明采用Wolfe型非精确线性搜索扰动BFGS方法求解非凸函数的极小化问题具有全局收敛性并且具有局部超线性收敛速度，而且保持BFGS方法的仿射不变性．我们的数值实验表明扰动BFGS方法比BFGS方法及修正BFGS方法具有更好的数值效果．
BFGS方法中的校正公式经常被其它优化方法所使用并被用来求解非线性方程组，约束优化问题，随机规划问题以及半无限规划问题等。我们在第3-5章里研究通过BFGS校正公式分别与SQP方法，既约Hessian SQP方法，SQCQP方法等的结合来求解一般的约束优化问题．
在第3章，我们研究SQP方法在较弱条件下的收敛问题．已有的关于SQP算法的全局收敛性研究结果通常要求拟牛顿矩阵序列一致正定和有界，然而是否存在满足该条件的拟牛顿法尚不清楚．利用扰动技术与BFGS校正技术的有效结合，我们提出了一种扰动SQP方法，并证明所提出的扰动SQP方法在较弱的约束品性下保持全局收敛性，特别地，全局收敛性不要求拟牛顿矩阵的一致正定性和有界性．此外，我们也研究了没有使用扰动技术的SQP方法的全局收敛问题，提出了确保SQP方法收敛的若干策略，其中包括一个新的拟牛顿矩阵校正公式和一个关于罚参数的有效校正准则．数值实验表明这些策略的使用使SQP方法具有更好的数值效果．
SQP方法通常被用来求解中小规模的约束问题，因此，我们在第4章研究求解较大规模问题的既约Hessian SQP方法．已有的既约Hessian SQP方法通常只能求解等式约束问题，而且它们的全局收敛分析要求约束函数的梯度向量是线性无关的以及拉格朗日函数的既约Hessian矩阵序列是一致正定的．使用前一条件的主要原因在于已有的拟牛顿校正公式只能产生具有固定阶的拟牛顿矩阵序列，而同时这种校正公式对既约Hessian SQP方法的全局收敛性起着重要的作用．因此，我们提出了一个产生的拟牛顿矩阵的阶可变化的校正公式，然后在此基础上，我们提出了求解一般等式约束问题(可以是退化问题)的修正既约Hessian SQp方法，并且在没有假定上述两个条件的情形下，我们证明修正既约Hessian SQP方法是全局收敛的．而且将这种方法推广然后用来求解不等式约束问题并获得了全局收敛性结果，该方法的优点是可以求解既有等式约束又有不等式约束的较大规模问题，有效克服了已有的这类方法在求解含不等式约束问题时所遇到的困难与限制．
在第5章，我们研究求解不等式约束问题的序列二次约束二次规划(SQCQP)方法．众所周知，传统的SQP方法通常会产生Maratos效应，阻碍了算法的快速收敛性．近年来，许多学者提出了使用约束函数的一阶和二阶信息的SQCQP方法，这类方法能有效地避免Maratos效应因而具有较快的收敛速度．然而已提出的SQCQP方法存在某些局限性，要么算法的全局收敛性条件太强，要么算法的全局收敛性没有保证，要么只能求解凸规划问题或约束函数是凸函数的问题．利用扰动技术或BFGS校正技术，我们提出两个求解一般不等约束问题的SQCQP方法，并证明它们在较弱的条件下仍然全局收敛，而且具有至少超线性收敛速度．
在第6章，我们针对前面各章提出的算法进行数值实验，数值结果表明所提出的算法比已有的同类算法更有效，有效地支持了本文的算法．
This thesis is concerned with the BFGS method for unconstrained optimization and its applications to sequential quadratic programming (SQP) method, reduced Hessian SQP method and sequential quadratically constrained quadratic programming (SQCQP) method for constrained optimization.
We first introduce the previous works on the thesis in Chapter 1. In Chapter 2, we study the convergence properties of BFGS method for solving nonconvex unconstrained problems. It is well-known that the BFGS method is one of the most famous quasi-Newton algorithms for solving unconstrained optimization problems because of its favorable numerical experiment and fast convergence property. However, The BFGS method with exact line search or Wolfe-type inexact line search or Armijo inexact line search need not converge for solving nonconvex minimization problem. In this chapter, we introduce a perturbation strategy in BFGS method to develop a perturbed BFGS method. We prove that under mild condition, the perturbed BFGS method with Wolfe line search is convergent globally and superlinearly even if the objective function is nonconvex. Moreover, the proposed method maintains the affine invariance of the BFGS method and enjoys more favorable numerical experiment results than the BFGS method and the modified BFGS methods.
The BFGS update technique is usually used by other methods for solving some related prblems such as nonlinear equations, constrained optimization problems, stochastic programming and semi-infinite programming. In next three chapters, we mainly analyze SQP method, reduced Hessian SQP method, SQCQP metod for solving constrained optimization problems by employing BFGS update technique.
In Chapter 3, we study the convergenc properties of SQP methods under mild conditions. The global convergence of the existed SQP methods usually requires that the quasi-Newton matrices are uniformly positive definite and bounded. However, it is unknown whether there exists the qusi-Newton method satisfying the above conditions. By employing BFGS update technique, we propose a perturbed SQP method for solving general constrained problems. We prove that the proposed method converges globally under mild condition. In particular, the global convergence does not require the uniformly positive definiteness and the boundedness of the quasi-Newton matrices, while existed SQP methos usually require these conditions. Besides, we propose some strategies for global convergence in SQP methods. Numerical results show that the proposed strategies are practically efficient.
SQP methods are usually used to solve small and medium-scale problems. In Chapter 4, we study reduced Hessian SQP methods for sloving large-scale optimization problems. The existed reduced Hessian methods slove only equality constrained problems and their global convergence require the linear independence and the uniformly positive definiteness of the reduced Hessian of Lagrangian function. The reason using the requirement of linear independence is that the existed quasi-Newton update formulas generate only quasi-Newton matrices with fixed order. On the other hand, the update formulas play important roles in analyzing the global convergence of reduced Hessian SQP methods. We propose a new quasi-Newton update formula which can generate quasi-Newton matrices with variable order, and then propose a reduced Hessian method for solving general equality constrained problems (including degnerate problems) and prove that the proposed method globally converges without above two requirements. Moreover, by using the proposed update formula, we extends the reduced Hessian method to solve constrained problems with inequality constraints.
In Chapter 5, we study the sequential quadratically constrained quadratic programming method for solving inequality constrained problems. It is well-known that traditional SQP methods may occur Maratos effect. Several authors have considered SQCQP-type methods which use information up to second-order for both the constraints and objective function. SQCQP methods are free of the Maratos effect and thus enjoy fast convergence property. However, the existed SQCQP methods solve only some special problems such as convex programming, or problems with convex feasible set or some problems with strong conditions. By employing the perturbed strategy or BFGS update technique we propose two SQCQP methods for general inequality constrained optimization and prove that the proposed SQCQP methods are globally convergent under mild condition and are of superlinear rate of convergence at least.
In Chapter 6, we report some numerical results for the proposed methods. The numerical results show that the proposed methods are practically efficient and thus support the proposed methods
在第2章，我们研究BFGS方法在求解无约束非凸问题时的收敛问题．众所周知，BFGS方法是求解无约束优化问题的拟牛顿法中最有效的方法之一，它具有很好的数值效果及快速的收敛性，然而采用精确线性搜索或非精确的Wolfe型线性搜索或Armijo线性搜索的BFGS方法在求解非凸函数的极小化问题时并不一定全局收敛．本文通过在拟牛顿方程中使用扰动策略提出了一种扰动BFGS方法．我们证明采用Wolfe型非精确线性搜索扰动BFGS方法求解非凸函数的极小化问题具有全局收敛性并且具有局部超线性收敛速度，而且保持BFGS方法的仿射不变性．我们的数值实验表明扰动BFGS方法比BFGS方法及修正BFGS方法具有更好的数值效果．
BFGS方法中的校正公式经常被其它优化方法所使用并被用来求解非线性方程组，约束优化问题，随机规划问题以及半无限规划问题等。我们在第3-5章里研究通过BFGS校正公式分别与SQP方法，既约Hessian SQP方法，SQCQP方法等的结合来求解一般的约束优化问题．
在第3章，我们研究SQP方法在较弱条件下的收敛问题．已有的关于SQP算法的全局收敛性研究结果通常要求拟牛顿矩阵序列一致正定和有界，然而是否存在满足该条件的拟牛顿法尚不清楚．利用扰动技术与BFGS校正技术的有效结合，我们提出了一种扰动SQP方法，并证明所提出的扰动SQP方法在较弱的约束品性下保持全局收敛性，特别地，全局收敛性不要求拟牛顿矩阵的一致正定性和有界性．此外，我们也研究了没有使用扰动技术的SQP方法的全局收敛问题，提出了确保SQP方法收敛的若干策略，其中包括一个新的拟牛顿矩阵校正公式和一个关于罚参数的有效校正准则．数值实验表明这些策略的使用使SQP方法具有更好的数值效果．
SQP方法通常被用来求解中小规模的约束问题，因此，我们在第4章研究求解较大规模问题的既约Hessian SQP方法．已有的既约Hessian SQP方法通常只能求解等式约束问题，而且它们的全局收敛分析要求约束函数的梯度向量是线性无关的以及拉格朗日函数的既约Hessian矩阵序列是一致正定的．使用前一条件的主要原因在于已有的拟牛顿校正公式只能产生具有固定阶的拟牛顿矩阵序列，而同时这种校正公式对既约Hessian SQP方法的全局收敛性起着重要的作用．因此，我们提出了一个产生的拟牛顿矩阵的阶可变化的校正公式，然后在此基础上，我们提出了求解一般等式约束问题(可以是退化问题)的修正既约Hessian SQp方法，并且在没有假定上述两个条件的情形下，我们证明修正既约Hessian SQP方法是全局收敛的．而且将这种方法推广然后用来求解不等式约束问题并获得了全局收敛性结果，该方法的优点是可以求解既有等式约束又有不等式约束的较大规模问题，有效克服了已有的这类方法在求解含不等式约束问题时所遇到的困难与限制．
在第5章，我们研究求解不等式约束问题的序列二次约束二次规划(SQCQP)方法．众所周知，传统的SQP方法通常会产生Maratos效应，阻碍了算法的快速收敛性．近年来，许多学者提出了使用约束函数的一阶和二阶信息的SQCQP方法，这类方法能有效地避免Maratos效应因而具有较快的收敛速度．然而已提出的SQCQP方法存在某些局限性，要么算法的全局收敛性条件太强，要么算法的全局收敛性没有保证，要么只能求解凸规划问题或约束函数是凸函数的问题．利用扰动技术或BFGS校正技术，我们提出两个求解一般不等约束问题的SQCQP方法，并证明它们在较弱的条件下仍然全局收敛，而且具有至少超线性收敛速度．
在第6章，我们针对前面各章提出的算法进行数值实验，数值结果表明所提出的算法比已有的同类算法更有效，有效地支持了本文的算法．
This thesis is concerned with the BFGS method for unconstrained optimization and its applications to sequential quadratic programming (SQP) method, reduced Hessian SQP method and sequential quadratically constrained quadratic programming (SQCQP) method for constrained optimization.
We first introduce the previous works on the thesis in Chapter 1. In Chapter 2, we study the convergence properties of BFGS method for solving nonconvex unconstrained problems. It is well-known that the BFGS method is one of the most famous quasi-Newton algorithms for solving unconstrained optimization problems because of its favorable numerical experiment and fast convergence property. However, The BFGS method with exact line search or Wolfe-type inexact line search or Armijo inexact line search need not converge for solving nonconvex minimization problem. In this chapter, we introduce a perturbation strategy in BFGS method to develop a perturbed BFGS method. We prove that under mild condition, the perturbed BFGS method with Wolfe line search is convergent globally and superlinearly even if the objective function is nonconvex. Moreover, the proposed method maintains the affine invariance of the BFGS method and enjoys more favorable numerical experiment results than the BFGS method and the modified BFGS methods.
The BFGS update technique is usually used by other methods for solving some related prblems such as nonlinear equations, constrained optimization problems, stochastic programming and semi-infinite programming. In next three chapters, we mainly analyze SQP method, reduced Hessian SQP method, SQCQP metod for solving constrained optimization problems by employing BFGS update technique.
In Chapter 3, we study the convergenc properties of SQP methods under mild conditions. The global convergence of the existed SQP methods usually requires that the quasi-Newton matrices are uniformly positive definite and bounded. However, it is unknown whether there exists the qusi-Newton method satisfying the above conditions. By employing BFGS update technique, we propose a perturbed SQP method for solving general constrained problems. We prove that the proposed method converges globally under mild condition. In particular, the global convergence does not require the uniformly positive definiteness and the boundedness of the quasi-Newton matrices, while existed SQP methos usually require these conditions. Besides, we propose some strategies for global convergence in SQP methods. Numerical results show that the proposed strategies are practically efficient.
SQP methods are usually used to solve small and medium-scale problems. In Chapter 4, we study reduced Hessian SQP methods for sloving large-scale optimization problems. The existed reduced Hessian methods slove only equality constrained problems and their global convergence require the linear independence and the uniformly positive definiteness of the reduced Hessian of Lagrangian function. The reason using the requirement of linear independence is that the existed quasi-Newton update formulas generate only quasi-Newton matrices with fixed order. On the other hand, the update formulas play important roles in analyzing the global convergence of reduced Hessian SQP methods. We propose a new quasi-Newton update formula which can generate quasi-Newton matrices with variable order, and then propose a reduced Hessian method for solving general equality constrained problems (including degnerate problems) and prove that the proposed method globally converges without above two requirements. Moreover, by using the proposed update formula, we extends the reduced Hessian method to solve constrained problems with inequality constraints.
In Chapter 5, we study the sequential quadratically constrained quadratic programming method for solving inequality constrained problems. It is well-known that traditional SQP methods may occur Maratos effect. Several authors have considered SQCQP-type methods which use information up to second-order for both the constraints and objective function. SQCQP methods are free of the Maratos effect and thus enjoy fast convergence property. However, the existed SQCQP methods solve only some special problems such as convex programming, or problems with convex feasible set or some problems with strong conditions. By employing the perturbed strategy or BFGS update technique we propose two SQCQP methods for general inequality constrained optimization and prove that the proposed SQCQP methods are globally convergent under mild condition and are of superlinear rate of convergence at least.
In Chapter 6, we report some numerical results for the proposed methods. The numerical results show that the proposed methods are practically efficient and thus support the proposed methods
引文
[1] Kuhn H W, TuckerA E. Nonlinear programming, in: Neyman J. ed., Proceeding of the Second Berkley Symposium on Mathematical Statistics and Probablity, Berkeley, California: University of California Press, 1951, 481-492
[21 Karush W. Minima of functions of several variables with inequalities as side conditions. Master's thesis, University of Chicago, Chicago, 1939, 1-56
[3] Fletcher R. A new approach to variable metric algorithms. Computer Journal, 1970,13:317-322
[4] Mangasarian O L. Nonlinear Programming. New York: Mc Graw Hill, 1969, 21-34
[5] 袁亚湘，孙文瑜．最优化理论与方法．北京：中国科学出版社，2001，1-627
[6] Broyden C G. The convergence of a class of double rank minimization algorithms: the new algorithm. Journal of the Institute of Mathematics and its Applications, 1970, 6:222-231
[7] Goldfarb D. A family of variable metric methods derived by variational means. Mathematics of Computation, 1970, 24:23-26
[8] Shanno D F. Conditioning of quasi-Newton methods for function minimization. Mathematics of Computation, 1970, 24:647-650
[9] Dennis J E, Moré J. A characterization of superlinear convergence and its applications to quasi-Newton methods. Mathematics of Computation, 1974, 28:549-560
[10] Dennis J E, Moré J J. Quasi-Newton methods, motivation and theory. SIAM Review, 1977, 19:46-89
[11] Armand P, Gilbert J C, Jgoue S J. A feasible BFGS interior point algorithm for solving convex minimization problems. SIAM Journal on Optimization, 2000, 11: 192-222
[12] Byrd R H, Nocedal J, Yuan Y X. Gloabl convergence of a class of qual-Newton methods on convex problems. SIAM Journal on Numerical Analysis, 1987, 24: 1171-1190
[13] Byrd R H, Nocedal J. A tool for the analysis of quasi-Newton methods with application to unconstrained minimization. SIAM Journal on Numerical Analysis, 1989,26: 727-739
[14] Dixon L C W. Variable metric algorithms: necessary and sufficient conditions for identical behavior of nonquadratic functions. Journal of Optimization Theory and Applications, 1972, 10:34-40
[15] Griewank A. The global convergence of partitioned BFGS on problems with convex decompositions and Lipschitzian gradients. Mathematical Programming, 1991, 50: 141-175
[16] Powell M J D. On the convergence of the variable metric algorithm. Journal of the Institute of Mathematics and its Applications, 1971, 7: 21-36
[17] Toint P H. Global convergence of the partitioned BFGS algorithm for convex partially separable optimization. Mathematical Programming, 1986, 36:290-306
[18] Powell M J D. Some convergence properties of a variable metric algorithms for minimization without exact line search, in Nonlinear Programming, SIAM-AMS Proceedings, Volume IX, Cottle R W and Lemke C E, eds., SIAM, Philadelphia, PA, 1976, 53-72
[19] Powell M J D. Quadratic termination properties of minimization algorithm, Part Ⅰ and Part Ⅱ. Journal of the Institute of Mathematics and its Applications, 1972, 10:333-357
[20] Pu D, Yu W. On the convergence of the DFP algorithm. Annal of Operations Reserch, 1990, 24:175-184
[21] Yuan Y X. A modified BFGS algorithm for unconstrained optimization. IMA Journal of Numerical Analysis, 1991, 11:325-332
[22] Li D H, Fuknshima M. A modified BFGS method and its global convergence in nonconvex minimization. Journal of Computational and Applied Mathematics, 2001, 129:15-35
[23] Li D H, Fukushima M. On the global convergence of the BFGS method for nonconvex unconstrained problems. SIAM Journal on Optimization, 2001, 11:1054-1064
[24] 李董辉，童小娇，万中．数值最优化．北京：科学出版社，2005，66-70
[25] Powell M J D. On the convergence of the DEP algorithm for unconstrained optimization when there are only two variables. Mathematical Programming, Series B, 2000, 87:281-301
[26] Dai Y H. Convergence properties of the BFGS algorithm. SIAM Journal on Optimization, 2002, 13:693-701
[27] Mascarenhas W F. The BFGS method with exact line searches fails for non-convex objective functions. Mathematical Programming, Series A, 2004, 99:49-61
[28] Coleman T F, Conn A R. On the local convergence of a quasi-Newton method for the nonlinear programming problem. SIAM Journal on Numerical Analysis, 1984, 21:755-769
[29] Wei Z, Qi L, Chen X. An SQP-type method and its application in stochastic programming. Journal of Optimization Theory and Applications, 2003, 116:205-228
[30] Yu G H, Wei Z X, Guan L T. A modified BFGS-trust region method for nonconvex minimization. Pacific Journal of Optimization, 2006, 2:119-133
[31] Li D H, Fukushima M. A globally and superlinearly convergent Gauss-Newton-based BFGS method for symmetric nonlinear equations. SIAM Journal on Numerical Analysis, 1999, 37:152-172
[32] Byrd R H, Nocedal J. An analysis of reduced Hessian methods for constrained optimization. Mathematical Programming, 1991, 49:285-323
[33] Chen X J. Convergence of the BFGS method for LC~1 convex constrained optimization. SIAM Journal on Control and Optimization, 1996, 34:2051-2063
[34] Pantoja J F A De O, Mayne D Q. Exact Penalty Function Algorithm with Simple Updating of the Penalty Parameter. Journal of Optimization Theory and Applications, 1991, 69:441-467
[35] Powell M J D, Yuan Y X. A recursive quadratic programming algorithm that uses differentiable exact penalty functions. Mathematical Programming, 1986, 35: 265-278
[36] Bell N M. Global convergence of a semi-infinite programming method. Applied Mathematics and Optimization, 1990, 21:69-88
[37] Vat F Ismael A, Fernandes M G P, Gomes S F Paula M. A quasi-Newton interior point method for semi-infinite programming. Optimization methods and software, 2003, 18:673-6&7
[38] Wei Z X, Yu G H, Yuan G L, et al. The superlinear convergence of a modified BFGS-type method for unconstrained optimization. Journal Computional Optimization and Applications, 2004, 29:315-332
[39] 袁亚湘．非线性规划数值方法．上海：上海科学技术出版社，1993，1-121
[40] Powell M J D. Restart procedure for the conjugate gradient method. Mathematical Programming. 1977, 12:241-254
[41] Han S P. A global convergent method for nonlinear programming. Journal of Optimization Theory and Applications, 1977, 22: 297-309
[42] Bertsekas D P. Constrained optimization and Lagrange multiplier methods. New York: Academic Press, 1982, 1-121
[43] Boggs P T, Tolle J W, Wang P. On the local convergence of quasi-Newton methods for constrained optimization. SIAM Journal on Control and Optimization, 1982, 20: 161-171
[44] Boggs P T, Tolle J W. Sequential quadratic programming. Acta Numerical Analysis, 1995, 1: 1-15
[45] Boggs P T, Tolle J W. A strategy for global convergence in a sequential quadratic programming algorithm. SIAM Journal on Numerical Analysis, 1989, 26: 600-623
[46] Byrd R H, Tapia R A, Zhang Y. An SQP augmented Lagrangian BFGS algorithms for constrained optimization. SIAM Journal on Optimization, 1992, 2: 210-241
[47] Coleman T F, Conn A R. A note on the computation of an orthonormal basis for the null space of a matrix. Mathematical Programming, 1984, 29: 234-242
[48] Fontecilla R, Steihaug T, Tapia A. A convergence theory for a class of quasi-Newton methods for constrained optimization. SIAM Journal on Numerical analysis, 1987, 24: 1133-1151
[49] Fontecilla R. Local convergence of secant methods for nonlinear constrained optimization. SIAM Journal on Numerical analysis, 1988, 25: 692-712
[50] Fukushima M. A successive quadratic programming algorithm with global and su-perlinear convergence properties. Mathematical Programming, 1986, 35: 253-264
[51] Qi L, Yang.Y F. A globally and superlinearly convergent SQP algorithm for nonlinear constrained optimization. Journal of Global Optimization, 2001, 21: 157-184
[52] Sargent R W H, Ding M. A new SQP algorithm for large-scale nonlinear programming. SIAM Journal on Optimization, 2000, 11: 716-747
[53] Schittkowski K. The nonlinear programming method of Wilson, Han and Powell with an Lagrangian type line search function. Numerische Mathematik, 1981, 38: 83-114
[54] Wright S J. Superlinear convergence of a stabilized SQP method to degenerate solution. Copmutational Optimization and Applications, 1998, 11: 253-275
[55] Wright S J. Modifying SQP for degenerate probloms. SIAM Journal on Optimization, 2002, 13: 470-497
[56] Pantoja J F A De O. Algorithms for constrained optimization problems. Ph.D Thesis, London: University London, 1983, 1-81
[57] Li D H, Qi L Q. A stabilized SQP method via linear equations. Technical Report, Department of Applied Matheamtics, School of Mathematics, New South Wales University, Sydney, Australia, 2000.
[58] Zhang J L, Zhang X S. A SQP method for inequality constrained optimization. Acta Mathematicae Applicatae Sinica, English Series, 2002, 18: 77-84
[59] Pukushima M, Luo Z Q, Tseng P. A sequential quadratically constrained quadratic programming method for differentiable convex minimization. SIAM Journal on Optimization, 2003, 13: 1098-1119
[60] Solodov M V. On the sequential quadratically constrained quadratic programming methods. Mathematics of Operations Research, 2004, 29: 64-79
[61] Chin M C, Fletcher R. On the global convergence of a SLR-filter algorithm that takes EQP steps. Mathematical Programming, 2003, Series B 96: 161-177
[62] Fletcher R, Leyffer S. Nonlinear programming without a penalty function. Mathematical Programming, 2002, 91: 239-269
[63] Fletcher R, Leyffer S, Toint P L. On the global convergence of a filter-SQP algorithm. SIAM Journal on Optimization, 2002, 13: 44-59
[64] Fletcher R, Nicholas I M G, Leyffer S. Global convergence of a trust-region SQP-filter algorithm for general nonlinear programming. SIAM Journal on Optimization, 2002, 13: 635-659
[65] Gill P E, Leonard M W. Reduced-Hessian quasi-Newton methods for unconstrained optimization. SIAM Journal on Optimization, 2001, 12: 209-237
[66] Nocedal J, Overton M L. Projected Hessian updating algorithms for nonlinearly constrained optimization. SIAM Journal on Numerical Analysis, 1985, 22: 821-850
[67] Schluz V. Solving discretized optimization problems by partially reduced SQP methods. Computing and Visualisation in Science, 1998, 1: 283-96
[68] Fletcher R. Stable reduced Hessian updates for indefinite quadratic programming. Methematical Programming, 2000 Series B 87: 251-264
[69] Xie Y F, Byrd R H. Practical update criteia for reduced Hessian SQP: global analysis. SIAM Journal on Optimization, 1999, 9:578-604
[70] Bonnans J F. Asmpotic admissiblity of the unit stepsize in exact penalty function methods. SIAM Journal on Control and Optimization, 1989, 27:631-641
[71] Bonnans J F, Panier E R, Tits A L, et al. Avoiding the Maratos effect by means of a nonmonotone line search. Ⅱ. inequality constrained problems- Feasible Iterates. SIAM Journal on Numerical Analysis, 1992, 29: 1187-1202
[72] Bonnans J F, Gilbert J Ch, Lemaréchal C, et al. Numerical optimization: Theoretical and Practical Aspects. Berlin: Springer-Verlag, 2003, 1-43
[73] Panier E R, Tits A L. Avoiding the Maratos effect by means of a nonmonotone line search. Ⅰ. general constrained problems. SIAM Journal on Numerical Analysis, 1991, 28:1183-1195
[74] Lobo M S, Vandenberghe L, Boyd S, et al. Applications of second-order cone programming. Linear Algebra and Applications, 1998, 284:193-228
[75] Nesterov Y E, Nemirovskii A S. Interior Point Polynomial Methods in Convex Programming: Theory and Applications. SIAM, Philadelphia, PA, 1993, 1-32
[76] Rockafellar R T. Convex Analysis. Princeton University Prees, Princeton, N J, 1970, 1-54
[77] Alizadeh F, Schmieta S. Symmetric cones, potenial reduction methods, in: Wolkowicz H, Saigal R, Vandenberghe L, eds., Handbook of Semidefinite Programming, Boston: Kluwer Academic Publishers, 2000, 195-233
[78] Monteiro R D C, Tschiya T. Polynomial convergence of primal-dual algorithms for the second-order cone programs based on the MZ- family of directions. Mathematical Programming, 2000, 88:61-83
[79] Tsuchiya T. A convergence analysis of the scaling-invariant primal-dual pathfollowing algorithms for second-order cone programming. Optimization Methods and Software, 1999, 11/12:141-182
[80] Anitescu M. A superlinearly convergent sequential quadratically constrained programming algorithm for degenerate nonlinear programming. SIAM Journal on Optimization, 2002, 12: 949-978
[81] Pain V M. A second-order methods for the discrete min-max problem. USSER Computational Mathematics and Mathematical Physics, 1979, 19:90-100
[82] Wiest E J, Polak E. A generalized quadratic programmingjbased phase I-phase II method for inequality constrained optimization. Applied Mathematics and Optimization, 1992, 26: 223-252
[83] Wolfe P. Convergence conditions for ascent methods. SIAM Review, 1969, 11: 226-235
[84] Armijo L. Minimization of functions having Lipschitz continuous partial derivatives. Pacific Journal of Mathematics, 1966, 16: 1-3
[85] Debreu G. Definite and semidefinite qudratic forms. Econometrica, 1952, 20: 295-300
[86] Broyden C G, Dennis J, More J, On the local and superlinear convergence of quasi-Newton methods. Journal of the Institute of Mathematics and its Applications, 1973, 12: 223-246
[87] Maratos N. Exact penalty function algorithms for finite-dimensional and control optimization problems. Ph.D Thesis, University of London, 1978, 1-42
[88] Amiri N M. An exact penalty method with reduced Hessian updates for solving constrained optimization problems. Journal of Science and Technique, 1994, 1: 1-14
[89] Anstreicherk M, Wright M H. A note on the augmented Hessian when the reduced Hessian is semidefinite. SIAM Journal on Optimization. 2000, 1: 243-253
[90] Biegler L T, Nocedal J, Schmid C. A reduced Hessian method for large-scale constrained optimization. SIAM Journal on Optimization, 1995, 5: 314-347
[91] Biegler L T, Nocedal J, Schmid C, et al. Numerical experience with a reduced Hessian method for large-scale constrained optimization. Computational Optimization and Applications, 2000, 1: 45-67
[92] Gabay D. Reduced quasi-Newton methods with feasibility improvement for nonlinear constrained optimization. Mathematical Programming Study, 1982, 16: 18-44
[93] Ghattas O, Orozcoc C E. A parallel reduced Hessian SQP method for shape optimization, in: Alexandrov N, Hussaini M, eds., Multidisciplinary Design Optimization, State-of-the-Art, SIAM, 1997, 133-152
[94] Liao A P. A reduced Hessian method for constrained optimization. Computational Optimization and Applications, 1993, 2: 129-143
[95] Murray W, Wright M H. Projected Lagrangian methods based on the trajectories of penalty and barrier functions. Systems Optimization Laboratory Report, Stanford University, Stanford, CA, 1978, 8-23
[96] Nocedal J. Theorey of algorithms for unconstrained optimization. Acta Numerica, 1992, 1: 199-242
[97] Janin R. Directional derivative of the marginal function in nonlinear programming. Mathematical Programming Study, 1984, 21: 110-126
[98] Penot J P. A new constraint qualification condition. Journal of Optimization the orey and Applications, 1986, 48: 459-468
[99] Mayne D Q, Polak E. A superlinearly convergent algorithm for constrained optimization problems. Mathematical Programming study, 1982, 16: 45-61
[100] Pain V M Some methods of solving convex programming problems. USSER Computational Mathematics and Mathematical Physics, 1981, 21: 57-72
[101] More J J, Garbow B S, Hillstrome K E. Testing unconstrained optimization software. ACM Transactions on Mathematical Software, 1981, 7: 17-41
[102] Hock W, Schittkowski K. Test examples for nonlinear programming codes, in: Lecture notes in Economic and Mathematical Systems. New York: Springer-Verlag, 1981, 1-56
[103] Gauvin J. A necessary and sufficient regularity condition to have a bounded multipliers in nonconvex programming. Mathematical Programming, 1977, 12: 136-138
[21 Karush W. Minima of functions of several variables with inequalities as side conditions. Master's thesis, University of Chicago, Chicago, 1939, 1-56
[3] Fletcher R. A new approach to variable metric algorithms. Computer Journal, 1970,13:317-322
[4] Mangasarian O L. Nonlinear Programming. New York: Mc Graw Hill, 1969, 21-34
[5] 袁亚湘，孙文瑜．最优化理论与方法．北京：中国科学出版社，2001，1-627
[6] Broyden C G. The convergence of a class of double rank minimization algorithms: the new algorithm. Journal of the Institute of Mathematics and its Applications, 1970, 6:222-231
[7] Goldfarb D. A family of variable metric methods derived by variational means. Mathematics of Computation, 1970, 24:23-26
[8] Shanno D F. Conditioning of quasi-Newton methods for function minimization. Mathematics of Computation, 1970, 24:647-650
[9] Dennis J E, Moré J. A characterization of superlinear convergence and its applications to quasi-Newton methods. Mathematics of Computation, 1974, 28:549-560
[10] Dennis J E, Moré J J. Quasi-Newton methods, motivation and theory. SIAM Review, 1977, 19:46-89
[11] Armand P, Gilbert J C, Jgoue S J. A feasible BFGS interior point algorithm for solving convex minimization problems. SIAM Journal on Optimization, 2000, 11: 192-222
[12] Byrd R H, Nocedal J, Yuan Y X. Gloabl convergence of a class of qual-Newton methods on convex problems. SIAM Journal on Numerical Analysis, 1987, 24: 1171-1190
[13] Byrd R H, Nocedal J. A tool for the analysis of quasi-Newton methods with application to unconstrained minimization. SIAM Journal on Numerical Analysis, 1989,26: 727-739
[14] Dixon L C W. Variable metric algorithms: necessary and sufficient conditions for identical behavior of nonquadratic functions. Journal of Optimization Theory and Applications, 1972, 10:34-40
[15] Griewank A. The global convergence of partitioned BFGS on problems with convex decompositions and Lipschitzian gradients. Mathematical Programming, 1991, 50: 141-175
[16] Powell M J D. On the convergence of the variable metric algorithm. Journal of the Institute of Mathematics and its Applications, 1971, 7: 21-36
[17] Toint P H. Global convergence of the partitioned BFGS algorithm for convex partially separable optimization. Mathematical Programming, 1986, 36:290-306
[18] Powell M J D. Some convergence properties of a variable metric algorithms for minimization without exact line search, in Nonlinear Programming, SIAM-AMS Proceedings, Volume IX, Cottle R W and Lemke C E, eds., SIAM, Philadelphia, PA, 1976, 53-72
[19] Powell M J D. Quadratic termination properties of minimization algorithm, Part Ⅰ and Part Ⅱ. Journal of the Institute of Mathematics and its Applications, 1972, 10:333-357
[20] Pu D, Yu W. On the convergence of the DFP algorithm. Annal of Operations Reserch, 1990, 24:175-184
[21] Yuan Y X. A modified BFGS algorithm for unconstrained optimization. IMA Journal of Numerical Analysis, 1991, 11:325-332
[22] Li D H, Fuknshima M. A modified BFGS method and its global convergence in nonconvex minimization. Journal of Computational and Applied Mathematics, 2001, 129:15-35
[23] Li D H, Fukushima M. On the global convergence of the BFGS method for nonconvex unconstrained problems. SIAM Journal on Optimization, 2001, 11:1054-1064
[24] 李董辉，童小娇，万中．数值最优化．北京：科学出版社，2005，66-70
[25] Powell M J D. On the convergence of the DEP algorithm for unconstrained optimization when there are only two variables. Mathematical Programming, Series B, 2000, 87:281-301
[26] Dai Y H. Convergence properties of the BFGS algorithm. SIAM Journal on Optimization, 2002, 13:693-701
[27] Mascarenhas W F. The BFGS method with exact line searches fails for non-convex objective functions. Mathematical Programming, Series A, 2004, 99:49-61
[28] Coleman T F, Conn A R. On the local convergence of a quasi-Newton method for the nonlinear programming problem. SIAM Journal on Numerical Analysis, 1984, 21:755-769
[29] Wei Z, Qi L, Chen X. An SQP-type method and its application in stochastic programming. Journal of Optimization Theory and Applications, 2003, 116:205-228
[30] Yu G H, Wei Z X, Guan L T. A modified BFGS-trust region method for nonconvex minimization. Pacific Journal of Optimization, 2006, 2:119-133
[31] Li D H, Fukushima M. A globally and superlinearly convergent Gauss-Newton-based BFGS method for symmetric nonlinear equations. SIAM Journal on Numerical Analysis, 1999, 37:152-172
[32] Byrd R H, Nocedal J. An analysis of reduced Hessian methods for constrained optimization. Mathematical Programming, 1991, 49:285-323
[33] Chen X J. Convergence of the BFGS method for LC~1 convex constrained optimization. SIAM Journal on Control and Optimization, 1996, 34:2051-2063
[34] Pantoja J F A De O, Mayne D Q. Exact Penalty Function Algorithm with Simple Updating of the Penalty Parameter. Journal of Optimization Theory and Applications, 1991, 69:441-467
[35] Powell M J D, Yuan Y X. A recursive quadratic programming algorithm that uses differentiable exact penalty functions. Mathematical Programming, 1986, 35: 265-278
[36] Bell N M. Global convergence of a semi-infinite programming method. Applied Mathematics and Optimization, 1990, 21:69-88
[37] Vat F Ismael A, Fernandes M G P, Gomes S F Paula M. A quasi-Newton interior point method for semi-infinite programming. Optimization methods and software, 2003, 18:673-6&7
[38] Wei Z X, Yu G H, Yuan G L, et al. The superlinear convergence of a modified BFGS-type method for unconstrained optimization. Journal Computional Optimization and Applications, 2004, 29:315-332
[39] 袁亚湘．非线性规划数值方法．上海：上海科学技术出版社，1993，1-121
[40] Powell M J D. Restart procedure for the conjugate gradient method. Mathematical Programming. 1977, 12:241-254
[41] Han S P. A global convergent method for nonlinear programming. Journal of Optimization Theory and Applications, 1977, 22: 297-309
[42] Bertsekas D P. Constrained optimization and Lagrange multiplier methods. New York: Academic Press, 1982, 1-121
[43] Boggs P T, Tolle J W, Wang P. On the local convergence of quasi-Newton methods for constrained optimization. SIAM Journal on Control and Optimization, 1982, 20: 161-171
[44] Boggs P T, Tolle J W. Sequential quadratic programming. Acta Numerical Analysis, 1995, 1: 1-15
[45] Boggs P T, Tolle J W. A strategy for global convergence in a sequential quadratic programming algorithm. SIAM Journal on Numerical Analysis, 1989, 26: 600-623
[46] Byrd R H, Tapia R A, Zhang Y. An SQP augmented Lagrangian BFGS algorithms for constrained optimization. SIAM Journal on Optimization, 1992, 2: 210-241
[47] Coleman T F, Conn A R. A note on the computation of an orthonormal basis for the null space of a matrix. Mathematical Programming, 1984, 29: 234-242
[48] Fontecilla R, Steihaug T, Tapia A. A convergence theory for a class of quasi-Newton methods for constrained optimization. SIAM Journal on Numerical analysis, 1987, 24: 1133-1151
[49] Fontecilla R. Local convergence of secant methods for nonlinear constrained optimization. SIAM Journal on Numerical analysis, 1988, 25: 692-712
[50] Fukushima M. A successive quadratic programming algorithm with global and su-perlinear convergence properties. Mathematical Programming, 1986, 35: 253-264
[51] Qi L, Yang.Y F. A globally and superlinearly convergent SQP algorithm for nonlinear constrained optimization. Journal of Global Optimization, 2001, 21: 157-184
[52] Sargent R W H, Ding M. A new SQP algorithm for large-scale nonlinear programming. SIAM Journal on Optimization, 2000, 11: 716-747
[53] Schittkowski K. The nonlinear programming method of Wilson, Han and Powell with an Lagrangian type line search function. Numerische Mathematik, 1981, 38: 83-114
[54] Wright S J. Superlinear convergence of a stabilized SQP method to degenerate solution. Copmutational Optimization and Applications, 1998, 11: 253-275
[55] Wright S J. Modifying SQP for degenerate probloms. SIAM Journal on Optimization, 2002, 13: 470-497
[56] Pantoja J F A De O. Algorithms for constrained optimization problems. Ph.D Thesis, London: University London, 1983, 1-81
[57] Li D H, Qi L Q. A stabilized SQP method via linear equations. Technical Report, Department of Applied Matheamtics, School of Mathematics, New South Wales University, Sydney, Australia, 2000.
[58] Zhang J L, Zhang X S. A SQP method for inequality constrained optimization. Acta Mathematicae Applicatae Sinica, English Series, 2002, 18: 77-84
[59] Pukushima M, Luo Z Q, Tseng P. A sequential quadratically constrained quadratic programming method for differentiable convex minimization. SIAM Journal on Optimization, 2003, 13: 1098-1119
[60] Solodov M V. On the sequential quadratically constrained quadratic programming methods. Mathematics of Operations Research, 2004, 29: 64-79
[61] Chin M C, Fletcher R. On the global convergence of a SLR-filter algorithm that takes EQP steps. Mathematical Programming, 2003, Series B 96: 161-177
[62] Fletcher R, Leyffer S. Nonlinear programming without a penalty function. Mathematical Programming, 2002, 91: 239-269
[63] Fletcher R, Leyffer S, Toint P L. On the global convergence of a filter-SQP algorithm. SIAM Journal on Optimization, 2002, 13: 44-59
[64] Fletcher R, Nicholas I M G, Leyffer S. Global convergence of a trust-region SQP-filter algorithm for general nonlinear programming. SIAM Journal on Optimization, 2002, 13: 635-659
[65] Gill P E, Leonard M W. Reduced-Hessian quasi-Newton methods for unconstrained optimization. SIAM Journal on Optimization, 2001, 12: 209-237
[66] Nocedal J, Overton M L. Projected Hessian updating algorithms for nonlinearly constrained optimization. SIAM Journal on Numerical Analysis, 1985, 22: 821-850
[67] Schluz V. Solving discretized optimization problems by partially reduced SQP methods. Computing and Visualisation in Science, 1998, 1: 283-96
[68] Fletcher R. Stable reduced Hessian updates for indefinite quadratic programming. Methematical Programming, 2000 Series B 87: 251-264
[69] Xie Y F, Byrd R H. Practical update criteia for reduced Hessian SQP: global analysis. SIAM Journal on Optimization, 1999, 9:578-604
[70] Bonnans J F. Asmpotic admissiblity of the unit stepsize in exact penalty function methods. SIAM Journal on Control and Optimization, 1989, 27:631-641
[71] Bonnans J F, Panier E R, Tits A L, et al. Avoiding the Maratos effect by means of a nonmonotone line search. Ⅱ. inequality constrained problems- Feasible Iterates. SIAM Journal on Numerical Analysis, 1992, 29: 1187-1202
[72] Bonnans J F, Gilbert J Ch, Lemaréchal C, et al. Numerical optimization: Theoretical and Practical Aspects. Berlin: Springer-Verlag, 2003, 1-43
[73] Panier E R, Tits A L. Avoiding the Maratos effect by means of a nonmonotone line search. Ⅰ. general constrained problems. SIAM Journal on Numerical Analysis, 1991, 28:1183-1195
[74] Lobo M S, Vandenberghe L, Boyd S, et al. Applications of second-order cone programming. Linear Algebra and Applications, 1998, 284:193-228
[75] Nesterov Y E, Nemirovskii A S. Interior Point Polynomial Methods in Convex Programming: Theory and Applications. SIAM, Philadelphia, PA, 1993, 1-32
[76] Rockafellar R T. Convex Analysis. Princeton University Prees, Princeton, N J, 1970, 1-54
[77] Alizadeh F, Schmieta S. Symmetric cones, potenial reduction methods, in: Wolkowicz H, Saigal R, Vandenberghe L, eds., Handbook of Semidefinite Programming, Boston: Kluwer Academic Publishers, 2000, 195-233
[78] Monteiro R D C, Tschiya T. Polynomial convergence of primal-dual algorithms for the second-order cone programs based on the MZ- family of directions. Mathematical Programming, 2000, 88:61-83
[79] Tsuchiya T. A convergence analysis of the scaling-invariant primal-dual pathfollowing algorithms for second-order cone programming. Optimization Methods and Software, 1999, 11/12:141-182
[80] Anitescu M. A superlinearly convergent sequential quadratically constrained programming algorithm for degenerate nonlinear programming. SIAM Journal on Optimization, 2002, 12: 949-978
[81] Pain V M. A second-order methods for the discrete min-max problem. USSER Computational Mathematics and Mathematical Physics, 1979, 19:90-100
[82] Wiest E J, Polak E. A generalized quadratic programmingjbased phase I-phase II method for inequality constrained optimization. Applied Mathematics and Optimization, 1992, 26: 223-252
[83] Wolfe P. Convergence conditions for ascent methods. SIAM Review, 1969, 11: 226-235
[84] Armijo L. Minimization of functions having Lipschitz continuous partial derivatives. Pacific Journal of Mathematics, 1966, 16: 1-3
[85] Debreu G. Definite and semidefinite qudratic forms. Econometrica, 1952, 20: 295-300
[86] Broyden C G, Dennis J, More J, On the local and superlinear convergence of quasi-Newton methods. Journal of the Institute of Mathematics and its Applications, 1973, 12: 223-246
[87] Maratos N. Exact penalty function algorithms for finite-dimensional and control optimization problems. Ph.D Thesis, University of London, 1978, 1-42
[88] Amiri N M. An exact penalty method with reduced Hessian updates for solving constrained optimization problems. Journal of Science and Technique, 1994, 1: 1-14
[89] Anstreicherk M, Wright M H. A note on the augmented Hessian when the reduced Hessian is semidefinite. SIAM Journal on Optimization. 2000, 1: 243-253
[90] Biegler L T, Nocedal J, Schmid C. A reduced Hessian method for large-scale constrained optimization. SIAM Journal on Optimization, 1995, 5: 314-347
[91] Biegler L T, Nocedal J, Schmid C, et al. Numerical experience with a reduced Hessian method for large-scale constrained optimization. Computational Optimization and Applications, 2000, 1: 45-67
[92] Gabay D. Reduced quasi-Newton methods with feasibility improvement for nonlinear constrained optimization. Mathematical Programming Study, 1982, 16: 18-44
[93] Ghattas O, Orozcoc C E. A parallel reduced Hessian SQP method for shape optimization, in: Alexandrov N, Hussaini M, eds., Multidisciplinary Design Optimization, State-of-the-Art, SIAM, 1997, 133-152
[94] Liao A P. A reduced Hessian method for constrained optimization. Computational Optimization and Applications, 1993, 2: 129-143
[95] Murray W, Wright M H. Projected Lagrangian methods based on the trajectories of penalty and barrier functions. Systems Optimization Laboratory Report, Stanford University, Stanford, CA, 1978, 8-23
[96] Nocedal J. Theorey of algorithms for unconstrained optimization. Acta Numerica, 1992, 1: 199-242
[97] Janin R. Directional derivative of the marginal function in nonlinear programming. Mathematical Programming Study, 1984, 21: 110-126
[98] Penot J P. A new constraint qualification condition. Journal of Optimization the orey and Applications, 1986, 48: 459-468
[99] Mayne D Q, Polak E. A superlinearly convergent algorithm for constrained optimization problems. Mathematical Programming study, 1982, 16: 45-61
[100] Pain V M Some methods of solving convex programming problems. USSER Computational Mathematics and Mathematical Physics, 1981, 21: 57-72
[101] More J J, Garbow B S, Hillstrome K E. Testing unconstrained optimization software. ACM Transactions on Mathematical Software, 1981, 7: 17-41
[102] Hock W, Schittkowski K. Test examples for nonlinear programming codes, in: Lecture notes in Economic and Mathematical Systems. New York: Springer-Verlag, 1981, 1-56
[103] Gauvin J. A necessary and sufficient regularity condition to have a bounded multipliers in nonconvex programming. Mathematical Programming, 1977, 12: 136-138