# Question about the simplex method complexity

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?

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.

• You asked several questions in one post, and I tried to address what I thought was the essence of what you wanted to know. If I misunderstood, let me know, and I'll adjust my answer. – Mike Spivey Sep 28 '11 at 20:58
• Ok, fair enough. The problem I am having is that the objective has infinitely many optimal solutions(all the same). Only finitely many of them are at vertices. If I get any one of these solutions at a vertex then I will be happy. If I get a point however that is strictly inside of the feasible region(Which always exist for this objective function), then I am not happy. You are saying that the ellipsoid method should work fine then? I have a feeling that I have to work on a less ambiguous formulation if I want this to actually work. – Tim Seguine Sep 29 '11 at 12:33
• @Tim: I've added a link to a paper that will get you to an optimal vertex from an optimal interior solution in polynomial-time. – Mike Spivey Sep 29 '11 at 13:44
• I wonder if there is a quadratic program whose linear KKT conditions are equivalent to the infamous Klee-Minty example... – J. M. is a poor mathematician Sep 29 '11 at 15:07
• @J.M.: Interesting question. My first guess is that you could probably reverse engineer the Klee-Minty example to produce such a quadratic program. – Mike Spivey Sep 29 '11 at 15:11