Actual source code: tr.c

petsc-master 2019-07-14
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_CONVERGED_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:    SNESNewtonTRSetPostCheck - Sets a user function that is called after the search step has been determined but before the next 
 72:        function evaluation. 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 SNESNewtonTRPostCheck()  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 evalaulation within the SNESNEWTONTR solver while the function set in
 84:    SNESLineSearchSetPostCheck() is called AFTER the function evaluation.

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

 94:   if (func) tr->postcheck    = func;
 95:   if (ctx)  tr->postcheckctx = ctx;
 96:   return(0);
 97: }

 99: /*@C
100:    SNESNewtonTRGetPostCheck - Gets the post-check function

102:    Not collective

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

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

111:    Level: intermediate

113: .seealso: SNESNewtonTRSetPostCheck(), SNESNewtonTRPostCheck()
114: @*/
115: PetscErrorCode  SNESNewtonTRGetPostCheck(SNES snes, PetscErrorCode (**func)(SNES,Vec,Vec,Vec,PetscBool*,void*),void **ctx)
116: {
117:   SNES_NEWTONTR  *tr = (SNES_NEWTONTR*)snes->data;

121:   if (func) *func = tr->postcheck;
122:   if (ctx)  *ctx  = tr->postcheckctx;
123:   return(0);
124: }

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

129:    Logically Collective on snes

131:    Input Parameters:
132: +  snes - the solver.  X - The last solution
133: .  Y - The full step direction
134: -  W - The updated solution, W = X + tao*Y for some tao

136:    Output Parameters:
137: .  changed_W - Indicator if the new candidate solution W has been changed.

139:    Notes:
140:      If Y is changed then W is recomputed as X + tao*Y where tao is the current update value in SNESNEWTONTR

142:    Level: developer

144: .seealso: SNESNewtonTRSetPostCheck(), SNESNewtonTRGetPostCheck()
145: @*/
146: static PetscErrorCode SNESNewtonTRPostCheck(SNES snes,Vec X,Vec Y,Vec W,PetscBool *changed_W)
147: {
148:   SNES_NEWTONTR  *tr = (SNES_NEWTONTR*)snes->data;

152:   *changed_W = PETSC_FALSE;
153:   if (tr->postcheck) {
154:     (*tr->postcheck)(snes,X,Y,W,changed_W,tr->postcheckctx);
156:   }
157:   return(0);
158: }

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


165: */
166: static PetscErrorCode SNESSolve_NEWTONTR(SNES snes)
167: {
168:   SNES_NEWTONTR            *neP = (SNES_NEWTONTR*)snes->data;
169:   Vec                      X,F,Y,G,Ytmp;
170:   PetscErrorCode           ierr;
171:   PetscInt                 maxits,i,lits;
172:   PetscReal                rho,fnorm,gnorm,gpnorm,xnorm=0,delta,nrm,ynorm,norm1;
173:   PetscScalar              cnorm;
174:   KSP                      ksp;
175:   SNESConvergedReason      reason = SNES_CONVERGED_ITERATING;
176:   PetscBool                breakout = PETSC_FALSE;
177:   SNES_TR_KSPConverged_Ctx *ctx;
178:   PetscErrorCode           (*convtest)(KSP,PetscInt,PetscReal,KSPConvergedReason*,void*);

181:   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);

183:   maxits = snes->max_its;               /* maximum number of iterations */
184:   X      = snes->vec_sol;               /* solution vector */
185:   F      = snes->vec_func;              /* residual vector */
186:   Y      = snes->work[0];               /* work vectors */
187:   G      = snes->work[1];
188:   Ytmp   = snes->work[2];

190:   PetscObjectSAWsTakeAccess((PetscObject)snes);
191:   snes->iter = 0;
192:   PetscObjectSAWsGrantAccess((PetscObject)snes);

