节点文献
BFGS方法及其在求解约束优化问题中的应用
BFGS Method and Its Applications in Solving Constrained Optimization Problems
【作者】 刘陶文;
【作者基本信息】 湖南大学 , 应用数学, 2006, 博士
【摘要】 本文研究求解无约束非凸问题的BFGS方法以及求解非线性约束问题的序列二次规划(SQP)方法,既约Hessian SQP方法,序列二次约束二次规划(SQCQP)方法.我们首先在第1章简单介绍将要研究的问题的背景和已有结果.在第2章,我们研究BFGS方法在求解无约束非凸问题时的收敛问题.众所周知,BFGS方法是求解无约束优化问题的拟牛顿法中最有效的方法之一,它具有很好的数值效果及快速的收敛性,然而采用精确线性搜索或非精确的Wolfe型线性搜索或Armijo线性搜索的BFGS方法在求解非凸函数的极小化问题时并不一定全局收敛.本文通过在拟牛顿方程中使用扰动策略提出了一种扰动BFGS方法.我们证明采用Wolfe型非精确线性搜索扰动BFGS方法求解非凸函数的极小化问题具有全局收敛性并且具有局部超线性收敛速度,而且保持BFGS方法的仿射不变性.我们的数值实验表明扰动BFGS方法比BFGS方法及修正BFGS方法具有更好的数值效果.BFGS方法中的校正公式经常被其它优化方法所使用并被用来求解非线性方程组,约束优化问题,随机规划问题以及半无限规划问题等。我们在第3-5章里研究通过BFGS校正公式分别与SQP方法,既约Hessian SQP方法,SQCQP方法等的结合来求解一般的约束优化问题.在第3章,我们研究SQP方法在较弱条件下的收敛问题.已有的关于SQP算法的全局收敛性研究结果通常要求拟牛顿矩阵序列一致正定和有界,然而是否存在满足该条件的拟牛顿法尚不清楚.利用扰动技术与BFGS校正技术的有效结合,我们提出了一种扰动SQP方法,并证明所提出的扰动SQP方法在较弱的约束品性下保持全局收敛性,特别地,全局收敛性不要求拟牛顿矩阵的一致正定性和有界性.此外,我们也研究了没有使用扰动技术的SQP方法的全局收敛问题,提出了确保SQP方法收敛的若干策略,其中包括一个新的拟牛顿矩阵校正公式和一个关于罚参数的有效校正准则.数值实验表明这些策略的使用使SQP方法具有更好的数值效果.SQP方法通常被用来求解中小规模的约束问题,因此,我们在第4章研究求解较大规模问题的既约Hessian SQP方法.已有的既约Hessian SQP方法通常只能求解等式约束问题,而且它们的全局收敛分析要求约束函数的梯度向量是线性无关的以及拉格朗日函数的既约Hessian矩阵序列是一致正定的.使用前一条件的主要原因在于已有的拟牛顿校正公式只能产生具有固定阶的拟牛顿矩阵序列,而同时这种校正公式对既约Hessian SQP方法的全局收敛性起着重要的作用.因此,我们提出了一个产生的拟牛顿矩阵的阶可变化的校正公式,然后在此基础上,我们提出了求解一般等式约束问题(可以是退化问题)的修正既约Hessian SQp方法,并且在没有假定上述两个条件的情形下,我们证明修正既约Hessian SQP方法是全局收敛的.而且将这种方法推广然后用来求解不等式约束问题并获得了全局收敛性结果,该方法的优点是可以求解既有等式约束又有不等式约束的较大规模问题,有效克服了已有的这类方法在求解含不等式约束问题时所遇到的困难与限制.在第5章,我们研究求解不等式约束问题的序列二次约束二次规划(SQCQP)方法.众所周知,传统的SQP方法通常会产生Maratos效应,阻碍了算法的快速收敛性.近年来,许多学者提出了使用约束函数的一阶和二阶信息的SQCQP方法,这类方法能有效地避免Maratos效应因而具有较快的收敛速度.然而已提出的SQCQP方法存在某些局限性,要么算法的全局收敛性条件太强,要么算法的全局收敛性没有保证,要么只能求解凸规划问题或约束函数是凸函数的问题.利用扰动技术或BFGS校正技术,我们提出两个求解一般不等约束问题的SQCQP方法,并证明它们在较弱的条件下仍然全局收敛,而且具有至少超线性收敛速度.在第6章,我们针对前面各章提出的算法进行数值实验,数值结果表明所提出的算法比已有的同类算法更有效,有效地支持了本文的算法.
【Abstract】 This thesis is concerned with the BFGS method for unconstrained optimization and its applications to sequential quadratic programming (SQP) method, reduced Hessian SQP method and sequential quadratically constrained quadratic programming (SQCQP) method for constrained optimization.We first introduce the previous works on the thesis in Chapter 1. In Chapter 2, we study the convergence properties of BFGS method for solving nonconvex unconstrained problems. It is well-known that the BFGS method is one of the most famous quasi-Newton algorithms for solving unconstrained optimization problems because of its favorable numerical experiment and fast convergence property. However, The BFGS method with exact line search or Wolfe-type inexact line search or Armijo inexact line search need not converge for solving nonconvex minimization problem. In this chapter, we introduce a perturbation strategy in BFGS method to develop a perturbed BFGS method. We prove that under mild condition, the perturbed BFGS method with Wolfe line search is convergent globally and superlinearly even if the objective function is nonconvex. Moreover, the proposed method maintains the affine invariance of the BFGS method and enjoys more favorable numerical experiment results than the BFGS method and the modified BFGS methods.The BFGS update technique is usually used by other methods for solving some related prblems such as nonlinear equations, constrained optimization problems, stochastic programming and semi-infinite programming. In next three chapters, we mainly analyze SQP method, reduced Hessian SQP method, SQCQP metod for solving constrained optimization problems by employing BFGS update technique.In Chapter 3, we study the convergenc properties of SQP methods under mild conditions. The global convergence of the existed SQP methods usually requires that the quasi-Newton matrices are uniformly positive definite and bounded. However, it is unknown whether there exists the qusi-Newton method satisfying the above conditions. By employing BFGS update technique, we propose a perturbed SQP method for solving general constrained problems. We prove that the proposed method converges globally under mild condition. In particular, the global convergence does not require the uniformly positive definiteness and the boundedness of the quasi-Newton matrices, while existed SQP methos usually require these conditions. Besides, we propose some strategies for global convergence in SQP methods. Numerical results show that the proposed strategies are practically efficient.SQP methods are usually used to solve small and medium-scale problems. In Chapter 4, we study reduced Hessian SQP methods for sloving large-scale optimization problems. The existed reduced Hessian methods slove only equality constrained problems and their global convergence require the linear independence and the uniformly positive definiteness of the reduced Hessian of Lagrangian function. The reason using the requirement of linear independence is that the existed quasi-Newton update formulas generate only quasi-Newton matrices with fixed order. On the other hand, the update formulas play important roles in analyzing the global convergence of reduced Hessian SQP methods. We propose a new quasi-Newton update formula which can generate quasi-Newton matrices with variable order, and then propose a reduced Hessian method for solving general equality constrained problems (including degnerate problems) and prove that the proposed method globally converges without above two requirements. Moreover, by using the proposed update formula, we extends the reduced Hessian method to solve constrained problems with inequality constraints.In Chapter 5, we study the sequential quadratically constrained quadratic programming method for solving inequality constrained problems. It is well-known that traditional SQP methods may occur Maratos effect. Several authors have considered SQCQP-type methods which use information up to second-order for both the constraints and objective function. SQCQP methods are free of the Maratos effect and thus enjoy fast convergence property. However, the existed SQCQP methods solve only some special problems such as convex programming, or problems with convex feasible set or some problems with strong conditions. By employing the perturbed strategy or BFGS update technique we propose two SQCQP methods for general inequality constrained optimization and prove that the proposed SQCQP methods are globally convergent under mild condition and are of superlinear rate of convergence at least.In Chapter 6, we report some numerical results for the proposed methods. The numerical results show that the proposed methods are practically efficient and thus support the proposed methods
【Key words】 BFGS method; nonconvex problem; constrained problem; SQP method; reduced Hessian method; SQCQP method; global convergence;