Actual source code: tron.c

petsc-3.9.4 2018-09-11
Report Typos and Errors
  1:  #include <../src/tao/bound/impls/tron/tron.h>
  2:  #include <../src/tao/matrix/submatfree.h>


  5: /* TRON Routines */
  6: static PetscErrorCode TronGradientProjections(Tao,TAO_TRON*);
  7: /*------------------------------------------------------------*/
  8: static PetscErrorCode TaoDestroy_TRON(Tao tao)
  9: {
 10:   TAO_TRON       *tron = (TAO_TRON *)tao->data;

 14:   VecDestroy(&tron->X_New);
 15:   VecDestroy(&tron->G_New);
 16:   VecDestroy(&tron->Work);
 17:   VecDestroy(&tron->DXFree);
 18:   VecDestroy(&tron->R);
 19:   VecDestroy(&tron->diag);
 20:   VecScatterDestroy(&tron->scatter);
 21:   ISDestroy(&tron->Free_Local);
 22:   MatDestroy(&tron->H_sub);
 23:   MatDestroy(&tron->Hpre_sub);
 24:   PetscFree(tao->data);
 25:   return(0);
 26: }

 28: /*------------------------------------------------------------*/
 29: static PetscErrorCode TaoSetFromOptions_TRON(PetscOptionItems *PetscOptionsObject,Tao tao)
 30: {
 31:   TAO_TRON       *tron = (TAO_TRON *)tao->data;
 33:   PetscBool      flg;

 36:   PetscOptionsHead(PetscOptionsObject,"Newton Trust Region Method for bound constrained optimization");
 37:   PetscOptionsInt("-tao_tron_maxgpits","maximum number of gradient projections per TRON iterate","TaoSetMaxGPIts",tron->maxgpits,&tron->maxgpits,&flg);
 38:   PetscOptionsTail();
 39:   TaoLineSearchSetFromOptions(tao->linesearch);
 40:   KSPSetFromOptions(tao->ksp);
 41:   return(0);
 42: }

 44: /*------------------------------------------------------------*/
 45: static PetscErrorCode TaoView_TRON(Tao tao, PetscViewer viewer)
 46: {
 47:   TAO_TRON         *tron = (TAO_TRON *)tao->data;
 48:   PetscBool        isascii;
 49:   PetscErrorCode   ierr;

 52:   PetscObjectTypeCompare((PetscObject)viewer,PETSCVIEWERASCII,&isascii);
 53:   if (isascii) {
 54:     PetscViewerASCIIPrintf(viewer,"Total PG its: %D,",tron->total_gp_its);
 55:     PetscViewerASCIIPrintf(viewer,"PG tolerance: %g \n",(double)tron->pg_ftol);
 56:   }
 57:   return(0);
 58: }

 60: /* ---------------------------------------------------------- */
 61: static PetscErrorCode TaoSetup_TRON(Tao tao)
 62: {
 64:   TAO_TRON       *tron = (TAO_TRON *)tao->data;


 68:   /* Allocate some arrays */
 69:   VecDuplicate(tao->solution, &tron->diag);
 70:   VecDuplicate(tao->solution, &tron->X_New);
 71:   VecDuplicate(tao->solution, &tron->G_New);
 72:   VecDuplicate(tao->solution, &tron->Work);
 73:   VecDuplicate(tao->solution, &tao->gradient);
 74:   VecDuplicate(tao->solution, &tao->stepdirection);
 75:   if (!tao->XL) {
 76:     VecDuplicate(tao->solution, &tao->XL);
 77:     VecSet(tao->XL, PETSC_NINFINITY);
 78:   }
 79:   if (!tao->XU) {
 80:     VecDuplicate(tao->solution, &tao->XU);
 81:     VecSet(tao->XU, PETSC_INFINITY);
 82:   }
 83:   return(0);
 84: }

 86: static PetscErrorCode TaoSolve_TRON(Tao tao)
 87: {
 88:   TAO_TRON                     *tron = (TAO_TRON *)tao->data;
 89:   PetscErrorCode               ierr;
 90:   PetscInt                     its;
 91:   TaoLineSearchConvergedReason ls_reason = TAOLINESEARCH_CONTINUE_ITERATING;
 92:   PetscReal                    prered,actred,delta,f,f_new,rhok,gdx,xdiff,stepsize;

 95:   tron->pgstepsize = 1.0;
 96:   tao->trust = tao->trust0;
 97:   /*   Project the current point onto the feasible set */
 98:   TaoComputeVariableBounds(tao);
 99:   TaoLineSearchSetVariableBounds(tao->linesearch,tao->XL,tao->XU);

101:   /* Project the initial point onto the feasible region */
102:   VecMedian(tao->XL,tao->solution,tao->XU,tao->solution);

104:   /* Compute the objective function and gradient */
105:   TaoComputeObjectiveAndGradient(tao,tao->solution,&tron->f,tao->gradient);
106:   VecNorm(tao->gradient,NORM_2,&tron->gnorm);
107:   if (PetscIsInfOrNanReal(tron->f) || PetscIsInfOrNanReal(tron->gnorm)) SETERRQ(PETSC_COMM_SELF,1, "User provided compute function generated Inf or NaN");

109:   /* Project the gradient and calculate the norm */
110:   VecBoundGradientProjection(tao->gradient,tao->solution,tao->XL,tao->XU,tao->gradient);
111:   VecNorm(tao->gradient,NORM_2,&tron->gnorm);

113:   /* Initialize trust region radius */
114:   tao->trust=tao->trust0;
115:   if (tao->trust <= 0) {
116:     tao->trust=PetscMax(tron->gnorm*tron->gnorm,1.0);
117:   }

119:   /* Initialize step sizes for the line searches */
120:   tron->pgstepsize=1.0;
121:   tron->stepsize=tao->trust;

123:   tao->reason = TAO_CONTINUE_ITERATING;
124:   TaoLogConvergenceHistory(tao,tron->f,tron->gnorm,0.0,tao->ksp_its);
125:   TaoMonitor(tao,tao->niter,tron->f,tron->gnorm,0.0,tron->stepsize);
126:   (*tao->ops->convergencetest)(tao,tao->cnvP);
127:   while (tao->reason==TAO_CONTINUE_ITERATING){

129:     /* Perform projected gradient iterations */
130:     TronGradientProjections(tao,tron);

132:     VecBoundGradientProjection(tao->gradient,tao->solution,tao->XL,tao->XU,tao->gradient);
133:     VecNorm(tao->gradient,NORM_2,&tron->gnorm);

135:     tao->ksp_its=0;
136:     f=tron->f; delta=tao->trust;
137:     tron->n_free_last = tron->n_free;
138:     TaoComputeHessian(tao,tao->solution,tao->hessian,tao->hessian_pre);

140:     /* Generate index set (IS) of which bound constraints are active */
141:     ISDestroy(&tron->Free_Local);
142:     VecWhichInactive(tao->XL,tao->solution,tao->gradient,tao->XU,PETSC_TRUE,&tron->Free_Local);
143:     ISGetSize(tron->Free_Local, &tron->n_free);

145:     /* If no free variables */
146:     if (tron->n_free == 0) {
147:       VecNorm(tao->gradient,NORM_2,&tron->gnorm);
148:       TaoLogConvergenceHistory(tao,tron->f,tron->gnorm,0.0,tao->ksp_its);
149:       TaoMonitor(tao,tao->niter,tron->f,tron->gnorm,0.0,delta);
150:       (*tao->ops->convergencetest)(tao,tao->cnvP);
151:       if (!tao->reason) {
152:         tao->reason = TAO_CONVERGED_STEPTOL;
153:       }
154:       break;
155:     }
156:     /* use free_local to mask/submat gradient, hessian, stepdirection */
157:     TaoVecGetSubVec(tao->gradient,tron->Free_Local,tao->subset_type,0.0,&tron->R);
158:     TaoVecGetSubVec(tao->gradient,tron->Free_Local,tao->subset_type,0.0,&tron->DXFree);
159:     VecSet(tron->DXFree,0.0);
160:     VecScale(tron->R, -1.0);
161:     TaoMatGetSubMat(tao->hessian, tron->Free_Local, tron->diag, tao->subset_type, &tron->H_sub);
162:     if (tao->hessian == tao->hessian_pre) {
163:       MatDestroy(&tron->Hpre_sub);
164:       PetscObjectReference((PetscObject)(tron->H_sub));
165:       tron->Hpre_sub = tron->H_sub;
166:     } else {
167:       TaoMatGetSubMat(tao->hessian_pre, tron->Free_Local, tron->diag, tao->subset_type,&tron->Hpre_sub);
168:     }
169:     KSPReset(tao->ksp);
170:     KSPSetOperators(tao->ksp, tron->H_sub, tron->Hpre_sub);
171:     while (1) {

173:       /* Approximately solve the reduced linear system */
174:       KSPCGSetRadius(tao->ksp,delta);

176:       KSPSolve(tao->ksp, tron->R, tron->DXFree);
177:       KSPGetIterationNumber(tao->ksp,&its);
178:       tao->ksp_its+=its;
179:       tao->ksp_tot_its+=its;
180:       VecSet(tao->stepdirection,0.0);

182:       /* Add dxfree matrix to compute step direction vector */
183:       VecISAXPY(tao->stepdirection,tron->Free_Local,1.0,tron->DXFree);

185:       VecDot(tao->gradient, tao->stepdirection, &gdx);
186:       VecCopy(tao->solution, tron->X_New);
187:       VecCopy(tao->gradient, tron->G_New);

189:       stepsize=1.0;f_new=f;

191:       TaoLineSearchSetInitialStepLength(tao->linesearch,1.0);
192:       TaoLineSearchApply(tao->linesearch, tron->X_New, &f_new, tron->G_New, tao->stepdirection,&stepsize,&ls_reason);
193:       TaoAddLineSearchCounts(tao);

195:       MatMult(tao->hessian, tao->stepdirection, tron->Work);
196:       VecAYPX(tron->Work, 0.5, tao->gradient);
197:       VecDot(tao->stepdirection, tron->Work, &prered);
198:       actred = f_new - f;
199:       if ((PetscAbsScalar(actred) <= 1e-6) && (PetscAbsScalar(prered) <= 1e-6)) {
200:         rhok = 1.0;
201:       } else if (actred<0) {
202:         rhok=PetscAbs(-actred/prered);
203:       } else {
204:         rhok=0.0;
205:       }

207:       /* Compare actual improvement to the quadratic model */
208:       if (rhok > tron->eta1) { /* Accept the point */
209:         /* d = x_new - x */
210:         VecCopy(tron->X_New, tao->stepdirection);
211:         VecAXPY(tao->stepdirection, -1.0, tao->solution);

213:         VecNorm(tao->stepdirection, NORM_2, &xdiff);
214:         xdiff *= stepsize;

216:         /* Adjust trust region size */
217:         if (rhok < tron->eta2 ){
218:           delta = PetscMin(xdiff,delta)*tron->sigma1;
219:         } else if (rhok > tron->eta4 ){
220:           delta= PetscMin(xdiff,delta)*tron->sigma3;
221:         } else if (rhok > tron->eta3 ){
222:           delta=PetscMin(xdiff,delta)*tron->sigma2;
223:         }
224:         VecBoundGradientProjection(tron->G_New,tron->X_New, tao->XL, tao->XU, tao->gradient);
225:         ISDestroy(&tron->Free_Local);
226:         VecWhichInactive(tao->XL,tron->X_New,tao->gradient,tao->XU,PETSC_TRUE,&tron->Free_Local);
227:         f=f_new;
228:         VecNorm(tao->gradient,NORM_2,&tron->gnorm);
229:         VecCopy(tron->X_New, tao->solution);
230:         VecCopy(tron->G_New, tao->gradient);
231:         break;
232:       }
233:       else if (delta <= 1e-30) {
234:         break;
235:       }
236:       else {
237:         delta /= 4.0;
238:       }
239:     } /* end linear solve loop */

241:     tron->f=f; tron->actred=actred; tao->trust=delta;
242:     tao->niter++;
243:     TaoLogConvergenceHistory(tao,tron->f,tron->gnorm,0.0,tao->ksp_its);
244:     TaoMonitor(tao,tao->niter,tron->f,tron->gnorm,0.0,delta);
245:     (*tao->ops->convergencetest)(tao,tao->cnvP);
246:   }  /* END MAIN LOOP  */
247:   return(0);
248: }