194:   /* Set the linear stopping criteria to use the More' trick. */
195:   SNESGetKSP(snes,&ksp);
196:   KSPGetConvergenceTest(ksp,&convtest,NULL,NULL);
197:   if (convtest != SNESTR_KSPConverged_Private) {
198:     PetscNew(&ctx);
199:     ctx->snes             = snes;
200:     KSPGetAndClearConvergenceTest(ksp,&ctx->convtest,&ctx->convctx,&ctx->convdestroy);
201:     KSPSetConvergenceTest(ksp,SNESTR_KSPConverged_Private,ctx,SNESTR_KSPConverged_Destroy);
202:     PetscInfo(snes,"Using Krylov convergence test SNESTR_KSPConverged_Private\n");
203:   }

205:   if (!snes->vec_func_init_set) {
206:     SNESComputeFunction(snes,X,F);          /* F(X) */
207:   } else snes->vec_func_init_set = PETSC_FALSE;

209:   VecNorm(F,NORM_2,&fnorm);             /* fnorm <- || F || */
210:   SNESCheckFunctionNorm(snes,fnorm);
211:   VecNorm(X,NORM_2,&xnorm);             /* fnorm <- || F || */
212:   PetscObjectSAWsTakeAccess((PetscObject)snes);
213:   snes->norm = fnorm;
214:   PetscObjectSAWsGrantAccess((PetscObject)snes);
215:   delta      = xnorm ? neP->delta0*xnorm : neP->delta0;
216:   neP->delta = delta;
217:   SNESLogConvergenceHistory(snes,fnorm,0);
218:   SNESMonitor(snes,0,fnorm);

220:   /* test convergence */
221:   (*snes->ops->converged)(snes,snes->iter,0.0,0.0,fnorm,&snes->reason,snes->cnvP);
222:   if (snes->reason) return(0);


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

227:     /* Call general purpose update function */
228:     if (snes->ops->update) {
229:       (*snes->ops->update)(snes, snes->iter);
230:     }

232:     /* Solve J Y = F, where J is Jacobian matrix */
233:     SNESComputeJacobian(snes,X,snes->jacobian,snes->jacobian_pre);
234:     SNESCheckJacobianDomainerror(snes);
235:     KSPSetOperators(snes->ksp,snes->jacobian,snes->jacobian_pre);
236:     KSPSolve(snes->ksp,F,Ytmp);
237:     KSPGetIterationNumber(snes->ksp,&lits);

239:     snes->linear_its += lits;

