Minimizer of $g(\mathbf{x}) = \frac12 \mathbf{x}^T A\mathbf{x}-\mathbf{b}^T\mathbf{x} + c$

Question

I have to find the minimizer of $g(\mathbf{x}) = \frac12 \mathbf{x}^T\ A\mathbf{x}-\mathbf{b}^T\mathbf{x} + c$ where $A=\begin{bmatrix} 2&6\\6&2 \end{bmatrix}$ and $\mathbf{b} = [1,2]^T$ and $c=9$

The issue that I have with this question is:

The hessian is given by $D'(g) = A^T\mathbf{x} - \mathbf{b}\rightarrow D''(g) = A$ which is not positive definite. So this is not a convex problem, does this mean there is no minimizer?

Answer 1

Problems like this can often be tackled by a multidimensional version of completing the square. If $\ \mathbf{v}\ $ is a solution of the equation $\ A\mathbf{v}=\mathbf{b}\ $ (in this case such a $\ \mathbf{v}=A^{-1}\mathbf{b}\ $ exists, because $\ A\ $ is invertible), then $$ g(\mathbf{x})={\small\frac{1}{2}}(\mathbf{x}-\mathbf{v})^TA(\mathbf{x}-\mathbf{v})+c-{\small\frac{1}{2}}\mathbf{v}^TA\mathbf{v}\ . $$ If $\ \mathbf{e}\ $ is an eigenvector of $\ A\ $ corresponding to a negative eigenvalue $\ \lambda\ $ (i.e. $\ A\mathbf{e}=\lambda\mathbf{e}\ $), and $\ \mathbf{x}=\mathbf{v}+t\mathbf{e}\ $, then $$ g(\mathbf{x})=\frac{\lambda t^2}{2}\mathbf{e}^T\mathbf{e}+c-{\small\frac{1}{2}}\mathbf{v}^TA\mathbf{v}\ , $$ and this can be made arbitrarily small by choosing $\ t\ $ arbitrarily large.

If you apply this to your particular problem, you should be able to find a line along which your $\ g(\mathbf{x})\ $ takes arbitrarily small values. I've given the answer below the spoiler fold.

For the particular $\ A\ $ you're given, $\begin{bmatrix}2&6\\ 6&2\end{bmatrix}\begin{bmatrix}1\\-1\end{bmatrix}=-4\begin{bmatrix}1\\-1\end{bmatrix}$, so $\ \lambda=-4\ $, and $\ \mathbf{e}=\begin{bmatrix}1\\-1\end{bmatrix}\ $ will do. $\ \begin{bmatrix}2&6\\ 6&2\end{bmatrix}\begin{bmatrix}\frac{5}{16}\\\frac{1}{16}\end{bmatrix}=\begin{bmatrix}1\\2\end{bmatrix}\ $, so $\ \mathbf{v}=\begin{bmatrix}\frac{5}{16}\\\frac{1}{16}\end{bmatrix}\ $. Along the line $\ \mathbf{x}=\begin{bmatrix}\frac{5}{16}+t\\\frac{1}{16}-t\end{bmatrix}\ $, therefore, the value of $\ g(\mathbf{x})\ $ is given by $\ g(\mathbf{x})=-4t^2+9-\frac{7}{32}=\frac{281}{32}-4t^2\ $.