Optimization Online


Properties of a Cutting Plane Method for Semidefinite Programming

Kartik Krishnan Sivaramakrishnan (kksivara***at***ncsu.edu)
John E. Mitchell (mitchj***at***rpi.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: Replaced by: http://www.optimization-online.org/DB_HTML/2011/09/3163.html


Entry Submitted: 10/01/2007
Entry Accepted: 10/01/2007
Entry Last Modified: 09/15/2011

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society