Actual source code: tr.c

petsc-master 2019-11-16
Report Typos and Errors

  2:  #include <../src/snes/impls/tr/trimpl.h>

  4: typedef struct {
  5:   SNES           snes;
  6:   /*  Information on the regular SNES convergence test; which may have been user provided */
  7:   PetscErrorCode (*convtest)(KSP,PetscInt,PetscReal,KSPConvergedReason*,void*);
  8:   PetscErrorCode (*convdestroy)(void*);
  9:   void           *convctx;
 10: } SNES_TR_KSPConverged_Ctx;

 12: static PetscErrorCode SNESTR_KSPConverged_Private(KSP ksp,PetscInt n,PetscReal rnorm,KSPConvergedReason *reason,void *cctx)
 13: {
 14:   SNES_TR_KSPConverged_Ctx *ctx = (SNES_TR_KSPConverged_Ctx*)cctx;
 15:   SNES                     snes = ctx->snes;
 16:   SNES_NEWTONTR            *neP = (SNES_NEWTONTR*)snes->data;
 17:   Vec                      x;
 18:   PetscReal                nrm;
 19:   PetscErrorCode           ierr;

 22:   (*ctx->convtest)(ksp,n,rnorm,reason,ctx->convctx);
 23:   if (*reason) {
 24:     PetscInfo2(snes,"Default or user provided convergence test KSP iterations=%D, rnorm=%g\n",n,(double)rnorm);
 25:   }
 26:   /* Determine norm of solution */
 27:   KSPBuildSolution(ksp,0,&x);
 28:   VecNorm(x,NORM_2,&nrm);
 29:   if (nrm >= neP->delta) {
 30:     PetscInfo2(snes,"Ending linear iteration early, delta=%g, length=%g\n",(double)neP->delta,(double)nrm);
 31:     *reason = KSP_CONVERGED_STEP_LENGTH;
 32:   }
 33:   return(0);
 34: }

 36: static PetscErrorCode SNESTR_KSPConverged_Destroy(void *cctx)
 37: {
 38:   SNES_TR_KSPConverged_Ctx *ctx = (SNES_TR_KSPConverged_Ctx*)cctx;
 39:   PetscErrorCode           ierr;

 42:   (*ctx->convdestroy)(ctx->convctx);
 43:   PetscFree(ctx);
 44:   return(0);
 45: }

 47: /* ---------------------------------------------------------------- */
 48: /*
 49:    SNESTR_Converged_Private -test convergence JUST for
 50:    the trust region tolerance.

 52: */
 53: static PetscErrorCode SNESTR_Converged_Private(SNES snes,PetscInt it,PetscReal xnorm,PetscReal pnorm,PetscReal fnorm,SNESConvergedReason *reason,void *dummy)
 54: {
 55:   SNES_NEWTONTR  *neP = (SNES_NEWTONTR*)snes->data;

 59:   *reason = SNES_CONVERGED_ITERATING;
 60:   if (neP->delta < xnorm * snes->deltatol) {
 61:     PetscInfo3(snes,"Converged due to trust region param %g<%g*%g\n",(double)neP->delta,(double)xnorm,(double)snes->deltatol);
 62:     *reason = SNES_DIVERGED_TR_DELTA;
 63:   } else if (snes->nfuncs >= snes->max_funcs && snes->max_funcs >= 0) {
 64:     PetscInfo1(snes,"Exceeded maximum number of function evaluations: %D\n",snes->max_funcs);
 65:     *reason = SNES_DIVERGED_FUNCTION_COUNT;
 66:   }
 67:   return(0);
 68: }

 70: /*@C
 71:    SNESNewtonTRSetPreCheck - Sets a user function that is called before the search step has been determined. 
 72:        Allows the user a chance to change or override the decision of the line search routine.

 74:    Logically Collective on snes

 76:    Input Parameters:
 77: +  snes - the nonlinear solver object
 78: .  func - [optional] function evaluation routine, see SNESNewtonTRPreCheck()  for the calling sequence
 79: -  ctx  - [optional] user-defined context for private data for the function evaluation routine (may be NULL)

 81:    Level: intermediate

 83:    Note: This function is called BEFORE the function evaluation within the SNESNEWTONTR solver.

 85: .seealso: SNESNewtonTRPreCheck(), SNESNewtonTRGetPreCheck(), SNESNewtonTRSetPostCheck(), SNESNewtonTRGetPostCheck()
 86: @*/
 87: PetscErrorCode  SNESNewtonTRSetPreCheck(SNES snes, PetscErrorCode (*func)(SNES,Vec,Vec,PetscBool*,void*),void *ctx)
 88: {
 89:   SNES_NEWTONTR  *tr = (SNES_NEWTONTR*)snes->data;

 93:   if (func) tr->precheck    = func;
 94:   if (ctx)  tr->precheckctx = ctx;
 95:   return(0);
 96: }

 98: /*@C
 99:    SNESNewtonTRGetPreCheck - Gets the pre-check function

101:    Not collective

103:    Input Parameter:
104: .  snes - the nonlinear solver context

106:    Output Parameters:
107: +  func - [optional] function evaluation routine, see for the calling sequence SNESNewtonTRPreCheck()
108: -  ctx  - [optional] user-defined context for private data for the function evaluation routine (may be NULL)

110:    Level: intermediate

112: .seealso: SNESNewtonTRSetPreCheck(), SNESNewtonTRPreCheck()
113: @*/
114: PetscErrorCode  SNESNewtonTRGetPreCheck(SNES snes, PetscErrorCode (**func)(SNES,Vec,Vec,PetscBool*,void*),void **ctx)
115: {
116:   SNES_NEWTONTR  *tr = (SNES_NEWTONTR*)snes->data;

120:   if (func) *func = tr->precheck;
121:   if (ctx)  *ctx  = tr->precheckctx;
122:   return(0);
123: }

