Analytical solution of quadratic programming when $H$ is not p.d.?

Question

Considering the unconstrained quadratic programming: $$\min_x \frac{1}{2}x^\top Hx+c^\top x$$ if $H$ is not positive definite, can we still calculate the analytical solution?

Answer 1

We consider the function $$ f \colon \def\R{\mathbf R}\R^n \to \R, \quad x \mapsto \frac 12 x^tHx + c^t x $$ for $H\in \def\M{\mathrm{Mat}}\M_n(\R)$, $c \in \R^n$. Taking derivatives gives \begin{align*} f'(x)h &= \frac 12 x^t(H+H^t)h + c^t h\\ f''(x)[h,k] &= \frac 12 h^t(H+H^t)k \end{align*} So we see that the critical points of $f$ are the solutions of $$ \frac 12(H + H^t)x = c$$ which are minima iff $\frac 12(H+H^t)$ is positive semi-definite.