Question about the simplex method complexity

Question

So I know that in general the simplex method for linear and convex quadratic programming can require exponential time. But assuming a positive semidefinite quadratic program that is solvable by the simplex method, then the problem is definitely in P, right?

The reason I ask: I am working on getting a handle on complexity theory. And I think I found a reduction from a problem to a positive semidefinite quadratic problem BUT the solution is only valid if the returned optimum is at a vertex of the feasible region. So that leaves out solving it with an interior point method since the minimum can be trivially obtained at the center of the feasible region and maybe at other points too. Since the simplex method operates on vertices, then I know that once the optimum is found, then it is at a point I actually care about.

Assuming the reduction is proper and always results in a correct answer: is reduction to the simplex method a sufficient condition for proving membership in P? OR does someone have a good reference to efficient exterior point methods for this class of problem? Is there another method for quadratic programs that I am overlooking? OR am I basically stuck with proving that the number of iterations is polynomial for this specific program? Is this question better suited to a different stack exchange site?

Answer 1

I think you may be misunderstanding how the simplex method is used to solve quadratic programs. It doesn't operate on the vertices of the feasible region of the original quadratic program; it operates on the vertices of the feasible region of the KKT conditions for the original quadratic program. This is because 1) the KKT conditions are sufficient as well as necessary for convex problems, and 2) for a quadratic program the KKT conditions are linear (well, except for complementary slackness, but that can be handled easily). Thus solving the original convex quadratic program reduces to solving its linear KKT conditions, and the simplex method is used to handle the latter. (See, for example, here.)

All of this means that the simplex method will output a vertex of the feasible region of the KKT conditions rather than necessarily a vertex of the feasible region of the original quadratic program.

However, if the quadratic program has the optimal solution at a vertex it means that if you use any of the algorithms for linear programming the algorithm will output that vertex as the optimal solution. (Well, assuming there aren't multiple optimal solutions.) So if you use one of the polynomial-time algorithms, that algorithm will output the vertex you want in polynomial time. For example, the ellipsoid method will work just fine, as in this recent answer on Math Overflow.

Added: If the quadratic programming problem has multiple optimal solutions, and you use, say, a polynomial-time interior-point algorithm to find one of them, it won't necessarily find one of the vertex optimal solutions. However, there is a polynomial-time algorithm due to Berkelaar, Jansen, Roos, and Terlaky for finding an optimal basis (which will give you an optimal vertex) from an optimal interior solution to a quadratic program. So all of that together will get you to an optimal vertex in polynomial time.