非线性优化问题的一类非拟牛顿算法研究
|
摘要
对于非线性优化问题寻找快速有效的算法一直是优化专家们研究的热门方向之一。文[28]基于校正的非拟牛顿方程，给出了无约束优化的一类非拟牛顿算法。本文结合文[28]中的非拟牛顿法，给出了求解无约束非线性优化问题的一类具有超线性收敛的非拟牛顿算法。
在第一章我们首先简要的介绍了最优化问题的提出以及判断最优解常用的最优性条件，回顾了无约束优化问题常用的几类导数下降类算法。
在第二章中，就非拟牛顿族在无约束最优化问题上，采用非单调线搜索下是否具有全局收敛性进行了研究。在目标函数满足一致凸的条件下，证明了非拟牛顿族是全局收敛的。
在第三章中，就非拟Newton族在无约束最优化问题上，采用非精确线搜索下是否具有全局收敛性进行了研究。文中提出了一种非拟Newton族校正，并证明在目标函数满足梯度Lipschitz连续的条件下，此校正在Wolfe或Armijo线搜索下具有全局收敛性。
Seeking fast theoretical convergence and effective algorithms in unconstrained optimization is a very interested research topic for the optimization specialists and engineers. Paper [28] gives a class of non-quasi-Newton algorithms about unconstrained programming problems based on the modified non-quasi-Newton equation. In this paper, we give a class of superlinearly convengent algorithms for nonlinear programming problems with unconstrained by combining non-quasi-Newton methods [28] with some inexact line searches.
In chapter 1 ,we first introduce the development of optimization and some extensive optimality conditions which to decide the optimum solution. We review several extensive derivative descent methods of unconstrained programming.
In chapter 2,the non-quasi-Newton's family is concerned with the problem of whether the method with inexact line search converges globally when applied to unconstrained optimization problems.We propose a update and prove that the method with either a Wolfe-type or an Armijo-type line search converges globally if the function to be minimized has Lipschitz continuous gradients.
In chapter 3,the non-quasi-Newton Methods for unconstrained optimization is investigated.Non-monotone line search procedure is introduced, which is combined with the non-quasi-Newton family.Under the uniformly convexity assumption on objective function,the global convergence of the quasi-Newton family is proved.
在第一章我们首先简要的介绍了最优化问题的提出以及判断最优解常用的最优性条件，回顾了无约束优化问题常用的几类导数下降类算法。
在第二章中，就非拟牛顿族在无约束最优化问题上，采用非单调线搜索下是否具有全局收敛性进行了研究。在目标函数满足一致凸的条件下，证明了非拟牛顿族是全局收敛的。
在第三章中，就非拟Newton族在无约束最优化问题上，采用非精确线搜索下是否具有全局收敛性进行了研究。文中提出了一种非拟Newton族校正，并证明在目标函数满足梯度Lipschitz连续的条件下，此校正在Wolfe或Armijo线搜索下具有全局收敛性。
Seeking fast theoretical convergence and effective algorithms in unconstrained optimization is a very interested research topic for the optimization specialists and engineers. Paper [28] gives a class of non-quasi-Newton algorithms about unconstrained programming problems based on the modified non-quasi-Newton equation. In this paper, we give a class of superlinearly convengent algorithms for nonlinear programming problems with unconstrained by combining non-quasi-Newton methods [28] with some inexact line searches.
In chapter 1 ,we first introduce the development of optimization and some extensive optimality conditions which to decide the optimum solution. We review several extensive derivative descent methods of unconstrained programming.
In chapter 2,the non-quasi-Newton's family is concerned with the problem of whether the method with inexact line search converges globally when applied to unconstrained optimization problems.We propose a update and prove that the method with either a Wolfe-type or an Armijo-type line search converges globally if the function to be minimized has Lipschitz continuous gradients.
In chapter 3,the non-quasi-Newton Methods for unconstrained optimization is investigated.Non-monotone line search procedure is introduced, which is combined with the non-quasi-Newton family.Under the uniformly convexity assumption on objective function,the global convergence of the quasi-Newton family is proved.
引文
[1] M.J.D.Powell. A new algorithm for unconstrained optimization,Nonlinear Programming, J.B.Rosen,O.L.Mangasarian and K.Rittle,eds.Academic Press, New York. 1970.
[2] M.J.D.Powell. On the convergence of the variable metric algorithm. J. Inst. Math. Appl .,7(1971), pp.21-36.
[3] M.J.D.Powell. Some global convergence properties of variable metric algorithm for minimization without exact line searches in nonlinear programming.SIAMAMS Proc Ⅸ R. WCottle and C.E.Lemke.eds.,AMS. Providence. RI ,(1976), pp.53-72.
[4] Powell M J D.Nonconvex minimization calculation and the conjugate gradient method Report No.DAMTP1983/NA14,Department of Applied Mathematics and Theoretical Physical, University of Cambridge, Cambridge, England,1983
[5] Pearson,J.D.Variable metric methods of minimization. The Computer Journal, 12(1969), pp.171-178.
[6] L.C.W.Dixon. Variable metric algrithms:Necessary and sufficient conditions for identical behavior on nonquadratic functions.J. Optim. Theory Appl .,10(1972), pp.34-40.
[7] J.E.Dennis, JR and J.J.Moré. A characterization of superlinear convergence and its application to quasi-Newton methodsMath. Comp ,28(1974) pp.549-560
[8] J.E.Dennis, JR and J.J.Moré. Quasi-Newton methods,motivation and theory. SIAM Rev .,19(1977), pp.46-89
[9] Al-Baali M.Descent Property and global convergence of the FletcherReeves method with inexact line searches.IMA Journal of Numerical Analysis,1985,5(1):121-124.
[10] J.J.Moré,B.S.Garbow and K.E.Hillstrome. Testing unconstrained optimization software.ACM Trans. Math. Software,7(1981), pp.17-41.
[11] Grippo,L.,Lampariello,F.,Lucidi,S. A nonmonotone line search technique for Newton's method.SIAM Journal on Numerical Analysis.,23(1986), pp.707-716.
[12] L.Grippo,S.Lucidi, A global convergence version of the Plak-Ribiére conjugate gradient method, Mathematical Programming 1997(78):375-391
[13] R.Fletcher. Practical methods of optimization. 2nd ed..John Wiley & Sons. Chichseter,1987.
[14] Zhang,Y.,Tewarson,R.P. Quasi-Newton algorithms with updates from the preconvex part of Broyden's family.IMA Journal on Numerical Analysis,8(1988), pp.487-509.
[15] R.Byrd, J.Nocedal and Y.Yuan. Global convergence of a class of quasi-Newton methods on convex problems.SIAM J. Number. Anal ,24(1987), pp.1171-1190
[16] R.Byrd and J.Nocedal. A tool for analysis of quasi-Newton methods with application to unconstrained minimization.SIAM J. Number. Anal .,26(1989), pp.727-739.
[17] Byrd,R.H.,Liu,D.C,Nocedal,J.On the behavior of Broyden's class of quasiNewton methods.Technical Report NAM 01,Department of Electrical Engineering and Computer Science,North-Western University, 1990.
[18] A.Griewank. The global convergence of partitioned BFGS on problem with convex decompositions and Lipschitzian gradients.Math. Program .,50(1991), pp.141-175.
[19] Ya-xiang Yuan. A modified BFGS algorithm for unconstrained optimization. IMA Joural of Numerical Analyses,1991,11,325-332.
[20] Yuan,Y.X., Numerical methods for nonlinear programming. Shanghai Scientific and Technical Publishers,Shanghai, 1993(in Chinese).
[21] Yuan.Y.X and Byrd.R.H. Non-quasi-Newton Updates for Unconstrained Optimization,J.of Computational Mathematics, Vol.13.N02,(1995), pp.95-107.
[22] PH.L.Toint. Global convergence of the patitioned BFGS algorithms for convex partially separable optimization.Math. Program .,36(1986), pp.290-306.
[23] PH.L.Toint. Global convergence of the patitioned BFGS algorithms for convex partially separable optimization.Mathematical Programming.,77(1997), pp.69-94.
[24] Han,J.Y.,Liu,G.H. Global convergence of the BFGS algorithm with nonmonontone linesearch. Optimization,34(1995), pp.147-159.
[25] Ke,X.W.Convergence of the preconvex part of Broyden's Family. Journal of Bei-
jing Normal University ,31(1)(1995),pp.6-10.
[26] Elijah Polak, Optimization: Algorithms and consistent Approximations ,Spinger Verlag New York Inc. ,1997.
[27] Han,J.Y.,Liu,G.H. Global convergence analysis of a new non-monontone BFGS algorithm on conex objective functions.Computational Optimization and Applications,7(1997), pp.277-289.
[28] Lanping Chen,Baocong Jiao. A. Class of Non-Quast-Newton Methods and Its Convergence.Comm on appl. and Comput,1997,11(2), pp.9-17(in chinese).
[29] Liu.G.H.,Han.J.Y.,Qi.H.D. and Xu.Z.L., Convergence analysis on a class of conjugate gradient methods Acta Math.Scientia, 1998(18):11-16.
[30] Lanping Chen,Baocong Jiao.Convergence Properties of the Preconvex Part of Non-Quast-Newton's family. Mathematica Numerica Sinica.2000,22(3), pp.369-378(in chinese).
[31] D.H.Li and M.Fukushima. On the global convegence of the BFGS methods of nonconvex unconstrained optimization problems.SIAM.J.Optim.,4(2001), pp.1054-1064.
[32] Xu,D.C. Global Convergence of the Broyden's Class of Quasi-Newton Methods with Nonmonotone Linesearch.Aeta Mathematicae Sinica, English Series.,19(2003), pp.19-24
[33] 赵云彬，段虞荣．伪Newton-B族的导出及其性质．应用数学与计算数学学报，1996，10(1)，pp82-90．
[34] 韩继业，刘光辉．无约束最优化线搜索一般模型及BFGS方法的整体收敛性．应用数学学报，1995，18(1)，112-122．
[35] 刘光辉，韩继业．带一类非精确搜索的Broyden族的全局收敛性．计算数学，1996，3，233-240．
[36] 席少霖．非线性最优化方法．高等教育版出社，1992．
[37] 袁亚湘，孙文瑜著．最优化理论与方法．科学出版社，1999．
[2] M.J.D.Powell. On the convergence of the variable metric algorithm. J. Inst. Math. Appl .,7(1971), pp.21-36.
[3] M.J.D.Powell. Some global convergence properties of variable metric algorithm for minimization without exact line searches in nonlinear programming.SIAMAMS Proc Ⅸ R. WCottle and C.E.Lemke.eds.,AMS. Providence. RI ,(1976), pp.53-72.
[4] Powell M J D.Nonconvex minimization calculation and the conjugate gradient method Report No.DAMTP1983/NA14,Department of Applied Mathematics and Theoretical Physical, University of Cambridge, Cambridge, England,1983
[5] Pearson,J.D.Variable metric methods of minimization. The Computer Journal, 12(1969), pp.171-178.
[6] L.C.W.Dixon. Variable metric algrithms:Necessary and sufficient conditions for identical behavior on nonquadratic functions.J. Optim. Theory Appl .,10(1972), pp.34-40.
[7] J.E.Dennis, JR and J.J.Moré. A characterization of superlinear convergence and its application to quasi-Newton methodsMath. Comp ,28(1974) pp.549-560
[8] J.E.Dennis, JR and J.J.Moré. Quasi-Newton methods,motivation and theory. SIAM Rev .,19(1977), pp.46-89
[9] Al-Baali M.Descent Property and global convergence of the FletcherReeves method with inexact line searches.IMA Journal of Numerical Analysis,1985,5(1):121-124.
[10] J.J.Moré,B.S.Garbow and K.E.Hillstrome. Testing unconstrained optimization software.ACM Trans. Math. Software,7(1981), pp.17-41.
[11] Grippo,L.,Lampariello,F.,Lucidi,S. A nonmonotone line search technique for Newton's method.SIAM Journal on Numerical Analysis.,23(1986), pp.707-716.
[12] L.Grippo,S.Lucidi, A global convergence version of the Plak-Ribiére conjugate gradient method, Mathematical Programming 1997(78):375-391
[13] R.Fletcher. Practical methods of optimization. 2nd ed..John Wiley & Sons. Chichseter,1987.
[14] Zhang,Y.,Tewarson,R.P. Quasi-Newton algorithms with updates from the preconvex part of Broyden's family.IMA Journal on Numerical Analysis,8(1988), pp.487-509.
[15] R.Byrd, J.Nocedal and Y.Yuan. Global convergence of a class of quasi-Newton methods on convex problems.SIAM J. Number. Anal ,24(1987), pp.1171-1190
[16] R.Byrd and J.Nocedal. A tool for analysis of quasi-Newton methods with application to unconstrained minimization.SIAM J. Number. Anal .,26(1989), pp.727-739.
[17] Byrd,R.H.,Liu,D.C,Nocedal,J.On the behavior of Broyden's class of quasiNewton methods.Technical Report NAM 01,Department of Electrical Engineering and Computer Science,North-Western University, 1990.
[18] A.Griewank. The global convergence of partitioned BFGS on problem with convex decompositions and Lipschitzian gradients.Math. Program .,50(1991), pp.141-175.
[19] Ya-xiang Yuan. A modified BFGS algorithm for unconstrained optimization. IMA Joural of Numerical Analyses,1991,11,325-332.
[20] Yuan,Y.X., Numerical methods for nonlinear programming. Shanghai Scientific and Technical Publishers,Shanghai, 1993(in Chinese).
[21] Yuan.Y.X and Byrd.R.H. Non-quasi-Newton Updates for Unconstrained Optimization,J.of Computational Mathematics, Vol.13.N02,(1995), pp.95-107.
[22] PH.L.Toint. Global convergence of the patitioned BFGS algorithms for convex partially separable optimization.Math. Program .,36(1986), pp.290-306.
[23] PH.L.Toint. Global convergence of the patitioned BFGS algorithms for convex partially separable optimization.Mathematical Programming.,77(1997), pp.69-94.
[24] Han,J.Y.,Liu,G.H. Global convergence of the BFGS algorithm with nonmonontone linesearch. Optimization,34(1995), pp.147-159.
[25] Ke,X.W.Convergence of the preconvex part of Broyden's Family. Journal of Bei-
jing Normal University ,31(1)(1995),pp.6-10.
[26] Elijah Polak, Optimization: Algorithms and consistent Approximations ,Spinger Verlag New York Inc. ,1997.
[27] Han,J.Y.,Liu,G.H. Global convergence analysis of a new non-monontone BFGS algorithm on conex objective functions.Computational Optimization and Applications,7(1997), pp.277-289.
[28] Lanping Chen,Baocong Jiao. A. Class of Non-Quast-Newton Methods and Its Convergence.Comm on appl. and Comput,1997,11(2), pp.9-17(in chinese).
[29] Liu.G.H.,Han.J.Y.,Qi.H.D. and Xu.Z.L., Convergence analysis on a class of conjugate gradient methods Acta Math.Scientia, 1998(18):11-16.
[30] Lanping Chen,Baocong Jiao.Convergence Properties of the Preconvex Part of Non-Quast-Newton's family. Mathematica Numerica Sinica.2000,22(3), pp.369-378(in chinese).
[31] D.H.Li and M.Fukushima. On the global convegence of the BFGS methods of nonconvex unconstrained optimization problems.SIAM.J.Optim.,4(2001), pp.1054-1064.
[32] Xu,D.C. Global Convergence of the Broyden's Class of Quasi-Newton Methods with Nonmonotone Linesearch.Aeta Mathematicae Sinica, English Series.,19(2003), pp.19-24
[33] 赵云彬，段虞荣．伪Newton-B族的导出及其性质．应用数学与计算数学学报，1996，10(1)，pp82-90．
[34] 韩继业，刘光辉．无约束最优化线搜索一般模型及BFGS方法的整体收敛性．应用数学学报，1995，18(1)，112-122．
[35] 刘光辉，韩继业．带一类非精确搜索的Broyden族的全局收敛性．计算数学，1996，3，233-240．
[36] 席少霖．非线性最优化方法．高等教育版出社，1992．
[37] 袁亚湘，孙文瑜著．最优化理论与方法．科学出版社，1999．