【作者】 乌彩英；

【导师】 陈国庆；

【作者基本信息】 内蒙古大学 ， 应用数学， 2009， 博士

【摘要】 本文主要研究互补问题与半定规划问题的数值解法。所取得的主要结果有:1.提出无约束最优化共轭梯度法参数β_κ修正的两种新形式。与经典共轭梯度法的区别是新方法中体现了函数值下降量信息。提出这两种方法的改进形式。证明了这四种方法的全局收敛性。数值实验表明了算法的有效性。2.提出求解大规模非线性互补问题（NCP（F））的共轭梯度法。（ⅰ）利用Fischer-BurmeisterNCP-函数,将NCP（F）转化为非线性方程组,基此提出PRP-型共轭梯度法。算法的突出特点是在不需要额外假设及线搜索的辅助下满足充分下降条件,在F是连续可微P₀+R₀函数且F′（x）在水平集上全局Lipschitz连续条件下,算法全局收敛。（ⅱ）利用光滑Fischer-Burmeister函数,将NCP（F）转化为光滑非线性方程组,基此对大规模非线性互补问题提出光滑PRP-型共轭梯度法。算法执行一步需进行两个Armijo线性搜索既确保光滑参数μ的非负性又极小化由光滑Fischer-Burmeister函数所形成的光滑价值函数.在F为P₀+R₀连续可微函数时,算法全局收敛。数值实验表明了这两种算法的数值有效性。3.提出半定规划的半定互补解法。首先考虑一类特殊的半定规划问题（即在对偶问题中加入约束条件y≥0）,将其最优性条件等价转化为半定互补问题（SDCP）,藉此提出预估-校正光滑牛顿法,证明了牛顿方向的存在性、迭代点列的有界性及算法的全局收敛性。在解点处广义导数可逆的假设下得到算法的超线性收敛率。然后推广这一思想,将标准半定规划的最优性条件转化为广义半定互补问题（GSDCP）,提出预估-校正光滑牛顿法。该方法是非线性互补问题（NCP（F））算法的推广。同样证明了牛顿方向的存在性、迭代点列的有界性及算法的全局收敛性。在解点处广义导数可逆的假设下得到算法的二次收敛率。不需要任何对称化技巧,此二方法自动产生对称搜索方向。4.提出半定规划的非内点连续化方法。该方法是求解半定互补问题（SDCP）算法的推广。证明了牛顿方向的存在性。在中心路径邻域有界的假设下得到迭代点列的有界性,进而证明了算法的全局收敛性。在解点处广义导数可逆的假设下算法局部二次收敛。给出了数值实验结果。5.提出半定规划的PRP⁺共轭梯度法。基于Fischer-Burmeister SDCP-函数,对SDP的最优性条件提出一梯度具有全局Lipschitz连续性的价值函数,从而将半定规划转化为无约束优化问题,进而用PRP⁺共轭梯度法求解.为得到PRP⁺共轭梯度法的收敛性同时使函数值在每次迭代中有所下降,提出一Armijo-型线搜索。无需水平集有界及迭代点列聚点的存在,算法全局收敛。更多还原

【Abstract】 This thesis is devoted to study the algorithms for complementarity and semidefinite programming problems.The main results,obtained in this dissertation,are summarized as follows:1.Two new formulas of the main parameterβ_k of conjugate gradient methods for unconstrained optimization problems are presented.In comparison with classic conjugate gradient methods,the new methods take both available gradient and function value information. Furthermore,their modifications are proposed.The global convergence of these methods are proved respectively.Numerical results indicate that these algorithms are efficient.2.The conjugate gradient algorithms for large scale nonlinear complementarity problems （NCP（F）） are proposed.（ⅰ） We present a new PRP-type conjugate gradient method for solving large scale nonlinear complementarity problems based on a nonlinear system of equations reformulated by Fischer-Burmeister NCP-function,which satisfies the sufficient descent condition without requiring any assumption.Under the conditions that F:IRⁿ→IRⁿ is a continuously differentiable P₀+R₀ function and the Jacobian matrix F′（x） satisfies global Lipschitzian continuity on level set,global convergence result is established.Numerical experience is reported which demonstrates good computational performance on large scale NCP（F）.（ⅱ） A PRP-type smoothing conjugate gradient method for solving large scale nonlinear complementarity problems is proposed based on a smoothing nonlinear system of equations reformulated by smoothing Fischer-Burmeister function.At each iteration,two Armijo line searches are performed,which guarantee the positive property of the smoothing parameterμand minimize the merit function formed by smoothing Fischer-Burmeister function,respectively.Global convergence is obtained when F:IRⁿ→IRⁿ is a continuously differentiable P₀+R₀ function. Finally,numerical examples are given to show the effectiveness of the method. 3.The semidefinite complementarity methods are presented to solve semidefinite programming （SDP）.Firstly,a special type of semidefinite programming（namely,the dual problem contains the constraint y≥0） is considered.The optimality conditions of semidefinite programming is reformulated equivalently as a semidefinite complementarity problem （SDCP）,and then a predictor-corrector smoothing Newton algorithm for SDCP is presented.The existence of Newton directions,boundedness of iterates and global convergence are proved.Local superlinear convergence is proved under the assumption that the generalized derivative at solution point are invertible.Secondly,the optimality conditions of the standard semidefinite programming is reformulated as a generalized semidefinite complementarity problem（GSDCP）.Then,enlightened by some techniques in algorithms for NCP（F）,we present a predictor-corrector smoothing Newton algorithm and prove the existence of Newton directions,boundedness of iterates and global convergence.Local quadratic convergence can be obtained under the condition that the generalized derivative at solution point are invertible.The presented methods generate symmetric directions without any further transformations.4.The noninterior continuation method for semidefinite complementarity problem（SDCP） is extended to semidefinite programming（SDP）.The existence of Newton directions is proved.The boundedness of iterates generated by the method is obtained under the condition that the neighborhood is bounded,and the global convergence is proved. Local quadratic convergence follows from the assumption that the generalized derivative at solution point are invertible.Some numerical results are also reported.5.The PRP⁺ conjugate gradient algorithm for solving semidefinite programming（SDP） is discussed.Based on the Fischer-Burmeister SDCP-function,a merit function with globally Lipschitzian continuously gradient for the optimality conditions of SDP is proposed, which reformulates the optimality conditions as an unconstrained optimization problem. The PRP⁺ conjugate gradient algorithm is applied to solve this problem.In order to obtain the convergence of the PRP⁺ method and decrease the function evaluation at each iteration,we provide a new Armijo-type line search rule.Global convergence of the algorithm is proved without requiring the boundedness of level set and existence of accumulation point of produced sequence by the method.更多还原