7
$\begingroup$

In the newton optimization algorithm to find the local minimum $x^*$ of a non-linear function $f(x)$ with iteration sequence of $x_0 \rightarrow x_1 \rightarrow x_2 ... \rightarrow x^*$ all $\nabla ^2 f(x_k)$ should be pos. definite otherwise search direction might not be a descent direction. The solution to this problem is to use Hessian modification techniques.

I am looking for a simple function that has local minimum at $x^*$, but $\nabla ^2 f(x_k)$ is not positive definite, and hence the Newton algorithm fails. Then after using one of the Hessian modification techniques, Newton algorithm converges to $x^*$

$\endgroup$
5
  • $\begingroup$ $f(x) = -x^2$. ${}{}$ $\endgroup$
    – copper.hat
    Feb 2 '15 at 7:29
  • $\begingroup$ @copper.hat: Thanks! I mean a function that has actually local min, and Hessian modification techniques can be applied to make the Hessian matrix close to positive definite. $\endgroup$
    – ManiAm
    Feb 2 '15 at 7:34
  • $\begingroup$ You need to be more specific about what you are looking for in the question, otherwise it becomes rather frustrating to try and help. $\endgroup$
    – copper.hat
    Feb 2 '15 at 7:36
  • $\begingroup$ @copper.hat: ok. I edited my post. Thanks! $\endgroup$
    – ManiAm
    Feb 2 '15 at 7:41
  • $\begingroup$ $f(x) = x_1^2$ on $\mathbb{R}^2$? $\endgroup$
    – copper.hat
    Feb 2 '15 at 7:51
13
$\begingroup$

I found a good example:

$f(x_1,x_2)=(1.5-x_1+x_1*x_2)^2 + (2.25-x_1+x_1*x_2^2)^2 + (2.625-x_1+x_1*x_2^3)^2$

Dampted Newton method with starting point $x_0 = (4,1)^T$ fails. This is why:

$\nabla^2 f(x_0)= \left( \begin{matrix} 0 & 27.75 \\ 27.75 & 610 \\ \end{matrix} \right) $ and search direction is $p_0=-\nabla^2 f(x_0)*\nabla f(x_0)=(-4,0)^T$

The search direction is pointing to a wrong direction! and this is because Hessian matrix is not positive definite and thus $p_0$ is not in the descent direction.

enter image description here

After using the Hessian modification technique such as "adding a multiple of the identity", the algorithm works fine and the search direction points to the corect direction, and eventually finds the local minimum $(3,0.5)^T$

enter image description here

$\endgroup$
0
$\begingroup$

If the Hessian is negative-definite, then the direction is automatically ascent. Proof: if the Hessian is negative-definite, then its inverse exists and is also negative-definite. Newton's direction is $-[\nabla^2 f(x)]^{-1}(\nabla f)(x)$. Descent direction is $-(\nabla f)(x)$. Now the scalar multiplication of both is negative: $[(\nabla f)(x)]^{\text{T}}[\nabla^2 f(x)]^{-1}(\nabla f)(x)<0$. $\diamondsuit$

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