250: static PetscErrorCode TronGradientProjections(Tao tao,TAO_TRON *tron)
251: {
252:   PetscErrorCode               ierr;
253:   PetscInt                     i;
254:   TaoLineSearchConvergedReason ls_reason;
255:   PetscReal                    actred=-1.0,actred_max=0.0;
256:   PetscReal                    f_new;
257:   /*
258:      The gradient and function value passed into and out of this
259:      routine should be current and correct.

261:      The free, active, and binding variables should be already identified
262:   */

265:   for (i=0;i<tron->maxgpits;++i){

267:     if (-actred <= (tron->pg_ftol)*actred_max) break;

269:     ++tron->gp_iterates;
270:     ++tron->total_gp_its;
271:     f_new=tron->f;

273:     VecCopy(tao->gradient,tao->stepdirection);
274:     VecScale(tao->stepdirection,-1.0);
275:     TaoLineSearchSetInitialStepLength(tao->linesearch,tron->pgstepsize);
276:     TaoLineSearchApply(tao->linesearch, tao->solution, &f_new, tao->gradient, tao->stepdirection,
277:                               &tron->pgstepsize, &ls_reason);
278:     TaoAddLineSearchCounts(tao);

280:     VecBoundGradientProjection(tao->gradient,tao->solution,tao->XL,tao->XU,tao->gradient);
281:     VecNorm(tao->gradient,NORM_2,&tron->gnorm);

283:     /* Update the iterate */
284:     actred = f_new - tron->f;
285:     actred_max = PetscMax(actred_max,-(f_new - tron->f));
286:     tron->f = f_new;
287:   }
288:   return(0);
289: }

