Linear Programming Approaches to Semidefinite Programming Problems

Kartik Krishnan Sivaramakrishnan

PhD Thesis, August 2002

Rensselaer Polytechnic Institute

One of the various characterizations of the positive semidefiniteness constraint leads to a semi-infinite LP formulation for the SDP. We formulate the dual SDP as a semi-infinite LP, and discuss the issue of its discretization in detail. Using the notions of nondegeneracy and basic feasible solutions developed in the context of semi-infinite linear programming, we recover a theorem due to Pataki on the rank of extreme matrices in SDP, which in turn implies that not more than $O(\sqrt{k})$ ($k$ is the number of constraints in the SDP) constraints are required in the LP relaxations. To generate these constraints we use the spectra l bundle approach due to Helmberg and Rendl. This scheme recasts any SDP with a bounded feasible set as a n eigenvalue optimization problem. These are convex but nonsmooth problems that can be tacked by bundle me thods for nondifferentiable optimization. The LP approach provides an upper bound, and can also be utilized to generate a primal feasible matrix $X$ for the spectral bundle app roach. We demonstrate the efficiency of the approach on two combinatorial optimization problems namely maxcut and minbisection.