125: /*@C
126:    SNESNewtonTRSetPostCheck - Sets a user function that is called after the search step has been determined but before the next 
127:        function evaluation. Allows the user a chance to change or override the decision of the line search routine

129:    Logically Collective on snes

131:    Input Parameters:
132: +  snes - the nonlinear solver object
133: .  func - [optional] function evaluation routine, see SNESNewtonTRPostCheck()  for the calling sequence
134: -  ctx  - [optional] user-defined context for private data for the function evaluation routine (may be NULL)

136:    Level: intermediate

138:    Note: This function is called BEFORE the function evaluation within the SNESNEWTONTR solver while the function set in
139:    SNESLineSearchSetPostCheck() is called AFTER the function evaluation.

141: .seealso: SNESNewtonTRPostCheck(), SNESNewtonTRGetPostCheck()
142: @*/
143: PetscErrorCode  SNESNewtonTRSetPostCheck(SNES snes, PetscErrorCode (*func)(SNES,Vec,Vec,Vec,PetscBool*,PetscBool*,void*),void *ctx)
144: {
145:   SNES_NEWTONTR  *tr = (SNES_NEWTONTR*)snes->data;

149:   if (func) tr->postcheck    = func;
150:   if (ctx)  tr->postcheckctx = ctx;
151:   return(0);
152: }

154: /*@C
155:    SNESNewtonTRGetPostCheck - Gets the post-check function

157:    Not collective

159:    Input Parameter:
160: .  snes - the nonlinear solver context

162:    Output Parameters:
163: +  func - [optional] function evaluation routine, see for the calling sequence SNESNewtonTRPostCheck()
164: -  ctx  - [optional] user-defined context for private data for the function evaluation routine (may be NULL)

166:    Level: intermediate

168: .seealso: SNESNewtonTRSetPostCheck(), SNESNewtonTRPostCheck()
169: @*/
170: PetscErrorCode  SNESNewtonTRGetPostCheck(SNES snes, PetscErrorCode (**func)(SNES,Vec,Vec,Vec,PetscBool*,PetscBool*,void*),void **ctx)
171: {
172:   SNES_NEWTONTR  *tr = (SNES_NEWTONTR*)snes->data;

176:   if (func) *func = tr->postcheck;
177:   if (ctx)  *ctx  = tr->postcheckctx;
178:   return(0);
179: }