291: static PetscErrorCode TaoComputeDual_TRON(Tao tao, Vec DXL, Vec DXU) {

293:   TAO_TRON       *tron = (TAO_TRON *)tao->data;

300:   if (!tron->Work || !tao->gradient) SETERRQ(PETSC_COMM_SELF,PETSC_ERR_ORDER,"Dual variables don't exist yet or no longer exist.\n");

302:   VecBoundGradientProjection(tao->gradient,tao->solution,tao->XL,tao->XU,tron->Work);
303:   VecCopy(tron->Work,DXL);
304:   VecAXPY(DXL,-1.0,tao->gradient);
305:   VecSet(DXU,0.0);
306:   VecPointwiseMax(DXL,DXL,DXU);

308:   VecCopy(tao->gradient,DXU);
309:   VecAXPY(DXU,-1.0,tron->Work);
310:   VecSet(tron->Work,0.0);
311:   VecPointwiseMin(DXU,tron->Work,DXU);
312:   return(0);
313: }

315: /*------------------------------------------------------------*/
316: /*MC
317:   TAOTRON - The TRON algorithm is an active-set Newton trust region method
318:   for bound-constrained minimization.

320:   Options Database Keys:
321: + -tao_tron_maxgpits - maximum number of gradient projections per TRON iterate
322: - -tao_subset_type - "subvec","mask","matrix-free", strategies for handling active-sets

324:   Level: beginner
325: M*/
326: PETSC_EXTERN PetscErrorCode TaoCreate_TRON(Tao tao)
327: {
328:   TAO_TRON       *tron;
330:   const char     *morethuente_type = TAOLINESEARCHMT;

333:   tao->ops->setup          = TaoSetup_TRON;
334:   tao->ops->solve          = TaoSolve_TRON;
335:   tao->ops->view           = TaoView_TRON;
336:   tao->ops->setfromoptions = TaoSetFromOptions_TRON;
337:   tao->ops->destroy        = TaoDestroy_TRON;
338:   tao->ops->computedual    = TaoComputeDual_TRON;

340:   PetscNewLog(tao,&tron);
341:   tao->data = (void*)tron;

343:   /* Override default settings (unless already changed) */
344:   if (!tao->max_it_changed) tao->max_it = 50;
345:   if (!tao->trust0_changed) tao->trust0 = 1.0;
346:   if (!tao->steptol_changed) tao->steptol = 0.0;

348:   /* Initialize pointers and variables */
349:   tron->n            = 0;
350:   tron->maxgpits     = 3;
351:   tron->pg_ftol      = 0.001;

353:   tron->eta1         = 1.0e-4;
354:   tron->eta2         = 0.25;
355:   tron->eta3         = 0.50;
356:   tron->eta4         = 0.90;

358:   tron->sigma1       = 0.5;
359:   tron->sigma2       = 2.0;
360:   tron->sigma3       = 4.0;

362:   tron->gp_iterates  = 0; /* Cumulative number */
363:   tron->total_gp_its = 0;
364:   tron->n_free       = 0;

366:   tron->DXFree=NULL;
367:   tron->R=NULL;
368:   tron->X_New=NULL;
369:   tron->G_New=NULL;
370:   tron->Work=NULL;
371:   tron->Free_Local=NULL;
372:   tron->H_sub=NULL;
373:   tron->Hpre_sub=NULL;
374:   tao->subset_type = TAO_SUBSET_SUBVEC;

376:   TaoLineSearchCreate(((PetscObject)tao)->comm, &tao->linesearch);
377:   PetscObjectIncrementTabLevel((PetscObject)tao->linesearch, (PetscObject)tao, 1);
378:   TaoLineSearchSetType(tao->linesearch,morethuente_type);
379:   TaoLineSearchUseTaoRoutines(tao->linesearch,tao);
380:   TaoLineSearchSetOptionsPrefix(tao->linesearch,tao->hdr.prefix);

382:   KSPCreate(((PetscObject)tao)->comm, &tao->ksp);
383:   PetscObjectIncrementTabLevel((PetscObject)tao->ksp, (PetscObject)tao, 1);
384:   KSPSetOptionsPrefix(tao->ksp, tao->hdr.prefix);
385:   KSPSetType(tao->ksp,KSPCGSTCG);
386:   return(0);
387: }