Algorithms For Semidefinite Programming And Its Applications In Combinatorial Optimization

Semidefinite programming (denoted SDP) is an extension of linear programming(LP), with vector variables replaced by matrix variables and nonnegativity elementwisereplaced by positive semidefinite. It is well known that the constraint of semidefiniteprogramming is nonlinear and nonsmooth , but convex, so semidefinite programming isconvex optimization problems. Semidefinite programming unifies several standardproblems (e.g., linear and quadratic programming) and finds many applications fromsystem and control theory to combinatorial optimization as well as eigenvalueoptimization, so semidefinite programming is viewed as a new and important researchdirection in mathematical programming. This paper consists of there parts:1.A new projection algorithm solving semidefinite programming is attainted by theequivalence of the optimality conditions and the variational inequality. Theconvergence analysis and numerical experiment are also contained.2.We translate the perturbed optimality conditions of semidefinite programminginto the least squares problem, a new primal-dual direction (Gauss-Newtondirection) is achieved by solving the least squares problem. An infeasibleshort-step path-following algorithm based on the Gauss-Newton direction andConvergence analysis are given. The empirical evidence suggests the directionoffer more robust than other directions currently in use.3.The strengthened SDP relaxation is based on applying a lifting procedure to thiswell-know SDP relaxation after adding the nonlinear constraints. It is shown thatthe new bound obtained this way strictly improves the previous SDP boundboth empirically and theoretically.