Properties of a Cutting Plane Method for Semidefinite Programming

Kartik Krishnan Sivaramakrishnan (kksivarancsu.edu)
John E. Mitchell (mitchjrpi.edu)

Abstract: We analyze the properties of an interior point cutting plane algorithm that is based on a semi-infinite linear formulation of the dual semidefinite program. The cutting plane algorithm approximately solves a linear relaxation of the dual semidefinite program in every iteration and relies on a separation oracle that returns linear cutting planes. We show that the complexity of a variant of the interior point cutting plane algorithm is slightly smaller than that of a direct interior point solver for semidefinite programs where the number of constraints is approximately equal to the dimension of the matrix. Our primary focus in this paper is the design of good separation oracles that return cutting planes that support the feasible region of the dual semidefinite program. Furthermore, we introduce a concept called the {\em tangent space induced by a supporting hyperplane} that measures the strength of a cutting plane, characterize the supporting hyperplanes that give higher dimensional tangent spaces, and show how such cutting planes can be found efficiently. Our procedures are analogous to finding facets of an integer polytope in cutting plane methods for integer programming. We illustrate these concepts with two examples in the paper. Finally, we describe separation oracles that return nonpolyhedral cutting surfaces. Recently, Krishnan et al.\ \cite{kartik8} and Oskoorouchi and Goffin \cite{oskoorouchi4} have adopted these separation oracles in conic interior point cutting plane algorithms for solving semidefinite programs.

Keywords: Semidefinite programming, interior point methods, regularized cutting plane algorithms, maximum eigenvalue function, cone of tangents

Category 1: Linear, Cone and Semidefinite Programming

Category 2: Convex and Nonsmooth Optimization (Nonsmooth Optimization )

Citation: Technical Report, Department of Mathematics, North Carolina State University, Raleigh, NC 27695-8205, September 2007, submitted for publication. Available at http://www4.ncsu.edu/~kksivara/publications/properties_revised.pdf

Download: [PDF]

Entry Submitted: 10/01/2007
Entry Accepted: 10/01/2007
Entry Last Modified: 10/01/2007

Modify/Update this entry