The convex conjugate of a quadratic form with positive semi definite matrix

Question

I want to find the convex conjugate (Legendre transform) of a quadratic for $1/2x^{t}Qx$ when $Q$ is positive semi-definite. If Q is non-singular, the solution is easy - the gradient is $y-Qx=0$ so $y=Q^{-1}x$ is the value for which the supremum is attained. But what should I do when Q is singular? In case there is some y for which $y=Qx$ (i.e. $y\in Image(Q)$) the solution is the same. But if it isn't - how can I prove the sup is infinite?

Answer 1

It's useful to know how to minimize a quadratic function $f(x) = \frac12 x^T Q x - b^T x$ when $Q \succeq 0$. Note that $f$ is convex, so minimizing $f$ is equivalent to solving $\nabla f(x) = 0$, which is equivalent to $Qx = b$.

If $b \in R(Q)$, then $Qx = b$ has a solution, which is a minimizer of $f$.

If $b \not \in R(Q)$, we can show that $\inf_x f(x) = -\infty$. Let's use the fact that $R(Q) = N(Q)^\perp$. Decompose $b$ as $b = u + v$ where $u \in N(Q)$ and $v \in R(Q)$ (so $u$ and $v$ are orthogonal). Note that $u \neq 0$. Now observe that \begin{align*} f(\lambda u) &= -(u + v)^T (\lambda u) \\ &= - \lambda \|u\|^2 \end{align*} which approaches $-\infty$ as $\lambda \to \infty$.