Re: [petsc-users] trust region/hook step equivalence

[Smith, Barry F. via petsc-users]

> On May 9, 2019, at 3:39 AM, Dave Lee via petsc-users 
> <petsc-users@mcs.anl.gov> wrote:
> 
> Hi PETSc,
> 
> I'm using the SNES trust region to solve a matrix free Newton problem. I 
> can't see a lot of description of the trust region algorithm in the manual 
> (section 5.2.2), and have also found it difficult to find documentation on 
> the MINPACK project from which it is apparently derived. I have a couple of 
> questions about this:
> 
> 1) Is the PETSc SNES trust region algorithm the same as the "hook step" 
> algorithm detailed in Section 6.4.1 of Dennis and Schnabel (1996) "Numerical 
> methods for Unconstrained Optimization and Nonlinear Equations"?

   No. It is more naive than that. If the trust region is detected to be too 
big it does a simple backtracking until it gets a sufficient decrease in the 
function norm. The "true" trust region algorithms do something more clever than 
just back tracking along the Newton direction.

> 
> 2) Is there anywhere I can find specific documentation on the trust region 
> control parameters as defined in: 
> https://www.mcs.anl.gov/petsc/petsc-current/docs/manualpages/SNES/SNESNEWTONTR.html#SNESNEWTONTR

  You need to look at the code. It is in src/snes/impls/tr/tr.c It is very 
simple.


> 
> 3) My solve returns before it is sufficiently converged.

   Define sufficiently converged? The whole point of trust regions is that the 
nonlinear solver/optimization algorithm decides when to stop the linear solver, 
not your measure of the residual of the linear system. 

> On the last few Newton iterations the KSP converges due to:
> CONVERGED_STEP_LENGTH 
> after only a couple of KSP iterations. What is the default for this 
> parameter?, and how can I change it? Should I change it?

   The name is slightly confusing. This means the solver has reached the size 
of the trust region. To change this value means to change the size of the trust 
region. The initial size of the trust region is given by  delta0*norm2(x) (or 
delta0 if x == 0). See SNESNEWTONTR. You can control delta0 with 
-snes_tr_delta0 delta0. After you start the algorithm it automatically adjusts 
the size of the trust region making it bigger or smaller based on how well 
Newton is working. 

   Normally as Newton's method starts to converge well the trust region gets 
bigger and bigger (and hence the linear solver is solved more and more 
accurately). If the trust region doesn't grow it usually means something has 
gone wrong. 

   Note you can run with -info to see with more detail what decisions the trust 
region algorithm is making..

  I'm not sure I recommend you spend a lot of time on the trust region 
approach. The various line searches in PETSc are more robust and mature and if 
they fail you the trust region code is unlikely to save you.

   Barry


 
> 
> Cheers, Dave.