1
$\begingroup$

so I'm dealing with the next problem: Let$\ \Phi(x) = \frac{1}{2}x^TAx - x^Tb$ where A is positive definite matrix. Prove that $\nabla\Phi = Ax - b$ and that minimum of $\Phi$ is $A^{-1}b$ on whole $\mathbb{R}^n$.

I really don't know how determine the gradient. I do know I have to prove that $\Phi(A^{-1}b)<\Phi(x),\ \forall x\in\mathbb{R}^n,x\neq A^{-1}b$.

Any suggestion would be appreciated.

Thanks.

$\endgroup$
  • $\begingroup$ What is the sufficent and necessary condition that minimas have/needs? Gradient: You can write it as <x,Ax>+<b,x> were <.,.> is the standard scalar product, and go from there. $\endgroup$ – user160069 May 4 '17 at 17:54
2
$\begingroup$

When in doubt about matrix calculus, just go to the basics.

$$x^TAx=\sum_{i}x_i\sum_{j}a_{ij}x_j=\sum_{i,j}x_ia_{ij}x_j.$$

Now proceed to calculate the gradient. For example $\partial_i$ would give:

$$\partial_k (x^TAx)=\sum_{j\neq k}a_{kj}x_j+\sum_{i\neq k}a_{ik}x_k+2a_{kk}x_i=\sum_{j=1}^na_{kj}x_j+\sum_{i=1}^na_{ik}x_k.$$

Notice that the r.h.s. is equivalent to $[Ax]_k+[x^TA]_k=[Ax]_k+[A^Tx]_k,$ (since transposes of vectors don't affect the $k$'th coefficient).

So, the full gradient is $x^T(A+A^T)$ (to make it a row vector). Since $A$ is symmetric, $A=A^T$, which will simplify it.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.