求解等式约束优化问题的基于拟牛顿校正的既约Hessian SQP方法
|
摘要
本文研究用既约Hessian SQP方法求解等式约束问题.与一般SQP方法相比,既约Hessian SQP方法能节省大量的存储空间.因此,这类方法能有效地求解较大规模的等式约束问题.然而已有的这类方法的全局收敛性分析需请求较强的条件,如假定Lagrange函数的既约Hessian矩阵序列的一致正定性,而这种假定通常很难被满足.因此,在没有上述假定的情况下研究用既约Hessian方法求解约束问题具有重要的理论与实际意义.
本文提出了既约Hessian SQP方法的两种修正.在第一章中,我们介绍了非线性规划的基本理论,包括BFGS校正技术,然后给出了既约Hessian SQP方法的基本结构.在第二章我们首先推广了求解无约束问题的MBFGS校正技术,并将其应用到求解等式约束优化问题中,提出了一个修正的既约Hessian SQP方法,并且在较弱的条件下建立了全局收敛性结果.分析表明该方法同时具有局部R-线性收敛性和2-步超线性收敛速度.我们在第三章研究了结合MBFGS与CBFGS两种方法的修正既约Hessian SQP方法,提出带混合校正技术的既约Hessian SQP方法,这种方法与第二章的方法具有相同的收敛性及优点.在第四章我们针对第二章,第三章所提出的算法进行了数值实验,数值结果表明本文所提出的算法是有效的.数值实验结果的比较表明第三章中的算法在各个方面均比第二章中的算法要更为有效.
In this thesis, we are concerned with equality constrained optimization prob-lems. It is well-known that the sequential quadratic programming(SQP) methodsare welcome for small and middle size problem. For large scale problem, how-ever, SQP method may not e?cient as even not over all. The reduced HessianSQP method can be applied to solve large scale problem due to its requirementof less space for storage. Existing reduced Hessian SQP methods are practicallye?cient. However, the conditions for a reduced Hessian SQP method are rigorous.In general the uniform positive definition of the reduced Hessian approximate isnecessary.
In this thesis, basing on an MBFGS update for unconstrained optimization,we propose a way to construct quasi-Newton update for the reduced Hessian ap-proximating. In Chapter One, we introduce some well known iteration methodsincluding BFGS method. We then introduce the basis steps of the reduced HessianSQP method. In Chapter Two, we first introduce the MBFGS formula and thenapply it to the equality constrained problems. Under mild conditions, we prove theglobal convergence of the related reduced Hessian SQP method. We also obtainthe R-linear and two step super linear convergence of the proposed method. InChapter Three, by combining the MBFGS and CBFGS update formula, we pro-pose another update formula for the reduced Hessian approximation. The relatemethod retains the same convergence property as the method in Chapter Two.In Chapter Four, we also do some numerical experiments, the results show thee?ciency of the proposed methods.
本文提出了既约Hessian SQP方法的两种修正.在第一章中,我们介绍了非线性规划的基本理论,包括BFGS校正技术,然后给出了既约Hessian SQP方法的基本结构.在第二章我们首先推广了求解无约束问题的MBFGS校正技术,并将其应用到求解等式约束优化问题中,提出了一个修正的既约Hessian SQP方法,并且在较弱的条件下建立了全局收敛性结果.分析表明该方法同时具有局部R-线性收敛性和2-步超线性收敛速度.我们在第三章研究了结合MBFGS与CBFGS两种方法的修正既约Hessian SQP方法,提出带混合校正技术的既约Hessian SQP方法,这种方法与第二章的方法具有相同的收敛性及优点.在第四章我们针对第二章,第三章所提出的算法进行了数值实验,数值结果表明本文所提出的算法是有效的.数值实验结果的比较表明第三章中的算法在各个方面均比第二章中的算法要更为有效.
In this thesis, we are concerned with equality constrained optimization prob-lems. It is well-known that the sequential quadratic programming(SQP) methodsare welcome for small and middle size problem. For large scale problem, how-ever, SQP method may not e?cient as even not over all. The reduced HessianSQP method can be applied to solve large scale problem due to its requirementof less space for storage. Existing reduced Hessian SQP methods are practicallye?cient. However, the conditions for a reduced Hessian SQP method are rigorous.In general the uniform positive definition of the reduced Hessian approximate isnecessary.
In this thesis, basing on an MBFGS update for unconstrained optimization,we propose a way to construct quasi-Newton update for the reduced Hessian ap-proximating. In Chapter One, we introduce some well known iteration methodsincluding BFGS method. We then introduce the basis steps of the reduced HessianSQP method. In Chapter Two, we first introduce the MBFGS formula and thenapply it to the equality constrained problems. Under mild conditions, we prove theglobal convergence of the related reduced Hessian SQP method. We also obtainthe R-linear and two step super linear convergence of the proposed method. InChapter Three, by combining the MBFGS and CBFGS update formula, we pro-pose another update formula for the reduced Hessian approximation. The relatemethod retains the same convergence property as the method in Chapter Two.In Chapter Four, we also do some numerical experiments, the results show thee?ciency of the proposed methods.
引文
[1] Broyden C G. The Convergence of a Class of Double-Rank Minimization Algo-rithms. Journal of Institute of Mathematics and Applications, 1970, 6: 76-90
[2] Fletcher R. A New Apporach to Variable Metric Algorithms. Computer Journal,1970, 13: 17-32
[3] Goldfarb D. A Family of Variable Metric Methods Derived by Variational Means.Mathematics of Computation, 1970, 24: 23-26
[4] Shanno D F. Conditioning of Quasi-Newton Methods for Function Minimization.Mathematics of Computation, 1970, 2: 647-656
[5] Byrd R H, Nocedal J. A Tool for the Analysis of Quasi-Newton Methods withApplication to Unconstrained Minization. SIAM Journal Numerical Analysis, 1989,26: 727-739
[6] Amiri N M. An Exact Penalty Method with Reduced Hessian Update for SolvingConstrained Optimization Problems. Journal Science Technol, 1994, 31: 1-14
[7] Coleman T F, Conn A R. A Note on the Compution of an Orthonormal Basis forthe Null Space of a Matrix. Mathematical Programming, 1984, 29: 234-242
[8] Li D H, Fukushima M. On the Global Convergence of the BFGS Method for Non-convex Unconstrained Optimization Problems. SIAM Journal Optimazation, 2001,11: 1054-1064
[9] Liu T W, Li D H. A Cautious BFGS Update for Reduced Hessian SQP. NumericalAlgorithms, 2007, 44: 11-28
[10] Liu T W, Li D H. A Pratical Update Criterion for SQP Method. OptimizationMethods and Software, 2007, 2: 253-266
[11] Gabay D. Reduced Quasi-Newton Methods with Feasibility Improvement for Non-linear Constrained Optimization. Mathmatics Program Study, 1982, 16: 441-467
[12] Nocedal J, Overton M L. Projected Hessian Updating Algorithms for NonlinearlyConstrained Optimization. SIAM Journal on Numerical Analysis, 1985, 22: 821-850
[13] Coleman T F, Cinn A R. On the Local Convergence of Quasi-Newton Method forthe Nonlinear Programming Problem. SIAM Journal on Numerical Analysis, 1984,21: 755-769
[14] Byrd R H, Nocedal J. An Analysis of Reduced Hessian Methods for ConstrainedOptimization. Mathematical Programming, 1991, 49: 285-323
[15] Xie Y F, Byrd R H. Practical Update Criteria for Reduced Hessian SQP: Globalanalysis. SIAM Journal on Optimization, 1999, 9: 578-604
[16] Byrd R H, Nocedal J, Yuan Y X. Gloabl Convergence of a Class of Quai-NewtonMethods on Convex Problems. SIAM Journal on Numerical Analysis, 1987, 24:1171-1190
[17] Powel M J D. On the Convergence of the Variable Metric Algorithm. Journal of theInstitute of Mathematics and its Appilcations, 1971, 7: 21-36
[18] Boggs P T, Tolle J W, Wang P. On the Local Convergence of Quasi-Newton Methodfor Constrained Optimization. SIAM Journal Control and Optimazation, 1982, 20:161-171
[19] Boggs P T, Tolle J W. A Strategy for Global Convergence in a Seouential QuadraticProgramming Algorithm. SIAM Journal Numerical Analysis, 1989, 26: 600-623
[20] Powell M J D, Yuan Y. A Recursive Quadratic Programming Algorithm that UsesDi?erentiable Exact Penalty Function. Mathematical Programming, 1986, 35: 265-278
[21] Schluz V. Solving Discretized Optimization Problems Partialy Reduced SQP Meth-ods. Computing and Visualisation in Science, 1998, 1: 283-296
[22] 朱红兰. 具有超线性收敛性质的一类广义拟牛顿算法: [南京航空航天大学硕士学位论文]. 南京: 南京航空航天大学, 2005, 10-15
[23] Han S P. A Global Convergent Method for Nonlinear Programming. Journal ofOptimization Theory and Applications, 1977, 22: 297-309
[24] Li D H. On the Global Convergence Properties of DFP Method. Journal of HunanUniversity (Natural Sciences), 1993, 20: 16-20
[25] Li D H, Fukushima M. A Modified BFGS Method and its Global Convergencein Nonconvex Minimization. Journal of Computational and Applied Mathematics,2001, 129: 15-35
[26] Dennis J E, More J J. Quasi-Newton Methods Motivation and Theory. SIAM Re-view, 1977, 19: 46-89
[27] 李董辉, 童小娇, 万中. 数值最优化. 北京: 科学出版社, 2005, 66-70
[28] Nocedal J, Overton M L. Projected Hessian Updating Algorithms for NonlinearlyConstrained Optimization. SIAM Journal on Numerical Analysis, 1985, 22: 821-850
[29] Powel M J D. Quadratic Termination Properties of Minimization Algorithm, PartI and Part II. Journal of the Institute of Mathematics and its Appilcations, 1972,10: 333-357
[30] Powel M J D. On the Convergence of the DEP Algorithm for Unconstrained Opti-mization when there are only two Variables. Mathematical Programming, Series B,2000, 87: 281-301
[31] Yuan Y X. A Modified BFGS Algorithm for Unconstrained Optimization. IMAJournal of Numerical Analysis, 1991, 11: 325-332
[32] Dai Y H. Convergence Properties of the BFGS Algorithm. SIAM Journalon Opti-mization, 2002, 13: 693-701
[33] Mascarenhas W F. The BFGS Method with Exact Line Searches Fails for Non-convex Objective Functions. Mathematical Programming, Series A, 2004, 99: 49-61
[34] Wei Z X, Yu G H, Yuan G L, etal. The Superlinear Convergence of a Modified BFGSType Method for Unconstrained Optimization. Journal Computional Optimizationand Appilcations, 2004, 29: 315-332
[35] Li D H, Fukushima M. A Globally and Superlinearly Convergent Gauss-Newtonbased BFGS Method for Symmetric Ninlinear Equations. SIAM Journal on Numer-ical Analysis, 1999, 37: 152-172
[36] Powel M J D, Yuan Y X. A Recursive Quadratic Programming Algorithm thatUses Diferentiable Exact Penalty Functions. Mathematical Programming, 1986, 35:265-278
[37] Bel N M. Global Convergence of a Semi-Infinite Programming Method. AppliedMathematics and Optimization, 1990, 21: 69-88
[38] Wei Z, Qi L, Chen X. An SQP-type Method and its Application in StochasticProgramming. Journal of Optimization Theory and Appilcations, 2003, 116: 205-228
[39] 刘陶文. BFGS方法及其在求解约束优化问题中的应用: [湖南大学博士学位论文]. 湖南: 湖南大学数学与计量经济学院, 2006, 1-20
[40] 伍兴国. 一类大规模最优化问题的并行BFGS算法: [湖南大学硕士学位论文].湖南: 湖南大学数学与计量经济学院, 2006, 1-4
[41] Fletcher R. Stable Reduced Hessian Updates for Indefinite Quadratic Programming.Methematical Programming, 2000, 87: 251-264
[42] Gill P E, Leonard M W. Reduced-Hessian Quasi-Newton Methods for Uncon-strained Optimization. SIAM Journal on Optimization, 2001, 12: 209-237
[43] Fontecilla R. Local Convergence of Secant Methods for Nonlinear Constrained Op-timization. SIAM Journal Numerical Analysis, 1988, 25: 692-712
[44] Jiang Li. On Global Convergence of the MBFGS Method in Equality ConstrainedOptimization. Journal of Hunan Agricultural University(Natural Sciences), 2006,32(3): 324-326
[45] Hock W, Schittkowski K. Test Examples for Nonlinear Programming Codes.Springer-Verlag, Berlin Heidelberg New York, 1981, 1-56
[2] Fletcher R. A New Apporach to Variable Metric Algorithms. Computer Journal,1970, 13: 17-32
[3] Goldfarb D. A Family of Variable Metric Methods Derived by Variational Means.Mathematics of Computation, 1970, 24: 23-26
[4] Shanno D F. Conditioning of Quasi-Newton Methods for Function Minimization.Mathematics of Computation, 1970, 2: 647-656
[5] Byrd R H, Nocedal J. A Tool for the Analysis of Quasi-Newton Methods withApplication to Unconstrained Minization. SIAM Journal Numerical Analysis, 1989,26: 727-739
[6] Amiri N M. An Exact Penalty Method with Reduced Hessian Update for SolvingConstrained Optimization Problems. Journal Science Technol, 1994, 31: 1-14
[7] Coleman T F, Conn A R. A Note on the Compution of an Orthonormal Basis forthe Null Space of a Matrix. Mathematical Programming, 1984, 29: 234-242
[8] Li D H, Fukushima M. On the Global Convergence of the BFGS Method for Non-convex Unconstrained Optimization Problems. SIAM Journal Optimazation, 2001,11: 1054-1064
[9] Liu T W, Li D H. A Cautious BFGS Update for Reduced Hessian SQP. NumericalAlgorithms, 2007, 44: 11-28
[10] Liu T W, Li D H. A Pratical Update Criterion for SQP Method. OptimizationMethods and Software, 2007, 2: 253-266
[11] Gabay D. Reduced Quasi-Newton Methods with Feasibility Improvement for Non-linear Constrained Optimization. Mathmatics Program Study, 1982, 16: 441-467
[12] Nocedal J, Overton M L. Projected Hessian Updating Algorithms for NonlinearlyConstrained Optimization. SIAM Journal on Numerical Analysis, 1985, 22: 821-850
[13] Coleman T F, Cinn A R. On the Local Convergence of Quasi-Newton Method forthe Nonlinear Programming Problem. SIAM Journal on Numerical Analysis, 1984,21: 755-769
[14] Byrd R H, Nocedal J. An Analysis of Reduced Hessian Methods for ConstrainedOptimization. Mathematical Programming, 1991, 49: 285-323
[15] Xie Y F, Byrd R H. Practical Update Criteria for Reduced Hessian SQP: Globalanalysis. SIAM Journal on Optimization, 1999, 9: 578-604
[16] Byrd R H, Nocedal J, Yuan Y X. Gloabl Convergence of a Class of Quai-NewtonMethods on Convex Problems. SIAM Journal on Numerical Analysis, 1987, 24:1171-1190
[17] Powel M J D. On the Convergence of the Variable Metric Algorithm. Journal of theInstitute of Mathematics and its Appilcations, 1971, 7: 21-36
[18] Boggs P T, Tolle J W, Wang P. On the Local Convergence of Quasi-Newton Methodfor Constrained Optimization. SIAM Journal Control and Optimazation, 1982, 20:161-171
[19] Boggs P T, Tolle J W. A Strategy for Global Convergence in a Seouential QuadraticProgramming Algorithm. SIAM Journal Numerical Analysis, 1989, 26: 600-623
[20] Powell M J D, Yuan Y. A Recursive Quadratic Programming Algorithm that UsesDi?erentiable Exact Penalty Function. Mathematical Programming, 1986, 35: 265-278
[21] Schluz V. Solving Discretized Optimization Problems Partialy Reduced SQP Meth-ods. Computing and Visualisation in Science, 1998, 1: 283-296
[22] 朱红兰. 具有超线性收敛性质的一类广义拟牛顿算法: [南京航空航天大学硕士学位论文]. 南京: 南京航空航天大学, 2005, 10-15
[23] Han S P. A Global Convergent Method for Nonlinear Programming. Journal ofOptimization Theory and Applications, 1977, 22: 297-309
[24] Li D H. On the Global Convergence Properties of DFP Method. Journal of HunanUniversity (Natural Sciences), 1993, 20: 16-20
[25] Li D H, Fukushima M. A Modified BFGS Method and its Global Convergencein Nonconvex Minimization. Journal of Computational and Applied Mathematics,2001, 129: 15-35
[26] Dennis J E, More J J. Quasi-Newton Methods Motivation and Theory. SIAM Re-view, 1977, 19: 46-89
[27] 李董辉, 童小娇, 万中. 数值最优化. 北京: 科学出版社, 2005, 66-70
[28] Nocedal J, Overton M L. Projected Hessian Updating Algorithms for NonlinearlyConstrained Optimization. SIAM Journal on Numerical Analysis, 1985, 22: 821-850
[29] Powel M J D. Quadratic Termination Properties of Minimization Algorithm, PartI and Part II. Journal of the Institute of Mathematics and its Appilcations, 1972,10: 333-357
[30] Powel M J D. On the Convergence of the DEP Algorithm for Unconstrained Opti-mization when there are only two Variables. Mathematical Programming, Series B,2000, 87: 281-301
[31] Yuan Y X. A Modified BFGS Algorithm for Unconstrained Optimization. IMAJournal of Numerical Analysis, 1991, 11: 325-332
[32] Dai Y H. Convergence Properties of the BFGS Algorithm. SIAM Journalon Opti-mization, 2002, 13: 693-701
[33] Mascarenhas W F. The BFGS Method with Exact Line Searches Fails for Non-convex Objective Functions. Mathematical Programming, Series A, 2004, 99: 49-61
[34] Wei Z X, Yu G H, Yuan G L, etal. The Superlinear Convergence of a Modified BFGSType Method for Unconstrained Optimization. Journal Computional Optimizationand Appilcations, 2004, 29: 315-332
[35] Li D H, Fukushima M. A Globally and Superlinearly Convergent Gauss-Newtonbased BFGS Method for Symmetric Ninlinear Equations. SIAM Journal on Numer-ical Analysis, 1999, 37: 152-172
[36] Powel M J D, Yuan Y X. A Recursive Quadratic Programming Algorithm thatUses Diferentiable Exact Penalty Functions. Mathematical Programming, 1986, 35:265-278
[37] Bel N M. Global Convergence of a Semi-Infinite Programming Method. AppliedMathematics and Optimization, 1990, 21: 69-88
[38] Wei Z, Qi L, Chen X. An SQP-type Method and its Application in StochasticProgramming. Journal of Optimization Theory and Appilcations, 2003, 116: 205-228
[39] 刘陶文. BFGS方法及其在求解约束优化问题中的应用: [湖南大学博士学位论文]. 湖南: 湖南大学数学与计量经济学院, 2006, 1-20
[40] 伍兴国. 一类大规模最优化问题的并行BFGS算法: [湖南大学硕士学位论文].湖南: 湖南大学数学与计量经济学院, 2006, 1-4
[41] Fletcher R. Stable Reduced Hessian Updates for Indefinite Quadratic Programming.Methematical Programming, 2000, 87: 251-264
[42] Gill P E, Leonard M W. Reduced-Hessian Quasi-Newton Methods for Uncon-strained Optimization. SIAM Journal on Optimization, 2001, 12: 209-237
[43] Fontecilla R. Local Convergence of Secant Methods for Nonlinear Constrained Op-timization. SIAM Journal Numerical Analysis, 1988, 25: 692-712
[44] Jiang Li. On Global Convergence of the MBFGS Method in Equality ConstrainedOptimization. Journal of Hunan Agricultural University(Natural Sciences), 2006,32(3): 324-326
[45] Hock W, Schittkowski K. Test Examples for Nonlinear Programming Codes.Springer-Verlag, Berlin Heidelberg New York, 1981, 1-56