241:     PetscInfo2(snes,"iter=%D, linear solve iterations=%D\n",snes->iter,lits);
242:     VecNorm(Ytmp,NORM_2,&nrm);
243:     norm1 = nrm;
244:     while (1) {
245:       PetscBool changed_w;
246:       VecCopy(Ytmp,Y);
247:       nrm  = norm1;

249:       /* Scale Y if need be and predict new value of F norm */
250:       if (nrm >= delta) {
251:         nrm    = delta/nrm;
252:         gpnorm = (1.0 - nrm)*fnorm;
253:         cnorm  = nrm;
254:         PetscInfo1(snes,"Scaling direction by %g\n",(double)nrm);
255:         VecScale(Y,cnorm);
256:         nrm    = gpnorm;
257:         ynorm  = delta;
258:       } else {
259:         gpnorm = 0.0;
260:         PetscInfo(snes,"Direction is in Trust Region\n");
261:         ynorm  = nrm;
262:       }
263:       VecCopy(Y,snes->vec_sol_update);
264:       VecAYPX(Y,-1.0,X);            /* Y <- X - Y */
265:       SNESNewtonTRPostCheck(snes,X,Ytmp,Y,&changed_w);
266:       SNESComputeFunction(snes,Y,G); /*  F(X) */
267:       VecNorm(G,NORM_2,&gnorm);      /* gnorm <- || g || */
268:       SNESCheckFunctionNorm(snes,gnorm);
269:       if (fnorm == gpnorm) rho = 0.0;
270:       else rho = (fnorm*fnorm - gnorm*gnorm)/(fnorm*fnorm - gpnorm*gpnorm);

272:       /* Update size of trust region */
273:       if      (rho < neP->mu)  delta *= neP->delta1;
274:       else if (rho < neP->eta) delta *= neP->delta2;
275:       else                     delta *= neP->delta3;
276:       PetscInfo3(snes,"fnorm=%g, gnorm=%g, ynorm=%g\n",(double)fnorm,(double)gnorm,(double)ynorm);
277:       PetscInfo3(snes,"gpred=%g, rho=%g, delta=%g\n",(double)gpnorm,(double)rho,(double)delta);

279:       neP->delta = delta;
280:       if (rho > neP->sigma) break;
281:       PetscInfo(snes,"Trying again in smaller region\n");
282:       /* check to see if progress is hopeless */
283:       neP->itflag = PETSC_FALSE;
284:       SNESTR_Converged_Private(snes,snes->iter,xnorm,ynorm,fnorm,&reason,snes->cnvP);
285:       if (!reason) {(*snes->ops->converged)(snes,snes->iter,xnorm,ynorm,fnorm,&reason,snes->cnvP);}
286:       if (reason == SNES_CONVERGED_SNORM_RELATIVE) reason = SNES_DIVERGED_INNER;
287:       if (reason) {
288:         /* We're not progressing, so return with the current iterate */
289:         SNESMonitor(snes,i+1,fnorm);
290:         breakout = PETSC_TRUE;
291:         break;
292:       }
293:       snes->numFailures++;
294:     }
295:     if (!breakout) {
296:       /* Update function and solution vectors */
297:       fnorm = gnorm;
298:       VecCopy(G,F);
299:       VecCopy(Y,X);
300:       /* Monitor convergence */
301:       PetscObjectSAWsTakeAccess((PetscObject)snes);
302:       snes->iter = i+1;
303:       snes->norm = fnorm;
304:       snes->xnorm = xnorm;
305:       snes->ynorm = ynorm;
306:       PetscObjectSAWsGrantAccess((PetscObject)snes);
307:       SNESLogConvergenceHistory(snes,snes->norm,lits);
308:       SNESMonitor(snes,snes->iter,snes->norm);
309:       /* Test for convergence, xnorm = || X || */
310:       neP->itflag = PETSC_TRUE;
311:       if (snes->ops->converged != SNESConvergedSkip) { VecNorm(X,NORM_2,&xnorm); }
312:       (*snes->ops->converged)(snes,snes->iter,xnorm,ynorm,fnorm,&reason,snes->cnvP);
313:       if (reason) break;
314:     } else break;
315:   }
316:   if (i == maxits) {
317:     PetscInfo1(snes,"Maximum number of iterations has been reached: %D\n",maxits);
318:     if (!reason) reason = SNES_DIVERGED_MAX_IT;
319:   }
320:   PetscObjectSAWsTakeAccess((PetscObject)snes);
321:   snes->reason = reason;
322:   PetscObjectSAWsGrantAccess((PetscObject)snes);
323:   return(0);
324: }
325: /*------------------------------------------------------------*/
326: static PetscErrorCode SNESSetUp_NEWTONTR(SNES snes)
327: {

331:   SNESSetWorkVecs(snes,3);
332:   SNESSetUpMatrices(snes);
333:   return(0);
334: }

336: PetscErrorCode SNESReset_NEWTONTR(SNES snes)
337: {

340:   return(0);
341: }

343: static PetscErrorCode SNESDestroy_NEWTONTR(SNES snes)
344: {

348:   SNESReset_NEWTONTR(snes);
349:   PetscFree(snes->data);
350:   return(0);
351: }
352: /*------------------------------------------------------------*/

