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?



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.


