oc.optimization control - Simplex method for SDP?

[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.