2
$\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$
11
  • 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$ Commented Aug 24, 2018 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
    Commented Aug 24, 2018 at 18:23
  • $\begingroup$ How big is big? $N=1,000,000$? billions? thousands? $\endgroup$ Commented Aug 24, 2018 at 19:45
  • $\begingroup$ @BrianBorchers let's say around hundreds of thousands. $\endgroup$
    – MAh2014
    Commented Aug 24, 2018 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$ Commented Aug 24, 2018 at 21:03

1 Answer 1

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$
9
  • $\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
    Commented Aug 24, 2018 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
    Commented Aug 24, 2018 at 18:39
  • $\begingroup$ Is this linear system always solvable for positive semidefinite $Q$, or should I solve the perturbed one? $\endgroup$
    – MAh2014
    Commented Aug 25, 2018 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
    Commented Aug 25, 2018 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
    Commented Aug 25, 2018 at 13:23

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .