1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ The size and sparsity of $A$ and $Q$ can make a huge difference. How big are your matrices? How dense are they? $\endgroup$ – Brian Borchers Aug 24 '18 at 18:18
  • $\begingroup$ @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. $\endgroup$ – MAh2014 Aug 24 '18 at 18:23
  • $\begingroup$ How big is big? $N=1,000,000$? billions? thousands? $\endgroup$ – Brian Borchers Aug 24 '18 at 19:45
  • $\begingroup$ @BrianBorchers let's say around hundreds of thousands. $\endgroup$ – MAh2014 Aug 24 '18 at 19:51
  • $\begingroup$ 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$? $\endgroup$ – Brian Borchers Aug 24 '18 at 21:03
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ The system is not sparse but it could be very large, So you mean in this case It's better to solve the KKT system directly, right? Thanks. $\endgroup$ – MAh2014 Aug 24 '18 at 18:31
  • 1
    $\begingroup$ I think the main takeaway is that you can reduce this to solving a system, so running the optimization version of CG won't give you anything. If you care about full accuracy and have a dense system, I'd argue that the LDL is the best you can do here. If the system dimension is 5000 this should take at most ~3 seconds. If you want a fast, quick approximation that is good but not great in terms of accuracy (seems like you don't want this) you might want to use traditional CG. $\endgroup$ – cdipaolo Aug 24 '18 at 18:39
  • $\begingroup$ Is this linear system always solvable for positive semidefinite $Q$, or should I solve the perturbed one? $\endgroup$ – MAh2014 Aug 25 '18 at 10:50
  • $\begingroup$ Regularization might help if the conditioning is terrible, but the system will always be solvable, yes. To see this, note that the KKT system is equivalent to optimality, and the restriction of the strongly convex objective to any subspace is still strongly convex and hence has a (unique) solution. $\endgroup$ – cdipaolo Aug 25 '18 at 13:14
  • 1
    $\begingroup$ 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. $\endgroup$ – cdipaolo Aug 25 '18 at 13:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.