181: /*@C
182:    SNESNewtonTRPreCheck - Called before the step has been determined in SNESNEWTONTR 

184:    Logically Collective on snes

186:    Input Parameters:
187: +  snes - the solver
188: .  X - The last solution
189: -  Y - The step direction

191:    Output Parameters:
192: .  changed_Y - Indicator that the step direction Y has been changed.

194:    Level: developer

196: .seealso: SNESNewtonTRSetPreCheck(), SNESNewtonTRGetPreCheck()
197: @*/
198: static PetscErrorCode SNESNewtonTRPreCheck(SNES snes,Vec X,Vec Y,PetscBool *changed_Y)
199: {
200:   SNES_NEWTONTR  *tr = (SNES_NEWTONTR*)snes->data;

204:   *changed_Y = PETSC_FALSE;
205:   if (tr->precheck) {
206:     (*tr->precheck)(snes,X,Y,changed_Y,tr->precheckctx);
208:   }
209:   return(0);
210: }

212: /*@C
213:    SNESNewtonTRPostCheck - Called after the step has been determined in SNESNEWTONTR but before the function evaluation

215:    Logically Collective on snes

217:    Input Parameters:
218: +  snes - the solver.  X - The last solution
219: .  Y - The full step direction
220: -  W - The updated solution, W = X - Y

222:    Output Parameters:
223: +  changed_Y - indicator if step has been changed
224: -  changed_W - Indicator if the new candidate solution W has been changed.

226:    Notes:
227:      If Y is changed then W is recomputed as X - Y

229:    Level: developer

231: .seealso: SNESNewtonTRSetPostCheck(), SNESNewtonTRGetPostCheck()
232: @*/
233: static PetscErrorCode SNESNewtonTRPostCheck(SNES snes,Vec X,Vec Y,Vec W,PetscBool *changed_Y,PetscBool *changed_W)
234: {
235:   SNES_NEWTONTR  *tr = (SNES_NEWTONTR*)snes->data;

239:   *changed_Y = PETSC_FALSE;
240:   *changed_W = PETSC_FALSE;
241:   if (tr->postcheck) {
242:     (*tr->postcheck)(snes,X,Y,W,changed_Y,changed_W,tr->postcheckctx);
245:   }
246:   return(0);
247: }

