# What is the fastest algorithm to solve an equality-constrained convex quadratic program?

I am trying to solve the following convex problem

$$\begin{array}{ll} \text{minimize} & x^T Q x + px\\ \text{subject to} & Ax + b = 0\end{array}$$

which arises in the active set method for inequality/equality constrained quadratic optimization).

I have studied the conjugate gradient method, Newton's method with equality constraints, or solving the KKT matrix directly. Which one do you think is fastest? I need the algorithm to converge to high accuracy and be as fast as possible, and I have to notice that I am going to use it for polishing the solution obtained by the other solver so it may converge after a few iterations.

• The size and sparsity of $A$ and $Q$ can make a huge difference. How big are your matrices? How dense are they? Commented Aug 24, 2018 at 18:18
• @BrianBorchers The algorithm is going to be used mostly for high dimensional problems, so $A$ and $Q$ are big, and also there is no restriction on their density. Commented Aug 24, 2018 at 18:23
• How big is big? $N=1,000,000$? billions? thousands? Commented Aug 24, 2018 at 19:45
• @BrianBorchers let's say around hundreds of thousands. Commented Aug 24, 2018 at 19:51
• If $n$ is on the order of hundreds of thousands then simply storing $A$ and $Q$ as dense matrices is likely to be impractical and direct factorization of the KKT system isn't going to work either. How do you plan to store $A$ and $Q$? Commented Aug 24, 2018 at 21:03

Assuming a dense system, solving the KKT system gives the solution as $$\begin{bmatrix} Q & A^*\\A & 0 \end{bmatrix}\begin{bmatrix} \mathbf{x}^\star\\\boldsymbol{\nu}^\star \end{bmatrix} = -\begin{bmatrix} \mathbf{p}\\\mathbf{b} \end{bmatrix}$$ which can be solved accurately by an $LDL^*$ factor-solve method in $\tfrac{1}{3}n^3 + 2n^2$ flops. This is equivalent to running Newton for one step, so no need to compare there. Conjugate gradients is numerically unstable so would perform worse unless potentially your system was very large or sparse.
• Is this linear system always solvable for positive semidefinite $Q$, or should I solve the perturbed one? Commented Aug 25, 2018 at 10:50
• Ah I read “positive definite” — sorry. This might not have a solution. Consider $Q=0$, which isn’t bounded. In that case you might want to add a small perturbation to $Q$, which would add and effective 2-norm regularization to your problem. Commented Aug 25, 2018 at 13:23