A Linear Programming Approach to Semidefinite Programming Problems
Download the talk,
in pdf format.
Authors:
Kartik Krishnan and
John E. Mitchell
Department of Mathematical Sciences
Rensselaer Polytechnic Institute
Troy, NY 12180 USA
kartis@rpi.edu and
mitchj@rpi.edu
April 9, 2001.
Given to the
Operations
Research area within the
Mathematics
center at IBM Yorktown Heights.
Abstract:
A semidefinite programming problem can be regarded as a convex nonsmooth
optimization problem, so it can be represented as a semi-infinite linear
programming problem. Thus, in principle, it can be solved using a cutting
plane approach; we describe such a method. The cutting plane method uses an
interior point algorithm to solve the linear programming relaxations
approximately, because this resulted in the generation of better constraints
than a simplex cutting plane method.
Further, the bundle method of Helmberg and Rendl can be used to generate a
set of linear constraints. Typically, these alone are not sufficient to give
a good linear programming relaxation. Nonetheless, if they are used in
conjunction with some families of problem specific constraints, tight LP
relaxations can be obtained.
Download the talk,
in pdf format.
Return to my list of talks.