354: static PetscErrorCode SNESSetFromOptions_NEWTONTR(PetscOptionItems *PetscOptionsObject,SNES snes)
355: {
356:   SNES_NEWTONTR  *ctx = (SNES_NEWTONTR*)snes->data;

360:   PetscOptionsHead(PetscOptionsObject,"SNES trust region options for nonlinear equations");
361:   PetscOptionsReal("-snes_trtol","Trust region tolerance","SNESSetTrustRegionTolerance",snes->deltatol,&snes->deltatol,NULL);
362:   PetscOptionsReal("-snes_tr_mu","mu","None",ctx->mu,&ctx->mu,NULL);
363:   PetscOptionsReal("-snes_tr_eta","eta","None",ctx->eta,&ctx->eta,NULL);
364:   PetscOptionsReal("-snes_tr_sigma","sigma","None",ctx->sigma,&ctx->sigma,NULL);
365:   PetscOptionsReal("-snes_tr_delta0","delta0","None",ctx->delta0,&ctx->delta0,NULL);
366:   PetscOptionsReal("-snes_tr_delta1","delta1","None",ctx->delta1,&ctx->delta1,NULL);
367:   PetscOptionsReal("-snes_tr_delta2","delta2","None",ctx->delta2,&ctx->delta2,NULL);
368:   PetscOptionsReal("-snes_tr_delta3","delta3","None",ctx->delta3,&ctx->delta3,NULL);
369:   PetscOptionsTail();
370:   return(0);
371: }

373: static PetscErrorCode SNESView_NEWTONTR(SNES snes,PetscViewer viewer)
374: {
375:   SNES_NEWTONTR  *tr = (SNES_NEWTONTR*)snes->data;
377:   PetscBool      iascii;

380:   PetscObjectTypeCompare((PetscObject)viewer,PETSCVIEWERASCII,&iascii);
381:   if (iascii) {
382:     PetscViewerASCIIPrintf(viewer,"  Trust region tolerance (-snes_trtol)\n",(double)snes->deltatol);
383:     PetscViewerASCIIPrintf(viewer,"  mu=%g, eta=%g, sigma=%g\n",(double)tr->mu,(double)tr->eta,(double)tr->sigma);
384:     PetscViewerASCIIPrintf(viewer,"  delta0=%g, delta1=%g, delta2=%g, delta3=%g\n",(double)tr->delta0,(double)tr->delta1,(double)tr->delta2,(double)tr->delta3);
385:   }
386:   return(0);
387: }
388: /* ------------------------------------------------------------ */
389: /*MC
390:       SNESNEWTONTR - Newton based nonlinear solver that uses a trust region

392:    Options Database:
393: +    -snes_trtol <tol> - trust region tolerance
394: .    -snes_tr_mu <mu> - trust region parameter
395: .    -snes_tr_eta <eta> - trust region parameter
396: .    -snes_tr_sigma <sigma> - trust region parameter
397: .    -snes_tr_delta0 <delta0> -  initial size of the trust region is delta0*norm2(x)
398: .    -snes_tr_delta1 <delta1> - trust region parameter
399: .    -snes_tr_delta2 <delta2> - trust region parameter
400: -    -snes_tr_delta3 <delta3> - trust region parameter

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

406:    Level: intermediate

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

410: M*/
411: PETSC_EXTERN PetscErrorCode SNESCreate_NEWTONTR(SNES snes)
412: {
413:   SNES_NEWTONTR  *neP;

417:   snes->ops->setup          = SNESSetUp_NEWTONTR;
418:   snes->ops->solve          = SNESSolve_NEWTONTR;
419:   snes->ops->destroy        = SNESDestroy_NEWTONTR;
420:   snes->ops->setfromoptions = SNESSetFromOptions_NEWTONTR;
421:   snes->ops->view           = SNESView_NEWTONTR;
422:   snes->ops->reset          = SNESReset_NEWTONTR;

424:   snes->usesksp = PETSC_TRUE;
425:   snes->usesnpc = PETSC_FALSE;

427:   snes->alwayscomputesfinalresidual = PETSC_TRUE;

429:   PetscNewLog(snes,&neP);
430:   snes->data  = (void*)neP;
431:   neP->mu     = 0.25;
432:   neP->eta    = 0.75;
433:   neP->delta  = 0.0;
434:   neP->delta0 = 0.2;
435:   neP->delta1 = 0.3;
436:   neP->delta2 = 0.75;
437:   neP->delta3 = 2.0;
438:   neP->sigma  = 0.0001;
439:   neP->itflag = PETSC_FALSE;
440:   neP->rnorm0 = 0.0;
441:   neP->ttol   = 0.0;
442:   return(0);
443: }