求解约束优化与半定互补问题的信赖域方法
|
摘要
信赖域方法是求解非线性最优化问题的一类重要数值计算方法，由于它具有较好的可靠性和很强的收敛性，因而在近三十年来受到了最优化研究界的重视。特别是近几年来，一直是最优化领域的一个研究重点。目前，信赖域方法已经和传统的线搜索方法并列为非线性规划的两类主要数值方法。在变分不等式与互补问题及平衡约束优化问题中也有信赖域算法可见，在最近兴起的filter方法中，信赖域方法也起着重要的作用。
本文主要研究非线性优化中的信赖域方法。其中包括信赖域子问题的构造、求解以及在约束优化及半定互补问题中的应用。全文共分六章。
第一章：简单介绍信赖域方法的起源及发展现状。
第二章：给出了带记忆的信赖域子问题模型。该模型不仅包含当前点的信息而且包含着过去迭代点的信息，从而使我们可以从更全局的角度来求得信赖域试探步，避免了传统信赖域方法中试探步的求取完全依赖于当前点的信息而过于局部化的困难。将此模型应用到凸约束优化及等式约束优化问题，在几种不同的非单调信赖域技术下，获得了方法的全局收敛性。
第三章：利用谱投影梯度方法与一个新的非单调线搜索技术给出了求解信赖域子问题的一个方法，在一般的假设条件下获得了方法的全局收敛性。
第四章：分析了求解一般非线性方程组的有效集信赖域-CG方法的全局收敛性。将一般非线性方程组问题转化为带非负约束的极小化问题，并利用有效集信赖域对其进行求解，其中信赖域子问题是利用截断共轭梯度方法求解的。在不需要聚点存在的条件下获得了算法的全局收敛性。
第五章：将Nocedal与Yuan的组合信赖域与线搜索技术应用到等式约束优化问题。通过求解某一信赖域子问题及对罚因子的矫正，证明了信赖域步为价值函数提供了一个下降方向。为允许负曲率方向及克服Maratos效应，我们在信赖域试探步中加入二阶校正步，线搜索时采用非单调技术。在一般信赖域方法的假
摘要
设条件下，我们证明了该方法的全局收敛性及局部收敛速度.数值试验表明了该
方法的有效性.
第六章:给出了求解非线性半定互补间题的一个新的光滑效益函数，在不需
要单调及LIPschitz连续的条件下，证明了效益函数的水平集有界且稳定点即为
全局极小点.进一步地，给出了求解带半定约束极小化间题的信赖域算法，其中
信赖域子问题是利用截断共扼梯度法近似求解的.
Trust region method is a class of important numerical method for nonlinear optimization problems. Because of its remarkable numerical reliability in conjunction with a sound and complete convergence theory, researchers in nonlinear optimization area have paid great attention to it since 80's, especially during 90's. At present, trust region method and line search method are two mainly types numerical algorithms for nonlinear programming. For variational inequality problems and complementarity problems, one can also design the corresponding trust region algorithms. Moreover, it also play an important role in a recently developed filter method.
The aim of this thesis is to study the trust region method in nonlinear optimization, which including the forming and the solving of the trust region subproblem and applications for constrained optimization and semidefmite complementarity problems. This thesis includes six chapters.
Chapter 1: Introduction.
Chapter 2: A trust region subproblem model with memory is proposed. The model includes memory of the past iteration, which makes the algorithm more farsighted in the sense that its behavior is not completely dominated by the local nature of the objective function, but rather by a more global view. We apply this model to convex constrained and equality constrained optimization problems and establish the global convergence with the help of nonmonotone techniques.
Chapter 3: Using spectral projected gradient method and a new nonmonotone line search technique, we propose a algorithm for solving the trust region subproblem. Under weak conditions, the global convergence is established.
Chapter 4: We analyze an active set trust region-CG method for the solution of nonlinear system with equalities and inequalities. By reformulating the system into a nonlinear minimization problem with non-negative constraint, we proposed an active set trust region algorithm with which the subproblem is solved by
the truncated conjugate gradient method. The global convergence is established without requiring the existence of an accumulation point.
Chapter 5: We apply the combining trust region and line search algorithm to solve equality constrained optimization. By using L1 exact penalty function as the merit function and solving a trust region subproblem, we prove that the trust region trial step provide a descent direction for the merit function. To allow the negative curvature direction and avoid the Maratos effect, we add second correction step to trust region trial step and employ nonmonotone technique in line search. The global convergence and local superlinear rate are obtained under certain conditions. Some numerical tests are also presented.
Chapter 6: In this chapter, we present a new merit function for the semi-definite complementarity problem (SDCP) by extending the bounded smooth reformulation for variational inequality problems. We prove that the merit function has a bounded level set and any stationary point of it is a global minimizer without the assumption of monotonicity. Moreover, we present a trust region algorithm for solving the minimization problem with semidefinite constraints. The trust region subproblem is solved by the truncated conjugate gradient method and the global convergence is established even without requiring the existence of an accumulation point of the generated sequence.
本文主要研究非线性优化中的信赖域方法。其中包括信赖域子问题的构造、求解以及在约束优化及半定互补问题中的应用。全文共分六章。
第一章：简单介绍信赖域方法的起源及发展现状。
第二章：给出了带记忆的信赖域子问题模型。该模型不仅包含当前点的信息而且包含着过去迭代点的信息，从而使我们可以从更全局的角度来求得信赖域试探步，避免了传统信赖域方法中试探步的求取完全依赖于当前点的信息而过于局部化的困难。将此模型应用到凸约束优化及等式约束优化问题，在几种不同的非单调信赖域技术下，获得了方法的全局收敛性。
第三章：利用谱投影梯度方法与一个新的非单调线搜索技术给出了求解信赖域子问题的一个方法，在一般的假设条件下获得了方法的全局收敛性。
第四章：分析了求解一般非线性方程组的有效集信赖域-CG方法的全局收敛性。将一般非线性方程组问题转化为带非负约束的极小化问题，并利用有效集信赖域对其进行求解，其中信赖域子问题是利用截断共轭梯度方法求解的。在不需要聚点存在的条件下获得了算法的全局收敛性。
第五章：将Nocedal与Yuan的组合信赖域与线搜索技术应用到等式约束优化问题。通过求解某一信赖域子问题及对罚因子的矫正，证明了信赖域步为价值函数提供了一个下降方向。为允许负曲率方向及克服Maratos效应，我们在信赖域试探步中加入二阶校正步，线搜索时采用非单调技术。在一般信赖域方法的假
摘要
设条件下，我们证明了该方法的全局收敛性及局部收敛速度.数值试验表明了该
方法的有效性.
第六章:给出了求解非线性半定互补间题的一个新的光滑效益函数，在不需
要单调及LIPschitz连续的条件下，证明了效益函数的水平集有界且稳定点即为
全局极小点.进一步地，给出了求解带半定约束极小化间题的信赖域算法，其中
信赖域子问题是利用截断共扼梯度法近似求解的.
Trust region method is a class of important numerical method for nonlinear optimization problems. Because of its remarkable numerical reliability in conjunction with a sound and complete convergence theory, researchers in nonlinear optimization area have paid great attention to it since 80's, especially during 90's. At present, trust region method and line search method are two mainly types numerical algorithms for nonlinear programming. For variational inequality problems and complementarity problems, one can also design the corresponding trust region algorithms. Moreover, it also play an important role in a recently developed filter method.
The aim of this thesis is to study the trust region method in nonlinear optimization, which including the forming and the solving of the trust region subproblem and applications for constrained optimization and semidefmite complementarity problems. This thesis includes six chapters.
Chapter 1: Introduction.
Chapter 2: A trust region subproblem model with memory is proposed. The model includes memory of the past iteration, which makes the algorithm more farsighted in the sense that its behavior is not completely dominated by the local nature of the objective function, but rather by a more global view. We apply this model to convex constrained and equality constrained optimization problems and establish the global convergence with the help of nonmonotone techniques.
Chapter 3: Using spectral projected gradient method and a new nonmonotone line search technique, we propose a algorithm for solving the trust region subproblem. Under weak conditions, the global convergence is established.
Chapter 4: We analyze an active set trust region-CG method for the solution of nonlinear system with equalities and inequalities. By reformulating the system into a nonlinear minimization problem with non-negative constraint, we proposed an active set trust region algorithm with which the subproblem is solved by
the truncated conjugate gradient method. The global convergence is established without requiring the existence of an accumulation point.
Chapter 5: We apply the combining trust region and line search algorithm to solve equality constrained optimization. By using L1 exact penalty function as the merit function and solving a trust region subproblem, we prove that the trust region trial step provide a descent direction for the merit function. To allow the negative curvature direction and avoid the Maratos effect, we add second correction step to trust region trial step and employ nonmonotone technique in line search. The global convergence and local superlinear rate are obtained under certain conditions. Some numerical tests are also presented.
Chapter 6: In this chapter, we present a new merit function for the semi-definite complementarity problem (SDCP) by extending the bounded smooth reformulation for variational inequality problems. We prove that the merit function has a bounded level set and any stationary point of it is a global minimizer without the assumption of monotonicity. Moreover, we present a trust region algorithm for solving the minimization problem with semidefinite constraints. The trust region subproblem is solved by the truncated conjugate gradient method and the global convergence is established even without requiring the existence of an accumulation point of the generated sequence.
引文
[1] M.J.D. Powell, Convergence properties of a class minimization algorithms, in O. L. Mangasarisaian, R.R.Meyer and S.M.Robinson, eds., Nonlinear programming 2, Academic Press, New York, (1975), 1-27.
[2] J.J. More, Recent developments in algorithm for trust region methods, in: A.Bachem, M.Grotchel and B.Korte, eds, Math. Prog: The state of the Art, Springer-Verlag, Berlin, (1983), 258-287.
[3] G.A.Schultz, R.B. Schnabel, R.H. Byrd, A family of trust region based algorithms for unconstrained minimization with strong global convergence, SIAM J. Numerical Analysis., 20(1985), 409-426.
[4] A.Levenberg, A method for the solution of certain nonlinear problem in least squares, Qart.Appl.Math., 2(1944), 164-166.
[5] D.M.Marquardt, An algorithm for least-squares estimation of nonlinear inequalities, SIAM J.Appl.Math., 11(1963), 431-441
[6] R.Fletcher, S.Leyffcr, Nonlinear programming without a penalty function, Math. Prog, 91(2002), 239-269.
[7] R.Fletcher, S.Leyffer, Ph.L.Toint, On the global convergence of a SLP-filter algorithm, Tech.Report, 98/13, Department of Mathematics, FUNDP, Narmur, 1998.
[8] R.Fletcher, S. Leyffer, Ph.L. Toint, On the global convergence of a SQP-filter algorithm, SIAM J. Optim, (2003)44-59.
[9] R.Fletcher, S.Leyffer, Ph.L.Toint, Global convergence of a trust region SQP-filter algorithm for general nonlinear programming, SIAM. J. Optim, 13(2003), 635-659.
[10] M.Ulbrich, S.Ulbrieh, Nonmonotone trust region algorithm for equality constrained optimization without a penalty function, Math. Prog, (2002)series B, in press.
[11] S. Di, W.Y. Sun, Trust region method for conic model to solve unconstrained optimization problems, Optimization methods and software, 6(1996), 237-263.
[12] W.Y. Sun, Y.Yuan, A eonle model trust region method for nonlinear constrained optimization, Annal of Operations Research, 103(2001) 175-191.
[13] Y．Yuan，信赖域方法的收敛性，计算数学， No．3 16(1994)，334-346．
[14] R.Fletcher, A model algorithm for composite NDO problem, Math. Prog.Study, 17(1982), 67-76.
[15] M.J.D, Powell, On global convergence of trust region algorithms for unconstrained optimization, Math. programming, 29(1984): 297-303.
[16] R. H. Byrd, R. B. Schnab and G. A.Schultz, A trust region algorithm for nonlinearly constrained optimization, SIAM J. Numerical Analysis, 24 (1987), 1152-1169.
[17] A.Vardi, A trust region algorithm for equality constrained minimization convergence properties and implemention, SIAM J. Numerical Analysis. 22(1985), No.3, 575-591.
[18] M.R.Celis, J.E.Dennis and R.A.Tapia, A trust region algorithm for nonlinear constrained optimization, in: P.T.Boggs, R.H.Byrd and R.B.Schnabel eds, Numerical optimization (SIAM, Philadelphia, 1985), 71-82.
[19] M.J.D Powell, Y. Yuan, A trust region algorithm for equality constrained optimization, Mathematical Programming, 49(1991).189-211.
[20] R.Fletcher, Practical method of optimization, Constrained optimization, vol 2, John Wiley, New York, 1981.
[21] Y. Yuan, A new trust region algorithm for nonlinear oiptimization, in: D.Bainov, V.Covachev, eds. Proc. First Int.Col.Nomer.Anal., VSP, Zeist, (1993), 141-152.
[22] J.V. Burke, A Robust trust region method for constrained nonlinear programming problems, SIAM J. Optim., 2(1992), 325-347.
[23] 袁亚湘，孙文瑜，最优化理论与方法，北京科学出版社，北京，1997．
[24] J.V.Burke, J.J.More, On the identification of active constraints, SIAM J.Numerical Analysis., 25(1988), 1197-1211.
[25] E.Omojokun, Trust region strategies for optimization with equality and inequality constraints, Ph.D Thesis, Department of Computer Science, University of Colorado at Boulder, 1989.
[26] R.H.Byrd, J.C.Gilbert, J.Nocedal, A trust region method based on interior point techniques for nonlinear programming, Math. Programming, 89(2000), 149-185.
[27] E. S.Bothina, A global convergence theory for an active-trust-region algorithm for solving the general nonlinear programming problem, Applied Mathematics and Computation, 144 (2003), 127-157.
[28] A.R.Conn, N.I.M.Gould, and Ph.L.Toint, Global convergence of a class of trust region algorithms for optimization with simple bounds, SIAM J. Numerical Analysis, 25(1988), 433-460.
[29] 陈中文，韩继业，求解变量带简单界约束的非线性规划问题的信赖域方法，计算数学，No．3，19(1997)，257-266，
[30] J.V. Burke, J.J. More, and G.Toraldo, Convergence properties of trust region methods for linear and convex constraints, Math. Programming, 4(1990), 305-336.
[31] J. E. Dennis, M. M. El-Alem and M. C. Maciel, A global convergence theory for general trust region-based Mgorithms for equality constrained optimization, SIAM J. Optim., 7 (1997), 177-207.
[32] J. E. Dennis, L. N. Vicente, On the convergence theory of trust-region-based algorithms for equality constrained optimization, SIAM J. Optim, 7 (1997), 927-950.
[33] L.Gripp, F.Lampariello, S.Lucidi, A nonmonotone line search technique for Newton's methods, SIAM J. Numer. Anal, No.4, 23(1986), 707-716.
[34] E.R.Panier and A.L.tits, Avoiding Maratos effect by means of nonmonotone line search
for constrained problems, SIAM J. Numer. Anal., No.4, 28(1991), 1183-1190.
[35] N. Y. Deng, Y. Xiao, F. Zhou, Nonmonotone trust region algorithm, Journal of Optimization Theory and Applications, 76 (1993), 259-285.
[36] X.W.Ke, J.Y.Han, A class of nonmonotone trust region algorithm for unconstrained optimization, Science in China, 1998, 28(6):488-492.
[37] P.L.Toint, A nonmonotone trust region algorithm for nonlinear programming subject to convex constraints, Mathematiocal programming, 77(1997), 69-94.
[38] M.Ulbrich, Nonmonotone trust region methods for bound-constrained semi-smooth equation with application to nonlinear complementarity problems, SIAM J.Optim, 2001, 11 (4) 889-917.
[39] 李正锋，邓乃扬，一族新的非单调信赖域方法及其收敛性，应用数学学报，22(1999)，457-265．
[40] X.J.Tong, S.Z.Zhou, Nonmonotone trust region algorithm for equality constrained optimization, 高校应用数学学报 (英文),15(2000), 201-210.
[41] Y.H.Dai, D.C.Xu, A new family of trust region algorithms for unconstrained optimization, Journal of Computation Mathematics, No2, 22 (2003), 221-228.
[42] R.H.Byrd, R.S.Schnabel, G.A.Schultz, Approximate solution of the trust region subproblem by minimization over two-dimension subspace, Math. Programming, 40(1988), 247-263.
[43] D.M.Gay, Subroutine for unconstrained minimization using a model/trust region approach, ACM Trans.Software, 9(1983), 503-524.
[44] T.Steihaug, The conjugate gradient method and trust regions in large scale optimization, SIAM J. Numer.Anal., 20(1983), 626-637.
[45] N.I.M.Gould, S.Lucidi, M.Roma, Ph.l.Toint, Solving the trust region subproblem using the Lanczos method, SIAM J.Optimization, 9(1999), 504-525.
[46] Ph.L.Toint, Towards an efficient sparsity exploiting Newton method for minimization, in:I Duff (eds) Sparse matrices and their uses, Academic press, (1981), 57-88.
[47] J.J.More, D.C. Sorensen, Computing a trust region step, SIAM J.Sci Statis. Comput., 4(1983), 553-572.
[48] P.D.Tao, L.T.Hoai An, A D.C. optimization algorithm for solving the trust region subproblem, SIAM J.Optimization, 8(1998), 476-505.
[49] J.Zhang, C.Xu, A class indefinite dogleg path methods for unconstrained minimization, SIAM J.Optimization, 9(1999), 646-667.
[50] Y.Yuan, On the truncated conjugate gradient method, Math programming, 87(2000), 561-573.
[51] B.S.He, Solving large-scale trust region subproblem, Journal of computing Mathematics, 20(2001),1-12.
[52] William W. Hager, Mininize a quadratic over a sphere, SIAM J.Optimization, 12(2002), 188-208.
[53] A.Sartenaer, Automatic determination of an intial trust region in nonlinear programming, SIAM J. Sci. Compuit., 18(1997), 1788-1803.
[54] X.S.Zhang, J.L.Zhang and L.Z.Liao, An adaptive trust region algorithm for unconstrained optimization, Science in China, 45(5)(2002), 620-631.
[55] X.S.Zhang, Z.W.Chen, J.L.Zhang, A self-adaptive trust region method for unconstrained optimization, OR Transactions, 5(1)(2001), 53-62.
[56] J. L. Zhang, Trust region algorithm for nonlinear optimization, Ph.D Thesis, Institute of Applied Mathematics, Chinese Academic of Science, 2001.
[57] T.Bannert, A trust region algorithm for nonsmooth optimization, Math.Programming, 67(1994), 247-264.
[58] J.E.Dennis, B.S.Li, R.A.Tapia, A untied approach to global convergence of trust region methods for nonsmooth optimization, Math. Programming, 68(1995), 319-346.
[59] Y.Yuan, Condition for convergence of trust region algorithm fo nonsmooth optimization, Math.Programming, 31(1985), 220-228.
[60] Y.Yuan, On the superlinear convergence of a trust region algorithm for nonsmooth optimization, Math.Programming, 31(1985), 269-285.
[61] W.Y.Sun, Quasi-Newton trust region method for nonsmooth equation, Applied Mathematics and Computation, (1998),183-194.
[62] A.R.Conn, N. I. M. Gould and P.L.Toint, Trust region methods, MPS/SIAM Series on Optimization, Society for Industrial and Applied Mathematics(SIAM), Philadelphia, PA. 2000.
[63] F.Rendl, H.Wolkowicz, A semidefinite framwork for trust region subproblem with application to large-scale minimization, Mathematical Programming, Series B, 77(2)(1997), 273-299.
[64] Y.Y.Ye, S.Z.Zhang, New results on minimization a quadratic function, SIAM J.Optim, 14(2003),245-267.
[65] F.Alizadeh, Interior point methods in semidefinite programming with application to combinatorial optimization, SIAM J.Optim 5(1995), 13-51.
[66] C.Helemery, F.Rendl, R.Vanderbei and H.Wolkowice, An interior point method for semidefinite programming, SIAM J.Optim, 6(1996), 342-361.
[67] L.Vandenberghe and S.Boyd, Semidefinite programming, SIAM Review, 38(1996), 49-95.
[68] R.D.C.Monteiro, Primal-dual path following algorithms for semidefinite programming, SIAM J.Optim, 7(1997), 663-678.
[69] Y.Zhang, Extending some interior point methods from linear programming to semidefinite programming, 8(1998), 365-378.
[70] P.Tseng, Merit function for semidefinite complementarity problems, Mathematical programming, 1998, 159-185.
[71] A.Auslender, Optimization: Methods and Numerical, Masson: Paris, 1976.
[72] M.Fukushima, Equivalent differentiable optimization problems and descent methods for symmetric variational inequalities, Mathematical Programming, 53(1992), 99-110.
[73] O.L.Mangasarian and M.V.Solodov, Nonlinear complementarity as unconstrained and constrained minimization, Mathematical programming, 62(1993), 277-297.
[74] A.Fischer, An NCP function and its use for the solution of complementarity problems, In: D.Z.Du, L.Qi and R.S.Womersley(Eds), Recent advance in nonsmooth optimization, Singapore, World Science Publishers, 1995, 88-105.
[75] Z.Q.Luo and P.Tseng, A new class of merit function for the nonlinear complementarity problems, In: M.C.Ferris and J.S.Pang(eds), Complementarity Problems: State of the Art, SIAM, Philsdel, 204-225, 1997.
[76] N.Yamashita and M.Fukushima, A New merit function and a decrease algorithm for semidefinite complementarity problems. In: M.Fukushima and L.Qi(Eds.) Reformulation: Nonsmooth, piecewise, semismooth and smoothing methods. Kulwer Academic Publisher, (1998), 405-420.
[77] 张立平，高自友，赖炎连，半定互补问题的全局收敛性算法，系统科学与数学，13(2001)480-485．
[78] X.Chen and P.Tseng, Non-interior continuous methods for semidefinite complementarity problems, Mathematical Programming. 95(2003), 431-474.
[79] Z.H.Huang, J.Y.Han, Non-interior continuous methods for solving semidefinite complementarity problems, Applied Mathematics and Optimization, 47(2003), 195-211.
[80] J.Sun, D.Sun, L.Qi, Quadratic convergence of a smoothing Newton method for nonsmooth matrix equation and its applications in semidefinite optimization problems, Preprint, Department of Decision Science, National University of Singapore, Republic of Singapore, 2002.
[81] C.Kanzow and C.Nage], Semidefinite programming: New search direction, smoothing-type methods and numerical results. SIAM J.Optim, 13(1)(2003), 1-23.
[82] J. Barzilai and J. M.Borwein, Two point step size gradient method, IMA Journal of Numerical Analysis (8)(1988), 174-184.
[83] M. Raydan, The Barzilai-Borwein gradient method for the large scale unconstrained optimization problem, SIAM Journal on Optimization, 7(1997), 26-33.
[84] E. G. Birgin , J. M. Martinez and Raydan, Nonmonotone spectral projected gradient methods on convex sets, SIAM Journal on Optimization, 10(2000), 1196-1211.
[85] Houduo Qi, Liqun Qi and Defeng Sun, Solving KKT systems via the trust region and conjugate gradient methods, SIAM J.Optim, 14(2003) 439-463.
[86] J.Nocedal, Y. Yuan, Combining trust region and line search techniques, in Yuan Y. eds., Advance in nonlinear programming, 1998, 153.176.
[87] P.H.Calamai, J.J.More, Projected gradient methods for linear constrained problems, Math. Programmming, 39(1987), 93-116.
[88] C.Y.Wang, N.H.Xiu, Convergence of the projected gradient method for generalized convex minimization, Comput. Optim. Appl. 16(2) (2000), 111-120.
[89] D.T.Zhu, Nonmonotone Projection Gradient Method for Inequality Constraints Optimization, Chinese Journal of Mathematics, 1998, 19(6): 749-760.
[90] J.Z.Zhang, D.T.Zhu, Projective quasi-Newton method for nonlinear optimization, J. Computational and Applied Mathematics, 1994, 291-307.
[91] N. I. M.Gould, S.Lucidi, M.Roma and P.L.Toint, A line search algorithm with memory for unconstrained optimization, In: High Performance algorithms and software in Nonlinear optimization (Deleone, Mauli, Pardalos and Toraldo eds), Kluwer Acaemic Publishers, 1998, 207-223.
[92] M. J. D. Powell and Y. Yuan, A recursive quadratic programming algorithm that uses differentiable exact penalty function, Mathematical Programming, 35(1986), 265-278.
[93] M. Fukushima, A successive quadratic programming algorithm with global and superlinear convergence properties, Mathematical Programming, 35(1986), 253-264.
[94] R. W. H. Sargent and M. Ding, A new SQP algorithm for large-scale nonlinear programming, SIAM J.Optim, 11(2001), 716-747.
[95] Chen Zhong wen, Han Jiye, and Han Qianmin, A global convergence trust region algorithm for optimization with general constraint and simple bounds, Acta Mathematics Application Sinica, 15(1999), 425-432.
[96] M.M.El-Alem, A global convergence theory for the Celis-Dennis-Tapia trust region algorithms for constrained optimization without assuming regularity, SlAM J.Optim, 9(1999), 965-990.
[97] Y.H.Dai, L.Z.Lio, R-linear convergence of the Barzilal and Borwein gradient method, IMA J. Numer. Anal., 22(2002), 1-10.
[98] E. G. Birgin , J. M. Martinez and Raydan, Inexact spectral projected gradient methods on convex sets, IMA J. Numer. Anal., 23(2003), 539-559.
[99] C.Y, Wang, Q. Liu and X.M.Yang, Convergence analysis of nonmonotone spectral projected gradient methods, Submitted to Journal of Computation and Applied Mathematics.
[100] 王长钰，刘茜，非精确投影梯度方法的收敛性分析，已投稿．
[101] E. G. Birgin and J. M. Martinez, Large scale active-set box-constrained optimization method with spectral projected gradients, Computational Optimization and Applications, 23(2002), 101-125.
[102] J.E.Dennis, R.B.Schnabel, Numerical methods for unconstrained optiraization and nonlin-
ear equations, Prentice-Hall, Englewood Cliffs, NJ, (1983).
[103] B.N.Psheniclmyi, Newton's method for the systems of equalities and inequalities, Math.notes Acad.Sci.USSR, 8(1970), 827-830.
[104] J. Burke, S.P.Han, A Guass-Newton approach to solving generalized inequalities, Math. Oper. Res., 11(1986), 632-643.
[105] J. Burke, Algorithms for solving finite dimensional system 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 Laboratory, Chicago, IL, 1985.
[106] J.E.Dennis, M.M.E1-Alem and K.Williamson, A trust region approach to nonlinear systems of equalities and inequalities, SIAM J.Optim, 9:2(1999), 291-315.
[107] X.J.Tong, S.Z.Zhou, A trust region algorithm for nonlinear problems of equalities and inequalities, 数值计算与计算机应用, 1(2001), 53-62.
[108] J.Z.Zhang and D.T.Zhu, A trust region dogleg method for nonlinear optimization Optimization, 21(1990), 543-557.
[109] Nocedal and M.L.Overton, Projection Hessian updatin9 method for nonlinear constrained optimization, SIAM J.Numer.Anal, 22(1985), No.5, 821-850.
[110] Zhu Detong, Nonmonotone projected algorithm with both trust region and line search for constrained optimization, J. Computational and Applied Mathematics, 117(2000), 35-60.
[111] Y.L.Lai, Z.Y.Gao, G.P.He, A generalized gradient projection algorithm of optimization with nonlinear constraints, Science in China(Series A), 36(1993), No.2, 170-180.
[112] T.F. Coleman A.R.Conn, Nonlinear programming via an exact penalty function: asymptotic analysis, Mathematical programming, 24(1982), No.2, 123-136.
[113] R.Andreani and J.M.Martinez, Reformulation of variational inequalities on a simplex and compactification of complementarity problems, SIAM J.Optim, (10) 2000, 878-895.
[114] F.Leibfritz and E.M.E.Mostafa, An interior point trust region method for a special class of nonlinear semidefinite programming, SIAM.J.Optim, 12(2002), 1048-1074.
[115] A.Friedlander, J.M.Martinez and S.A.Santos, A new strategy for solving variational inequalities in bounded polytopes, Numer.Funct.anal.and Optim., 16(5 and 6)1995:653-668.
[116] J.M.Peng, Global convergence method for monotone variational inequality problems, J. Optimization Theory and Applications, 1995: 299-310.
[117] 王宜举，修乃华，非线性规划讲义，(2003)手稿．
[2] J.J. More, Recent developments in algorithm for trust region methods, in: A.Bachem, M.Grotchel and B.Korte, eds, Math. Prog: The state of the Art, Springer-Verlag, Berlin, (1983), 258-287.
[3] G.A.Schultz, R.B. Schnabel, R.H. Byrd, A family of trust region based algorithms for unconstrained minimization with strong global convergence, SIAM J. Numerical Analysis., 20(1985), 409-426.
[4] A.Levenberg, A method for the solution of certain nonlinear problem in least squares, Qart.Appl.Math., 2(1944), 164-166.
[5] D.M.Marquardt, An algorithm for least-squares estimation of nonlinear inequalities, SIAM J.Appl.Math., 11(1963), 431-441
[6] R.Fletcher, S.Leyffcr, Nonlinear programming without a penalty function, Math. Prog, 91(2002), 239-269.
[7] R.Fletcher, S.Leyffer, Ph.L.Toint, On the global convergence of a SLP-filter algorithm, Tech.Report, 98/13, Department of Mathematics, FUNDP, Narmur, 1998.
[8] R.Fletcher, S. Leyffer, Ph.L. Toint, On the global convergence of a SQP-filter algorithm, SIAM J. Optim, (2003)44-59.
[9] R.Fletcher, S.Leyffer, Ph.L.Toint, Global convergence of a trust region SQP-filter algorithm for general nonlinear programming, SIAM. J. Optim, 13(2003), 635-659.
[10] M.Ulbrich, S.Ulbrieh, Nonmonotone trust region algorithm for equality constrained optimization without a penalty function, Math. Prog, (2002)series B, in press.
[11] S. Di, W.Y. Sun, Trust region method for conic model to solve unconstrained optimization problems, Optimization methods and software, 6(1996), 237-263.
[12] W.Y. Sun, Y.Yuan, A eonle model trust region method for nonlinear constrained optimization, Annal of Operations Research, 103(2001) 175-191.
[13] Y．Yuan，信赖域方法的收敛性，计算数学， No．3 16(1994)，334-346．
[14] R.Fletcher, A model algorithm for composite NDO problem, Math. Prog.Study, 17(1982), 67-76.
[15] M.J.D, Powell, On global convergence of trust region algorithms for unconstrained optimization, Math. programming, 29(1984): 297-303.
[16] R. H. Byrd, R. B. Schnab and G. A.Schultz, A trust region algorithm for nonlinearly constrained optimization, SIAM J. Numerical Analysis, 24 (1987), 1152-1169.
[17] A.Vardi, A trust region algorithm for equality constrained minimization convergence properties and implemention, SIAM J. Numerical Analysis. 22(1985), No.3, 575-591.
[18] M.R.Celis, J.E.Dennis and R.A.Tapia, A trust region algorithm for nonlinear constrained optimization, in: P.T.Boggs, R.H.Byrd and R.B.Schnabel eds, Numerical optimization (SIAM, Philadelphia, 1985), 71-82.
[19] M.J.D Powell, Y. Yuan, A trust region algorithm for equality constrained optimization, Mathematical Programming, 49(1991).189-211.
[20] R.Fletcher, Practical method of optimization, Constrained optimization, vol 2, John Wiley, New York, 1981.
[21] Y. Yuan, A new trust region algorithm for nonlinear oiptimization, in: D.Bainov, V.Covachev, eds. Proc. First Int.Col.Nomer.Anal., VSP, Zeist, (1993), 141-152.
[22] J.V. Burke, A Robust trust region method for constrained nonlinear programming problems, SIAM J. Optim., 2(1992), 325-347.
[23] 袁亚湘，孙文瑜，最优化理论与方法，北京科学出版社，北京，1997．
[24] J.V.Burke, J.J.More, On the identification of active constraints, SIAM J.Numerical Analysis., 25(1988), 1197-1211.
[25] E.Omojokun, Trust region strategies for optimization with equality and inequality constraints, Ph.D Thesis, Department of Computer Science, University of Colorado at Boulder, 1989.
[26] R.H.Byrd, J.C.Gilbert, J.Nocedal, A trust region method based on interior point techniques for nonlinear programming, Math. Programming, 89(2000), 149-185.
[27] E. S.Bothina, A global convergence theory for an active-trust-region algorithm for solving the general nonlinear programming problem, Applied Mathematics and Computation, 144 (2003), 127-157.
[28] A.R.Conn, N.I.M.Gould, and Ph.L.Toint, Global convergence of a class of trust region algorithms for optimization with simple bounds, SIAM J. Numerical Analysis, 25(1988), 433-460.
[29] 陈中文，韩继业，求解变量带简单界约束的非线性规划问题的信赖域方法，计算数学，No．3，19(1997)，257-266，
[30] J.V. Burke, J.J. More, and G.Toraldo, Convergence properties of trust region methods for linear and convex constraints, Math. Programming, 4(1990), 305-336.
[31] J. E. Dennis, M. M. El-Alem and M. C. Maciel, A global convergence theory for general trust region-based Mgorithms for equality constrained optimization, SIAM J. Optim., 7 (1997), 177-207.
[32] J. E. Dennis, L. N. Vicente, On the convergence theory of trust-region-based algorithms for equality constrained optimization, SIAM J. Optim, 7 (1997), 927-950.
[33] L.Gripp, F.Lampariello, S.Lucidi, A nonmonotone line search technique for Newton's methods, SIAM J. Numer. Anal, No.4, 23(1986), 707-716.
[34] E.R.Panier and A.L.tits, Avoiding Maratos effect by means of nonmonotone line search
for constrained problems, SIAM J. Numer. Anal., No.4, 28(1991), 1183-1190.
[35] N. Y. Deng, Y. Xiao, F. Zhou, Nonmonotone trust region algorithm, Journal of Optimization Theory and Applications, 76 (1993), 259-285.
[36] X.W.Ke, J.Y.Han, A class of nonmonotone trust region algorithm for unconstrained optimization, Science in China, 1998, 28(6):488-492.
[37] P.L.Toint, A nonmonotone trust region algorithm for nonlinear programming subject to convex constraints, Mathematiocal programming, 77(1997), 69-94.
[38] M.Ulbrich, Nonmonotone trust region methods for bound-constrained semi-smooth equation with application to nonlinear complementarity problems, SIAM J.Optim, 2001, 11 (4) 889-917.
[39] 李正锋，邓乃扬，一族新的非单调信赖域方法及其收敛性，应用数学学报，22(1999)，457-265．
[40] X.J.Tong, S.Z.Zhou, Nonmonotone trust region algorithm for equality constrained optimization, 高校应用数学学报 (英文),15(2000), 201-210.
[41] Y.H.Dai, D.C.Xu, A new family of trust region algorithms for unconstrained optimization, Journal of Computation Mathematics, No2, 22 (2003), 221-228.
[42] R.H.Byrd, R.S.Schnabel, G.A.Schultz, Approximate solution of the trust region subproblem by minimization over two-dimension subspace, Math. Programming, 40(1988), 247-263.
[43] D.M.Gay, Subroutine for unconstrained minimization using a model/trust region approach, ACM Trans.Software, 9(1983), 503-524.
[44] T.Steihaug, The conjugate gradient method and trust regions in large scale optimization, SIAM J. Numer.Anal., 20(1983), 626-637.
[45] N.I.M.Gould, S.Lucidi, M.Roma, Ph.l.Toint, Solving the trust region subproblem using the Lanczos method, SIAM J.Optimization, 9(1999), 504-525.
[46] Ph.L.Toint, Towards an efficient sparsity exploiting Newton method for minimization, in:I Duff (eds) Sparse matrices and their uses, Academic press, (1981), 57-88.
[47] J.J.More, D.C. Sorensen, Computing a trust region step, SIAM J.Sci Statis. Comput., 4(1983), 553-572.
[48] P.D.Tao, L.T.Hoai An, A D.C. optimization algorithm for solving the trust region subproblem, SIAM J.Optimization, 8(1998), 476-505.
[49] J.Zhang, C.Xu, A class indefinite dogleg path methods for unconstrained minimization, SIAM J.Optimization, 9(1999), 646-667.
[50] Y.Yuan, On the truncated conjugate gradient method, Math programming, 87(2000), 561-573.
[51] B.S.He, Solving large-scale trust region subproblem, Journal of computing Mathematics, 20(2001),1-12.
[52] William W. Hager, Mininize a quadratic over a sphere, SIAM J.Optimization, 12(2002), 188-208.
[53] A.Sartenaer, Automatic determination of an intial trust region in nonlinear programming, SIAM J. Sci. Compuit., 18(1997), 1788-1803.
[54] X.S.Zhang, J.L.Zhang and L.Z.Liao, An adaptive trust region algorithm for unconstrained optimization, Science in China, 45(5)(2002), 620-631.
[55] X.S.Zhang, Z.W.Chen, J.L.Zhang, A self-adaptive trust region method for unconstrained optimization, OR Transactions, 5(1)(2001), 53-62.
[56] J. L. Zhang, Trust region algorithm for nonlinear optimization, Ph.D Thesis, Institute of Applied Mathematics, Chinese Academic of Science, 2001.
[57] T.Bannert, A trust region algorithm for nonsmooth optimization, Math.Programming, 67(1994), 247-264.
[58] J.E.Dennis, B.S.Li, R.A.Tapia, A untied approach to global convergence of trust region methods for nonsmooth optimization, Math. Programming, 68(1995), 319-346.
[59] Y.Yuan, Condition for convergence of trust region algorithm fo nonsmooth optimization, Math.Programming, 31(1985), 220-228.
[60] Y.Yuan, On the superlinear convergence of a trust region algorithm for nonsmooth optimization, Math.Programming, 31(1985), 269-285.
[61] W.Y.Sun, Quasi-Newton trust region method for nonsmooth equation, Applied Mathematics and Computation, (1998),183-194.
[62] A.R.Conn, N. I. M. Gould and P.L.Toint, Trust region methods, MPS/SIAM Series on Optimization, Society for Industrial and Applied Mathematics(SIAM), Philadelphia, PA. 2000.
[63] F.Rendl, H.Wolkowicz, A semidefinite framwork for trust region subproblem with application to large-scale minimization, Mathematical Programming, Series B, 77(2)(1997), 273-299.
[64] Y.Y.Ye, S.Z.Zhang, New results on minimization a quadratic function, SIAM J.Optim, 14(2003),245-267.
[65] F.Alizadeh, Interior point methods in semidefinite programming with application to combinatorial optimization, SIAM J.Optim 5(1995), 13-51.
[66] C.Helemery, F.Rendl, R.Vanderbei and H.Wolkowice, An interior point method for semidefinite programming, SIAM J.Optim, 6(1996), 342-361.
[67] L.Vandenberghe and S.Boyd, Semidefinite programming, SIAM Review, 38(1996), 49-95.
[68] R.D.C.Monteiro, Primal-dual path following algorithms for semidefinite programming, SIAM J.Optim, 7(1997), 663-678.
[69] Y.Zhang, Extending some interior point methods from linear programming to semidefinite programming, 8(1998), 365-378.
[70] P.Tseng, Merit function for semidefinite complementarity problems, Mathematical programming, 1998, 159-185.
[71] A.Auslender, Optimization: Methods and Numerical, Masson: Paris, 1976.
[72] M.Fukushima, Equivalent differentiable optimization problems and descent methods for symmetric variational inequalities, Mathematical Programming, 53(1992), 99-110.
[73] O.L.Mangasarian and M.V.Solodov, Nonlinear complementarity as unconstrained and constrained minimization, Mathematical programming, 62(1993), 277-297.
[74] A.Fischer, An NCP function and its use for the solution of complementarity problems, In: D.Z.Du, L.Qi and R.S.Womersley(Eds), Recent advance in nonsmooth optimization, Singapore, World Science Publishers, 1995, 88-105.
[75] Z.Q.Luo and P.Tseng, A new class of merit function for the nonlinear complementarity problems, In: M.C.Ferris and J.S.Pang(eds), Complementarity Problems: State of the Art, SIAM, Philsdel, 204-225, 1997.
[76] N.Yamashita and M.Fukushima, A New merit function and a decrease algorithm for semidefinite complementarity problems. In: M.Fukushima and L.Qi(Eds.) Reformulation: Nonsmooth, piecewise, semismooth and smoothing methods. Kulwer Academic Publisher, (1998), 405-420.
[77] 张立平，高自友，赖炎连，半定互补问题的全局收敛性算法，系统科学与数学，13(2001)480-485．
[78] X.Chen and P.Tseng, Non-interior continuous methods for semidefinite complementarity problems, Mathematical Programming. 95(2003), 431-474.
[79] Z.H.Huang, J.Y.Han, Non-interior continuous methods for solving semidefinite complementarity problems, Applied Mathematics and Optimization, 47(2003), 195-211.
[80] J.Sun, D.Sun, L.Qi, Quadratic convergence of a smoothing Newton method for nonsmooth matrix equation and its applications in semidefinite optimization problems, Preprint, Department of Decision Science, National University of Singapore, Republic of Singapore, 2002.
[81] C.Kanzow and C.Nage], Semidefinite programming: New search direction, smoothing-type methods and numerical results. SIAM J.Optim, 13(1)(2003), 1-23.
[82] J. Barzilai and J. M.Borwein, Two point step size gradient method, IMA Journal of Numerical Analysis (8)(1988), 174-184.
[83] M. Raydan, The Barzilai-Borwein gradient method for the large scale unconstrained optimization problem, SIAM Journal on Optimization, 7(1997), 26-33.
[84] E. G. Birgin , J. M. Martinez and Raydan, Nonmonotone spectral projected gradient methods on convex sets, SIAM Journal on Optimization, 10(2000), 1196-1211.
[85] Houduo Qi, Liqun Qi and Defeng Sun, Solving KKT systems via the trust region and conjugate gradient methods, SIAM J.Optim, 14(2003) 439-463.
[86] J.Nocedal, Y. Yuan, Combining trust region and line search techniques, in Yuan Y. eds., Advance in nonlinear programming, 1998, 153.176.
[87] P.H.Calamai, J.J.More, Projected gradient methods for linear constrained problems, Math. Programmming, 39(1987), 93-116.
[88] C.Y.Wang, N.H.Xiu, Convergence of the projected gradient method for generalized convex minimization, Comput. Optim. Appl. 16(2) (2000), 111-120.
[89] D.T.Zhu, Nonmonotone Projection Gradient Method for Inequality Constraints Optimization, Chinese Journal of Mathematics, 1998, 19(6): 749-760.
[90] J.Z.Zhang, D.T.Zhu, Projective quasi-Newton method for nonlinear optimization, J. Computational and Applied Mathematics, 1994, 291-307.
[91] N. I. M.Gould, S.Lucidi, M.Roma and P.L.Toint, A line search algorithm with memory for unconstrained optimization, In: High Performance algorithms and software in Nonlinear optimization (Deleone, Mauli, Pardalos and Toraldo eds), Kluwer Acaemic Publishers, 1998, 207-223.
[92] M. J. D. Powell and Y. Yuan, A recursive quadratic programming algorithm that uses differentiable exact penalty function, Mathematical Programming, 35(1986), 265-278.
[93] M. Fukushima, A successive quadratic programming algorithm with global and superlinear convergence properties, Mathematical Programming, 35(1986), 253-264.
[94] R. W. H. Sargent and M. Ding, A new SQP algorithm for large-scale nonlinear programming, SIAM J.Optim, 11(2001), 716-747.
[95] Chen Zhong wen, Han Jiye, and Han Qianmin, A global convergence trust region algorithm for optimization with general constraint and simple bounds, Acta Mathematics Application Sinica, 15(1999), 425-432.
[96] M.M.El-Alem, A global convergence theory for the Celis-Dennis-Tapia trust region algorithms for constrained optimization without assuming regularity, SlAM J.Optim, 9(1999), 965-990.
[97] Y.H.Dai, L.Z.Lio, R-linear convergence of the Barzilal and Borwein gradient method, IMA J. Numer. Anal., 22(2002), 1-10.
[98] E. G. Birgin , J. M. Martinez and Raydan, Inexact spectral projected gradient methods on convex sets, IMA J. Numer. Anal., 23(2003), 539-559.
[99] C.Y, Wang, Q. Liu and X.M.Yang, Convergence analysis of nonmonotone spectral projected gradient methods, Submitted to Journal of Computation and Applied Mathematics.
[100] 王长钰，刘茜，非精确投影梯度方法的收敛性分析，已投稿．
[101] E. G. Birgin and J. M. Martinez, Large scale active-set box-constrained optimization method with spectral projected gradients, Computational Optimization and Applications, 23(2002), 101-125.
[102] J.E.Dennis, R.B.Schnabel, Numerical methods for unconstrained optiraization and nonlin-
ear equations, Prentice-Hall, Englewood Cliffs, NJ, (1983).
[103] B.N.Psheniclmyi, Newton's method for the systems of equalities and inequalities, Math.notes Acad.Sci.USSR, 8(1970), 827-830.
[104] J. Burke, S.P.Han, A Guass-Newton approach to solving generalized inequalities, Math. Oper. Res., 11(1986), 632-643.
[105] J. Burke, Algorithms for solving finite dimensional system 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 Laboratory, Chicago, IL, 1985.
[106] J.E.Dennis, M.M.E1-Alem and K.Williamson, A trust region approach to nonlinear systems of equalities and inequalities, SIAM J.Optim, 9:2(1999), 291-315.
[107] X.J.Tong, S.Z.Zhou, A trust region algorithm for nonlinear problems of equalities and inequalities, 数值计算与计算机应用, 1(2001), 53-62.
[108] J.Z.Zhang and D.T.Zhu, A trust region dogleg method for nonlinear optimization Optimization, 21(1990), 543-557.
[109] Nocedal and M.L.Overton, Projection Hessian updatin9 method for nonlinear constrained optimization, SIAM J.Numer.Anal, 22(1985), No.5, 821-850.
[110] Zhu Detong, Nonmonotone projected algorithm with both trust region and line search for constrained optimization, J. Computational and Applied Mathematics, 117(2000), 35-60.
[111] Y.L.Lai, Z.Y.Gao, G.P.He, A generalized gradient projection algorithm of optimization with nonlinear constraints, Science in China(Series A), 36(1993), No.2, 170-180.
[112] T.F. Coleman A.R.Conn, Nonlinear programming via an exact penalty function: asymptotic analysis, Mathematical programming, 24(1982), No.2, 123-136.
[113] R.Andreani and J.M.Martinez, Reformulation of variational inequalities on a simplex and compactification of complementarity problems, SIAM J.Optim, (10) 2000, 878-895.
[114] F.Leibfritz and E.M.E.Mostafa, An interior point trust region method for a special class of nonlinear semidefinite programming, SIAM.J.Optim, 12(2002), 1048-1074.
[115] A.Friedlander, J.M.Martinez and S.A.Santos, A new strategy for solving variational inequalities in bounded polytopes, Numer.Funct.anal.and Optim., 16(5 and 6)1995:653-668.
[116] J.M.Peng, Global convergence method for monotone variational inequality problems, J. Optimization Theory and Applications, 1995: 299-310.
[117] 王宜举，修乃华，非线性规划讲义，(2003)手稿．