非线性最优化的几种算法研究
|
摘要
对求解无约束优化问题的共轭梯度法中的方向参数给定了一种新的区间取法以保证搜索方向是目标函数的充分下降方向,在此基础上提出了一种新的记忆梯度算法,在目标函数的梯度一致连续的条件下证明了算法的全局收敛性,数值试验表明新算法是有效的.然后将该算法应用于以下两个方面的研究:(i)在将互补问题转化为无约束优化问题的基础上,应用记忆梯度算法求解之并证明了算法的收敛性和线性收敛速度;(ii)在通过广义D-gap函数将半定互补问题转化为无约束优化问题的基础上,应用记忆梯度算法求解之并证明了算法的收敛性.进一步,增加记忆项的项数,将记忆梯度算法推广到三项记忆梯度算法,在算法的步长选取上提出了一种新的非单调线搜索技巧,该线搜索在每一迭代步内得到较大的步长,有利于算法的快速收敛,在目标函数的梯度一致连续的条件下证明了算法的全局收敛性,并在一定条件下讨论了算法线性收敛速度.最后,应用三项记忆梯度算法求解信赖域子问题,该方法保证试探步的充分下降性,并结合线搜索技巧,即在试探步不成功时,不重解信赖域子问题,而采用非精确Armijo线搜索获得下一迭代点,从而减少了计算量.在此基础上,提出了一种带线搜索的信赖域算法,在一定的条件下证明了算法的全局收敛性.数值试验表明新算法是有效的.
A new assumption is given on the scalar of conjugate gradient method to ensure that the direction is a sufficient descent direction. A new class of memory gradient method for unconstrained optimization is presented and global convergence properties of the new algorithm are discussed on condition that the gradient of the objective function is uniformly continuous. Numerical results show that the new algorithm is efficient. And then the algorithm is applied to the following aspects: (i) Based on a reformulation of the complementarity problem as unconstrained optimization, the memory gradient method is used for solving the complementarity problem. The global convergence and the linear convergence of the new algorithm are shown. Numerical results show that the new algorithm is efficient. (ii) Based on a reformulation of the semi-definite complementarity problem as unconstrained optimization by the generalized D-gap merit function, the memory gradient algorithm is used for solving the semi-definite complementarity problem, which is proved globally convergent. Furthermore, by adding the numbers of memory term, the memory gradient algorithm is generalized to the three-term memory gradient method. On choosing the step size of the algorithm, a new non-monotone line-search rule is proposed which can get a larger step size at each iteration and be benefit to the fast convergence of the algorithm. The global convergence property of the new algorithm is discussed on condition that the gradient of the objective function is uniformly continuous and the linear convergence is also discussed under certain conditions. Numerical results show that the new algorithm is efficient. Finally, the new three-term memory gradient method is used to solve the trust region sub-problem, which ensures the trial step is sufficient descent. A new algorithm for unconstrained optimization that employs both trust region and line-search is proposed, and the algorithm does not resolve the sub-problem if the trial step results in an increase in the objective function, but performs a new inexact Armijo line search to obtain the next iteration point. The convergence property of the algorithm is proved under certain conditions. Numerical results show that the new algorithm is efficient.
A new assumption is given on the scalar of conjugate gradient method to ensure that the direction is a sufficient descent direction. A new class of memory gradient method for unconstrained optimization is presented and global convergence properties of the new algorithm are discussed on condition that the gradient of the objective function is uniformly continuous. Numerical results show that the new algorithm is efficient. And then the algorithm is applied to the following aspects: (i) Based on a reformulation of the complementarity problem as unconstrained optimization, the memory gradient method is used for solving the complementarity problem. The global convergence and the linear convergence of the new algorithm are shown. Numerical results show that the new algorithm is efficient. (ii) Based on a reformulation of the semi-definite complementarity problem as unconstrained optimization by the generalized D-gap merit function, the memory gradient algorithm is used for solving the semi-definite complementarity problem, which is proved globally convergent. Furthermore, by adding the numbers of memory term, the memory gradient algorithm is generalized to the three-term memory gradient method. On choosing the step size of the algorithm, a new non-monotone line-search rule is proposed which can get a larger step size at each iteration and be benefit to the fast convergence of the algorithm. The global convergence property of the new algorithm is discussed on condition that the gradient of the objective function is uniformly continuous and the linear convergence is also discussed under certain conditions. Numerical results show that the new algorithm is efficient. Finally, the new three-term memory gradient method is used to solve the trust region sub-problem, which ensures the trial step is sufficient descent. A new algorithm for unconstrained optimization that employs both trust region and line-search is proposed, and the algorithm does not resolve the sub-problem if the trial step results in an increase in the objective function, but performs a new inexact Armijo line search to obtain the next iteration point. The convergence property of the algorithm is proved under certain conditions. Numerical results show that the new algorithm is efficient.
引文
[1] Miele, A., Cantrell, J. W. Memory gradient method for the minimization of functions [J]. Journal of Optimization Theory and Application , 1969; 3: 459-470
[2] Wolfe, M.A.A quasi-Newton method with memory for unconstrained function minimization[J]. J.Inst.Maths Applics, 1975;15: 85-94
[3] Wolfe, M.A., Viazminsky, C. Super-memory descent methods for unconstrained function minimization [J]. Journal of Optimization Theory and Application, 1976; 18: 455-468
[4] Cragg, E.E., Levy,A.V.. Study on a memory gradient method for the minimization of function[J]. Journal of Optimization Theory and Application , 1969; 4(3): 191-205
[5] 赵庆祯. 一个改进的超记忆梯度法的收敛性及其敛速估计[J]. 应用数学学报, 1983; 6(3): 376-385
[6] 胡宗英. 一个改进的记忆梯度法[J].高等学校计算数学学报, 1989; 2: 173-179
[7] 时贞军. 无约束优化的超记忆梯度算法[J].工程数学学报, 2000; 17(2): 99-104
[8] 时贞军. 改进 HS 共轭梯度算法及其全局收敛性[J]. 计算数学, 2001; 23(4): 393- 406
[9] 孙清滢, 刘新海. 结合广义 Armijo 步长搜索的一类新的三项共轭梯度算法及其收敛特征[J]. 计算数学, 2004; 26(1): 25-36
[10] 时贞军, 明清河. 超记忆梯度算法的线性收敛速度[J]. 工程数学学报, 2003; 20(1): 107-110
[11] Beale EML. A derivative of conjugate gradients, in: Lootsma F A, eds. Numerical methods for nonlinear optimization, London, Academic Press, 1972;39-43
[12] Sun Qingying. Global convergence results of a three term memory gradient method with a non-monotone line search technique [J]. Acta Mathematica Scientia, 2005; 25B(1): 170-178
[13] L.Grippo, F.Lampariello, S.Lucidi. A truncated Newton method with nonmonotone line search for unconstrained optimization [J]. Numer. Math., 1991; 59: 779-805
[14] Zhang H.C, William W. Hager. A nonmonotone line search technique and its application to unconstrained optimization [J]. SIAM J.OPTIM, 2004; 14(4): 1043- 1056
[15] Shi Z.J., Shen J.New Inexact Line Search Method for Unconstrained Optimization [J]. Journal of Optimization Theory and Application, 2005; 127(2): 425- 445
[16] Touati-Ahmed, D., and Storey, C. Efficient hybrid conjugate gradient techniques [J]. Journal of Optimization Theory and Applications, 1990; 64(2): 379-397
[17] Dai Y. H. On the nonmonotone line search [J]. Journal of Optimization Theory and Application , 2002;112:315-330
[18] Dai Y.H, Yuan Y.X. Convergence of three terms conjugate gradient methods[J]. Mathematica Numerica Sinica,1999;3:355-362
[19] Kanzow, C. Nonlinear complementarity as unconstrained optimization [J].Journal of Optimization Theory and Application, 1996; 88:139-155
[20] J.M.奥特加, W.C.莱因波尔特. 多元非线性方程组迭代解法[M]. 朱季纳. 北京:科学出版社, 1983: 504-509
[21] Kanzow.C., Pieper.H.. Jacobian smoothing methods for nonlinear complementarity problems[J]. SIAM journal on Optimization, 1999; 9(2):342-373
[22] Harker P.T., Pang J.S. Finite-dimensional variational inequality and nonlinear complementarity problem: A survey of theory, algorithms and application[J]. Mathematical Programming, 1990; 48B:161-220
[23] Ferris,M.C., Pang, J.S. Engineering and economic applications of complementarity problems[J]. SIAM Review, 1997; 39:669-713
[24] P.Tseng. Merit function for semi-definite complementarity problems[J]. Mathematical Programming, 1998; 83:159-185
[25] Peng J.M., Fukushima M. A hybrid Newton method for solving the variational inequality problem via the D-gap function[J]. Mathematical Programming, 1999; 86: 367-386
[26] Yamashita N., Takji., Fukushima M..Unconstrained optimization reformulations of variational inequality problems [J]. Journal of Optimization Theory and Application, 1997; 92: 439-456
[27] Wu J. H., Florian M., Marcotte P.. A general descent framework for the monotone variational inequality problem [J].Mathematical Programming, 1993; 61:281-300
[28] E.H.Zarantonello. Projections on convex sets in Hilbert space and spectral theory, in: E.H.Zarantonello(Ed.),Contributions to Nonlinear Functional Analysis, Academic Press, New York, 1971;237-424
[29] 张立平. 变分不等式和半定互补问题的存在理论和算法[中国科学院数学与系统科学研究院博士学位论文], 中国科学院数学与系统科学研究院, 北京: 2001
[30] 屈彪. 求解互补问题的一种混合方法: [大连理工大学博士学位论文], 大连理工大学, 大连: 2002
[31] J .Nocedal,Y .Yuan, Combining trust region and line search techniques[J]. in Yuan Y .eds Advance in nonlinear programming, 1998;153-176
[32] Steihaug T. The conjugate gradient method and trust region in large-scale optimization [J]. SIAM Journal on Numerical Analysis, 1983; 20(3): 626-637
[33] 姚升保, 施宝昌, 彭叶辉. 一类带线搜索的非单调信赖域算法[J]. 数学杂志, 2003; 23(3): 290-294
[34] Shultz G A, Schnabel R B,Byrd R H. A family of trust-region-base algorithms for unconstrained minimization with strong global convergence properties[J]. SIAM Journal on Numerical Analysis, 1985;22(1):47-67
[35] Yuan Yaxiang. On the truncated conjugate gradient method [J], Mathematical Programming. 2000; (87): 561-571
[36] Steihaug T. The conjugate gradient method and trust regions in lager scale optimization [J ] . SIAM J. Numer. Anal. 1983; 20 :626-637
[37] 后六生, 孙文瑜. 三项预处理共轭梯度法与信赖域子问题[J]. 南京师大学报(自然科学版), 2001; 24(3): 1-6
[38] Tonit Ph. L. A non-monotone trust region algorithm for nonlinear optimization subject to convex constraints[J]. Mathematical Programming.1997; 77: 69-94
[39] Deng N Y, Xiao Y, Zhou F. J. Non-monotone Trust-region Algorithms [J]. Journal of Optimization Theory and Application, 1993; 26: 259-285
[40] 柯小伍, 韩继业. 一类新的信赖域算法的全局收敛性[J]. 应用数学学报, 1995; 18(4): 608-615
[41] 宇振盛. 求解约束优化与半定互补问题的信赖域方法: [大连理工大学博士学位论文], 大连理工大学, 大连: 2004
[42] 袁亚湘, 孙文瑜. 最优化理论与方法[M]. 北京: 科学出版社, 1997
[2] Wolfe, M.A.A quasi-Newton method with memory for unconstrained function minimization[J]. J.Inst.Maths Applics, 1975;15: 85-94
[3] Wolfe, M.A., Viazminsky, C. Super-memory descent methods for unconstrained function minimization [J]. Journal of Optimization Theory and Application, 1976; 18: 455-468
[4] Cragg, E.E., Levy,A.V.. Study on a memory gradient method for the minimization of function[J]. Journal of Optimization Theory and Application , 1969; 4(3): 191-205
[5] 赵庆祯. 一个改进的超记忆梯度法的收敛性及其敛速估计[J]. 应用数学学报, 1983; 6(3): 376-385
[6] 胡宗英. 一个改进的记忆梯度法[J].高等学校计算数学学报, 1989; 2: 173-179
[7] 时贞军. 无约束优化的超记忆梯度算法[J].工程数学学报, 2000; 17(2): 99-104
[8] 时贞军. 改进 HS 共轭梯度算法及其全局收敛性[J]. 计算数学, 2001; 23(4): 393- 406
[9] 孙清滢, 刘新海. 结合广义 Armijo 步长搜索的一类新的三项共轭梯度算法及其收敛特征[J]. 计算数学, 2004; 26(1): 25-36
[10] 时贞军, 明清河. 超记忆梯度算法的线性收敛速度[J]. 工程数学学报, 2003; 20(1): 107-110
[11] Beale EML. A derivative of conjugate gradients, in: Lootsma F A, eds. Numerical methods for nonlinear optimization, London, Academic Press, 1972;39-43
[12] Sun Qingying. Global convergence results of a three term memory gradient method with a non-monotone line search technique [J]. Acta Mathematica Scientia, 2005; 25B(1): 170-178
[13] L.Grippo, F.Lampariello, S.Lucidi. A truncated Newton method with nonmonotone line search for unconstrained optimization [J]. Numer. Math., 1991; 59: 779-805
[14] Zhang H.C, William W. Hager. A nonmonotone line search technique and its application to unconstrained optimization [J]. SIAM J.OPTIM, 2004; 14(4): 1043- 1056
[15] Shi Z.J., Shen J.New Inexact Line Search Method for Unconstrained Optimization [J]. Journal of Optimization Theory and Application, 2005; 127(2): 425- 445
[16] Touati-Ahmed, D., and Storey, C. Efficient hybrid conjugate gradient techniques [J]. Journal of Optimization Theory and Applications, 1990; 64(2): 379-397
[17] Dai Y. H. On the nonmonotone line search [J]. Journal of Optimization Theory and Application , 2002;112:315-330
[18] Dai Y.H, Yuan Y.X. Convergence of three terms conjugate gradient methods[J]. Mathematica Numerica Sinica,1999;3:355-362
[19] Kanzow, C. Nonlinear complementarity as unconstrained optimization [J].Journal of Optimization Theory and Application, 1996; 88:139-155
[20] J.M.奥特加, W.C.莱因波尔特. 多元非线性方程组迭代解法[M]. 朱季纳. 北京:科学出版社, 1983: 504-509
[21] Kanzow.C., Pieper.H.. Jacobian smoothing methods for nonlinear complementarity problems[J]. SIAM journal on Optimization, 1999; 9(2):342-373
[22] Harker P.T., Pang J.S. Finite-dimensional variational inequality and nonlinear complementarity problem: A survey of theory, algorithms and application[J]. Mathematical Programming, 1990; 48B:161-220
[23] Ferris,M.C., Pang, J.S. Engineering and economic applications of complementarity problems[J]. SIAM Review, 1997; 39:669-713
[24] P.Tseng. Merit function for semi-definite complementarity problems[J]. Mathematical Programming, 1998; 83:159-185
[25] Peng J.M., Fukushima M. A hybrid Newton method for solving the variational inequality problem via the D-gap function[J]. Mathematical Programming, 1999; 86: 367-386
[26] Yamashita N., Takji., Fukushima M..Unconstrained optimization reformulations of variational inequality problems [J]. Journal of Optimization Theory and Application, 1997; 92: 439-456
[27] Wu J. H., Florian M., Marcotte P.. A general descent framework for the monotone variational inequality problem [J].Mathematical Programming, 1993; 61:281-300
[28] E.H.Zarantonello. Projections on convex sets in Hilbert space and spectral theory, in: E.H.Zarantonello(Ed.),Contributions to Nonlinear Functional Analysis, Academic Press, New York, 1971;237-424
[29] 张立平. 变分不等式和半定互补问题的存在理论和算法[中国科学院数学与系统科学研究院博士学位论文], 中国科学院数学与系统科学研究院, 北京: 2001
[30] 屈彪. 求解互补问题的一种混合方法: [大连理工大学博士学位论文], 大连理工大学, 大连: 2002
[31] J .Nocedal,Y .Yuan, Combining trust region and line search techniques[J]. in Yuan Y .eds Advance in nonlinear programming, 1998;153-176
[32] Steihaug T. The conjugate gradient method and trust region in large-scale optimization [J]. SIAM Journal on Numerical Analysis, 1983; 20(3): 626-637
[33] 姚升保, 施宝昌, 彭叶辉. 一类带线搜索的非单调信赖域算法[J]. 数学杂志, 2003; 23(3): 290-294
[34] Shultz G A, Schnabel R B,Byrd R H. A family of trust-region-base algorithms for unconstrained minimization with strong global convergence properties[J]. SIAM Journal on Numerical Analysis, 1985;22(1):47-67
[35] Yuan Yaxiang. On the truncated conjugate gradient method [J], Mathematical Programming. 2000; (87): 561-571
[36] Steihaug T. The conjugate gradient method and trust regions in lager scale optimization [J ] . SIAM J. Numer. Anal. 1983; 20 :626-637
[37] 后六生, 孙文瑜. 三项预处理共轭梯度法与信赖域子问题[J]. 南京师大学报(自然科学版), 2001; 24(3): 1-6
[38] Tonit Ph. L. A non-monotone trust region algorithm for nonlinear optimization subject to convex constraints[J]. Mathematical Programming.1997; 77: 69-94
[39] Deng N Y, Xiao Y, Zhou F. J. Non-monotone Trust-region Algorithms [J]. Journal of Optimization Theory and Application, 1993; 26: 259-285
[40] 柯小伍, 韩继业. 一类新的信赖域算法的全局收敛性[J]. 应用数学学报, 1995; 18(4): 608-615
[41] 宇振盛. 求解约束优化与半定互补问题的信赖域方法: [大连理工大学博士学位论文], 大连理工大学, 大连: 2004
[42] 袁亚湘, 孙文瑜. 最优化理论与方法[M]. 北京: 科学出版社, 1997