249: /*
250:    SNESSolve_NEWTONTR - Implements Newton's Method with a very simple trust
251:    region approach for solving systems of nonlinear equations.


254: */
255: static PetscErrorCode SNESSolve_NEWTONTR(SNES snes)
256: {
257:   SNES_NEWTONTR            *neP = (SNES_NEWTONTR*)snes->data;
258:   Vec                      X,F,Y,G,Ytmp,W;
259:   PetscErrorCode           ierr;
260:   PetscInt                 maxits,i,lits;
261:   PetscReal                rho,fnorm,gnorm,gpnorm,xnorm=0,delta,nrm,ynorm,norm1;
262:   PetscScalar              cnorm;
263:   KSP                      ksp;
264:   SNESConvergedReason      reason = SNES_CONVERGED_ITERATING;
265:   PetscBool                breakout = PETSC_FALSE;
266:   SNES_TR_KSPConverged_Ctx *ctx;
267:   PetscErrorCode           (*convtest)(KSP,PetscInt,PetscReal,KSPConvergedReason*,void*);

270:   if (snes->xl || snes->xu || snes->ops->computevariablebounds) SETERRQ1(PetscObjectComm((PetscObject)snes),PETSC_ERR_ARG_WRONGSTATE, "SNES solver %s does not support bounds", ((PetscObject)snes)->type_name);

272:   maxits = snes->max_its;               /* maximum number of iterations */
273:   X      = snes->vec_sol;               /* solution vector */
274:   F      = snes->vec_func;              /* residual vector */
275:   Y      = snes->work[0];               /* work vectors */
276:   G      = snes->work[1];
277:   Ytmp   = snes->work[2];
278:   W      = snes->work[3];

280:   PetscObjectSAWsTakeAccess((PetscObject)snes);
281:   snes->iter = 0;
282:   PetscObjectSAWsGrantAccess((PetscObject)snes);

284:   /* Set the linear stopping criteria to use the More' trick. */
285:   SNESGetKSP(snes,&ksp);
286:   KSPGetConvergenceTest(ksp,&convtest,NULL,NULL);
287:   if (convtest != SNESTR_KSPConverged_Private) {
288:     PetscNew(&ctx);
289:     ctx->snes             = snes;
290:     KSPGetAndClearConvergenceTest(ksp,&ctx->convtest,&ctx->convctx,&ctx->convdestroy);
291:     KSPSetConvergenceTest(ksp,SNESTR_KSPConverged_Private,ctx,SNESTR_KSPConverged_Destroy);
292:     PetscInfo(snes,"Using Krylov convergence test SNESTR_KSPConverged_Private\n");
293:   }

295:   if (!snes->vec_func_init_set) {
296:     SNESComputeFunction(snes,X,F);          /* F(X) */
297:   } else snes->vec_func_init_set = PETSC_FALSE;

299:   VecNorm(F,NORM_2,&fnorm);             /* fnorm <- || F || */
300:   SNESCheckFunctionNorm(snes,fnorm);
301:   VecNorm(X,NORM_2,&xnorm);             /* fnorm <- || F || */
302:   PetscObjectSAWsTakeAccess((PetscObject)snes);
303:   snes->norm = fnorm;
304:   PetscObjectSAWsGrantAccess((PetscObject)snes);
305:   delta      = xnorm ? neP->delta0*xnorm : neP->delta0;
306:   neP->delta = delta;
307:   SNESLogConvergenceHistory(snes,fnorm,0);
308:   SNESMonitor(snes,0,fnorm);

310:   /* test convergence */
311:   (*snes->ops->converged)(snes,snes->iter,0.0,0.0,fnorm,&snes->reason,snes->cnvP);
312:   if (snes->reason) return(0);


315:   for (i=0; i<maxits; i++) {

317:     /* Call general purpose update function */
318:     if (snes->ops->update) {
319:       (*snes->ops->update)(snes, snes->iter);
320:     }

322:     /* Solve J Y = F, where J is Jacobian matrix */
323:     SNESComputeJacobian(snes,X,snes->jacobian,snes->jacobian_pre);
324:     SNESCheckJacobianDomainerror(snes);
325:     KSPSetOperators(snes->ksp,snes->jacobian,snes->jacobian_pre);
326:     KSPSolve(snes->ksp,F,Ytmp);
327:     KSPGetIterationNumber(snes->ksp,&lits);

329:     snes->linear_its += lits;

331:     PetscInfo2(snes,"iter=%D, linear solve iterations=%D\n",snes->iter,lits);
332:     VecNorm(Ytmp,NORM_2,&nrm);
333:     norm1 = nrm;
334:     while (1) {
335:       PetscBool changed_y;
336:       PetscBool changed_w;
337:       VecCopy(Ytmp,Y);
338:       nrm  = norm1;

340:       /* Scale Y if need be and predict new value of F norm */
341:       if (nrm >= delta) {
342:         nrm    = delta/nrm;
343:         gpnorm = (1.0 - nrm)*fnorm;
344:         cnorm  = nrm;
345:         PetscInfo1(snes,"Scaling direction by %g\n",(double)nrm);
346:         VecScale(Y,cnorm);
347:         nrm    = gpnorm;
348:         ynorm  = delta;
349:       } else {
350:         gpnorm = 0.0;
351:         PetscInfo(snes,"Direction is in Trust Region\n");
352:         ynorm  = nrm;
353:       }
354:       /* PreCheck() allows for updates to Y prior to W <- X - Y */
355:       SNESNewtonTRPreCheck(snes,X,Y,&changed_y);
356:       VecWAXPY(W,-1.0,Y,X);         /* W <- X - Y */
357:       SNESNewtonTRPostCheck(snes,X,Y,W,&changed_y,&changed_w);
358:       if (changed_y) VecWAXPY(W,-1.0,Y,X);
359:       VecCopy(Y,snes->vec_sol_update);
360:       SNESComputeFunction(snes,W,G); /*  F(X) */
361:       VecNorm(G,NORM_2,&gnorm);      /* gnorm <- || g || */
362:       SNESCheckFunctionNorm(snes,gnorm);
363:       if (fnorm == gpnorm) rho = 0.0;
364:       else rho = (fnorm*fnorm - gnorm*gnorm)/(fnorm*fnorm - gpnorm*gpnorm);

366:       /* Update size of trust region */
367:       if      (rho < neP->mu)  delta *= neP->delta1;
368:       else if (rho < neP->eta) delta *= neP->delta2;
369:       else                     delta *= neP->delta3;
370:       PetscInfo3(snes,"fnorm=%g, gnorm=%g, ynorm=%g\n",(double)fnorm,(double)gnorm,(double)ynorm);
371:       PetscInfo3(snes,"gpred=%g, rho=%g, delta=%g\n",(double)gpnorm,(double)rho,(double)delta);

373:       neP->delta = delta;
374:       if (rho > neP->sigma) break;
375:       PetscInfo(snes,"Trying again in smaller region\n");
376:       /* check to see if progress is hopeless */
377:       neP->itflag = PETSC_FALSE;
378:       SNESTR_Converged_Private(snes,snes->iter,xnorm,ynorm,fnorm,&reason,snes->cnvP);
379:       if (!reason) {(*snes->ops->converged)(snes,snes->iter,xnorm,ynorm,fnorm,&reason,snes->cnvP);}
380:       if (reason == SNES_CONVERGED_SNORM_RELATIVE) reason = SNES_DIVERGED_INNER;
381:       if (reason) {
382:         /* We're not progressing, so return with the current iterate */
383:         SNESMonitor(snes,i+1,fnorm);
384:         breakout = PETSC_TRUE;
385:         break;
386:       }
387:       snes->numFailures++;
388:     }
389:     if (!breakout) {
390:       /* Update function and solution vectors */
391:       fnorm = gnorm;
392:       VecCopy(G,F);
393:       VecCopy(W,X);
394:       /* Monitor convergence */
395:       PetscObjectSAWsTakeAccess((PetscObject)snes);
396:       snes->iter = i+1;
397:       snes->norm = fnorm;
398:       snes->xnorm = xnorm;
399:       snes->ynorm = ynorm;
400:       PetscObjectSAWsGrantAccess((PetscObject)snes);
401:       SNESLogConvergenceHistory(snes,snes->norm,lits);
402:       SNESMonitor(snes,snes->iter,snes->norm);
403:       /* Test for convergence, xnorm = || X || */
404:       neP->itflag = PETSC_TRUE;
405:       if (snes->ops->converged != SNESConvergedSkip) { VecNorm(X,NORM_2,&xnorm); }
406:       (*snes->ops->converged)(snes,snes->iter,xnorm,ynorm,fnorm,&reason,snes->cnvP);
407:       if (reason) break;
408:     } else break;
409:   }
410:   if (i == maxits) {
411:     PetscInfo1(snes,"Maximum number of iterations has been reached: %D\n",maxits);
412:     if (!reason) reason = SNES_DIVERGED_MAX_IT;
413:   }
414:   PetscObjectSAWsTakeAccess((PetscObject)snes);
415:   snes->reason = reason;
416:   PetscObjectSAWsGrantAccess((PetscObject)snes);
417:   return(0);
418: }
419: /*------------------------------------------------------------*/
420: static PetscErrorCode SNESSetUp_NEWTONTR(SNES snes)
421: {

425:   SNESSetWorkVecs(snes,4);
426:   SNESSetUpMatrices(snes);
427:   return(0);
428: }

