[petsc-users] Linesearch algorithm

[Jed Brown]

On Tue, May 15, 2012 at 2:41 PM, behzad baghapour <
behzad.baghapour at gmail.com> wrote:

> Thanks. Of course, the Line-search just change the step length. But I
> could not get What you mean that the residual must be increased before
> reaching the steady-state?


This is the key to pseudotransient continuation's global convergence. If
steady state could be reached by simply minimizing the residual, then
steepest descent (and trust region Newton) would be globally convergent. It
would also render optimization research obsolete because nonlinear equation
solvers could naively be applied to the first order optimality conditions
without concern for the objective. Alas, it doesn't work that way: steady
state often cannot be reached without increasing the steady-state residual
and non-convex optimization problems require that the gradient be allowed
to increase.

This is perhaps easier to illustrate for the optimization case. Consider

f(x) = x^2 - exp(-4*(x-2)^2)

which is a nice-looking function with a single minimum very close to x=0.

http://www.wolframalpha.com/input/?i=x%5E2+-+exp%28-4*%28x-2%29%5E2%29

Now the gradient clearly has these local minima, so searching in the norm
of the gradient will get stuck at a point that is not a local minima.

http://www.wolframalpha.com/input/?i=diff%28x%5E2+-+exp%28-4*%28x-2%29%5E2%29%2Cx%29


For transient problems, there are lots of reasons that the residual may
need to grow before steady state can be reached. See, for example, Figure
3.1 and 3.2 of  http://www.cs.odu.edu/~keyes/papers/ptc03.pdf . Note that
the residual is not monotone. Although they do not prove it here, steady
state for these problems cannot be reached without hill climbing:
inherently transient processes like combustion must take place before a
steady state can be reached.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.mcs.anl.gov/pipermail/petsc-users/attachments/20120515/431b6427/attachment-0001.htm>