Interior Point Methods in Semidefinite Programming with Applications to Combinatorial Optimization
Farid Alizadeh · SIAM Journal on Optimization · 1995
This paper studies the semidefinite programming SDP problem, 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 the classical cone duality is reviewed as it is specialized to SDP is reviewed. Next an interior point algorithm is presented that converges to the optimal solution in polynomial time. The approach is a direct extension of Ye’s projective method for linear programming. It is also argued that many 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 carrying over in a similar fashion. Finally, the significance of these results is studied 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, barrier oracles are presented 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 to solve a combinatorial optimization problem with interior point methods, its linear programming formulation is eeded explicitly.
Cited by 892 works. doi:10.1137/0805002
Authors
References
- Convex Analysis
- A new polynomial-time algorithm for linear programming
- Matrix Analysis
- Interior-Point Polynomial Algorithms in Convex Programming
- The ellipsoid method and its consequences in combinatorial optimization
- Geometric Algorithms and Combinatorial Optimization
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- Lower Bounds for the Partitioning of Graphs
- Theory of Linear and Integer Programming
- Normal hypergraphs and the perfect graph conjecture