Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I'm wondering how to compute gradient and hessian for this function $$f(\textbf{x}) = ||\textbf{x}||_2^p$$, where $\textbf{x}$ is a vector and $p$ is a constant and $p>1$.

This is a homework question. As I'm unfamiliar with vector calculus which is the prerequisite of my class, I'm having a difficult time finding the solution. I'll appreciate it if you can give me reference to materials of vector calculus that helps finding the solution of this problem.

The original homework question is to perform Newton's method to minimize $f(x)$. So I'm thinking of computing gradient and Hessian. Any hints on the original question will be appreciated.

Thanks

share|improve this question
1  
$f(x_1,...,x_)=(x_1^2+...+x_n^2)^{\frac p 2}$ –  azarel Feb 8 '12 at 4:59

3 Answers 3

As $$ f(\mathbf{x}):=||\mathbf{x}||_{2}^{p}=\left(\sum_{i=1}^{n}x_{i}^{2}\right)^{p/2} $$ and $$ \nabla f(\mathbf{x}) := \left(\frac{\partial f}{\partial x_{1}},\frac{\partial f}{\partial x_{2}}, \ldots, \frac{\partial f }{\partial x_{n} } \right) $$ and noting that $$ \frac{\partial f}{\partial x_{j}} = \frac{p}{2}\left(\sum_{i=1}^{n} x_{i}^{2} \right)^{p/2-1}\cdot 2x_{j} =px_{j}||\mathbf{x}||_{2}^{p-2} $$ then $$ \nabla f(\mathbf{x})=p||\mathbf{x}||_{2}^{p-2}\left(x_{1},x_{2},\ldots, x_{n}\right) $$ As for the Hessian, $$ \nabla^{2}f := \begin{pmatrix} \frac{\partial^{2} f}{\partial x_{1}^{2}} & \frac{\partial^{2} f}{\partial x_{1} \partial_{x_{2}}} & \cdots &\frac{\partial^{2} f}{\partial x_{1}\partial_{x_{n}}} \\ \frac{\partial^{2} f}{\partial x_{2} \partial x_{1}} & \frac{\partial^{2} f}{\partial x_{2}^{2}} & \cdots & \frac{\partial^{2} f}{\partial x_{2}\partial_{x_{n}}} \\ \vdots & \vdots & \ddots & \vdots \\ \frac{\partial^{2} f}{\partial x_{n} \partial_{x_{1}}} & \frac{\partial^{2} f}{\partial x_{n} \partial_{x_{2}}} & \cdots & \frac{\partial^{2} f}{\partial x_{n}^{2}} \end{pmatrix} $$ so we consider two cases: The diagonal elements and off-diagonal elements. These entries are computed easily from standard rules of calculus; I'm too worn out to compute them explicitly.

A good book on vector calculus is Div, Grad, Curl, And All That: An Informal Text on Vector Calculus by H.M. Schey. Newton's Method in the multivariate case is a pretty straightforward generalization of the single-variable case, noting that $$ f(\mathbf{x}+\mathbf{h})\approx f(\mathbf{x})+\left<\nabla f(\mathbf{x}),\mathbf{h} \right> + \frac{1}{2}\left<\mathbf{h},\nabla^{2}f(\mathbf{x})\mathbf{h}\right> $$ where $\left<\cdot, \cdot\right>$ denotes the ordinary dot product on $\mathbb{R}^{n}$.

share|improve this answer
    
Thanks Nick. I see where this is going. But I have another question: is it easy to get inverse of the Hessian? –  SeeBees Feb 8 '12 at 5:44
    
Absolutely not. There are schemes for getting around having to invert the Hessian which I have forgot, I believe that can be found in Kendall Atkinson's book <em>Theoretical Numerical Analysis</em>. –  Nick Thompson Feb 8 '12 at 5:47
    
But if I want to compute $H^{-1} * g$, where $H$ is the Hessian and $g$ is the gradient, would there be easy way? –  SeeBees Feb 8 '12 at 5:54
1  
Hit both sides with $H$ then use Cholesky decomposition to solve the resulting system. –  Nick Thompson Feb 8 '12 at 7:34

The second derivatives are

$$\frac{\partial^2 f}{\partial x_i^2}=\frac{\partial}{\partial x_i}\left(px_i\left(\mathbf x^2\right)^{p/2-1}\right)=p\left(\left(\mathbf x^2\right)^{p/2-1}+(p-2)x_i^2\left(\mathbf x^2\right)^{p/2-2}\right)$$

and

$$\frac{\partial^2 f}{\partial x_i\partial x_j}=\frac{\partial}{\partial x_i}\left(px_j\left(\mathbf x^2\right)^{p/2-1}\right)=p(p-2)x_ix_j\left(\mathbf x^2\right)^{p/2-2}$$

for $i\ne j$, so the Hessian matrix $H$ is given by

$$H=p\left(\mathbf x^2\right)^{p/2-2}\left((\mathbf x^\top\mathbf x) I+(p-2)\mathbf x\mathbf x^\top\right)\;,$$

where $I$ is the identity matrix. Symmetry suggests that its inverse should then also be a linear combination of $I$ and $\mathbf x\mathbf x^\top$, and you can find it by using that as an ansatz and determining the coefficients of the linear combination from the condition that the product is the identity matrix. (You'll need to use $(\mathbf x\mathbf x^\top)(\mathbf x\mathbf x^\top)=\mathbf x(\mathbf x^\top\mathbf x)\mathbf x^\top=(\mathbf x^\top\mathbf x)\mathbf x\mathbf x^\top$ in the process.)

share|improve this answer
    
Thanks. Is there any good tutorial on matrix calculus? I'm unfamiliar with basic rules. –  SeeBees Feb 9 '12 at 20:14
    
@SeeBees: This isn't what I'd call matrix calculus (on which there is, by the way, a Wikipedia article). It's just calculus that leads to a matrix, and then inverting that matrix involves only ordinary matrix operations, not calculus. In case you mean that you're unfamiliar with the basic rules of matrix operations, this Wikipedia section might be a good place to start. I can't recommend any books because I learned linear algebra from a German book way back when :-) –  joriki Feb 9 '12 at 20:24

I was able to derive the gradient by the doing the following:

$f(\mathbf x) = (\mathbf x ^\top \mathbf x) ^{p/2}$

$f'(\mathbf x) = p/2 (\mathbf x^\top \mathbf x) ^{(p-2)/2} 2\mathbf x = p (\mathbf x^\top \mathbf x) ^{(p-2)/2} \mathbf x$

I'm wondering if this is what's called matrix calculus.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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