Properties of a Cutting Plane Method for Semidefinite Programming
Download the paper,
as a pdf file.
Authors:
Kartik Krishnan Sivaramakrishnan
Department of Mathematics
North Carolina State University
Raleigh, NC 27695-8205
kksivara at ncsu dot edu
John E. Mitchell
Department of Mathematical Sciences
Rensselaer Polytechnic Institute
Troy, NY 12180 USA
mitchj at rpi dot edu
September 2007.
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. (2005) and
Oskoorouchi and Goffin (2007) 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.
Download the paper,
as a pdf file.
Optimization
Online listing
Return to my list of papers.