Study On The Algorithms For Complementarity And Semidefinite Programming Problems

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.