430: PetscErrorCode SNESReset_NEWTONTR(SNES snes)
431: {

434:   return(0);
435: }

437: static PetscErrorCode SNESDestroy_NEWTONTR(SNES snes)
438: {

442:   SNESReset_NEWTONTR(snes);
443:   PetscFree(snes->data);
444:   return(0);
445: }
446: /*------------------------------------------------------------*/

448: static PetscErrorCode SNESSetFromOptions_NEWTONTR(PetscOptionItems *PetscOptionsObject,SNES snes)
449: {
450:   SNES_NEWTONTR  *ctx = (SNES_NEWTONTR*)snes->data;

454:   PetscOptionsHead(PetscOptionsObject,"SNES trust region options for nonlinear equations");
455:   PetscOptionsReal("-snes_trtol","Trust region tolerance","SNESSetTrustRegionTolerance",snes->deltatol,&snes->deltatol,NULL);
456:   PetscOptionsReal("-snes_tr_mu","mu","None",ctx->mu,&ctx->mu,NULL);
457:   PetscOptionsReal("-snes_tr_eta","eta","None",ctx->eta,&ctx->eta,NULL);
458:   PetscOptionsReal("-snes_tr_sigma","sigma","None",ctx->sigma,&ctx->sigma,NULL);
459:   PetscOptionsReal("-snes_tr_delta0","delta0","None",ctx->delta0,&ctx->delta0,NULL);
460:   PetscOptionsReal("-snes_tr_delta1","delta1","None",ctx->delta1,&ctx->delta1,NULL);
461:   PetscOptionsReal("-snes_tr_delta2","delta2","None",ctx->delta2,&ctx->delta2,NULL);
462:   PetscOptionsReal("-snes_tr_delta3","delta3","None",ctx->delta3,&ctx->delta3,NULL);
463:   PetscOptionsTail();
464:   return(0);
465: }

