求解约束最优化问题和对称变分不等式KKT系统的BFGS法

【作者】 张继伟；

【导师】 李董辉； 王仙桃；

【作者基本信息】 湖南大学 ， 基础数学， 2003， 硕士

【摘要】 本文研究求解约束最优化问题和对称变分不等式KKT系统的BFGS算法。首先利用NCP函数将问题的KKT系统转化为等价的非光滑方程组。在此基础上，提出求解该非光滑方程组的BFGS算法。 对约束最优化问题的KKT系统等价的非光滑方程组，在广义Newton法的基础上，利用BFGS修正公式产生的矩阵取代广义Jacobi矩阵。提出一种Gauss-Newton型BFGS算法。并利用非单调线性搜索对算法进行全局化。在较弱的条件下，得到了算法的全局收敛性及其超线性收敛性。此外，还证明了经一定的迭代步后，单位步长总可以取到。因此算法在解的局部还原为用单位步长的BFGS算法。 对对称变分不等式的KKT系统等价的非光滑方程组，我们利用函数的半光滑性质及其广义导数的某种对称性质，得到相应的BFGS法的一个下降方向。在此基础上，我们提出一种单调下降的线性搜索，进而提出求解该非光滑方程组的具有单调下降性的BFGS算法。并证明算法的全局收敛性和超线性收敛性。更多还原

【Abstract】 In this thesis, we consider the BFGS method for solving the constrained optimizatiom problem and the symmetric variational inequality problem. First, we reformulate the KKT systems of the constrained optimization problem and the symmetric variational inequality prpoblem into equivalent nonsrnooth equations by using the so called NCP functions. Based on these reformulations, we propose BFGS methods for solving these nonsmooth equations.For the nonsmooth equation reformulation of the KKT system of the constrained optimization problem, we develop the method on the basis of a generalized Newton method. We use the matrices generated by a modified BFGS formula to replace the generalized Jacobian matrices in the generalized Newton method. By virtue of a non-monotone line search, we propose a Gauss-Newton-based BFGS method for solving the nonsmooth euqation. Under mild conditions, we prove the global and superlinear convergence of the method. Moreover, we prove that after finite iterations, the unit step is always accepted and the proposed method essentially reduces to the modified BGS method with the unit steplength.We also propose a BFGS method for solving the nonsmooth equation reformulation of the KKT system of the symmetric variational inequality problem. We introduce a parameter in the non-monotone line search. By changing the parameter in a suitable way, we get a descent direction of the BFGS method. We then develop a BFGS method for solving the nonsmooth equation. The method possess some descent property. Under mild conditions, we establish the global and superlinear convergence of the proposed method. We also show that the unit steplength is essentially accepted.更多还原