Non-positive-definite quadratic program minimum simplification

221 Views Asked by At

I was finding the minimum of a simple quadratic program with equality constraints:

$$ m = \min_x x^TQx\qquad\mathrm{s.t.}\quad Ax=b. $$

Using a formulation with Lagrange multipliers from Wikipedia I was able to find the closed-form minimizer $x^*$ from $$ \left(\begin{array}{c}x^* \\ \lambda^*\end{array}\right) = \left(\begin{array}{cc}Q & A^T \\ A & 0\end{array}\right)^{-1} \left(\begin{array}{c}0 \\ b\end{array}\right). $$ Using block-wise matrix inversion for the inverse here and pushing everything through gives: $$ x^* = Q^{-1}A^T(AQ^{-1}A^T)^{-1}b $$

and, from that, that the minimum is $$m = b^T(AQ^{-1}A^T)^{-1}b.$$

The above requires, though, that $Q$ be positive-definite.

I'm interested in whether there's a simple formula for the minimum if $Q$ is not positive-definite or invertible, but is positive-semi-definite. For example, for some toy problems I've found that

$$ \lim_{\epsilon\to 0} b^T(A(Q + \epsilon I)^{-1}A^T)^{-1}b $$

exists and is equal to $m$, but I couldn't find an expression that this limit is equal to, in terms of operations that standard linear algebra packages could do. I could of course find the minimum by evaluating this expression for a small $\epsilon$, but that's quite unsatisfying.

Since this has a pseudo-inversey flavor, I've tried a few things with them, but none of these get the same minimum, e.g.

$$ m\ne b^T(AQ^{+}A^T)^+b $$

and

$$ m \ne b^T(A^+)^TQA^+b. $$

Is anyone familiar with a closed-form way to evaluate this limit, or with some other expression for $m$ with non-positive-definite $Q$? It feels like there's something obvious here that I haven't hit yet.