4
$\begingroup$

I can't seem to find the name of this method anywhere in literature, but it has appeared in my assignment.

Modified Newton Method. Let $f\in C^2$, convex, $\mathbb{R}^n\to\mathbb{R}$. The following method minimizes $f$.

Step 0: Given $x^0\in\mathbb{R}^n$, $\eta\in(0,1)$, $\rho, \sigma\in(0,1/2)$. $k:=0.$

Step 1: Solve $$\nabla f(x^k)+(\nabla^2f(x^k)+c\|\nabla f(x^k)\|I)d=0$$ with $c>0$ approximately to get an approximate solution $d^k$ such that $$\|\nabla f(x^k)+(\nabla^2f(x^k)+c\|\nabla f(x^k)\|I)d\|\leq \eta_k\|\nabla f(x^k)\|$$, where $\eta_k:=\min\{\eta,\|\nabla f(x^k)\|\}$. If $d^k$ does not satisfy $$<\nabla f(x^k),d^k>\leq -\eta_k\|d^k\|^2$$, let $d^k=-\nabla f(x^k)$.

Step 2: Let $m_k$ be the smallest non-negative integer $m$ such that $$f(x^k+\rho^md^k)-f(x^k)\leq \sigma \rho^m\nabla f(x^k)^Td^k$$ Set $t_k:=\rho^{m_k}$ and $x^{k+1}:=x^k+t_kd^k$.

Step 3: Replace $k$ by $k+1$ and go to Step 1.

I understand that it is a line search method, there $t_k$ is the step length and $d^k$ is the direction. Also, Step 2 tells us that the step length satisfies the sufficient decrease condition of the Wolfe condition.

I am trying to answer the following question:

How does one show that any accumulation point of $\{x^k\}$ is a solution to $\min f(x)$?

What is the name of this method?

If $\nabla^2f(x^*)$ is positive definite, prove superlinear convergence.

I will be placing a bounty on this question =) I only seek an answer to one of the above questions.

$\endgroup$
  • $\begingroup$ a "T" appears in several of the formulas without any explanation? $\endgroup$ – Brian Borchers Oct 27 '16 at 4:26
  • $\begingroup$ Probably a typo, I have edited it away. It should be I, the identity matrix. $\endgroup$ – Yellow Skies Oct 27 '16 at 5:25
  • 2
    $\begingroup$ It just blends Newton direction with steepest descent direction as a form of regulation. Not sure if there are much theory. It is more a ad hoc fix for non positive definite hessian, similar to (but not that sophisticated as) trust region techniques. Convergence follows from the general results about descent / gradient methods. $\endgroup$ – user251257 Oct 31 '16 at 2:09

Your Answer

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

Browse other questions tagged or ask your own question.