# 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? – Brian Borchers Aug 24 '18 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. – MAh2014 Aug 24 '18 at 18:23
• How big is big? $N=1,000,000$? billions? thousands? – Brian Borchers Aug 24 '18 at 19:45
• @BrianBorchers let's say around hundreds of thousands. – MAh2014 Aug 24 '18 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$? – Brian Borchers Aug 24 '18 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? – MAh2014 Aug 25 '18 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. – cdipaolo Aug 25 '18 at 13:23