滤子方法求解非线性优化问题
|
摘要
非线性(无)约束的最优化理论与方法的研究,由整体收敛性和局部收敛速率两部分构成,其中线搜索技术与信赖域策略是保证算法的整体收敛性的两个重要手段。同时,伴随着计算机的发展和软件的完善,最优化问题的数值求解正变得越来越实际可行。
本文主要针对非线性等式约束、非负约束、一般约束优化问题与非线性等式和不等式系统,借助Fletcher和Leyffer提出的滤子思想,将约束优化问题和非线性系统转化为多目标优化问题,提出了各类有效的线搜索滤子方法,求解非线性约束优化问题以及非线性等式和不等式系统。
Fletcher和Leyffer针对非线性优化问题提出了滤子方法,从而代替传统的罚函数方法来保证优化算法的整体收敛性。其主要的思想是,当目标函数或约束违反度被改进时,就接受试探点。但是,先前的工作只考虑滤子信赖域方法和算法的整体收敛性。因此,本文将滤子线搜索方法结合两类正割算法求解非线性等式约束优化问题。与一般的滤子方法不同的是,本文用拉格朗日函数代替目标函数作为滤子的组成部分。在保持整体收敛性的情况下,算法具有局部二步Q-超线性收敛速率,而且不需要引入二阶校正步。
近期的研究表明,单调的线搜索方法存在一些缺点。尤其是当迭代点到达函数的狭窄谷底时,单调下降的要求可能导致降低收敛速率。Grippo等人推广了Armijo条件,提出了非单调线搜索方法。该方法允许函数值上升,同时保证算法的整体收敛性。数值实验结果证明非单调线搜索方法是有效的、可靠的。本文将滤子正割方法与非单调技术结合求解非线性等式约束优化问题。主要贡献在于将非单调技术应用于滤子和下降条件,使得新方法相对于单调方法更容易接受试探步长,减少了计算量。
既约Hessian二次规划算法被证实是求解大规模优化问题的有效方法,尤其是对自由度相对不大的问题。通过空间分解技术,在相对较小的空间里面求解QP子问题,可以大大降低存贮空间和计算量。考虑既约Hessian二次规划算法和由Yu等人提出的非单调技术,本文构造了非单调滤子既约Hessian算法求解非线性等式约束优化问题。在合理假设下,证明了算法具有整体收敛性和二步Q-超线性收敛速率。数值结果表明非单调方法比单调的情形更有效,同时不会受到Maratos效应的影响,即最后几次迭代的步长都是1。
内点障碍方法在大规模优化计算当中得到日益重视。与积极集策略不同,这些方法提供了解决不等式约束优化问题的另一种有效手段。本文提出了滤子内点方法求解非线性等式和非负约束优化问题。数值结果表明该算法是可行的。
国际上很多学者提出了多维滤子的定义,Gould, Leyffer和Toint用多维滤子的思想求解非线性方程组和非线性最小二乘问题。Gould, Sainvitu和Toint则解决了无约束优化问题的求解。Wachter和Biegler提出了滤子线搜索方法求解等式约束优化问题。由于很多问题同时含有等式和不等式约束,本文基于多维滤子和非单调技术将Wachter-Biegler的方法推广到求解一般约束优化问题。当优化问题只有等式约束和M=1时,该方法就是Wachter-Biegler的方法。数值结果与SNOPT比较,表明新方法是有效的。
非线性等式和不等式系统在应用数学领域有大量的应用,在数学建模、优化、互补问题以及变分不等式的数值算法中起着核心地位。作为滤子方法的应用,本文提出了非单调滤子方法求解非线性等式和不等式系统。在合理假设下,该方法具有整体收敛性和局部Q-超线性收敛速率。数值结果与两类信赖域方法比较,表明新方法是有效的,同时,完全步χκ+1=χκ+dκ或χκ+1=χκ+dκc+dκsoc在最后几次迭代中被接受,使得序列{xk}Q-超线性收敛于x*。
最后本文对所做的研究工作进行总结,特别是创新点小结,并提出了进一步的研究方向。
The study of theory and methods of nonlinear (un)constrained optimization is composed of two parts, i.e., global convergence and local convergent rate. Both line search technique and trust region strategy are well-accepted methods in the optimization in order to assure global con-vergence. At the same time, accompany with the development of computer and the perfect of software, numerical experiments of optimization problems are becoming more and more feasible and effective.
This thesis is devoted to studying systematically the algorithms of nonlinear constrained optimization, including with equality constraints, nonnegative constraints, general constraints. The algorithm of nonlinear systems of equalities and inequalities is also considered. By employing the filter idea introduced by Fletcher and Leyffer, we propose several efficient line search filter method for solving nonlinear constrained optimization and nonlinear systems of equalities and inequalities.
Fletcher and Leyffer presented filter methods for nonlinear programming (NLP), offering an alternative to merit functions, as a tool to guarantee global convergence of algorithms for nonlinear programming. The underlying concept is that trial points are accepted if they improve the objective function or improve the constraint violation. Previous theoretical work on filter methods has considered trust region algorithms and only the question of global convergence. So we extend the line search filter method to two secant algorithms for nonlinear equality constrained optimization by employing the Lagrangian function (?)(x,λ) (instead of the objective function f(x)) in the filter. Besides global convergence, we prove our approach converges locally two-step Q-superlinear, even without an additional second order correction that is needed by many algorithms to avoid the Maratos effect.
Recent research indicates that the monotone line search technique may have some drawbacks. In particular, enforcing monotonicity may considerably reduce the rate of convergence when the iteration is trapped near a narrow curved valley. Grippo et al. generalized the Armijo rule and proposed a nonmonotone line search technique for Newton's method which permits increase in function value, while retaining global convergence of the minimization algorithm. Several nu-merical tests show that the nonmonotone line search technique is efficient and competitive. We propose a filter secant method with nonmonotone line search for nonlinear equality constrained optimization. The main contribution of our paper is to employ the nonmonotone idea to the suf-ficient reduction conditions and filter. This new method has more flexibility for the acceptance of the trial step and requires less computational costs compared with the monotone one.
A reduced Hessian successive quadratic programming algorithm has been shown to be suc-cessful in solving large-scale nonlinear optimization, especially for problems with few degrees of freedom. Based on reduced Hessian algorithm and nonmonotone technique presented by Yu and Pu, we propose a nonmonotone filter reduced Hessian method for nonlinear equality constrained optimization. Similar to Chapter 2, the Lagrangian function (?)(x,λ) is employed in the filter. The global and local convergence is given under reasonable assumption. The numerical results show that the nonmonotone algorithm is more effective than monotone one and does not suffer from the Maratos effect for all problems tested here, i.e., unit steps are accepted in last several iterations.
Growing interest in efficient optimization methods has led to the development of interior-point or barrier methods for large-scale nonlinear programming. In particular, these methods provide an attractive alternative to active set strategies in handling problems with large numbers of inequality constraints. We propose a filter interior-point method for nonlinear equality and nonnegative constrained optimization. Some numerical experiments to show the effectiveness of the proposed algorithm.
Filter methods have been extended by Gould, Leyffer and Toint to the nonliear equations and nonlinear least squares and by Gould, Sainvitu and Toint to the unconstrained optimization problem with multidimensional filter technique. Wachter and Biegler presented line search filter methods for nonlinear equality constrained programming. Since many problems contain both equality and inequality constraints, we generalize Wachter-Biegler methods for solving general nonlinear programming based on the multidimensional filter technique. Under mild conditions, the global convergence and local superlinear convergence of the method are obtained. If nonlinear programming only has equality constraints and M= 1, the method actual is the Wachter-Biegler line search filter methods. The numerical results show that the new method is effective compared with SNOPT.
Systems of nonlinear equalities and inequalities appear in a wide variety of problems in ap-plied mathematics. These systems play a central role in the model formulation design and analysis of numerical techniques employed in solving problems arising in optimization, complementarity, and variational inequalities. As application, we propose a nonmonotone filter method for nonlin-ear systems of equalities and inequalities which guarantee global convergence and possess local superlinear convergent rate under suitable conditions. From the numerical results, we can see that our algorithm performs well compared with two trust-region methods and full stepχκ+1=χκ+dκorχκ+1 =χκ+dκ+dκsoc is accepted in last several iterations so the sequence{xk} converges to x* Q-superlinearly.
Finally, we conclude the main new research results of this thesis and propose some further research direction about our work.
本文主要针对非线性等式约束、非负约束、一般约束优化问题与非线性等式和不等式系统,借助Fletcher和Leyffer提出的滤子思想,将约束优化问题和非线性系统转化为多目标优化问题,提出了各类有效的线搜索滤子方法,求解非线性约束优化问题以及非线性等式和不等式系统。
Fletcher和Leyffer针对非线性优化问题提出了滤子方法,从而代替传统的罚函数方法来保证优化算法的整体收敛性。其主要的思想是,当目标函数或约束违反度被改进时,就接受试探点。但是,先前的工作只考虑滤子信赖域方法和算法的整体收敛性。因此,本文将滤子线搜索方法结合两类正割算法求解非线性等式约束优化问题。与一般的滤子方法不同的是,本文用拉格朗日函数代替目标函数作为滤子的组成部分。在保持整体收敛性的情况下,算法具有局部二步Q-超线性收敛速率,而且不需要引入二阶校正步。
近期的研究表明,单调的线搜索方法存在一些缺点。尤其是当迭代点到达函数的狭窄谷底时,单调下降的要求可能导致降低收敛速率。Grippo等人推广了Armijo条件,提出了非单调线搜索方法。该方法允许函数值上升,同时保证算法的整体收敛性。数值实验结果证明非单调线搜索方法是有效的、可靠的。本文将滤子正割方法与非单调技术结合求解非线性等式约束优化问题。主要贡献在于将非单调技术应用于滤子和下降条件,使得新方法相对于单调方法更容易接受试探步长,减少了计算量。
既约Hessian二次规划算法被证实是求解大规模优化问题的有效方法,尤其是对自由度相对不大的问题。通过空间分解技术,在相对较小的空间里面求解QP子问题,可以大大降低存贮空间和计算量。考虑既约Hessian二次规划算法和由Yu等人提出的非单调技术,本文构造了非单调滤子既约Hessian算法求解非线性等式约束优化问题。在合理假设下,证明了算法具有整体收敛性和二步Q-超线性收敛速率。数值结果表明非单调方法比单调的情形更有效,同时不会受到Maratos效应的影响,即最后几次迭代的步长都是1。
内点障碍方法在大规模优化计算当中得到日益重视。与积极集策略不同,这些方法提供了解决不等式约束优化问题的另一种有效手段。本文提出了滤子内点方法求解非线性等式和非负约束优化问题。数值结果表明该算法是可行的。
国际上很多学者提出了多维滤子的定义,Gould, Leyffer和Toint用多维滤子的思想求解非线性方程组和非线性最小二乘问题。Gould, Sainvitu和Toint则解决了无约束优化问题的求解。Wachter和Biegler提出了滤子线搜索方法求解等式约束优化问题。由于很多问题同时含有等式和不等式约束,本文基于多维滤子和非单调技术将Wachter-Biegler的方法推广到求解一般约束优化问题。当优化问题只有等式约束和M=1时,该方法就是Wachter-Biegler的方法。数值结果与SNOPT比较,表明新方法是有效的。
非线性等式和不等式系统在应用数学领域有大量的应用,在数学建模、优化、互补问题以及变分不等式的数值算法中起着核心地位。作为滤子方法的应用,本文提出了非单调滤子方法求解非线性等式和不等式系统。在合理假设下,该方法具有整体收敛性和局部Q-超线性收敛速率。数值结果与两类信赖域方法比较,表明新方法是有效的,同时,完全步χκ+1=χκ+dκ或χκ+1=χκ+dκc+dκsoc在最后几次迭代中被接受,使得序列{xk}Q-超线性收敛于x*。
最后本文对所做的研究工作进行总结,特别是创新点小结,并提出了进一步的研究方向。
The study of theory and methods of nonlinear (un)constrained optimization is composed of two parts, i.e., global convergence and local convergent rate. Both line search technique and trust region strategy are well-accepted methods in the optimization in order to assure global con-vergence. At the same time, accompany with the development of computer and the perfect of software, numerical experiments of optimization problems are becoming more and more feasible and effective.
This thesis is devoted to studying systematically the algorithms of nonlinear constrained optimization, including with equality constraints, nonnegative constraints, general constraints. The algorithm of nonlinear systems of equalities and inequalities is also considered. By employing the filter idea introduced by Fletcher and Leyffer, we propose several efficient line search filter method for solving nonlinear constrained optimization and nonlinear systems of equalities and inequalities.
Fletcher and Leyffer presented filter methods for nonlinear programming (NLP), offering an alternative to merit functions, as a tool to guarantee global convergence of algorithms for nonlinear programming. The underlying concept is that trial points are accepted if they improve the objective function or improve the constraint violation. Previous theoretical work on filter methods has considered trust region algorithms and only the question of global convergence. So we extend the line search filter method to two secant algorithms for nonlinear equality constrained optimization by employing the Lagrangian function (?)(x,λ) (instead of the objective function f(x)) in the filter. Besides global convergence, we prove our approach converges locally two-step Q-superlinear, even without an additional second order correction that is needed by many algorithms to avoid the Maratos effect.
Recent research indicates that the monotone line search technique may have some drawbacks. In particular, enforcing monotonicity may considerably reduce the rate of convergence when the iteration is trapped near a narrow curved valley. Grippo et al. generalized the Armijo rule and proposed a nonmonotone line search technique for Newton's method which permits increase in function value, while retaining global convergence of the minimization algorithm. Several nu-merical tests show that the nonmonotone line search technique is efficient and competitive. We propose a filter secant method with nonmonotone line search for nonlinear equality constrained optimization. The main contribution of our paper is to employ the nonmonotone idea to the suf-ficient reduction conditions and filter. This new method has more flexibility for the acceptance of the trial step and requires less computational costs compared with the monotone one.
A reduced Hessian successive quadratic programming algorithm has been shown to be suc-cessful in solving large-scale nonlinear optimization, especially for problems with few degrees of freedom. Based on reduced Hessian algorithm and nonmonotone technique presented by Yu and Pu, we propose a nonmonotone filter reduced Hessian method for nonlinear equality constrained optimization. Similar to Chapter 2, the Lagrangian function (?)(x,λ) is employed in the filter. The global and local convergence is given under reasonable assumption. The numerical results show that the nonmonotone algorithm is more effective than monotone one and does not suffer from the Maratos effect for all problems tested here, i.e., unit steps are accepted in last several iterations.
Growing interest in efficient optimization methods has led to the development of interior-point or barrier methods for large-scale nonlinear programming. In particular, these methods provide an attractive alternative to active set strategies in handling problems with large numbers of inequality constraints. We propose a filter interior-point method for nonlinear equality and nonnegative constrained optimization. Some numerical experiments to show the effectiveness of the proposed algorithm.
Filter methods have been extended by Gould, Leyffer and Toint to the nonliear equations and nonlinear least squares and by Gould, Sainvitu and Toint to the unconstrained optimization problem with multidimensional filter technique. Wachter and Biegler presented line search filter methods for nonlinear equality constrained programming. Since many problems contain both equality and inequality constraints, we generalize Wachter-Biegler methods for solving general nonlinear programming based on the multidimensional filter technique. Under mild conditions, the global convergence and local superlinear convergence of the method are obtained. If nonlinear programming only has equality constraints and M= 1, the method actual is the Wachter-Biegler line search filter methods. The numerical results show that the new method is effective compared with SNOPT.
Systems of nonlinear equalities and inequalities appear in a wide variety of problems in ap-plied mathematics. These systems play a central role in the model formulation design and analysis of numerical techniques employed in solving problems arising in optimization, complementarity, and variational inequalities. As application, we propose a nonmonotone filter method for nonlin-ear systems of equalities and inequalities which guarantee global convergence and possess local superlinear convergent rate under suitable conditions. From the numerical results, we can see that our algorithm performs well compared with two trust-region methods and full stepχκ+1=χκ+dκorχκ+1 =χκ+dκ+dκsoc is accepted in last several iterations so the sequence{xk} converges to x* Q-superlinearly.
Finally, we conclude the main new research results of this thesis and propose some further research direction about our work.
引文
[1]C. Audet, J.E. Dennis, A pattern search filter method for nonlinear programming without derivatives, SIAM J. Optim.14 (2004) 980-1010.
[2]L.T. Biegler, J. Nocedal, C. Schmid, A reduced Hessian method for large-scale constrained optimization, SIAM J. Optim.5 (1995) 314-347.
[3]P.T. Boggs, J.W. Tolle, Sequential quadratic programming, Acta Numerica.4 (1995) 1-51.
[4]J. Burke, Algorithms for Solving Finite Dimensional Systems of Nonlinear Equations and Inequalities that have Both Global and Quadratic Convergence Properties, Tech. report ANL/MCS-TM-54, Mathematics and Computer Science Division, Argonne National Lab-oratory, Chicago, IL,1985.
[5]J. Burke, S.P. Han, A Gauss-Newton approach to solving generalized inequalities, Math. Oper. Res.11 (1986) 632-643.
[6]J. Burke, M.C. Ferris, A Gauss-Newton method for convex composite optimization, Tech. report 1176, Center for Parallel Optimization, Computer Sciences, University of Wisconsin, Madison, WI,1993.
[7]R.H. Byrd, R.B. Schnabel, Continuity of the null space basis and constrained optimization, Math. Programming.35 (1986) 32-41.
[8]R.H. Byrd, G. Liu, J. Nocedal, On the local behaviour of an interior point method for non-linear programming. In Numerical Analysis 1997, Pitman Res. Notes Math. Ser.380, D. F. Griffiths and D. J. Higham, eds., Longman, Harlow, UK,1998, pp.37-56.
[9]M.F.P. Costa, E.M.G.P. Fernandes, Practical implementation of an interior point nonmono-toneline search filter method, International Journal of Computer Mathematics.85 (2008) 397-409.
[10]C.M. Chin, R. Fletcher, On the global convergence of an SLP-filter algorithm that takes EQP steps, Math Program.96 (2003) 161-177.
[11]C. Chin, A. Rashid, K. Nor Global and local convergence of a filter line search method for nonlinear programming, Optimization Methods and Software.22 (2007) 365-390.
[12]T.F. Coleman, A.R. Conn, On the local convergence of a quasi-Newton method for the non-linear programming problem, SIAM J. Numer. Anal.21 (1984) 755-769.
[13]A.R. Conn, N.I.M. Gould, Ph.L. Toint, Trust Region Methods, MPS/SIAM Ser. Optim.1, SIAM, Philadelphia,2000.
[14]Y.H. Dai, On the nonmonotone line search, J. Optim. Theory Appl.112 (2001) 315-330.
[15]J.W. Daniel, Newton's method for nonlinear inequalities, Numer. Math.6 (1973) 381-387.
[16]J.E. Dennis, R.B. Schnabel, Numerical Methods for Unconstrained Optimization and Non-linear Equations, Prentice-Hall, Englewood Cliffs, NJ,1983.
[17]J.E. Dennis, M. El-Alem, K. Williamson, A trust-region approach to nonlinear systems of equalities and inequalities, SIAM J. Optim.9 (1999) 291-315.
[18]R. Fletcher, S. Leyffer, Nonlinear programming without a penalty function. Math. Program. 91 (2002) 239-269.
[19]R. Fletcher, S. Leyffer, P.L. Toint, On the global convergence of a filter-SQP algorithm. SIAM J. Optim.13 (2002) 44-59.
[20]R. Fletcher, N.I.M. Gould, S. Leyffer, P.L. Toint, A. Wachter, Global convergence of a trust-region SQP-filter algorithm for general nonlinear programming. SIAM J. Optim.13 (2002) 635-659.
[21]R. Fontecilla, T. Steihaug, R.A. Tapia, A convergence theory for a class of quasi-Newton methods for constrained optimization, SIAM J. Numer. Anal.24 (1987) 1133-1151.
[22]R. Fontecilla, Local convergence of secant methods for nonlinear constrained optimization, SIAM J. Numer. Anal.25 (1988) 692-712.
[23]U.M. Garcia-Palomares, A. Restuccia, A global quadratic algorithm for solving a system of mixed equalities and inequalities, Math. Program.21 (1981) 290-300.
[24]U.M. Garcia-Palomares, On the Minimax Solution of a Nonlinear System of Mixed Equali-ties and Inequalities, Tech. report, Departmento de procesos y sistemas, Universidad Simon Bolivar, Caracas, Venezuela,1983.
[25]Ph.E. Gill, W. Murray, M.A. Saunders, SNOPT:An SQP algorithm for large-scale con-strained optimization. SIAM Review.47 (2005) 99-131.
[26]L. Grippo, F. Lampariello, S. Lucidi, A nonmonotone line search technique for Newton's methods, SIAM J. Numer. Anal.23 (1986) 707-716.
[27]L. Grippo, F. Lampariello, S. Lucidi, A truncated Newton method with nonmonotone line search for unconstrained optimization, J. Optim. Theory Appl.60 (1989) 410-419.
[28]C.C. Gonzaga, E. Karas, M. Vanti, A globally convergent filter method for nonlinear pro-gramming. Technical Report, Department of Mathematics, Federal University of Santa Cata-rina, Brazil,2001 (Revised 2002)
[29]N.I.M. Gould, S. Leyffer, P.L. Toint, A multidimensional filter algorithm for nonliear equa-tions and nonlinear least squares, SIAM J. Optim.15 (2005) 17-38.
[30]N.I.M. Gould, C. Sainvitu, P.L. Toint, A filter trust region method for unconstrained opti-mization, SIAM J. Optim.16 (2005) 341-357.
[31]N.I.M. Gould, D. Orban, A. Sartenaer, Ph.L. Toint, Superlinear convergence of primal-dual interior point algorithms for nonlinear programming. SIAM J. Optim.11 (2001) 974-1002.
[32]C. Gu, D. Zhu, A projected Hessian algorithm with line search filter method for nonlinear optimization. Technical Report, Department of Mathematics, Shanghai Normal University, Shanghai, China,2007.
[33]C. Gu, D. Zhu, A secant algorithm with line search filter method for nonlinear optimiza-tion. Technical Report, Department of Mathematics, Shanghai Normal University, Shanghai, China,2007.
[34]C. Gu, D. Zhu, A filter interior-point algorithm with projected Hessian updating for nonlinear optimization, J. Appl. Math. Comput.29 (2009) 67-80.
[35]W. Hock, K. Schittkowski, Test examples for nonlinear programming codes, Lecture Notes in Economics and Mathematics System, vol.187, Springer-Verlag,1981.
[36]X. Jin, Y. Wei, Numerical Linear Algebra and Its Application, Science Press, Beijing,2004.
[37]G. Liu, J. Han, D. Sun, Global convergence of BFGS algorithm with nonmonotone line search, Optimization.34 (1995) 147-159.
[38]E.R. Panier, Avoiding Maratos effect by means of nonmonotone line search constrained problems, SIAM J. Numer. Anal.28 (1991) 1183-1190.
[39]K. Schittkowski, More test examples for nonlinear mathematical programming codes, Lec-ture Notes in Economics and Mathematics System, vol.282, Springer-Verlag, Berlin, Hei-delberg,1987.
[40]M. Macconi, B. Morini, M. Porcelli, Trust-region quadratic methods for nonlinear systems of mixed equalities and inequalities, Appl. Numer. Math.59 (2009) 859-876.
[41]S.G. Nash, A. Sofer, Why Extrapolation Helps Barrier Methods, Tech report. Operations Research and Engineering Department, George Mason University, Fairfax, VA 22030,1998.
[42]P.Y. Nie, A null space method for solving system of nonlinear equations, Appl. Math. Com-put.149 (2004) 215-226.
[43]P.Y. Nie, Filter methods for system of nonlinear equations, Acta Nathematicae Applicatae Sinica (in Chinese).27 (2004) 407-415.
[44]P.Y. Nie, C.F. Ma, A trust region filter method for general non-linear programming, Appl. Math. Comput.172 (2006) 1000-1017.
[45]P.Y. Nie, Sequential penalty quadratic programming filter methods for nonlinear program-ming, Nonlinear Analysis:RealWorld Applications 8 (2007) 118-129.
[46]J. Nocedal, M.L. Overton, Projected Hessian updating algorithms for nonlinearly constrained optimization, SIAM J. Numer. Anal.22 (1985) 821-850.
[47]J. Nocedal, S. Wright, Numerical Optimization, Springer-Verlag, New York, NY,1999.
[48]E.R. Panier, A.L. Tits, Avoiding the Maratos effect by means of a nonmonotone line search I:general constrained problems. SIAM J. Numer. Anal.28 (1991) 1183-1195.
[49]B.T. Polyak, Gradient methods for solving equations and inequalities, USSR Comput. Math. 4(1964) 17-32.
[50]B.N. Pshenichnyi, Newton's method for the solution of systems of equalities and inequalities, Math. Notes Acad. Sci. USSR.8 (1970) 827-830.
[51]S.M. Robinson, Extension of Newton's method to nonlinear functions with values in a cone, Numer. Math.19 (1972) 341-347.
[52]C. Schmid, L.T. Biegler, Acceleration of Reduced Hessian methods for large-scale nonlinear programming, Computers and Chemical Engineering.17 (1993) 451-463.
[53]J.S. Albuquerquea, V. Gopala, G.H. Stausa, L.T. Biegler, B.E. Ydstiea, Interior point SQP strategies for structured process optimization problems, Computers and Chemical Engineer-ing.21 (1997)853-859.
[54]D.J. Terneta, L.T. Bieglera, Recent improvements to a multiplier-free reduced Hessian suc-cessive quadratic programming algorithm, Computers and Chemical Engineering.22 (1998) 963-978.
[55]C. Shen, W. Xue, D. Pu, Global convergence of a tri-dimensional filter SQP algorithm based on the line search method. Appl. Numer. Math.59 (2009) 235-250.
[56]W.Y. Sun, J.Y. Han, J. Sun, Global convergence of non-monotone descent methods for un-constrained optimization problems, J. Comput. Appl. Math.146 (2002) 89-98.
[57]K. Su, Z. Yu, A modified SQP method with nonmonotone technique and its global conver-gence, Comput. Math. Appl.57 (2009) 240-247.
[58]P.L. Toint, An assessment of nonmonotone line search technique for unconstrained optimiza-tion, SIAM J. on Scientific Comput.17 (1996) 725-739.
[59]P.L. Toint, A nonmonotone trust region algorithm for nonlinear programming subject to convex constraints, Math. Programming.77 (1997) 69-94.
[60]M. Ulbrich, Nonmonotone trust region methods for bound-constrained semi-smooth equa-tion with application to nonlinear complementarity problems, SIAM J. on Optim.11 (2001) 889-917.
[61]M. Ulbrich, S. Ulbrich, Non-monotone trust region methods for nonlinear equality con-strained optimization without a penalty function. Math. Program.95 (2003) 103-135.
[62]M. Ulbrich, S. Ulbrich, L.N. Vicente, A globally convergent primal-dual interior-point filter method for nonlinear programming. Math. Program.100 (2004) 379-410.
[63]A. Wachter, L.T. Biegler, Line search filter methods for nonlinear programming:Motivation and Global convergence. SIAM J. Comput.16 (2005) 1-31.
[64]A. Wachter, L.T. Biegler, Line search filter methods for nonlinear programming:Local con-vergence. SIAM J. Optim.6 (2005) 32-48.
[65]A. Wachter, L.T. Biegler, Global and local convergence of line search filter methods for nonlinear programming, CAPD Technical Report B-01-09, Department of Chemical Engi-neering, Carnegie Mellon University, Pittsburgh, Pennsylvania,2001 (Revised 2002)
[66]A. Wachter, L.T. Biegler, On the implementation of an interior-point filter line-search algo-rithm for large-scale nonlinear programming, Math. Program.106 (2006) 25-57.
[67]G. Wang, Y. Wei, S. Qiao, Generalized Inverses:Theory and Computations, Science Press, Beijing,2004.
[68]H. Yamashita, A globally convergent primal-dual interior-point method for constrained op-timization. Optimization Methods and Software.10 (1998) 443-469.
[69]Z. Yang, W. Sun, C. Dang, A filter-trust-region method for LC1 unconstrained optimization and its global convergence. Analysis in Theory and Applications.24 (2008) 55-66.
[70]Y. Yuan, Trust region algorithms for nonlinear programming. In Computational Mathematics in China, Contemp. Math.163. Z.C.Shi, ed., AMS, Providence, RI,1994,205-225.
[71]Z. Yu, D. Pu, A new nonmonotone line search technique for unconstrained optimization, J. Comput. Appl. Math.219 (2008) 134-144.
[72]J. Zhang, D. Zhu, A projective quasi-Newton method for nonlinear optimization. J. Comput. Appl. Math.53 (1994) 291-307.
[73]D. Zhu, An affine scaling projective reduced Hessian algorithm for minimum optimization with nonlinear equality and linear inequality constraints. Appl. Math. Comput.166 (2005) 131-163.
[74]D. Zhu, Nonmonotonic projected algorithm with both trust region and line search for con-strained optimization. J. Comput. Appl. Math.117 (2000) 35-60.
[75]NEOS Server:http://neos.mcs.anl.gov/neos/solvers/nco:SNOPT/GAMS.html,2006.
[76]韩继业,修乃华,戚厚铎.非线性互补理论与算法.上海科学技术出版社,2006.
[77]韩渭敏,程晓良.变分不等式简介—基本理论、数值分析及应用.高等教育出版社,2007.
[78]袁亚湘,孙文瑜.最优化理论与方法.科学出版社,1999.
[2]L.T. Biegler, J. Nocedal, C. Schmid, A reduced Hessian method for large-scale constrained optimization, SIAM J. Optim.5 (1995) 314-347.
[3]P.T. Boggs, J.W. Tolle, Sequential quadratic programming, Acta Numerica.4 (1995) 1-51.
[4]J. Burke, Algorithms for Solving Finite Dimensional Systems of Nonlinear Equations and Inequalities that have Both Global and Quadratic Convergence Properties, Tech. report ANL/MCS-TM-54, Mathematics and Computer Science Division, Argonne National Lab-oratory, Chicago, IL,1985.
[5]J. Burke, S.P. Han, A Gauss-Newton approach to solving generalized inequalities, Math. Oper. Res.11 (1986) 632-643.
[6]J. Burke, M.C. Ferris, A Gauss-Newton method for convex composite optimization, Tech. report 1176, Center for Parallel Optimization, Computer Sciences, University of Wisconsin, Madison, WI,1993.
[7]R.H. Byrd, R.B. Schnabel, Continuity of the null space basis and constrained optimization, Math. Programming.35 (1986) 32-41.
[8]R.H. Byrd, G. Liu, J. Nocedal, On the local behaviour of an interior point method for non-linear programming. In Numerical Analysis 1997, Pitman Res. Notes Math. Ser.380, D. F. Griffiths and D. J. Higham, eds., Longman, Harlow, UK,1998, pp.37-56.
[9]M.F.P. Costa, E.M.G.P. Fernandes, Practical implementation of an interior point nonmono-toneline search filter method, International Journal of Computer Mathematics.85 (2008) 397-409.
[10]C.M. Chin, R. Fletcher, On the global convergence of an SLP-filter algorithm that takes EQP steps, Math Program.96 (2003) 161-177.
[11]C. Chin, A. Rashid, K. Nor Global and local convergence of a filter line search method for nonlinear programming, Optimization Methods and Software.22 (2007) 365-390.
[12]T.F. Coleman, A.R. Conn, On the local convergence of a quasi-Newton method for the non-linear programming problem, SIAM J. Numer. Anal.21 (1984) 755-769.
[13]A.R. Conn, N.I.M. Gould, Ph.L. Toint, Trust Region Methods, MPS/SIAM Ser. Optim.1, SIAM, Philadelphia,2000.
[14]Y.H. Dai, On the nonmonotone line search, J. Optim. Theory Appl.112 (2001) 315-330.
[15]J.W. Daniel, Newton's method for nonlinear inequalities, Numer. Math.6 (1973) 381-387.
[16]J.E. Dennis, R.B. Schnabel, Numerical Methods for Unconstrained Optimization and Non-linear Equations, Prentice-Hall, Englewood Cliffs, NJ,1983.
[17]J.E. Dennis, M. El-Alem, K. Williamson, A trust-region approach to nonlinear systems of equalities and inequalities, SIAM J. Optim.9 (1999) 291-315.
[18]R. Fletcher, S. Leyffer, Nonlinear programming without a penalty function. Math. Program. 91 (2002) 239-269.
[19]R. Fletcher, S. Leyffer, P.L. Toint, On the global convergence of a filter-SQP algorithm. SIAM J. Optim.13 (2002) 44-59.
[20]R. Fletcher, N.I.M. Gould, S. Leyffer, P.L. Toint, A. Wachter, Global convergence of a trust-region SQP-filter algorithm for general nonlinear programming. SIAM J. Optim.13 (2002) 635-659.
[21]R. Fontecilla, T. Steihaug, R.A. Tapia, A convergence theory for a class of quasi-Newton methods for constrained optimization, SIAM J. Numer. Anal.24 (1987) 1133-1151.
[22]R. Fontecilla, Local convergence of secant methods for nonlinear constrained optimization, SIAM J. Numer. Anal.25 (1988) 692-712.
[23]U.M. Garcia-Palomares, A. Restuccia, A global quadratic algorithm for solving a system of mixed equalities and inequalities, Math. Program.21 (1981) 290-300.
[24]U.M. Garcia-Palomares, On the Minimax Solution of a Nonlinear System of Mixed Equali-ties and Inequalities, Tech. report, Departmento de procesos y sistemas, Universidad Simon Bolivar, Caracas, Venezuela,1983.
[25]Ph.E. Gill, W. Murray, M.A. Saunders, SNOPT:An SQP algorithm for large-scale con-strained optimization. SIAM Review.47 (2005) 99-131.
[26]L. Grippo, F. Lampariello, S. Lucidi, A nonmonotone line search technique for Newton's methods, SIAM J. Numer. Anal.23 (1986) 707-716.
[27]L. Grippo, F. Lampariello, S. Lucidi, A truncated Newton method with nonmonotone line search for unconstrained optimization, J. Optim. Theory Appl.60 (1989) 410-419.
[28]C.C. Gonzaga, E. Karas, M. Vanti, A globally convergent filter method for nonlinear pro-gramming. Technical Report, Department of Mathematics, Federal University of Santa Cata-rina, Brazil,2001 (Revised 2002)
[29]N.I.M. Gould, S. Leyffer, P.L. Toint, A multidimensional filter algorithm for nonliear equa-tions and nonlinear least squares, SIAM J. Optim.15 (2005) 17-38.
[30]N.I.M. Gould, C. Sainvitu, P.L. Toint, A filter trust region method for unconstrained opti-mization, SIAM J. Optim.16 (2005) 341-357.
[31]N.I.M. Gould, D. Orban, A. Sartenaer, Ph.L. Toint, Superlinear convergence of primal-dual interior point algorithms for nonlinear programming. SIAM J. Optim.11 (2001) 974-1002.
[32]C. Gu, D. Zhu, A projected Hessian algorithm with line search filter method for nonlinear optimization. Technical Report, Department of Mathematics, Shanghai Normal University, Shanghai, China,2007.
[33]C. Gu, D. Zhu, A secant algorithm with line search filter method for nonlinear optimiza-tion. Technical Report, Department of Mathematics, Shanghai Normal University, Shanghai, China,2007.
[34]C. Gu, D. Zhu, A filter interior-point algorithm with projected Hessian updating for nonlinear optimization, J. Appl. Math. Comput.29 (2009) 67-80.
[35]W. Hock, K. Schittkowski, Test examples for nonlinear programming codes, Lecture Notes in Economics and Mathematics System, vol.187, Springer-Verlag,1981.
[36]X. Jin, Y. Wei, Numerical Linear Algebra and Its Application, Science Press, Beijing,2004.
[37]G. Liu, J. Han, D. Sun, Global convergence of BFGS algorithm with nonmonotone line search, Optimization.34 (1995) 147-159.
[38]E.R. Panier, Avoiding Maratos effect by means of nonmonotone line search constrained problems, SIAM J. Numer. Anal.28 (1991) 1183-1190.
[39]K. Schittkowski, More test examples for nonlinear mathematical programming codes, Lec-ture Notes in Economics and Mathematics System, vol.282, Springer-Verlag, Berlin, Hei-delberg,1987.
[40]M. Macconi, B. Morini, M. Porcelli, Trust-region quadratic methods for nonlinear systems of mixed equalities and inequalities, Appl. Numer. Math.59 (2009) 859-876.
[41]S.G. Nash, A. Sofer, Why Extrapolation Helps Barrier Methods, Tech report. Operations Research and Engineering Department, George Mason University, Fairfax, VA 22030,1998.
[42]P.Y. Nie, A null space method for solving system of nonlinear equations, Appl. Math. Com-put.149 (2004) 215-226.
[43]P.Y. Nie, Filter methods for system of nonlinear equations, Acta Nathematicae Applicatae Sinica (in Chinese).27 (2004) 407-415.
[44]P.Y. Nie, C.F. Ma, A trust region filter method for general non-linear programming, Appl. Math. Comput.172 (2006) 1000-1017.
[45]P.Y. Nie, Sequential penalty quadratic programming filter methods for nonlinear program-ming, Nonlinear Analysis:RealWorld Applications 8 (2007) 118-129.
[46]J. Nocedal, M.L. Overton, Projected Hessian updating algorithms for nonlinearly constrained optimization, SIAM J. Numer. Anal.22 (1985) 821-850.
[47]J. Nocedal, S. Wright, Numerical Optimization, Springer-Verlag, New York, NY,1999.
[48]E.R. Panier, A.L. Tits, Avoiding the Maratos effect by means of a nonmonotone line search I:general constrained problems. SIAM J. Numer. Anal.28 (1991) 1183-1195.
[49]B.T. Polyak, Gradient methods for solving equations and inequalities, USSR Comput. Math. 4(1964) 17-32.
[50]B.N. Pshenichnyi, Newton's method for the solution of systems of equalities and inequalities, Math. Notes Acad. Sci. USSR.8 (1970) 827-830.
[51]S.M. Robinson, Extension of Newton's method to nonlinear functions with values in a cone, Numer. Math.19 (1972) 341-347.
[52]C. Schmid, L.T. Biegler, Acceleration of Reduced Hessian methods for large-scale nonlinear programming, Computers and Chemical Engineering.17 (1993) 451-463.
[53]J.S. Albuquerquea, V. Gopala, G.H. Stausa, L.T. Biegler, B.E. Ydstiea, Interior point SQP strategies for structured process optimization problems, Computers and Chemical Engineer-ing.21 (1997)853-859.
[54]D.J. Terneta, L.T. Bieglera, Recent improvements to a multiplier-free reduced Hessian suc-cessive quadratic programming algorithm, Computers and Chemical Engineering.22 (1998) 963-978.
[55]C. Shen, W. Xue, D. Pu, Global convergence of a tri-dimensional filter SQP algorithm based on the line search method. Appl. Numer. Math.59 (2009) 235-250.
[56]W.Y. Sun, J.Y. Han, J. Sun, Global convergence of non-monotone descent methods for un-constrained optimization problems, J. Comput. Appl. Math.146 (2002) 89-98.
[57]K. Su, Z. Yu, A modified SQP method with nonmonotone technique and its global conver-gence, Comput. Math. Appl.57 (2009) 240-247.
[58]P.L. Toint, An assessment of nonmonotone line search technique for unconstrained optimiza-tion, SIAM J. on Scientific Comput.17 (1996) 725-739.
[59]P.L. Toint, A nonmonotone trust region algorithm for nonlinear programming subject to convex constraints, Math. Programming.77 (1997) 69-94.
[60]M. Ulbrich, Nonmonotone trust region methods for bound-constrained semi-smooth equa-tion with application to nonlinear complementarity problems, SIAM J. on Optim.11 (2001) 889-917.
[61]M. Ulbrich, S. Ulbrich, Non-monotone trust region methods for nonlinear equality con-strained optimization without a penalty function. Math. Program.95 (2003) 103-135.
[62]M. Ulbrich, S. Ulbrich, L.N. Vicente, A globally convergent primal-dual interior-point filter method for nonlinear programming. Math. Program.100 (2004) 379-410.
[63]A. Wachter, L.T. Biegler, Line search filter methods for nonlinear programming:Motivation and Global convergence. SIAM J. Comput.16 (2005) 1-31.
[64]A. Wachter, L.T. Biegler, Line search filter methods for nonlinear programming:Local con-vergence. SIAM J. Optim.6 (2005) 32-48.
[65]A. Wachter, L.T. Biegler, Global and local convergence of line search filter methods for nonlinear programming, CAPD Technical Report B-01-09, Department of Chemical Engi-neering, Carnegie Mellon University, Pittsburgh, Pennsylvania,2001 (Revised 2002)
[66]A. Wachter, L.T. Biegler, On the implementation of an interior-point filter line-search algo-rithm for large-scale nonlinear programming, Math. Program.106 (2006) 25-57.
[67]G. Wang, Y. Wei, S. Qiao, Generalized Inverses:Theory and Computations, Science Press, Beijing,2004.
[68]H. Yamashita, A globally convergent primal-dual interior-point method for constrained op-timization. Optimization Methods and Software.10 (1998) 443-469.
[69]Z. Yang, W. Sun, C. Dang, A filter-trust-region method for LC1 unconstrained optimization and its global convergence. Analysis in Theory and Applications.24 (2008) 55-66.
[70]Y. Yuan, Trust region algorithms for nonlinear programming. In Computational Mathematics in China, Contemp. Math.163. Z.C.Shi, ed., AMS, Providence, RI,1994,205-225.
[71]Z. Yu, D. Pu, A new nonmonotone line search technique for unconstrained optimization, J. Comput. Appl. Math.219 (2008) 134-144.
[72]J. Zhang, D. Zhu, A projective quasi-Newton method for nonlinear optimization. J. Comput. Appl. Math.53 (1994) 291-307.
[73]D. Zhu, An affine scaling projective reduced Hessian algorithm for minimum optimization with nonlinear equality and linear inequality constraints. Appl. Math. Comput.166 (2005) 131-163.
[74]D. Zhu, Nonmonotonic projected algorithm with both trust region and line search for con-strained optimization. J. Comput. Appl. Math.117 (2000) 35-60.
[75]NEOS Server:http://neos.mcs.anl.gov/neos/solvers/nco:SNOPT/GAMS.html,2006.
[76]韩继业,修乃华,戚厚铎.非线性互补理论与算法.上海科学技术出版社,2006.
[77]韩渭敏,程晓良.变分不等式简介—基本理论、数值分析及应用.高等教育出版社,2007.
[78]袁亚湘,孙文瑜.最优化理论与方法.科学出版社,1999.