[petsc-users] trust region/hook step equivalence

[Smith, Barry F.]

   Dave,

     You could explore adding the "hook step" feature to the current TR code. We've never done it due to lack of resources and low priority for us but it is a completely reasonable thing to support.

    Barry


> On May 9, 2019, at 10:41 PM, Dave Lee <davelee2804 at gmail.com> wrote:
> 
> Thanks Barry,
> 
> I will try reducing the default -snes_tr_delta0 from 0.2 to 0.1, and also take a look at using the line search method as well.
> 
> The reason I wanted to use the trust region solver instead is that previous studies of my problem have used the "hook step" method, which I gather is more in line with the trust region method in that it first chooses a step size and then determines a direction for which convergence is ensured w.r.t. the step size, and not vice versa, as I gather is the case for the line search algorithm.
> 
> Thanks again, Dave.
> 
> 
> 
> On Fri, May 10, 2019 at 3:56 AM Smith, Barry F. <bsmith at mcs.anl.gov> wrote:
> 
> 
> > 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:
> > 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.
>