Interior Point Methods in Semidefinite Progrmming with Applications to Combinatorial Optimization

We study the semidefinite programming problem (SDP), i.e the optimization problem of a linear function of a symmetric matrix subject to linear equality constraints and the additional condition that the matrix be positive semidefinite. First we review the classical cone duality as specialized to SDP. Next we present aninterior point algorithm which converges to the optimal solution in polynomial time. The approach is a direct extension of Ye's projective method for linear programming. We also argue that most known interior point methods for linear programs can be transformed in a mechanical way to algorithms for SDP with proofs of convergence and polynomial time complexity also carrying over in a similar fashion. Finally we study the significance of these results in a variety of combinatorial optimization problems including the general 0-1 integer programs, the maximum clique and maximum stable set problems in perfect graphs, the maximum k-partite subgraph problem in graphs, and various graph partitioning and cut problems. As a result, we present barrier oracles for certain combinatorial optimization problems (in particular, clique and stable set problem for perfect graphs) whose linear programming formulation requires exponentially many inequalities. Existence of such barrier oracles refutes the commonly believed notion that in order to solve a combinatorial optimization problem with interior point methods, one needs its linear programming formulation explicitly.

ICSI Technical Report TR-93-050

Technical Report