Properties of a Cutting Plane Method for Semidefinite Programming
Download the paper,
postscript or pdf.
Authors:
Kartik Krishnan
Department of Computational and
Applied Mathematics
Rice University
Houston, Texas 77005
kksivara at ncsu.edu
John E. Mitchell
Department of Mathematical Sciences
Rensselaer Polytechnic Institute
Troy, NY 12180 USA
mitchj@rpi.edu
May 14, 2003.
Abstract:
A semidefinite programming problem is a nonsmooth optimization problem,
so it can be solved using a cutting plane approach.
In this paper, we analyze properties of such an algorithm.
We discuss characteristics of good polyhedral representations
for the semidefinite program.
We show that the complexity of an interior point cutting plane
approach based on a semi-infinite formulation of the
semidefinite program has complexity comparable with that of
a direct interior point solver.
We show that cutting planes
can always be found efficiently that support the feasible region.
Further, we characterize the supporting hyperplanes that give
high dimensional tangent planes, and show how such supporting hyperplanes
can be found efficiently.
Keywords:
Semidefinite programming, column generation, cutting plane methods,
tangent space.
Download the paper,
postscript or pdf.
Optimization
Online listing
Return to my list of papers.