一个新的MA模型信赖域方法
|
摘要
解一般非线性规划问题的移动渐近线(moving asymptotes,以下简称MA)信赖域方法,是一类最新提出的优化方法,主要用于解工程上经常出现的结构优化问题. MA模型具有严格凸和可分的良好特性,以此建立的算法具有全局收敛性质.本文分析了MA模型和信赖域方法的特点,构造了MA模型信赖域子问题,并利用投影梯度法进行求解,在此基础上提出了一个新的求解非线性规划问题的MA(移动渐近线)模型信赖域方法.对方法中MA模型渐近线参数的选择进行了讨论,给出了方法的全局收敛性证明.文章最后给出了数值实验,验证了此方法的可行性.研究结果表明,本文提出的MA模型信赖域方法可能是一种有效的方法.
论文的第一章简介了最优化方法和MA模型的基本思想.第二章对一些背景知识如非线性规划、信赖域方法和投影梯度法进行了介绍,提出了用投影梯度法求解MA模型的思路.在第三章建立了一个新的MA模型信赖域子问题,并讨论了它的性质.第四章主要考虑解子问题的投影梯度算法及收敛性质,同时给出一个新的解非线性规划问题的MA模型信赖域方法.第五章是MA模型信赖域方法的收敛性分析,第六章是相应的数值实验.
The method of moving asymptotes (MA) with trust region technique is a kind of new optimization method for solving general nonlinear programming problems, especially for structure optimization problem in engineering. The MA model is strict convex and separable, and the algorithm based on this model is globally convergent. In this paper the characters of MA model and the trust region method are analyzed, a subproblem with MA model and trust region technique is presented, and a projected gradient method is used to solve the subproblem. Based on these results we proposed a new trust region method with MA model for solving nonlinear programming problems. We discuss how to design the MA model and its parameters in this method and prove the global convergence of this method. In addition, we carry out some numerical tests for this method. It can be concluded from these results that the trust region method with MA model is efficient.
In Chapter one, basic theories of optimization method and MA model are introduced. The backgrounds of nonlinear programming, trust-region method as well as projected gradient method are illustrated in the following chapter. Then it also gives the general ideas of methods for solving MA model with projected gradient method. In Chapter three, a new projected gradient method for solving MA model is given. It can deal with general nonlinear programming with trust region technique. The important properties of the improved model are analyzed and the algorithm is proposed, too. After that a MA model with trust region technique is obtained and the local convergence is proved in Chapter four, and a new trust region method is proposed for solving nonlinear programming problems. At last in Chapter five the global convergence of this method is proved. In addition, some numerical tests are given, which shows that this method is efficient.
论文的第一章简介了最优化方法和MA模型的基本思想.第二章对一些背景知识如非线性规划、信赖域方法和投影梯度法进行了介绍,提出了用投影梯度法求解MA模型的思路.在第三章建立了一个新的MA模型信赖域子问题,并讨论了它的性质.第四章主要考虑解子问题的投影梯度算法及收敛性质,同时给出一个新的解非线性规划问题的MA模型信赖域方法.第五章是MA模型信赖域方法的收敛性分析,第六章是相应的数值实验.
The method of moving asymptotes (MA) with trust region technique is a kind of new optimization method for solving general nonlinear programming problems, especially for structure optimization problem in engineering. The MA model is strict convex and separable, and the algorithm based on this model is globally convergent. In this paper the characters of MA model and the trust region method are analyzed, a subproblem with MA model and trust region technique is presented, and a projected gradient method is used to solve the subproblem. Based on these results we proposed a new trust region method with MA model for solving nonlinear programming problems. We discuss how to design the MA model and its parameters in this method and prove the global convergence of this method. In addition, we carry out some numerical tests for this method. It can be concluded from these results that the trust region method with MA model is efficient.
In Chapter one, basic theories of optimization method and MA model are introduced. The backgrounds of nonlinear programming, trust-region method as well as projected gradient method are illustrated in the following chapter. Then it also gives the general ideas of methods for solving MA model with projected gradient method. In Chapter three, a new projected gradient method for solving MA model is given. It can deal with general nonlinear programming with trust region technique. The important properties of the improved model are analyzed and the algorithm is proposed, too. After that a MA model with trust region technique is obtained and the local convergence is proved in Chapter four, and a new trust region method is proposed for solving nonlinear programming problems. At last in Chapter five the global convergence of this method is proved. In addition, some numerical tests are given, which shows that this method is efficient.
引文
[1] Svanberg K. The method of moving asymptotes (MMA) with some extension. In: Rozvany, G. I. N. Ed., Optimization of Large Structural Systems, Dordrecht: Kluwer Academic Publishers, 1993, 555-566
[2] Ni Q. A globally convergent method of moving asymptotes with trust region technique. Optimization Methods and Software, 2003, 18: 288-297
[3] Zillober Ch. A globally convergent version of the method of moving asymptotes. Structural Optimization, 1993, 6 : 166-174
[4] 罗晓雁.解非线性规划的 MA 模型信赖域方法.[硕士学位论文],南京:南京航空航天大学,2006
[5] Svanberg K. The method of moving asymptotes-a new method for structural optimization. International Journal for Numerical Methods in Engineering, 1987, 24: 359-373
[6] Schmit A, Farshi B. Some approximation concepts for structural synthesis. AIAA Journal, 1974, 12: 692-699
[7] Feury C, Braibant V. Structural optimization: a new dual method using mixed variables. International Journal for Numerical for Methods in Engineering, 1986, 23(3): 409-430
[8] Powell M J D. Convergence properties of a class of minimization algorithms. In: Mangasarian O L , Meyer R, Robinson S M, eds. Nonlinear Programming 2, New York: Academic Press, 1975, 1-27
[9] Lenvenberg K. A method for the solution of certain nonlinear problems in least squares. Quart Appl Math, 1944, 2: 164-166
[10] Marquardt D W. An algorithm for least-squares estimation of nonlinear inequalities. SIAM J Appl Math, 1963, 11: 431-441
[11] Moré J J. The Levenberg-Marquardt algorithm: implementation and theory. In: Watson G A, ed., Lecture Notes in Mathematics 630: Numerical Analysis, Berlin:Springer-Verlag, 1978, 105-116
[12] 袁亚湘,孙文瑜.最优化理论与方法.北京:科学出版社,1997
[13] Powell M J D. On the global convergence of trust region algorithms for unconstrained minimization. Mathematical Programming, 1984, 29: 297-303
[14] Moré J J, Sorensen D C. Computing a trust region step. SIAM J Sci Stat Comp, 1983, 4: 553
[15] Shultz G A, Schnabel R B, Byrd R H. A family of trust-region-based algorithms for unconstrained minimization with strong global convergence properties. SIAM J Numer Anal, 1985, 22: 47
[16] Li Q, Sun J. A trust region algorithm for minimization of locally Lipschitzian function. Mathematical Programming, 1994, 66: 25-43
[17] Byrd R, Schnabel R B, Shultz G A. A trust region algorithm for nonlinearly constrained optimization. SIAM Journal of Numer Anal, 1987, 24: 1152-1170
[18] Vardi A. A trust region algorithm for equality constrained minimization: convergence properties and implementation. SIAM J Numer Anal, 1985, 22: 575-591
[19] Powell M J D, Yuan Y. A trust region algorithm for equality constrained optimization. Mathematical Programming, 1991, 49: 189-211
[20] Yuan Y. On a subproblem of trust region algorithms for constrained optimization. Mathematical Programming, 1990, 47: 53-63
[21] 袁亚湘.信赖域方法的收敛性.计算数学,1994, 16(3): 333-346
[22] Yuan Y. On the convergence of a new trust region algorithm. Numerische Mathematik, 1995, 70: 515-539
[23] Fletcher R. A model algorithm for composite NDO problem. Mathematical Programming Study, 1982, 17: 67-76
[24] Womersley R S. Local properties of algorithms for minimizing nonsmooth composite functions. Mathematical Programming, 1985, 32: 69-89
[25] Yuan Y. Conditions for convergence of trust region algorithms for nonsmooth optimization. Mathematical Programming, 1985, 31: 220-228
[26] Yuan Y. On the superlinear convergence of a trust region algorithm for nonsmooth optimization. Mathematical Programming, 1985, 31: 269-285
[27] 刘国山. 无约束非光滑信赖域算法及其收敛性. 计算数学,1988,20(2): 113-120
[28] 刘国山,王安心,李龙镇. 一种改进的非光滑无约束问题的信赖域算法. 应用数学学报,1999, 22(3): 337-342.
[29] 陈宝林.最优化理论与算法.北京:清华大学出版社,1989
[30] Zillober Ch. Global convergence of a nonlinear programming method using convex approximations. Numerical Algorithms, 2001, 27 : 256-289
[31] Rockefeller R T. Convex Analysis. Princeton, New Jersey: Princeton University Press, 1972
[32] Eggleston H G. Convexity. Cambridge: Cambridge University Press, 1958
[33] Burke J V. An exact penalization viewpoint of constrained optimization. SIAM J, Control and Opt, 1991, 29: 968-998
[34] 张志勇.精通 MATLAB6. 5 版.北京:北京航空航天大学出版社,2003
[35] 刘宏友, 彭锋. MATLAB 6. x 符号运算及其应用.北京:机械工业出版社,2003
[36] Zhang W H, Fleury C, Duysinx P. A generalized method of moving asymptotes (GMMA)including equality constraints. Structural Optimization, 1996, 12: 143-146
[37] Diaz A R, Mukherjee R. A topology optimization problem in control of structures using modal disparity. Journal of Mechanical Design, 2006, 128: 536-541
[38] Mahey P, Saldanha R R, Coulomb J L. Moving asymptotes and active set strategy for constrained optimization design in magnetostatic problems. International Journal for Numerical Methods in Engineering, 2005, 38: 1021-1030
[39] Svanberg K. The MMA for modeling and solving optimization problems. In: The Third World Congress on Structural and Multidisciplinary Optimization, Buffalo, New York, 1999, 1-6
[40] Bletzinger K U. Extended method of moving asymptotes based on second-order information. Structural Optimization, 1993, 5: 175-183
[2] Ni Q. A globally convergent method of moving asymptotes with trust region technique. Optimization Methods and Software, 2003, 18: 288-297
[3] Zillober Ch. A globally convergent version of the method of moving asymptotes. Structural Optimization, 1993, 6 : 166-174
[4] 罗晓雁.解非线性规划的 MA 模型信赖域方法.[硕士学位论文],南京:南京航空航天大学,2006
[5] Svanberg K. The method of moving asymptotes-a new method for structural optimization. International Journal for Numerical Methods in Engineering, 1987, 24: 359-373
[6] Schmit A, Farshi B. Some approximation concepts for structural synthesis. AIAA Journal, 1974, 12: 692-699
[7] Feury C, Braibant V. Structural optimization: a new dual method using mixed variables. International Journal for Numerical for Methods in Engineering, 1986, 23(3): 409-430
[8] Powell M J D. Convergence properties of a class of minimization algorithms. In: Mangasarian O L , Meyer R, Robinson S M, eds. Nonlinear Programming 2, New York: Academic Press, 1975, 1-27
[9] Lenvenberg K. A method for the solution of certain nonlinear problems in least squares. Quart Appl Math, 1944, 2: 164-166
[10] Marquardt D W. An algorithm for least-squares estimation of nonlinear inequalities. SIAM J Appl Math, 1963, 11: 431-441
[11] Moré J J. The Levenberg-Marquardt algorithm: implementation and theory. In: Watson G A, ed., Lecture Notes in Mathematics 630: Numerical Analysis, Berlin:Springer-Verlag, 1978, 105-116
[12] 袁亚湘,孙文瑜.最优化理论与方法.北京:科学出版社,1997
[13] Powell M J D. On the global convergence of trust region algorithms for unconstrained minimization. Mathematical Programming, 1984, 29: 297-303
[14] Moré J J, Sorensen D C. Computing a trust region step. SIAM J Sci Stat Comp, 1983, 4: 553
[15] Shultz G A, Schnabel R B, Byrd R H. A family of trust-region-based algorithms for unconstrained minimization with strong global convergence properties. SIAM J Numer Anal, 1985, 22: 47
[16] Li Q, Sun J. A trust region algorithm for minimization of locally Lipschitzian function. Mathematical Programming, 1994, 66: 25-43
[17] Byrd R, Schnabel R B, Shultz G A. A trust region algorithm for nonlinearly constrained optimization. SIAM Journal of Numer Anal, 1987, 24: 1152-1170
[18] Vardi A. A trust region algorithm for equality constrained minimization: convergence properties and implementation. SIAM J Numer Anal, 1985, 22: 575-591
[19] Powell M J D, Yuan Y. A trust region algorithm for equality constrained optimization. Mathematical Programming, 1991, 49: 189-211
[20] Yuan Y. On a subproblem of trust region algorithms for constrained optimization. Mathematical Programming, 1990, 47: 53-63
[21] 袁亚湘.信赖域方法的收敛性.计算数学,1994, 16(3): 333-346
[22] Yuan Y. On the convergence of a new trust region algorithm. Numerische Mathematik, 1995, 70: 515-539
[23] Fletcher R. A model algorithm for composite NDO problem. Mathematical Programming Study, 1982, 17: 67-76
[24] Womersley R S. Local properties of algorithms for minimizing nonsmooth composite functions. Mathematical Programming, 1985, 32: 69-89
[25] Yuan Y. Conditions for convergence of trust region algorithms for nonsmooth optimization. Mathematical Programming, 1985, 31: 220-228
[26] Yuan Y. On the superlinear convergence of a trust region algorithm for nonsmooth optimization. Mathematical Programming, 1985, 31: 269-285
[27] 刘国山. 无约束非光滑信赖域算法及其收敛性. 计算数学,1988,20(2): 113-120
[28] 刘国山,王安心,李龙镇. 一种改进的非光滑无约束问题的信赖域算法. 应用数学学报,1999, 22(3): 337-342.
[29] 陈宝林.最优化理论与算法.北京:清华大学出版社,1989
[30] Zillober Ch. Global convergence of a nonlinear programming method using convex approximations. Numerical Algorithms, 2001, 27 : 256-289
[31] Rockefeller R T. Convex Analysis. Princeton, New Jersey: Princeton University Press, 1972
[32] Eggleston H G. Convexity. Cambridge: Cambridge University Press, 1958
[33] Burke J V. An exact penalization viewpoint of constrained optimization. SIAM J, Control and Opt, 1991, 29: 968-998
[34] 张志勇.精通 MATLAB6. 5 版.北京:北京航空航天大学出版社,2003
[35] 刘宏友, 彭锋. MATLAB 6. x 符号运算及其应用.北京:机械工业出版社,2003
[36] Zhang W H, Fleury C, Duysinx P. A generalized method of moving asymptotes (GMMA)including equality constraints. Structural Optimization, 1996, 12: 143-146
[37] Diaz A R, Mukherjee R. A topology optimization problem in control of structures using modal disparity. Journal of Mechanical Design, 2006, 128: 536-541
[38] Mahey P, Saldanha R R, Coulomb J L. Moving asymptotes and active set strategy for constrained optimization design in magnetostatic problems. International Journal for Numerical Methods in Engineering, 2005, 38: 1021-1030
[39] Svanberg K. The MMA for modeling and solving optimization problems. In: The Third World Congress on Structural and Multidisciplinary Optimization, Buffalo, New York, 1999, 1-6
[40] Bletzinger K U. Extended method of moving asymptotes based on second-order information. Structural Optimization, 1993, 5: 175-183