Linear programming approaches to semidefinite programming problems.

摘要

The thesis investigates linear programming approaches to solving Semidefinite Programming (SDP's). 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($k$) (k is the number of constraints in the SDP) constraints are required in the LP relaxations. To generate these constraints we use the spectral bundle approach due to Helmberg and Rendl. This scheme recasts any SDP with a bounded feasible set as an eigenvalue optimization problem. These are convex but nonsmooth problems that can be tacked by bundle methods 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 approach. We demonstrate the efficiency of the approach on two combinatorial optimization problems namely maxcut and minbisection.; The semi-infinite LP formulation of the SDP, together with its polynomial time separation oracle leads naturally to a cutting plane LP approach for the SDP. We investigate such an approach. However to make the resulting method competitive with interior point methods for the SDP, several refinements are necessary. In particular the cutting plane method requires solving the LP relaxations approximately using an interior point method, since this results in better cutting planes. We experiment with various separation oracles generating deep cuts, and techniques to restart the LP relaxations with strictly feasible starting points. We also relate these cutting planes to the geometry of the SDP cone. We then test the approach on the maxcut SDP.; Finally we incorporate the cutting plane LP approach to the SDP in an SDP approach for the maxcut problem. In particular, we formulate the dual of the well known SDP relaxation for maxcut as a semi-infinite LP, and solve it using an interior point cutting plane scheme. We present computational results on a variety of maxcut problems. (Abstract shortened by UMI.)