467: static PetscErrorCode SNESView_NEWTONTR(SNES snes,PetscViewer viewer)
468: {
469:   SNES_NEWTONTR  *tr = (SNES_NEWTONTR*)snes->data;
471:   PetscBool      iascii;

474:   PetscObjectTypeCompare((PetscObject)viewer,PETSCVIEWERASCII,&iascii);
475:   if (iascii) {
476:     PetscViewerASCIIPrintf(viewer,"  Trust region tolerance (-snes_trtol)\n",(double)snes->deltatol);
477:     PetscViewerASCIIPrintf(viewer,"  mu=%g, eta=%g, sigma=%g\n",(double)tr->mu,(double)tr->eta,(double)tr->sigma);
478:     PetscViewerASCIIPrintf(viewer,"  delta0=%g, delta1=%g, delta2=%g, delta3=%g\n",(double)tr->delta0,(double)tr->delta1,(double)tr->delta2,(double)tr->delta3);
479:   }
480:   return(0);
481: }
482: /* ------------------------------------------------------------ */
483: /*MC
484:       SNESNEWTONTR - Newton based nonlinear solver that uses a trust region

486:    Options Database:
487: +    -snes_trtol <tol> - trust region tolerance
488: .    -snes_tr_mu <mu> - trust region parameter
489: .    -snes_tr_eta <eta> - trust region parameter
490: .    -snes_tr_sigma <sigma> - trust region parameter
491: .    -snes_tr_delta0 <delta0> -  initial size of the trust region is delta0*norm2(x)
492: .    -snes_tr_delta1 <delta1> - trust region parameter
493: .    -snes_tr_delta2 <delta2> - trust region parameter
494: -    -snes_tr_delta3 <delta3> - trust region parameter

496:    The basic algorithm is taken from "The Minpack Project", by More',
497:    Sorensen, Garbow, Hillstrom, pages 88-111 of "Sources and Development
498:    of Mathematical Software", Wayne Cowell, editor.

500:    Level: intermediate

502: .seealso:  SNESCreate(), SNES, SNESSetType(), SNESNEWTONLS, SNESSetTrustRegionTolerance()

504: M*/
505: PETSC_EXTERN PetscErrorCode SNESCreate_NEWTONTR(SNES snes)
506: {
507:   SNES_NEWTONTR  *neP;

511:   snes->ops->setup          = SNESSetUp_NEWTONTR;
512:   snes->ops->solve          = SNESSolve_NEWTONTR;
513:   snes->ops->destroy        = SNESDestroy_NEWTONTR;
514:   snes->ops->setfromoptions = SNESSetFromOptions_NEWTONTR;
515:   snes->ops->view           = SNESView_NEWTONTR;
516:   snes->ops->reset          = SNESReset_NEWTONTR;

518:   snes->usesksp = PETSC_TRUE;
519:   snes->usesnpc = PETSC_FALSE;

521:   snes->alwayscomputesfinalresidual = PETSC_TRUE;

523:   PetscNewLog(snes,&neP);
524:   snes->data  = (void*)neP;
525:   neP->mu     = 0.25;
526:   neP->eta    = 0.75;
527:   neP->delta  = 0.0;
528:   neP->delta0 = 0.2;
529:   neP->delta1 = 0.3;
530:   neP->delta2 = 0.75;
531:   neP->delta3 = 2.0;
532:   neP->sigma  = 0.0001;
533:   neP->itflag = PETSC_FALSE;
534:   neP->rnorm0 = 0.0;
535:   neP->ttol   = 0.0;
536:   return(0);
537: }