Properties of a Cutting Plane Method for Semidefinite Programming
Download the paper,
as a pdf file.
Authors:
Kartik Krishnan Sivaramakrishnan
Axioma Inc.
Atlanta, GA 30350
kksivara at gmail dot com
John E. Mitchell
Department of Mathematical Sciences
Rensselaer Polytechnic Institute
Troy, NY 12180 USA
mitchj at rpi dot edu
Pacific Journal
of Optimization,Volume 8(4), pages 779-802, 2012.
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 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. We present
computational results that highlight the strength of these cutting planes
in a practical setting. Our technique of finding higher dimensional cutting
planes can conceivably be used to improve the convergence of the spectral
bundle method of Helmberg et al. (2000, 2003)
and the non-polyhedral cutting surface algorithms of
Sivaramakrishnan et al. (2005)
and Oskoorouchi et al. (2007, 2009).
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.