6
$\begingroup$

I know the interior point method works both for Linear Programming (LP) and semidefinite programming (SDP). My question is, can the other popular method for solving LP, namely the simplex method, be extended to SDP? If not, what is the barrier?

Improve this question
$\endgroup$

5 Answers 5

Reset to default
3
$\begingroup$

[the first part of this answer is similar to Dinakar Muthiah's]

When optimizing a linear function on a convex set, it can always be assumed that the optimal solution lies on an extreme point of the feasible region (if there are several optimal solutions, at least one is an extreme point).

In the case of linear programming, these extreme points are vertices of a polyhedron, with the nice property that

  • there are a finite number of vertices
  • every vertex admits a simple algebraic description (this is the notion of basis, which is essentially a list of active inequalities)

However, for semidefinite programming, the feasible region, altough convex, typically admits an infinite number of extreme points, for which there is no clear equivalent to the concept of basis.

Note that simplex-type methods (also called active-set methods) can be generalized to quadratic programming (minimization of a convex quadratic function over a polyhedron). On the other hand, I am not aware of any such generalization for quadratically constrained quadratic programming (QCQP, i.e. quadratic programming with convex quadratic constraints) or second-order cone programming (a slight extension of QCQP), two problem classes whose instances can be posed as semidefinite programming problems.

Improve this answer
$\endgroup$
4
$\begingroup$

I believe as of now simplex methods have not been extended to SDP. The problem is that the feasible region of an SDP has a curved boundary. So for any point on the boundary I can cook up a linear function that is minimized there. So there are infinite set of possible candidates for the minimizing point.

For LP the boundary consists of straight segments, so minima occur only at vertices of the feasible region. As there are only finitely many vertices, you can search over this finite set to find your minimizing point, which is what the simplex algorithm does.

Improve this answer
$\endgroup$
2
$\begingroup$

well, here is some work toward a simplex-like approach to SDP.

http://www4.ncsu.edu/~kksivara/publications/rpi-colloquium.pdf

the author says you can email him for the pre-print but the slides for a talk are there.

If I understand it correctly, it's simplex-like in the sense that it's working with matrices that aren't full rank. So instead of variables entering and leaving a basis, as in LP, you would swap columns in and out. It's not simplex-like in the geometric sense of moving from extreme point to extreme point on a polyhedron.

X can be factorized as X=P^TDP where P isn't of full rank so the problem can be reduced to finding the right P. The talk goes into how to update the columns of P iteratively till the optimality criterion (having a psd slack matrix) is met. The columns with negative reduced costs at any iteration are the eigenvectors associated with negative eigenvalues of the indefinite slack matrices.

If I understand it all correctly.

Improve this answer
$\endgroup$
2
$\begingroup$

See: semidefinite simplex method. A.I. Kosolap, A.S. Peretyatko “Numerical efficiency of methods semidefinite optimization” «Journal of Automation and Information Sciences» 2014.

Improve this answer
$\endgroup$
1
$\begingroup$

V. Zhadan, Two-Phase Dual Simplex Method for Linear Semidefinite Optimization, Optimization Letters, November 2019, Volume 13, Issue 8, pp 1969–1984

contains these additional references:

Pataki, G. (1996). Cone-LP’s and Semidefinite Programs: Geometry and Simplex-type Method. In Proceedings of Conference on Integer Programming and Combinatorial Optimization (IPCO 5), 1-13.

Kosolap, A. I. (2009). Symplex method for solving semi-definite programming problems. Vest.Donetsk nats. Univ., Ser A Estestv. Nauki, No. 2, 365-369 (in Russian).

Zhadan, V. G. (2015). On variant of the simplex method for linear semidefinite programmingproblem.Proceedings of the Institute of Mathematics and Mechanics Ural Branch of RAS, 21(3), 117-127 (in Russian).

Zhadan, V. G. (2016). A variant of dual simplex method for linear semidefinite programming problem.Proceedings of the Institute of Mathematics and Mechanics Ural Branch of RAS, 22(3), 90-100 (in Russian)

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .