Why can quadratic functions over polyhedrons be minimized exactly in finite time?

Question

I have heard it said that QP problems $$\min f(x) = \frac 12 x^TAx + b^T x$$ $$x \in P$$ where $A$ is a symmetric matrix and $P$ is a polyhedron can all be solved exactly and in finite time (or it can be shown that there is no minimum in finite time). I can solve a few of the cases, but not all of them.

I have done a couple of cases below, but they all involve $P$ being bounded. I'm not sure how to deal with $P$ being unbounded. I think there are two cases to do when $P$ is unbounded: $f$ is bounded below on $P$, and $f$ is unbounded below on $P$.

Case 1: $P$ is bounded, $A$ is P.S.D.

By boundedness a minimum exists. The minimum can be found by analyzing the KKT points. Indeed, we have $\nabla^2_{xx} L = Q$ is P.S.D., so every KKT point satisfies the SOSC, so is a local minimum . But $f$ is convex, so any local minimum is global.

Finding the KKT points for quadratic problems reduces to solving a bunch of systems of linear equations, which can be done exactly in finite time.

Case 2: $P$ is bounded, $A$ is N.S.D.

In this case $f(x)$ is concave, and it is well-known that the minimum of a concave function over a polytope occurs at a vertex. Therefore we could find the minimum by examining the vertices, which can be done exactly in finite time to find.

Case 3: $P$ is bounded, $A$ is indefinite.

I know that the minimum will occur at a boundary point of the domain, but I don't know how to go further.

Answer 1

I would point to a paper by Vavasis "Quadratic Programming is in NP" https://www.sciencedirect.com/science/article/abs/pii/002001909090100C

His proof shows that the optimal solution to minimizing a QP over a polyhedron is in fact the solution to a certain set of linear equations, and hence the optimal solution has a polynomial encoding size in the bit model. So, as a brute force, you could enumerate rational points in a given region to find such a point in finite time.

But the proof does one bit better. It essentially outlines an exponential-time algorithm to solve the problem. Let me explain.

The proof shows that the optimal solution lies in the relative interior of a face of the polyhedron (that defines the feasible region). If the objective is convex, then it may lie on the actual interior of the feasible region. Otherwise, if the objective is nonconvex, then the objective function pushes towards boundaries. Hence, let's look at a facet of the polyhedron. If we restrict to a facet, then we can project into a lower dimension, and rethink the problem. Is the objective convex after the projection? If so, then solve like a normal convex QP. Otherwise, push to other faces.

Hence, the brute-force algorithm is:

• Let $P$ be the polyhedron defining the feasible region.
• Compute all faces of $P$. This means faces of any dimension.
• For each face, check if the objective, when projected into that face, is convex.
• If so, compute the optimal solution in that face and store it.

Lastly, compare all the solutions that you found and return the optimal one.

Answer 2

[EDIT]: this answer is only valid for the convex quadratic programming case.

This comes from the solution set of the KKT conditions having a particular structure, that can be exploited in a simplex-like fashion (see the seminal paper of Wolfe).

Consider a quadratic programming problem in standard form \begin{align} (QP) \ \ \ \min_{x} \ \ \ & \frac{1}{2}x^{T} Q x + c^{T} x\\ s.t. \ \ \ & A x = b,\\ x \geq 0. \end{align} and its dual \begin{align} (QD) \ \ \ \max_{x, y, s} \ \ \ & b^{T}y - \frac{1}{2}x^{T} Q x\\ s.t. \ \ \ & -Q x + A^{T}y + s = c,\\ s \geq 0. \end{align}

Then, the first-order KKT conditions write \begin{align} A x &= b,\\ -Qx + A^{T}y + s &= c\\ x_{j} s_{j} &= 0, \ \ j = 1, ..., n\\ x, s & \geq 0 \end{align}

The mathematical details are given in Wolfe's paper but, essentially, one can use the simplex algorithm to find a solution to this system. There are only a finite number of steps the simplex algorithm can take before converging, hence finite-time termination. The exact part relies on the fact that all linear systems are solved exactly, which is possible in practice if the problem's data is rational.

Some final remarks:

• The Simplex-QP algorithm is finite-time, but is not polynomial
• Interior-point methods run in polynomial time, but do not produce exact solutions
• If one allows for quadratic constraints, then "exactness" is generally not possible in practice, since the solution may be irrational (e.g., $\sqrt{2}$ cannot be represented using finite-precision arithmetic).

Answer 3

Deterministic global optimisation algorithms can solve all problems up to and including algebraic MINLPs (which of course includes QPs) to global optimality in finite time, up to an arbitrary tolerance (which, for all intents and purposes is equivalent to "exactly" when it comes to floating point numbers). That time might be exponentially long, but is still finite. Neumaier provided an extensive review of the methods in 2004 if you're curious about the fundamentals.

This is the class of algorithms used in global optimisation solvers such as Couenne, BARON, ANTIGONE, and our own Octeract Engine.

The underlying reason is that certain classes of convex/linear relaxations such as generalised McCormick relaxations or $\alpha$BB relaxations have been proven to improve their bound (quadraticaly but that's of secondary import here) as the domain is reduced (typically through branching). Mitsos has a nice proof of the convergence rate for both classes of relaxations.