0
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ $f(x_1,...,x_)=(x_1^2+...+x_n^2)^{\frac p 2}$ $\endgroup$ – azarel Feb 8 '12 at 4:59
1
$\begingroup$

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}$.

$\endgroup$
  • $\begingroup$ Thanks Nick. I see where this is going. But I have another question: is it easy to get inverse of the Hessian? $\endgroup$ – SeeBees Feb 8 '12 at 5:44
  • $\begingroup$ 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>. $\endgroup$ – user14717 Feb 8 '12 at 5:47
  • $\begingroup$ But if I want to compute $H^{-1} * g$, where $H$ is the Hessian and $g$ is the gradient, would there be easy way? $\endgroup$ – SeeBees Feb 8 '12 at 5:54
  • 1
    $\begingroup$ Hit both sides with $H$ then use Cholesky decomposition to solve the resulting system. $\endgroup$ – user14717 Feb 8 '12 at 7:34
  • $\begingroup$ @SeeBees: Take a look at Pearlmutter and Schraudolph's work on the R technique that approximates exactly that in linear time. $\endgroup$ – Neil G Oct 31 '14 at 12:11
1
$\begingroup$

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.)

$\endgroup$
  • $\begingroup$ Thanks. Is there any good tutorial on matrix calculus? I'm unfamiliar with basic rules. $\endgroup$ – SeeBees Feb 9 '12 at 20:14
  • $\begingroup$ @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 :-) $\endgroup$ – joriki Feb 9 '12 at 20:24
0
$\begingroup$

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.

$\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.