A unifying framework for several cutting plane methods for semidefinite
programming
Download the paper,
pdf.
Authors:
Kartik Krishnan
Department of Computing & Software
McMaster University
Hamilton, ON L8S 4K1
Canada
kksivara at ncsu.edu
John E. Mitchell
Department of Mathematical Sciences
Rensselaer Polytechnic Institute
Troy, NY 12180 USA
mitchj@rpi.edu
Abstract:
Cutting plane methods provide the means to solve large scale
semidefinite programs (SDP) cheaply and quickly. They can also
conceivably be employed for the purposes of re-optimization after
branching, or the addition of cutting planes. We give a survey of
various cutting plane approaches for SDP in this paper. These
cutting plane approaches arise from various perspectives, and
include techniques based on interior point cutting plane
approaches, non-differentiable optimization, and finally an
approach which mimics the simplex method for linear programming
(LP).
We present an accessible introduction to various cutting plane
approaches that have appeared in the literature.
We place these methods in a unifying framework which illustrates
how each approach
arises as a natural enhancement of a primordial LP cutting plane
scheme based on a semi-infinite formulation of the SDP.
Keywords:
Semidefinite programming, nondifferentiable optimization,
interior point cutting plane methods,
active set approaches.
Download the paper,
pdf.
Optimization
Online listing
Return to my list of papers.