[petsc-users] trust region/hook step equivalence

Smith, Barry F. bsmith at mcs.anl.gov
Thu May 9 12:56:19 CDT 2019

> On May 9, 2019, at 3:39 AM, Dave Lee via petsc-users <petsc-users at 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:
> 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.


> Cheers, Dave.

More information about the petsc-users mailing list