7
$\begingroup$

We are working on the solution of large non-linear PDE (say the Navier-Stokes equation) which we solve using Newton's method with an analytical formulation of the jacobian. For very large systems, we are interested in optimally choosing the tolerance of our iterative linear solver to maximise our use of the Newton's method quadratic convergence rate, while ensuring that we do not oversolve each linear system. I have read that a good approach to achieve this is the Eisenstat-Walker method which is described in the following paper: https://epubs.siam.org/doi/10.1137/0917003

However, even after reading through the paper, I am unable to clearly identify the algorithm to implement. My math knowledge on this type of analysis is limited.

The algorithm (that I think is the one we would need) is : enter image description here

So my understanding of this is difficult. In the case of the newton method, $s_k$ should always be equal to one if we do a full step? How then do we chose the initial tolerance? And I am unsure on to chose $\theta$ within the given interval?

I really am unsure how to translate the results of this article, which are very interesting for our applications, into a clear algorithm...

Improve this question
$\endgroup$

1 Answer 1

Reset to default
8
+50
$\begingroup$

$s_k$ is the "approximate Newton" search direction. So in essence, when they say

Choose $s_k$ such that $\|F(x_k)+F'(x_k)s_k\| \le \eta_k \|F(x_k)\|$

they are saying: Solve the Newton system $F'(x_k)s_k = - F(x_k)$ inexactly for $s_k$ until the norm of the residual $F(x_k)+F'(x_k)s_k$ is smaller than the norm of the right hand side $-F(x_k)$ by a factor of $\eta_k$. The result of this is a search direction $s_k$ that approximates the exact Newton search direction.

The second step is simply a backtracking line search. It is a bit confusing because they use the same symbol $\eta_k$ again, but it has a different meaning. Maybe it is easier to read if we rewrote it as follows:

Set $\alpha_k = 1-\eta_k$. Choose a step length reduction factor $\theta$. Then iterate:

While $\|F(x_k+s_k)\| > \|F(x_k)\| - t\alpha_k\|F(x_k)\|$, do:

(1) Reduce the step by a factor of $\theta$: $s_k = \theta s_k$ (2) Reduce $\alpha_k$: $\alpha_k = \theta \alpha_k$.

The condition that is tested in the "while" loop is related to the "first Wolfe condition". It tests whether a step $s_k$ is acceptable, and if it is not, one "backtracks" to a point $x_k+\theta s_k$ closer to the current iterate $x_k$ until the condition indicates that this point is acceptable.

If (i) the quadratic model of $F$ on which Newton's method is built is accurate, and (ii) you solve the linear system exactly (i.e., if $s_k$ is the true Newton step), then you will be able to take a full step; in that case, the Wolfe condition will always be satisfied, and you never execute the body of the "while" loop.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Ahh I understand. This is much clearer. Is there any way to establish an optimal value for $\eta_k$ ? $\endgroup$
    – BlaB
    Commented Nov 21, 2019 at 6:16
  • $\begingroup$ Nocedal and Wright, in their excellent book on Numerical Optimization, have a discussion that if you make sure that $\eta_k\rightarrow 0$ as $k\rightarrow 0$, you can guarantee that the method guarantees with superlinear order. That is often good enough. They also prove that if $\eta_k$ goes to zero at least as fast as the residual $\|F(x_k)\|$ goes to zero, then you actually get quadratic convergence. I think that's what is usually referred to as the "Eisenstat Walker method". $\endgroup$
    – Wolfgang Bangerth
    Commented Nov 21, 2019 at 19:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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