Any help with a Hessian Headache?

Question

Let $f(x) = \frac{1}{2}\langle Ax,x\rangle - \langle b,x \rangle + c$ with $A\in \mathbb{R}^{n\times n}$ and $b\in \mathbb{R}^n$, $c\in \mathbb{R}$. Assume that $A$ is symmetric and positive definite. Show that $f$ has a unique global minimum at some point $x_{*}$ and determine $f(x_{*})$ in terms of $A,b,c$.

---

So my idea was to show that $f$ is strongly convex. Then there would exist a unique global minimum for $f$.

I computed the gradient and the hessian of $f$:

$\nabla f(x)$ = \begin{bmatrix} \sum^{n}_{i=1}a_{1i}x_i + a_{11}\sum^{n}_{i=1}x_i + b_1 \\ \vdots \\ \sum^{n}_{i=1}a_{ni}x_i + a_{nn}\sum^{n}_{i=1}x_i + b_n \\ \end{bmatrix}

$D^2f|_x$ = \begin{bmatrix} a_{11}+a_{11} & a_{12}+a_{11}&.&.&.&.& a_{1n}+a_{11} \\ a_{21}+a_{22} & a_{21}+a_{22}&.&.&.&.& a_{2n}+a_{22} \\ \vdots \\ a_{n1}+a_{nn} & a_{n1}+a_{nn}&.&.&.&.& a_{nn}+a_{nn} \\ \end{bmatrix}

But I've been having a lot of trouble showing that $D^2f|_x$ is positive definite (if it even is). Does anyone have an hints for this problem.

Answer 1

$$ f(x) = \frac{1}{2}\sum_{ij}x_i A_{ij}x_j - \sum_i b_i x_i + c $$

The gradient has components

\begin{eqnarray} \frac{\partial f}{\partial x_\alpha} &=& \frac{1}{2}\sum_{ij}(x_iA_{ij}\delta_{\alpha j } + \delta_{\alpha i}A_{ij}x_j) - \sum_i b_i \delta_{\alpha i} \\ &=& \frac{1}{2}\sum_{i}x_i A_{i\alpha} + \frac{1}{2}\sum_{j}A_{\alpha j}x_j - b_\alpha \\ &=& \frac{1}{2} \sum_iA_{\alpha i} x_i + \frac{1}{2}\sum_i A_{\alpha i}x_i - b_\alpha = \sum_{i}A_{\alpha i}x_i - b_\alpha \\ &=& (Ax - b)_\alpha \end{eqnarray}

In other words

$$ \nabla f = Ax - b \tag{1} $$

As for the hessian

\begin{eqnarray} \frac{\partial^2 f}{\partial x_\alpha \partial x_\beta} &=& \sum_{i}A_{\alpha j}\delta_{\beta i} = A_{\alpha \beta} \end{eqnarray}

So the Hessian is

$$ Hf = A \tag{2} $$

From (1), the critical point is $x^* = A^{-1}b$, and is a minimum because $H$ is positive definite

Answer 2

Its easier to complete the square, but you can compute derivatives if you liked. You need to know the following identities (using that $A$ is symmetric positive definite): $$\nabla_x \langle b,x\rangle = b\\ \nabla_x \frac12\langle x,Ax \rangle\cdot h = \langle x,Ah\rangle = \langle h,Ax\rangle \\ \nabla^2_x\frac12 \langle x,Ax\rangle (h,v) = h^T A v = v^TAh = \langle h,Av\rangle $$ so the hessian is the constant matrix $A$ assumed to be positive definite.

Your computation seems to have a mistake, $$\partial _{x_i} \langle x,Ax \rangle = \partial_i (x_j A_{kj}x_k) = \delta_{ij} A_{kj}x_k + \delta_{ik} x_jA_{kj} = 2 Ax$$

---

Completing the square: Set $B^2 = A$ (exists by pos. def.). Then we have $\langle Ax,x\rangle = \|Bx\|^2$, $$ f(x) = \frac12 \langle Ax,x\rangle - \langle b,x\rangle + c= \frac 12 \|Bx-B^{-1}b\|^2+c -\frac12 \|B^{-1} b\|^2$$