Semidefinite Programming With Applications To Combinatorial Optimization

It is significantly important to discuss semidefmite programming. Its most important applications are found within many fields; on the other hand, several classical optimization problems can be formulated as standard semidefinite programming. Therefore semidefinite programming provides a unit form to study these problems and construct algorithms.Firstly, based on the s -subdifferential theory and strong duality of semidefinite programming, we propose one method to solve semidefinite programming. In this method, we get the optimal value of semidefinite programming by finding the optimal descent direction of its dual problem. Both theoretical proof and Numerical experiments indicate that this algorithm is convergent and effective for solving large-scale semidefinite programming. In the following section, we work over the bisection problems. By adding nonlinear constraints to Circuit Bisection, we offer equivalent forms to readers. Executing the lifting method to the equivalent programming, we present a strengthened semidefmite relaxation. As predicted by theory and confirmed by numerical experiments the tight semidefinite relaxation gives a better lower bound of Circuit Bisection than the one that the previous semidefinite relaxation gives. Then a suboptimal solution of the graph maximum equal-cut problem is presented employing the randomized algorithm and the improved coordinate ascent (descent) algorithm on the optimal solution of semidefmite relaxation. Its implementation shows that the improved coordinate ascent (descent) algorithm is practical.