Actual source code: bnk.c

  1: #include <petsctaolinesearch.h>
  2: #include <../src/tao/bound/impls/bnk/bnk.h>
  3: #include <petscksp.h>

  5: static const char *BNK_INIT[64]   = {"constant", "direction", "interpolation"};
  6: static const char *BNK_UPDATE[64] = {"step", "reduction", "interpolation"};
  7: static const char *BNK_AS[64]     = {"none", "bertsekas"};

  9: /* Extracts from the full Hessian the part associated with the current bnk->inactive_idx and set the PCLMVM preconditioner */

 11: static PetscErrorCode TaoBNKComputeSubHessian(Tao tao)
 12: {
 13:   TAO_BNK *bnk = (TAO_BNK *)tao->data;

 15:   PetscFunctionBegin;
 16:   PetscCall(MatDestroy(&bnk->Hpre_inactive));
 17:   PetscCall(MatDestroy(&bnk->H_inactive));
 18:   if (bnk->active_idx) {
 19:     PetscCall(MatCreateSubMatrix(tao->hessian, bnk->inactive_idx, bnk->inactive_idx, MAT_INITIAL_MATRIX, &bnk->H_inactive));
 20:     if (tao->hessian == tao->hessian_pre) {
 21:       PetscCall(PetscObjectReference((PetscObject)bnk->H_inactive));
 22:       bnk->Hpre_inactive = bnk->H_inactive;
 23:     } else {
 24:       PetscCall(MatCreateSubMatrix(tao->hessian_pre, bnk->inactive_idx, bnk->inactive_idx, MAT_INITIAL_MATRIX, &bnk->Hpre_inactive));
 25:     }
 26:     if (bnk->bfgs_pre) PetscCall(PCLMVMSetIS(bnk->bfgs_pre, bnk->inactive_idx));
 27:   } else {
 28:     PetscCall(PetscObjectReference((PetscObject)tao->hessian));
 29:     bnk->H_inactive = tao->hessian;
 30:     PetscCall(PetscObjectReference((PetscObject)tao->hessian_pre));
 31:     bnk->Hpre_inactive = tao->hessian_pre;
 32:     if (bnk->bfgs_pre) PetscCall(PCLMVMClearIS(bnk->bfgs_pre));
 33:   }
 34:   PetscFunctionReturn(PETSC_SUCCESS);
 35: }

 37: /* Initializes the KSP solver, the BFGS preconditioner, and the initial trust radius estimation */

 39: PetscErrorCode TaoBNKInitialize(Tao tao, PetscInt initType, PetscBool *needH)
 40: {
 41:   TAO_BNK          *bnk = (TAO_BNK *)tao->data;
 42:   PC                pc;
 43:   PetscReal         f_min, ftrial, prered, actred, kappa, sigma, resnorm;
 44:   PetscReal         tau, tau_1, tau_2, tau_max, tau_min, max_radius;
 45:   PetscBool         is_bfgs, is_jacobi, is_symmetric, sym_set;
 46:   PetscInt          n, N, nDiff;
 47:   PetscInt          i_max = 5;
 48:   PetscInt          j_max = 1;
 49:   PetscInt          i, j;
 50:   PetscVoidFunction kspTR;

 52:   PetscFunctionBegin;
 53:   /* Project the current point onto the feasible set */
 54:   PetscCall(TaoComputeVariableBounds(tao));
 55:   PetscCall(TaoSetVariableBounds(bnk->bncg, tao->XL, tao->XU));
 56:   if (tao->bounded) PetscCall(TaoLineSearchSetVariableBounds(tao->linesearch, tao->XL, tao->XU));

 58:   /* Project the initial point onto the feasible region */
 59:   PetscCall(TaoBoundSolution(tao->solution, tao->XL, tao->XU, 0.0, &nDiff, tao->solution));

 61:   /* Check convergence criteria */
 62:   PetscCall(TaoComputeObjectiveAndGradient(tao, tao->solution, &bnk->f, bnk->unprojected_gradient));
 63:   PetscCall(TaoBNKEstimateActiveSet(tao, bnk->as_type));
 64:   PetscCall(VecCopy(bnk->unprojected_gradient, tao->gradient));
 65:   PetscCall(VecISSet(tao->gradient, bnk->active_idx, 0.0));
 66:   PetscCall(TaoGradientNorm(tao, tao->gradient, NORM_2, &bnk->gnorm));

 68:   /* Test the initial point for convergence */
 69:   PetscCall(VecFischer(tao->solution, bnk->unprojected_gradient, tao->XL, tao->XU, bnk->W));
 70:   PetscCall(VecNorm(bnk->W, NORM_2, &resnorm));
 71:   PetscCheck(!PetscIsInfOrNanReal(bnk->f) && !PetscIsInfOrNanReal(resnorm), PetscObjectComm((PetscObject)tao), PETSC_ERR_USER, "User provided compute function generated Inf or NaN");
 72:   PetscCall(TaoLogConvergenceHistory(tao, bnk->f, resnorm, 0.0, tao->ksp_its));
 73:   PetscCall(TaoMonitor(tao, tao->niter, bnk->f, resnorm, 0.0, 1.0));
 74:   PetscUseTypeMethod(tao, convergencetest, tao->cnvP);
 75:   if (tao->reason != TAO_CONTINUE_ITERATING) PetscFunctionReturn(PETSC_SUCCESS);

 77:   /* Reset KSP stopping reason counters */
 78:   bnk->ksp_atol = 0;
 79:   bnk->ksp_rtol = 0;
 80:   bnk->ksp_dtol = 0;
 81:   bnk->ksp_ctol = 0;
 82:   bnk->ksp_negc = 0;
 83:   bnk->ksp_iter = 0;
 84:   bnk->ksp_othr = 0;

 86:   /* Reset accepted step type counters */
 87:   bnk->tot_cg_its = 0;
 88:   bnk->newt       = 0;
 89:   bnk->bfgs       = 0;
 90:   bnk->sgrad      = 0;
 91:   bnk->grad       = 0;

 93:   /* Initialize the Hessian perturbation */
 94:   bnk->pert = bnk->sval;

 96:   /* Reset initial steplength to zero (this helps BNCG reset its direction internally) */
 97:   PetscCall(VecSet(tao->stepdirection, 0.0));

 99:   /* Allocate the vectors needed for the BFGS approximation */
100:   PetscCall(KSPGetPC(tao->ksp, &pc));
101:   PetscCall(PetscObjectTypeCompare((PetscObject)pc, PCLMVM, &is_bfgs));
102:   PetscCall(PetscObjectTypeCompare((PetscObject)pc, PCJACOBI, &is_jacobi));
103:   if (is_bfgs) {
104:     bnk->bfgs_pre = pc;
105:     PetscCall(PCLMVMGetMatLMVM(bnk->bfgs_pre, &bnk->M));
106:     PetscCall(VecGetLocalSize(tao->solution, &n));
107:     PetscCall(VecGetSize(tao->solution, &N));
108:     PetscCall(MatSetSizes(bnk->M, n, n, N, N));
109:     PetscCall(MatLMVMAllocate(bnk->M, tao->solution, bnk->unprojected_gradient));
110:     PetscCall(MatIsSymmetricKnown(bnk->M, &sym_set, &is_symmetric));
111:     PetscCheck(sym_set && is_symmetric, PetscObjectComm((PetscObject)tao), PETSC_ERR_ARG_INCOMP, "LMVM matrix in the LMVM preconditioner must be symmetric.");
112:   } else if (is_jacobi) PetscCall(PCJacobiSetUseAbs(pc, PETSC_TRUE));

114:   /* Prepare the min/max vectors for safeguarding diagonal scales */
115:   PetscCall(VecSet(bnk->Diag_min, bnk->dmin));
116:   PetscCall(VecSet(bnk->Diag_max, bnk->dmax));

118:   /* Initialize trust-region radius.  The initialization is only performed
119:      when we are using Nash, Steihaug-Toint or the Generalized Lanczos method. */
120:   *needH = PETSC_TRUE;
121:   PetscCall(PetscObjectQueryFunction((PetscObject)tao->ksp, "KSPCGSetRadius_C", &kspTR));
122:   if (kspTR) {
123:     switch (initType) {
124:     case BNK_INIT_CONSTANT:
125:       /* Use the initial radius specified */
126:       tao->trust = tao->trust0;
127:       break;

129:     case BNK_INIT_INTERPOLATION:
130:       /* Use interpolation based on the initial Hessian */
131:       max_radius = 0.0;
132:       tao->trust = tao->trust0;
133:       for (j = 0; j < j_max; ++j) {
134:         f_min = bnk->f;
135:         sigma = 0.0;

137:         if (*needH) {
138:           /* Compute the Hessian at the new step, and extract the inactive subsystem */
139:           PetscCall((*bnk->computehessian)(tao));
140:           PetscCall(TaoBNKEstimateActiveSet(tao, BNK_AS_NONE));
141:           PetscCall(TaoBNKComputeSubHessian(tao));
142:           *needH = PETSC_FALSE;
143:         }

145:         for (i = 0; i < i_max; ++i) {
146:           /* Take a steepest descent step and snap it to bounds */
147:           PetscCall(VecCopy(tao->solution, bnk->Xold));
148:           PetscCall(VecAXPY(tao->solution, -tao->trust / bnk->gnorm, tao->gradient));
149:           PetscCall(TaoBoundSolution(tao->solution, tao->XL, tao->XU, 0.0, &nDiff, tao->solution));
150:           /* Compute the step we actually accepted */
151:           PetscCall(VecCopy(tao->solution, bnk->W));
152:           PetscCall(VecAXPY(bnk->W, -1.0, bnk->Xold));
153:           /* Compute the objective at the trial */
154:           PetscCall(TaoComputeObjective(tao, tao->solution, &ftrial));
155:           PetscCheck(!PetscIsInfOrNanReal(bnk->f), PetscObjectComm((PetscObject)tao), PETSC_ERR_USER, "User provided compute function generated Inf or NaN");
156:           PetscCall(VecCopy(bnk->Xold, tao->solution));
157:           if (PetscIsInfOrNanReal(ftrial)) {
158:             tau = bnk->gamma1_i;
159:           } else {
160:             if (ftrial < f_min) {
161:               f_min = ftrial;
162:               sigma = -tao->trust / bnk->gnorm;
163:             }

165:             /* Compute the predicted and actual reduction */
166:             if (bnk->active_idx) {
167:               PetscCall(VecGetSubVector(bnk->W, bnk->inactive_idx, &bnk->X_inactive));
168:               PetscCall(VecGetSubVector(bnk->Xwork, bnk->inactive_idx, &bnk->inactive_work));
169:             } else {
170:               bnk->X_inactive    = bnk->W;
171:               bnk->inactive_work = bnk->Xwork;
172:             }
173:             PetscCall(MatMult(bnk->H_inactive, bnk->X_inactive, bnk->inactive_work));
174:             PetscCall(VecDot(bnk->X_inactive, bnk->inactive_work, &prered));
175:             if (bnk->active_idx) {
176:               PetscCall(VecRestoreSubVector(bnk->W, bnk->inactive_idx, &bnk->X_inactive));
177:               PetscCall(VecRestoreSubVector(bnk->Xwork, bnk->inactive_idx, &bnk->inactive_work));
178:             }
179:             prered = tao->trust * (bnk->gnorm - 0.5 * tao->trust * prered / (bnk->gnorm * bnk->gnorm));
180:             actred = bnk->f - ftrial;
181:             if ((PetscAbsScalar(actred) <= bnk->epsilon) && (PetscAbsScalar(prered) <= bnk->epsilon)) {
182:               kappa = 1.0;
183:             } else {
184:               kappa = actred / prered;
185:             }

187:             tau_1   = bnk->theta_i * bnk->gnorm * tao->trust / (bnk->theta_i * bnk->gnorm * tao->trust + (1.0 - bnk->theta_i) * prered - actred);
188:             tau_2   = bnk->theta_i * bnk->gnorm * tao->trust / (bnk->theta_i * bnk->gnorm * tao->trust - (1.0 + bnk->theta_i) * prered + actred);
189:             tau_min = PetscMin(tau_1, tau_2);
190:             tau_max = PetscMax(tau_1, tau_2);

192:             if (PetscAbsScalar(kappa - (PetscReal)1.0) <= bnk->mu1_i) {
193:               /*  Great agreement */
194:               max_radius = PetscMax(max_radius, tao->trust);

196:               if (tau_max < 1.0) {
197:                 tau = bnk->gamma3_i;
198:               } else if (tau_max > bnk->gamma4_i) {
199:                 tau = bnk->gamma4_i;
200:               } else {
201:                 tau = tau_max;
202:               }
203:             } else if (PetscAbsScalar(kappa - (PetscReal)1.0) <= bnk->mu2_i) {
204:               /*  Good agreement */
205:               max_radius = PetscMax(max_radius, tao->trust);

207:               if (tau_max < bnk->gamma2_i) {
208:                 tau = bnk->gamma2_i;
209:               } else if (tau_max > bnk->gamma3_i) {
210:                 tau = bnk->gamma3_i;
211:               } else {
212:                 tau = tau_max;
213:               }
214:             } else {
215:               /*  Not good agreement */
216:               if (tau_min > 1.0) {
217:                 tau = bnk->gamma2_i;
218:               } else if (tau_max < bnk->gamma1_i) {
219:                 tau = bnk->gamma1_i;
220:               } else if ((tau_min < bnk->gamma1_i) && (tau_max >= 1.0)) {
221:                 tau = bnk->gamma1_i;
222:               } else if ((tau_1 >= bnk->gamma1_i) && (tau_1 < 1.0) && ((tau_2 < bnk->gamma1_i) || (tau_2 >= 1.0))) {
223:                 tau = tau_1;
224:               } else if ((tau_2 >= bnk->gamma1_i) && (tau_2 < 1.0) && ((tau_1 < bnk->gamma1_i) || (tau_2 >= 1.0))) {
225:                 tau = tau_2;
226:               } else {
227:                 tau = tau_max;
228:               }
229:             }
230:           }
231:           tao->trust = tau * tao->trust;
232:         }

234:         if (f_min < bnk->f) {
235:           /* We accidentally found a solution better than the initial, so accept it */
236:           bnk->f = f_min;
237:           PetscCall(VecCopy(tao->solution, bnk->Xold));
238:           PetscCall(VecAXPY(tao->solution, sigma, tao->gradient));
239:           PetscCall(TaoBoundSolution(tao->solution, tao->XL, tao->XU, 0.0, &nDiff, tao->solution));
240:           PetscCall(VecCopy(tao->solution, tao->stepdirection));
241:           PetscCall(VecAXPY(tao->stepdirection, -1.0, bnk->Xold));
242:           PetscCall(TaoComputeGradient(tao, tao->solution, bnk->unprojected_gradient));
243:           PetscCall(TaoBNKEstimateActiveSet(tao, bnk->as_type));
244:           PetscCall(VecCopy(bnk->unprojected_gradient, tao->gradient));
245:           PetscCall(VecISSet(tao->gradient, bnk->active_idx, 0.0));
246:           /* Compute gradient at the new iterate and flip switch to compute the Hessian later */
247:           PetscCall(TaoGradientNorm(tao, tao->gradient, NORM_2, &bnk->gnorm));
248:           *needH = PETSC_TRUE;
249:           /* Test the new step for convergence */
250:           PetscCall(VecFischer(tao->solution, bnk->unprojected_gradient, tao->XL, tao->XU, bnk->W));
251:           PetscCall(VecNorm(bnk->W, NORM_2, &resnorm));
252:           PetscCheck(!PetscIsInfOrNanReal(resnorm), PetscObjectComm((PetscObject)tao), PETSC_ERR_USER, "User provided compute function generated Inf or NaN");
253:           PetscCall(TaoLogConvergenceHistory(tao, bnk->f, resnorm, 0.0, tao->ksp_its));
254:           PetscCall(TaoMonitor(tao, tao->niter, bnk->f, resnorm, 0.0, 1.0));
255:           PetscUseTypeMethod(tao, convergencetest, tao->cnvP);
256:           if (tao->reason != TAO_CONTINUE_ITERATING) PetscFunctionReturn(PETSC_SUCCESS);
257:           /* active BNCG recycling early because we have a stepdirection computed */
258:           PetscCall(TaoSetRecycleHistory(bnk->bncg, PETSC_TRUE));
259:         }
260:       }
261:       tao->trust = PetscMax(tao->trust, max_radius);

263:       /* Ensure that the trust radius is within the limits */
264:       tao->trust = PetscMax(tao->trust, bnk->min_radius);
265:       tao->trust = PetscMin(tao->trust, bnk->max_radius);
266:       break;

268:     default:
269:       /* Norm of the first direction will initialize radius */
270:       tao->trust = 0.0;
271:       break;
272:     }
273:   }
274:   PetscFunctionReturn(PETSC_SUCCESS);
275: }

277: /*------------------------------------------------------------*/

279: /* Computes the exact Hessian and extracts its subHessian */

281: PetscErrorCode TaoBNKComputeHessian(Tao tao)
282: {
283:   TAO_BNK *bnk = (TAO_BNK *)tao->data;

285:   PetscFunctionBegin;
286:   /* Compute the Hessian */
287:   PetscCall(TaoComputeHessian(tao, tao->solution, tao->hessian, tao->hessian_pre));
288:   /* Add a correction to the BFGS preconditioner */
289:   if (bnk->M) PetscCall(MatLMVMUpdate(bnk->M, tao->solution, bnk->unprojected_gradient));
290:   /* Prepare the reduced sub-matrices for the inactive set */
291:   PetscCall(TaoBNKComputeSubHessian(tao));
292:   PetscFunctionReturn(PETSC_SUCCESS);
293: }

295: /*------------------------------------------------------------*/

297: /* Routine for estimating the active set */

299: PetscErrorCode TaoBNKEstimateActiveSet(Tao tao, PetscInt asType)
300: {
301:   TAO_BNK  *bnk = (TAO_BNK *)tao->data;
302:   PetscBool hessComputed, diagExists, hadactive;

304:   PetscFunctionBegin;
305:   hadactive = bnk->active_idx ? PETSC_TRUE : PETSC_FALSE;
306:   switch (asType) {
307:   case BNK_AS_NONE:
308:     PetscCall(ISDestroy(&bnk->inactive_idx));
309:     PetscCall(VecWhichInactive(tao->XL, tao->solution, bnk->unprojected_gradient, tao->XU, PETSC_TRUE, &bnk->inactive_idx));
310:     PetscCall(ISDestroy(&bnk->active_idx));
311:     PetscCall(ISComplementVec(bnk->inactive_idx, tao->solution, &bnk->active_idx));
312:     break;

314:   case BNK_AS_BERTSEKAS:
315:     /* Compute the trial step vector with which we will estimate the active set at the next iteration */
316:     if (bnk->M) {
317:       /* If the BFGS preconditioner matrix is available, we will construct a trial step with it */
318:       PetscCall(MatSolve(bnk->M, bnk->unprojected_gradient, bnk->W));
319:     } else {
320:       hessComputed = diagExists = PETSC_FALSE;
321:       if (tao->hessian) PetscCall(MatAssembled(tao->hessian, &hessComputed));
322:       if (hessComputed) PetscCall(MatHasOperation(tao->hessian, MATOP_GET_DIAGONAL, &diagExists));
323:       if (diagExists) {
324:         /* BFGS preconditioner doesn't exist so let's invert the absolute diagonal of the Hessian instead onto the gradient */
325:         PetscCall(MatGetDiagonal(tao->hessian, bnk->Xwork));
326:         PetscCall(VecAbs(bnk->Xwork));
327:         PetscCall(VecMedian(bnk->Diag_min, bnk->Xwork, bnk->Diag_max, bnk->Xwork));
328:         PetscCall(VecReciprocal(bnk->Xwork));
329:         PetscCall(VecPointwiseMult(bnk->W, bnk->Xwork, bnk->unprojected_gradient));
330:       } else {
331:         /* If the Hessian or its diagonal does not exist, we will simply use gradient step */
332:         PetscCall(VecCopy(bnk->unprojected_gradient, bnk->W));
333:       }
334:     }
335:     PetscCall(VecScale(bnk->W, -1.0));
336:     PetscCall(TaoEstimateActiveBounds(tao->solution, tao->XL, tao->XU, bnk->unprojected_gradient, bnk->W, bnk->Xwork, bnk->as_step, &bnk->as_tol, &bnk->active_lower, &bnk->active_upper, &bnk->active_fixed, &bnk->active_idx, &bnk->inactive_idx));
337:     break;

339:   default:
340:     break;
341:   }
342:   bnk->resetksp = (PetscBool)(bnk->active_idx || hadactive); /* inactive Hessian size may have changed, need to reset operators */
343:   PetscFunctionReturn(PETSC_SUCCESS);
344: }

346: /*------------------------------------------------------------*/

348: /* Routine for bounding the step direction */

350: PetscErrorCode TaoBNKBoundStep(Tao tao, PetscInt asType, Vec step)
351: {
352:   TAO_BNK *bnk = (TAO_BNK *)tao->data;

354:   PetscFunctionBegin;
355:   switch (asType) {
356:   case BNK_AS_NONE:
357:     PetscCall(VecISSet(step, bnk->active_idx, 0.0));
358:     break;

360:   case BNK_AS_BERTSEKAS:
361:     PetscCall(TaoBoundStep(tao->solution, tao->XL, tao->XU, bnk->active_lower, bnk->active_upper, bnk->active_fixed, 1.0, step));
362:     break;

364:   default:
365:     break;
366:   }
367:   PetscFunctionReturn(PETSC_SUCCESS);
368: }

370: /*------------------------------------------------------------*/

372: /* Routine for taking a finite number of BNCG iterations to
373:    accelerate Newton convergence.

375:    In practice, this approach simply trades off Hessian evaluations
376:    for more gradient evaluations.
377: */

379: PetscErrorCode TaoBNKTakeCGSteps(Tao tao, PetscBool *terminate)
380: {
381:   TAO_BNK *bnk = (TAO_BNK *)tao->data;

383:   PetscFunctionBegin;
384:   *terminate = PETSC_FALSE;
385:   if (bnk->max_cg_its > 0) {
386:     /* Copy the current function value (important vectors are already shared) */
387:     bnk->bncg_ctx->f = bnk->f;
388:     /* Take some small finite number of BNCG iterations */
389:     PetscCall(TaoSolve(bnk->bncg));
390:     /* Add the number of gradient and function evaluations to the total */
391:     tao->nfuncs += bnk->bncg->nfuncs;
392:     tao->nfuncgrads += bnk->bncg->nfuncgrads;
393:     tao->ngrads += bnk->bncg->ngrads;
394:     tao->nhess += bnk->bncg->nhess;
395:     bnk->tot_cg_its += bnk->bncg->niter;
396:     /* Extract the BNCG function value out and save it into BNK */
397:     bnk->f = bnk->bncg_ctx->f;
398:     if (bnk->bncg->reason == TAO_CONVERGED_GATOL || bnk->bncg->reason == TAO_CONVERGED_GRTOL || bnk->bncg->reason == TAO_CONVERGED_GTTOL || bnk->bncg->reason == TAO_CONVERGED_MINF) {
399:       *terminate = PETSC_TRUE;
400:     } else {
401:       PetscCall(TaoBNKEstimateActiveSet(tao, bnk->as_type));
402:     }
403:   }
404:   PetscFunctionReturn(PETSC_SUCCESS);
405: }

407: /*------------------------------------------------------------*/

409: /* Routine for computing the Newton step. */

411: PetscErrorCode TaoBNKComputeStep(Tao tao, PetscBool shift, KSPConvergedReason *ksp_reason, PetscInt *step_type)
412: {
413:   TAO_BNK          *bnk         = (TAO_BNK *)tao->data;
414:   PetscInt          bfgsUpdates = 0;
415:   PetscInt          kspits;
416:   PetscBool         is_lmvm;
417:   PetscVoidFunction kspTR;

419:   PetscFunctionBegin;
420:   /* If there are no inactive variables left, save some computation and return an adjusted zero step
421:      that has (l-x) and (u-x) for lower and upper bounded variables. */
422:   if (!bnk->inactive_idx) {
423:     PetscCall(VecSet(tao->stepdirection, 0.0));
424:     PetscCall(TaoBNKBoundStep(tao, bnk->as_type, tao->stepdirection));
425:     PetscFunctionReturn(PETSC_SUCCESS);
426:   }

428:   /* Shift the reduced Hessian matrix */
429:   if (shift && bnk->pert > 0) {
430:     PetscCall(PetscObjectTypeCompare((PetscObject)tao->hessian, MATLMVM, &is_lmvm));
431:     if (is_lmvm) {
432:       PetscCall(MatShift(tao->hessian, bnk->pert));
433:     } else {
434:       PetscCall(MatShift(bnk->H_inactive, bnk->pert));
435:       if (bnk->H_inactive != bnk->Hpre_inactive) PetscCall(MatShift(bnk->Hpre_inactive, bnk->pert));
436:     }
437:   }

439:   /* Solve the Newton system of equations */
440:   tao->ksp_its = 0;
441:   PetscCall(VecSet(tao->stepdirection, 0.0));
442:   if (bnk->resetksp) {
443:     PetscCall(KSPReset(tao->ksp));
444:     PetscCall(KSPResetFromOptions(tao->ksp));
445:     bnk->resetksp = PETSC_FALSE;
446:   }
447:   PetscCall(KSPSetOperators(tao->ksp, bnk->H_inactive, bnk->Hpre_inactive));
448:   PetscCall(VecCopy(bnk->unprojected_gradient, bnk->Gwork));
449:   if (bnk->active_idx) {
450:     PetscCall(VecGetSubVector(bnk->Gwork, bnk->inactive_idx, &bnk->G_inactive));
451:     PetscCall(VecGetSubVector(tao->stepdirection, bnk->inactive_idx, &bnk->X_inactive));
452:   } else {
453:     bnk->G_inactive = bnk->unprojected_gradient;
454:     bnk->X_inactive = tao->stepdirection;
455:   }
456:   PetscCall(KSPCGSetRadius(tao->ksp, tao->trust));
457:   PetscCall(KSPSolve(tao->ksp, bnk->G_inactive, bnk->X_inactive));
458:   PetscCall(KSPGetIterationNumber(tao->ksp, &kspits));
459:   tao->ksp_its += kspits;
460:   tao->ksp_tot_its += kspits;
461:   PetscCall(PetscObjectQueryFunction((PetscObject)tao->ksp, "KSPCGGetNormD_C", &kspTR));
462:   if (kspTR) {
463:     PetscCall(KSPCGGetNormD(tao->ksp, &bnk->dnorm));

465:     if (0.0 == tao->trust) {
466:       /* Radius was uninitialized; use the norm of the direction */
467:       if (bnk->dnorm > 0.0) {
468:         tao->trust = bnk->dnorm;

470:         /* Modify the radius if it is too large or small */
471:         tao->trust = PetscMax(tao->trust, bnk->min_radius);
472:         tao->trust = PetscMin(tao->trust, bnk->max_radius);
473:       } else {
474:         /* The direction was bad; set radius to default value and re-solve
475:            the trust-region subproblem to get a direction */
476:         tao->trust = tao->trust0;

478:         /* Modify the radius if it is too large or small */
479:         tao->trust = PetscMax(tao->trust, bnk->min_radius);
480:         tao->trust = PetscMin(tao->trust, bnk->max_radius);

482:         PetscCall(KSPCGSetRadius(tao->ksp, tao->trust));
483:         PetscCall(KSPSolve(tao->ksp, bnk->G_inactive, bnk->X_inactive));
484:         PetscCall(KSPGetIterationNumber(tao->ksp, &kspits));
485:         tao->ksp_its += kspits;
486:         tao->ksp_tot_its += kspits;
487:         PetscCall(KSPCGGetNormD(tao->ksp, &bnk->dnorm));

489:         PetscCheck(bnk->dnorm != 0.0, PetscObjectComm((PetscObject)tao), PETSC_ERR_PLIB, "Initial direction zero");
490:       }
491:     }
492:   }
493:   /* Restore sub vectors back */
494:   if (bnk->active_idx) {
495:     PetscCall(VecRestoreSubVector(bnk->Gwork, bnk->inactive_idx, &bnk->G_inactive));
496:     PetscCall(VecRestoreSubVector(tao->stepdirection, bnk->inactive_idx, &bnk->X_inactive));
497:   }
498:   /* Make sure the safeguarded fall-back step is zero for actively bounded variables */
499:   PetscCall(VecScale(tao->stepdirection, -1.0));
500:   PetscCall(TaoBNKBoundStep(tao, bnk->as_type, tao->stepdirection));

502:   /* Record convergence reasons */
503:   PetscCall(KSPGetConvergedReason(tao->ksp, ksp_reason));
504:   if (KSP_CONVERGED_ATOL == *ksp_reason) {
505:     ++bnk->ksp_atol;
506:   } else if (KSP_CONVERGED_RTOL == *ksp_reason) {
507:     ++bnk->ksp_rtol;
508:   } else if (KSP_CONVERGED_STEP_LENGTH == *ksp_reason) {
509:     ++bnk->ksp_ctol;
510:   } else if (KSP_CONVERGED_NEG_CURVE == *ksp_reason) {
511:     ++bnk->ksp_negc;
512:   } else if (KSP_DIVERGED_DTOL == *ksp_reason) {
513:     ++bnk->ksp_dtol;
514:   } else if (KSP_DIVERGED_ITS == *ksp_reason) {
515:     ++bnk->ksp_iter;
516:   } else {
517:     ++bnk->ksp_othr;
518:   }

520:   /* Make sure the BFGS preconditioner is healthy */
521:   if (bnk->M) {
522:     PetscCall(MatLMVMGetUpdateCount(bnk->M, &bfgsUpdates));
523:     if ((KSP_DIVERGED_INDEFINITE_PC == *ksp_reason) && (bfgsUpdates > 0)) {
524:       /* Preconditioner is numerically indefinite; reset the approximation. */
525:       PetscCall(MatLMVMReset(bnk->M, PETSC_FALSE));
526:       PetscCall(MatLMVMUpdate(bnk->M, tao->solution, bnk->unprojected_gradient));
527:     }
528:   }
529:   *step_type = BNK_NEWTON;
530:   PetscFunctionReturn(PETSC_SUCCESS);
531: }

533: /*------------------------------------------------------------*/

535: /* Routine for recomputing the predicted reduction for a given step vector */

537: PetscErrorCode TaoBNKRecomputePred(Tao tao, Vec S, PetscReal *prered)
538: {
539:   TAO_BNK *bnk = (TAO_BNK *)tao->data;

541:   PetscFunctionBegin;
542:   /* Extract subvectors associated with the inactive set */
543:   if (bnk->active_idx) {
544:     PetscCall(VecGetSubVector(tao->stepdirection, bnk->inactive_idx, &bnk->X_inactive));
545:     PetscCall(VecGetSubVector(bnk->Xwork, bnk->inactive_idx, &bnk->inactive_work));
546:     PetscCall(VecGetSubVector(bnk->Gwork, bnk->inactive_idx, &bnk->G_inactive));
547:   } else {
548:     bnk->X_inactive    = tao->stepdirection;
549:     bnk->inactive_work = bnk->Xwork;
550:     bnk->G_inactive    = bnk->Gwork;
551:   }
552:   /* Recompute the predicted decrease based on the quadratic model */
553:   PetscCall(MatMult(bnk->H_inactive, bnk->X_inactive, bnk->inactive_work));
554:   PetscCall(VecAYPX(bnk->inactive_work, -0.5, bnk->G_inactive));
555:   PetscCall(VecDot(bnk->inactive_work, bnk->X_inactive, prered));
556:   /* Restore the sub vectors */
557:   if (bnk->active_idx) {
558:     PetscCall(VecRestoreSubVector(tao->stepdirection, bnk->inactive_idx, &bnk->X_inactive));
559:     PetscCall(VecRestoreSubVector(bnk->Xwork, bnk->inactive_idx, &bnk->inactive_work));
560:     PetscCall(VecRestoreSubVector(bnk->Gwork, bnk->inactive_idx, &bnk->G_inactive));
561:   }
562:   PetscFunctionReturn(PETSC_SUCCESS);
563: }

565: /*------------------------------------------------------------*/

567: /* Routine for ensuring that the Newton step is a descent direction.

569:    The step direction falls back onto BFGS, scaled gradient and gradient steps
570:    in the event that the Newton step fails the test.
571: */

573: PetscErrorCode TaoBNKSafeguardStep(Tao tao, KSPConvergedReason ksp_reason, PetscInt *stepType)
574: {
575:   TAO_BNK  *bnk = (TAO_BNK *)tao->data;
576:   PetscReal gdx, e_min;
577:   PetscInt  bfgsUpdates;

579:   PetscFunctionBegin;
580:   switch (*stepType) {
581:   case BNK_NEWTON:
582:     PetscCall(VecDot(tao->stepdirection, tao->gradient, &gdx));
583:     if ((gdx >= 0.0) || PetscIsInfOrNanReal(gdx)) {
584:       /* Newton step is not descent or direction produced Inf or NaN
585:         Update the perturbation for next time */
586:       if (bnk->pert <= 0.0) {
587:         PetscBool is_gltr;

589:         /* Initialize the perturbation */
590:         bnk->pert = PetscMin(bnk->imax, PetscMax(bnk->imin, bnk->imfac * bnk->gnorm));
591:         PetscCall(PetscObjectTypeCompare((PetscObject)(tao->ksp), KSPGLTR, &is_gltr));
592:         if (is_gltr) {
593:           PetscCall(KSPGLTRGetMinEig(tao->ksp, &e_min));
594:           bnk->pert = PetscMax(bnk->pert, -e_min);
595:         }
596:       } else {
597:         /* Increase the perturbation */
598:         bnk->pert = PetscMin(bnk->pmax, PetscMax(bnk->pgfac * bnk->pert, bnk->pmgfac * bnk->gnorm));
599:       }

601:       if (!bnk->M) {
602:         /* We don't have the bfgs matrix around and updated
603:           Must use gradient direction in this case */
604:         PetscCall(VecCopy(tao->gradient, tao->stepdirection));
605:         *stepType = BNK_GRADIENT;
606:       } else {
607:         /* Attempt to use the BFGS direction */
608:         PetscCall(MatSolve(bnk->M, bnk->unprojected_gradient, tao->stepdirection));

610:         /* Check for success (descent direction)
611:           NOTE: Negative gdx here means not a descent direction because
612:           the fall-back step is missing a negative sign. */
613:         PetscCall(VecDot(tao->gradient, tao->stepdirection, &gdx));
614:         if ((gdx <= 0.0) || PetscIsInfOrNanReal(gdx)) {
615:           /* BFGS direction is not descent or direction produced not a number
616:             We can assert bfgsUpdates > 1 in this case because
617:             the first solve produces the scaled gradient direction,
618:             which is guaranteed to be descent */

620:           /* Use steepest descent direction (scaled) */
621:           PetscCall(MatLMVMReset(bnk->M, PETSC_FALSE));
622:           PetscCall(MatLMVMUpdate(bnk->M, tao->solution, bnk->unprojected_gradient));
623:           PetscCall(MatSolve(bnk->M, bnk->unprojected_gradient, tao->stepdirection));

625:           *stepType = BNK_SCALED_GRADIENT;
626:         } else {
627:           PetscCall(MatLMVMGetUpdateCount(bnk->M, &bfgsUpdates));
628:           if (1 == bfgsUpdates) {
629:             /* The first BFGS direction is always the scaled gradient */
630:             *stepType = BNK_SCALED_GRADIENT;
631:           } else {
632:             *stepType = BNK_BFGS;
633:           }
634:         }
635:       }
636:       /* Make sure the safeguarded fall-back step is zero for actively bounded variables */
637:       PetscCall(VecScale(tao->stepdirection, -1.0));
638:       PetscCall(TaoBNKBoundStep(tao, bnk->as_type, tao->stepdirection));
639:     } else {
640:       /* Computed Newton step is descent */
641:       switch (ksp_reason) {
642:       case KSP_DIVERGED_NANORINF:
643:       case KSP_DIVERGED_BREAKDOWN:
644:       case KSP_DIVERGED_INDEFINITE_MAT:
645:       case KSP_DIVERGED_INDEFINITE_PC:
646:       case KSP_CONVERGED_NEG_CURVE:
647:         /* Matrix or preconditioner is indefinite; increase perturbation */
648:         if (bnk->pert <= 0.0) {
649:           PetscBool is_gltr;

651:           /* Initialize the perturbation */
652:           bnk->pert = PetscMin(bnk->imax, PetscMax(bnk->imin, bnk->imfac * bnk->gnorm));
653:           PetscCall(PetscObjectTypeCompare((PetscObject)(tao->ksp), KSPGLTR, &is_gltr));
654:           if (is_gltr) {
655:             PetscCall(KSPGLTRGetMinEig(tao->ksp, &e_min));
656:             bnk->pert = PetscMax(bnk->pert, -e_min);
657:           }
658:         } else {
659:           /* Increase the perturbation */
660:           bnk->pert = PetscMin(bnk->pmax, PetscMax(bnk->pgfac * bnk->pert, bnk->pmgfac * bnk->gnorm));
661:         }
662:         break;

664:       default:
665:         /* Newton step computation is good; decrease perturbation */
666:         bnk->pert = PetscMin(bnk->psfac * bnk->pert, bnk->pmsfac * bnk->gnorm);
667:         if (bnk->pert < bnk->pmin) bnk->pert = 0.0;
668:         break;
669:       }
670:       *stepType = BNK_NEWTON;
671:     }
672:     break;

674:   case BNK_BFGS:
675:     /* Check for success (descent direction) */
676:     PetscCall(VecDot(tao->stepdirection, tao->gradient, &gdx));
677:     if (gdx >= 0 || PetscIsInfOrNanReal(gdx)) {
678:       /* Step is not descent or solve was not successful
679:          Use steepest descent direction (scaled) */
680:       PetscCall(MatLMVMReset(bnk->M, PETSC_FALSE));
681:       PetscCall(MatLMVMUpdate(bnk->M, tao->solution, bnk->unprojected_gradient));
682:       PetscCall(MatSolve(bnk->M, tao->gradient, tao->stepdirection));
683:       PetscCall(VecScale(tao->stepdirection, -1.0));
684:       PetscCall(TaoBNKBoundStep(tao, bnk->as_type, tao->stepdirection));
685:       *stepType = BNK_SCALED_GRADIENT;
686:     } else {
687:       *stepType = BNK_BFGS;
688:     }
689:     break;

691:   case BNK_SCALED_GRADIENT:
692:     break;

694:   default:
695:     break;
696:   }

698:   PetscFunctionReturn(PETSC_SUCCESS);
699: }

701: /*------------------------------------------------------------*/

703: /* Routine for performing a bound-projected More-Thuente line search.

705:   Includes fallbacks to BFGS, scaled gradient, and unscaled gradient steps if the
706:   Newton step does not produce a valid step length.
707: */

709: PetscErrorCode TaoBNKPerformLineSearch(Tao tao, PetscInt *stepType, PetscReal *steplen, TaoLineSearchConvergedReason *reason)
710: {
711:   TAO_BNK                     *bnk = (TAO_BNK *)tao->data;
712:   TaoLineSearchConvergedReason ls_reason;
713:   PetscReal                    e_min, gdx;
714:   PetscInt                     bfgsUpdates;

716:   PetscFunctionBegin;
717:   /* Perform the linesearch */
718:   PetscCall(TaoLineSearchApply(tao->linesearch, tao->solution, &bnk->f, bnk->unprojected_gradient, tao->stepdirection, steplen, &ls_reason));
719:   PetscCall(TaoAddLineSearchCounts(tao));

721:   while (ls_reason != TAOLINESEARCH_SUCCESS && ls_reason != TAOLINESEARCH_SUCCESS_USER && *stepType != BNK_SCALED_GRADIENT && *stepType != BNK_GRADIENT) {
722:     /* Linesearch failed, revert solution */
723:     bnk->f = bnk->fold;
724:     PetscCall(VecCopy(bnk->Xold, tao->solution));
725:     PetscCall(VecCopy(bnk->unprojected_gradient_old, bnk->unprojected_gradient));

727:     switch (*stepType) {
728:     case BNK_NEWTON:
729:       /* Failed to obtain acceptable iterate with Newton step
730:          Update the perturbation for next time */
731:       if (bnk->pert <= 0.0) {
732:         PetscBool is_gltr;

734:         /* Initialize the perturbation */
735:         bnk->pert = PetscMin(bnk->imax, PetscMax(bnk->imin, bnk->imfac * bnk->gnorm));
736:         PetscCall(PetscObjectTypeCompare((PetscObject)(tao->ksp), KSPGLTR, &is_gltr));
737:         if (is_gltr) {
738:           PetscCall(KSPGLTRGetMinEig(tao->ksp, &e_min));
739:           bnk->pert = PetscMax(bnk->pert, -e_min);
740:         }
741:       } else {
742:         /* Increase the perturbation */
743:         bnk->pert = PetscMin(bnk->pmax, PetscMax(bnk->pgfac * bnk->pert, bnk->pmgfac * bnk->gnorm));
744:       }

746:       if (!bnk->M) {
747:         /* We don't have the bfgs matrix around and being updated
748:            Must use gradient direction in this case */
749:         PetscCall(VecCopy(bnk->unprojected_gradient, tao->stepdirection));
750:         *stepType = BNK_GRADIENT;
751:       } else {
752:         /* Attempt to use the BFGS direction */
753:         PetscCall(MatSolve(bnk->M, bnk->unprojected_gradient, tao->stepdirection));
754:         /* Check for success (descent direction)
755:            NOTE: Negative gdx means not a descent direction because the step here is missing a negative sign. */
756:         PetscCall(VecDot(tao->gradient, tao->stepdirection, &gdx));
757:         if ((gdx <= 0.0) || PetscIsInfOrNanReal(gdx)) {
758:           /* BFGS direction is not descent or direction produced not a number
759:              We can assert bfgsUpdates > 1 in this case
760:              Use steepest descent direction (scaled) */
761:           PetscCall(MatLMVMReset(bnk->M, PETSC_FALSE));
762:           PetscCall(MatLMVMUpdate(bnk->M, tao->solution, bnk->unprojected_gradient));
763:           PetscCall(MatSolve(bnk->M, bnk->unprojected_gradient, tao->stepdirection));

765:           bfgsUpdates = 1;
766:           *stepType   = BNK_SCALED_GRADIENT;
767:         } else {
768:           PetscCall(MatLMVMGetUpdateCount(bnk->M, &bfgsUpdates));
769:           if (1 == bfgsUpdates) {
770:             /* The first BFGS direction is always the scaled gradient */
771:             *stepType = BNK_SCALED_GRADIENT;
772:           } else {
773:             *stepType = BNK_BFGS;
774:           }
775:         }
776:       }
777:       break;

779:     case BNK_BFGS:
780:       /* Can only enter if pc_type == BNK_PC_BFGS
781:          Failed to obtain acceptable iterate with BFGS step
782:          Attempt to use the scaled gradient direction */
783:       PetscCall(MatLMVMReset(bnk->M, PETSC_FALSE));
784:       PetscCall(MatLMVMUpdate(bnk->M, tao->solution, bnk->unprojected_gradient));
785:       PetscCall(MatSolve(bnk->M, bnk->unprojected_gradient, tao->stepdirection));

787:       bfgsUpdates = 1;
788:       *stepType   = BNK_SCALED_GRADIENT;
789:       break;
790:     }
791:     /* Make sure the safeguarded fall-back step is zero for actively bounded variables */
792:     PetscCall(VecScale(tao->stepdirection, -1.0));
793:     PetscCall(TaoBNKBoundStep(tao, bnk->as_type, tao->stepdirection));

795:     /* Perform one last line search with the fall-back step */
796:     PetscCall(TaoLineSearchApply(tao->linesearch, tao->solution, &bnk->f, bnk->unprojected_gradient, tao->stepdirection, steplen, &ls_reason));
797:     PetscCall(TaoAddLineSearchCounts(tao));
798:   }
799:   *reason = ls_reason;
800:   PetscFunctionReturn(PETSC_SUCCESS);
801: }

803: /*------------------------------------------------------------*/

805: /* Routine for updating the trust radius.

807:   Function features three different update methods:
808:   1) Line-search step length based
809:   2) Predicted decrease on the CG quadratic model
810:   3) Interpolation
811: */

813: PetscErrorCode TaoBNKUpdateTrustRadius(Tao tao, PetscReal prered, PetscReal actred, PetscInt updateType, PetscInt stepType, PetscBool *accept)
814: {
815:   TAO_BNK *bnk = (TAO_BNK *)tao->data;

817:   PetscReal step, kappa;
818:   PetscReal gdx, tau_1, tau_2, tau_min, tau_max;

820:   PetscFunctionBegin;
821:   /* Update trust region radius */
822:   *accept = PETSC_FALSE;
823:   switch (updateType) {
824:   case BNK_UPDATE_STEP:
825:     *accept = PETSC_TRUE; /* always accept here because line search succeeded */
826:     if (stepType == BNK_NEWTON) {
827:       PetscCall(TaoLineSearchGetStepLength(tao->linesearch, &step));
828:       if (step < bnk->nu1) {
829:         /* Very bad step taken; reduce radius */
830:         tao->trust = bnk->omega1 * PetscMin(bnk->dnorm, tao->trust);
831:       } else if (step < bnk->nu2) {
832:         /* Reasonably bad step taken; reduce radius */
833:         tao->trust = bnk->omega2 * PetscMin(bnk->dnorm, tao->trust);
834:       } else if (step < bnk->nu3) {
835:         /*  Reasonable step was taken; leave radius alone */
836:         if (bnk->omega3 < 1.0) {
837:           tao->trust = bnk->omega3 * PetscMin(bnk->dnorm, tao->trust);
838:         } else if (bnk->omega3 > 1.0) {
839:           tao->trust = PetscMax(bnk->omega3 * bnk->dnorm, tao->trust);
840:         }
841:       } else if (step < bnk->nu4) {
842:         /*  Full step taken; increase the radius */
843:         tao->trust = PetscMax(bnk->omega4 * bnk->dnorm, tao->trust);
844:       } else {
845:         /*  More than full step taken; increase the radius */
846:         tao->trust = PetscMax(bnk->omega5 * bnk->dnorm, tao->trust);
847:       }
848:     } else {
849:       /*  Newton step was not good; reduce the radius */
850:       tao->trust = bnk->omega1 * PetscMin(bnk->dnorm, tao->trust);
851:     }
852:     break;

854:   case BNK_UPDATE_REDUCTION:
855:     if (stepType == BNK_NEWTON) {
856:       if ((prered < 0.0) || PetscIsInfOrNanReal(prered)) {
857:         /* The predicted reduction has the wrong sign.  This cannot
858:            happen in infinite precision arithmetic.  Step should
859:            be rejected! */
860:         tao->trust = bnk->alpha1 * PetscMin(tao->trust, bnk->dnorm);
861:       } else {
862:         if (PetscIsInfOrNanReal(actred)) {
863:           tao->trust = bnk->alpha1 * PetscMin(tao->trust, bnk->dnorm);
864:         } else {
865:           if ((PetscAbsScalar(actred) <= PetscMax(1.0, PetscAbsScalar(bnk->f)) * bnk->epsilon) && (PetscAbsScalar(prered) <= PetscMax(1.0, PetscAbsScalar(bnk->f)) * bnk->epsilon)) {
866:             kappa = 1.0;
867:           } else {
868:             kappa = actred / prered;
869:           }
870:           /* Accept or reject the step and update radius */
871:           if (kappa < bnk->eta1) {
872:             /* Reject the step */
873:             tao->trust = bnk->alpha1 * PetscMin(tao->trust, bnk->dnorm);
874:           } else {
875:             /* Accept the step */
876:             *accept = PETSC_TRUE;
877:             /* Update the trust region radius only if the computed step is at the trust radius boundary */
878:             if (bnk->dnorm == tao->trust) {
879:               if (kappa < bnk->eta2) {
880:                 /* Marginal bad step */
881:                 tao->trust = bnk->alpha2 * tao->trust;
882:               } else if (kappa < bnk->eta3) {
883:                 /* Reasonable step */
884:                 tao->trust = bnk->alpha3 * tao->trust;
885:               } else if (kappa < bnk->eta4) {
886:                 /* Good step */
887:                 tao->trust = bnk->alpha4 * tao->trust;
888:               } else {
889:                 /* Very good step */
890:                 tao->trust = bnk->alpha5 * tao->trust;
891:               }
892:             }
893:           }
894:         }
895:       }
896:     } else {
897:       /*  Newton step was not good; reduce the radius */
898:       tao->trust = bnk->alpha1 * PetscMin(bnk->dnorm, tao->trust);
899:     }
900:     break;

902:   default:
903:     if (stepType == BNK_NEWTON) {
904:       if (prered < 0.0) {
905:         /*  The predicted reduction has the wrong sign.  This cannot */
906:         /*  happen in infinite precision arithmetic.  Step should */
907:         /*  be rejected! */
908:         tao->trust = bnk->gamma1 * PetscMin(tao->trust, bnk->dnorm);
909:       } else {
910:         if (PetscIsInfOrNanReal(actred)) {
911:           tao->trust = bnk->gamma1 * PetscMin(tao->trust, bnk->dnorm);
912:         } else {
913:           if ((PetscAbsScalar(actred) <= bnk->epsilon) && (PetscAbsScalar(prered) <= bnk->epsilon)) {
914:             kappa = 1.0;
915:           } else {
916:             kappa = actred / prered;
917:           }

919:           PetscCall(VecDot(tao->gradient, tao->stepdirection, &gdx));
920:           tau_1   = bnk->theta * gdx / (bnk->theta * gdx - (1.0 - bnk->theta) * prered + actred);
921:           tau_2   = bnk->theta * gdx / (bnk->theta * gdx + (1.0 + bnk->theta) * prered - actred);
922:           tau_min = PetscMin(tau_1, tau_2);
923:           tau_max = PetscMax(tau_1, tau_2);

925:           if (kappa >= 1.0 - bnk->mu1) {
926:             /*  Great agreement */
927:             *accept = PETSC_TRUE;
928:             if (tau_max < 1.0) {
929:               tao->trust = PetscMax(tao->trust, bnk->gamma3 * bnk->dnorm);
930:             } else if (tau_max > bnk->gamma4) {
931:               tao->trust = PetscMax(tao->trust, bnk->gamma4 * bnk->dnorm);
932:             } else {
933:               tao->trust = PetscMax(tao->trust, tau_max * bnk->dnorm);
934:             }
935:           } else if (kappa >= 1.0 - bnk->mu2) {
936:             /*  Good agreement */
937:             *accept = PETSC_TRUE;
938:             if (tau_max < bnk->gamma2) {
939:               tao->trust = bnk->gamma2 * PetscMin(tao->trust, bnk->dnorm);
940:             } else if (tau_max > bnk->gamma3) {
941:               tao->trust = PetscMax(tao->trust, bnk->gamma3 * bnk->dnorm);
942:             } else if (tau_max < 1.0) {
943:               tao->trust = tau_max * PetscMin(tao->trust, bnk->dnorm);
944:             } else {
945:               tao->trust = PetscMax(tao->trust, tau_max * bnk->dnorm);
946:             }
947:           } else {
948:             /*  Not good agreement */
949:             if (tau_min > 1.0) {
950:               tao->trust = bnk->gamma2 * PetscMin(tao->trust, bnk->dnorm);
951:             } else if (tau_max < bnk->gamma1) {
952:               tao->trust = bnk->gamma1 * PetscMin(tao->trust, bnk->dnorm);
953:             } else if ((tau_min < bnk->gamma1) && (tau_max >= 1.0)) {
954:               tao->trust = bnk->gamma1 * PetscMin(tao->trust, bnk->dnorm);
955:             } else if ((tau_1 >= bnk->gamma1) && (tau_1 < 1.0) && ((tau_2 < bnk->gamma1) || (tau_2 >= 1.0))) {
956:               tao->trust = tau_1 * PetscMin(tao->trust, bnk->dnorm);
957:             } else if ((tau_2 >= bnk->gamma1) && (tau_2 < 1.0) && ((tau_1 < bnk->gamma1) || (tau_2 >= 1.0))) {
958:               tao->trust = tau_2 * PetscMin(tao->trust, bnk->dnorm);
959:             } else {
960:               tao->trust = tau_max * PetscMin(tao->trust, bnk->dnorm);
961:             }
962:           }
963:         }
964:       }
965:     } else {
966:       /*  Newton step was not good; reduce the radius */
967:       tao->trust = bnk->gamma1 * PetscMin(bnk->dnorm, tao->trust);
968:     }
969:     break;
970:   }
971:   /* Make sure the radius does not violate min and max settings */
972:   tao->trust = PetscMin(tao->trust, bnk->max_radius);
973:   tao->trust = PetscMax(tao->trust, bnk->min_radius);
974:   PetscFunctionReturn(PETSC_SUCCESS);
975: }

977: /* ---------------------------------------------------------- */

979: PetscErrorCode TaoBNKAddStepCounts(Tao tao, PetscInt stepType)
980: {
981:   TAO_BNK *bnk = (TAO_BNK *)tao->data;

983:   PetscFunctionBegin;
984:   switch (stepType) {
985:   case BNK_NEWTON:
986:     ++bnk->newt;
987:     break;
988:   case BNK_BFGS:
989:     ++bnk->bfgs;
990:     break;
991:   case BNK_SCALED_GRADIENT:
992:     ++bnk->sgrad;
993:     break;
994:   case BNK_GRADIENT:
995:     ++bnk->grad;
996:     break;
997:   default:
998:     break;
999:   }
1000:   PetscFunctionReturn(PETSC_SUCCESS);
1001: }

1003: /* ---------------------------------------------------------- */

1005: PetscErrorCode TaoSetUp_BNK(Tao tao)
1006: {
1007:   TAO_BNK *bnk = (TAO_BNK *)tao->data;
1008:   PetscInt i;

1010:   PetscFunctionBegin;
1011:   if (!tao->gradient) PetscCall(VecDuplicate(tao->solution, &tao->gradient));
1012:   if (!tao->stepdirection) PetscCall(VecDuplicate(tao->solution, &tao->stepdirection));
1013:   if (!bnk->W) PetscCall(VecDuplicate(tao->solution, &bnk->W));
1014:   if (!bnk->Xold) PetscCall(VecDuplicate(tao->solution, &bnk->Xold));
1015:   if (!bnk->Gold) PetscCall(VecDuplicate(tao->solution, &bnk->Gold));
1016:   if (!bnk->Xwork) PetscCall(VecDuplicate(tao->solution, &bnk->Xwork));
1017:   if (!bnk->Gwork) PetscCall(VecDuplicate(tao->solution, &bnk->Gwork));
1018:   if (!bnk->unprojected_gradient) PetscCall(VecDuplicate(tao->solution, &bnk->unprojected_gradient));
1019:   if (!bnk->unprojected_gradient_old) PetscCall(VecDuplicate(tao->solution, &bnk->unprojected_gradient_old));
1020:   if (!bnk->Diag_min) PetscCall(VecDuplicate(tao->solution, &bnk->Diag_min));
1021:   if (!bnk->Diag_max) PetscCall(VecDuplicate(tao->solution, &bnk->Diag_max));
1022:   if (bnk->max_cg_its > 0) {
1023:     /* Ensure that the important common vectors are shared between BNK and embedded BNCG */
1024:     bnk->bncg_ctx = (TAO_BNCG *)bnk->bncg->data;
1025:     PetscCall(PetscObjectReference((PetscObject)(bnk->unprojected_gradient_old)));
1026:     PetscCall(VecDestroy(&bnk->bncg_ctx->unprojected_gradient_old));
1027:     bnk->bncg_ctx->unprojected_gradient_old = bnk->unprojected_gradient_old;
1028:     PetscCall(PetscObjectReference((PetscObject)(bnk->unprojected_gradient)));
1029:     PetscCall(VecDestroy(&bnk->bncg_ctx->unprojected_gradient));
1030:     bnk->bncg_ctx->unprojected_gradient = bnk->unprojected_gradient;
1031:     PetscCall(PetscObjectReference((PetscObject)(bnk->Gold)));
1032:     PetscCall(VecDestroy(&bnk->bncg_ctx->G_old));
1033:     bnk->bncg_ctx->G_old = bnk->Gold;
1034:     PetscCall(PetscObjectReference((PetscObject)(tao->gradient)));
1035:     PetscCall(VecDestroy(&bnk->bncg->gradient));
1036:     bnk->bncg->gradient = tao->gradient;
1037:     PetscCall(PetscObjectReference((PetscObject)(tao->stepdirection)));
1038:     PetscCall(VecDestroy(&bnk->bncg->stepdirection));
1039:     bnk->bncg->stepdirection = tao->stepdirection;
1040:     PetscCall(TaoSetSolution(bnk->bncg, tao->solution));
1041:     /* Copy over some settings from BNK into BNCG */
1042:     PetscCall(TaoSetMaximumIterations(bnk->bncg, bnk->max_cg_its));
1043:     PetscCall(TaoSetTolerances(bnk->bncg, tao->gatol, tao->grtol, tao->gttol));
1044:     PetscCall(TaoSetFunctionLowerBound(bnk->bncg, tao->fmin));
1045:     PetscCall(TaoSetConvergenceTest(bnk->bncg, tao->ops->convergencetest, tao->cnvP));
1046:     PetscCall(TaoSetObjective(bnk->bncg, tao->ops->computeobjective, tao->user_objP));
1047:     PetscCall(TaoSetGradient(bnk->bncg, NULL, tao->ops->computegradient, tao->user_gradP));
1048:     PetscCall(TaoSetObjectiveAndGradient(bnk->bncg, NULL, tao->ops->computeobjectiveandgradient, tao->user_objgradP));
1049:     PetscCall(PetscObjectCopyFortranFunctionPointers((PetscObject)tao, (PetscObject)(bnk->bncg)));
1050:     for (i = 0; i < tao->numbermonitors; ++i) {
1051:       PetscCall(TaoSetMonitor(bnk->bncg, tao->monitor[i], tao->monitorcontext[i], tao->monitordestroy[i]));
1052:       PetscCall(PetscObjectReference((PetscObject)(tao->monitorcontext[i])));
1053:     }
1054:   }
1055:   bnk->X_inactive    = NULL;
1056:   bnk->G_inactive    = NULL;
1057:   bnk->inactive_work = NULL;
1058:   bnk->active_work   = NULL;
1059:   bnk->inactive_idx  = NULL;
1060:   bnk->active_idx    = NULL;
1061:   bnk->active_lower  = NULL;
1062:   bnk->active_upper  = NULL;
1063:   bnk->active_fixed  = NULL;
1064:   bnk->M             = NULL;
1065:   bnk->H_inactive    = NULL;
1066:   bnk->Hpre_inactive = NULL;
1067:   PetscFunctionReturn(PETSC_SUCCESS);
1068: }

1070: /*------------------------------------------------------------*/

1072: PetscErrorCode TaoDestroy_BNK(Tao tao)
1073: {
1074:   TAO_BNK *bnk = (TAO_BNK *)tao->data;

1076:   PetscFunctionBegin;
1077:   PetscCall(VecDestroy(&bnk->W));
1078:   PetscCall(VecDestroy(&bnk->Xold));
1079:   PetscCall(VecDestroy(&bnk->Gold));
1080:   PetscCall(VecDestroy(&bnk->Xwork));
1081:   PetscCall(VecDestroy(&bnk->Gwork));
1082:   PetscCall(VecDestroy(&bnk->unprojected_gradient));
1083:   PetscCall(VecDestroy(&bnk->unprojected_gradient_old));
1084:   PetscCall(VecDestroy(&bnk->Diag_min));
1085:   PetscCall(VecDestroy(&bnk->Diag_max));
1086:   PetscCall(ISDestroy(&bnk->active_lower));
1087:   PetscCall(ISDestroy(&bnk->active_upper));
1088:   PetscCall(ISDestroy(&bnk->active_fixed));
1089:   PetscCall(ISDestroy(&bnk->active_idx));
1090:   PetscCall(ISDestroy(&bnk->inactive_idx));
1091:   PetscCall(MatDestroy(&bnk->Hpre_inactive));
1092:   PetscCall(MatDestroy(&bnk->H_inactive));
1093:   PetscCall(TaoDestroy(&bnk->bncg));
1094:   PetscCall(KSPDestroy(&tao->ksp));
1095:   PetscCall(PetscFree(tao->data));
1096:   PetscFunctionReturn(PETSC_SUCCESS);
1097: }

1099: /*------------------------------------------------------------*/

1101: PetscErrorCode TaoSetFromOptions_BNK(Tao tao, PetscOptionItems *PetscOptionsObject)
1102: {
1103:   TAO_BNK *bnk = (TAO_BNK *)tao->data;

1105:   PetscFunctionBegin;
1106:   PetscOptionsHeadBegin(PetscOptionsObject, "Newton-Krylov method for bound constrained optimization");
1107:   PetscCall(PetscOptionsEList("-tao_bnk_init_type", "radius initialization type", "", BNK_INIT, BNK_INIT_TYPES, BNK_INIT[bnk->init_type], &bnk->init_type, NULL));
1108:   PetscCall(PetscOptionsEList("-tao_bnk_update_type", "radius update type", "", BNK_UPDATE, BNK_UPDATE_TYPES, BNK_UPDATE[bnk->update_type], &bnk->update_type, NULL));
1109:   PetscCall(PetscOptionsEList("-tao_bnk_as_type", "active set estimation method", "", BNK_AS, BNK_AS_TYPES, BNK_AS[bnk->as_type], &bnk->as_type, NULL));
1110:   PetscCall(PetscOptionsReal("-tao_bnk_sval", "(developer) Hessian perturbation starting value", "", bnk->sval, &bnk->sval, NULL));
1111:   PetscCall(PetscOptionsReal("-tao_bnk_imin", "(developer) minimum initial Hessian perturbation", "", bnk->imin, &bnk->imin, NULL));
1112:   PetscCall(PetscOptionsReal("-tao_bnk_imax", "(developer) maximum initial Hessian perturbation", "", bnk->imax, &bnk->imax, NULL));
1113:   PetscCall(PetscOptionsReal("-tao_bnk_imfac", "(developer) initial merit factor for Hessian perturbation", "", bnk->imfac, &bnk->imfac, NULL));
1114:   PetscCall(PetscOptionsReal("-tao_bnk_pmin", "(developer) minimum Hessian perturbation", "", bnk->pmin, &bnk->pmin, NULL));
1115:   PetscCall(PetscOptionsReal("-tao_bnk_pmax", "(developer) maximum Hessian perturbation", "", bnk->pmax, &bnk->pmax, NULL));
1116:   PetscCall(PetscOptionsReal("-tao_bnk_pgfac", "(developer) Hessian perturbation growth factor", "", bnk->pgfac, &bnk->pgfac, NULL));
1117:   PetscCall(PetscOptionsReal("-tao_bnk_psfac", "(developer) Hessian perturbation shrink factor", "", bnk->psfac, &bnk->psfac, NULL));
1118:   PetscCall(PetscOptionsReal("-tao_bnk_pmgfac", "(developer) merit growth factor for Hessian perturbation", "", bnk->pmgfac, &bnk->pmgfac, NULL));
1119:   PetscCall(PetscOptionsReal("-tao_bnk_pmsfac", "(developer) merit shrink factor for Hessian perturbation", "", bnk->pmsfac, &bnk->pmsfac, NULL));
1120:   PetscCall(PetscOptionsReal("-tao_bnk_eta1", "(developer) threshold for rejecting step (-tao_bnk_update_type reduction)", "", bnk->eta1, &bnk->eta1, NULL));
1121:   PetscCall(PetscOptionsReal("-tao_bnk_eta2", "(developer) threshold for accepting marginal step (-tao_bnk_update_type reduction)", "", bnk->eta2, &bnk->eta2, NULL));
1122:   PetscCall(PetscOptionsReal("-tao_bnk_eta3", "(developer) threshold for accepting reasonable step (-tao_bnk_update_type reduction)", "", bnk->eta3, &bnk->eta3, NULL));
1123:   PetscCall(PetscOptionsReal("-tao_bnk_eta4", "(developer) threshold for accepting good step (-tao_bnk_update_type reduction)", "", bnk->eta4, &bnk->eta4, NULL));
1124:   PetscCall(PetscOptionsReal("-tao_bnk_alpha1", "(developer) radius reduction factor for rejected step (-tao_bnk_update_type reduction)", "", bnk->alpha1, &bnk->alpha1, NULL));
1125:   PetscCall(PetscOptionsReal("-tao_bnk_alpha2", "(developer) radius reduction factor for marginally accepted bad step (-tao_bnk_update_type reduction)", "", bnk->alpha2, &bnk->alpha2, NULL));
1126:   PetscCall(PetscOptionsReal("-tao_bnk_alpha3", "(developer) radius increase factor for reasonable accepted step (-tao_bnk_update_type reduction)", "", bnk->alpha3, &bnk->alpha3, NULL));
1127:   PetscCall(PetscOptionsReal("-tao_bnk_alpha4", "(developer) radius increase factor for good accepted step (-tao_bnk_update_type reduction)", "", bnk->alpha4, &bnk->alpha4, NULL));
1128:   PetscCall(PetscOptionsReal("-tao_bnk_alpha5", "(developer) radius increase factor for very good accepted step (-tao_bnk_update_type reduction)", "", bnk->alpha5, &bnk->alpha5, NULL));
1129:   PetscCall(PetscOptionsReal("-tao_bnk_nu1", "(developer) threshold for small line-search step length (-tao_bnk_update_type step)", "", bnk->nu1, &bnk->nu1, NULL));
1130:   PetscCall(PetscOptionsReal("-tao_bnk_nu2", "(developer) threshold for reasonable line-search step length (-tao_bnk_update_type step)", "", bnk->nu2, &bnk->nu2, NULL));
1131:   PetscCall(PetscOptionsReal("-tao_bnk_nu3", "(developer) threshold for large line-search step length (-tao_bnk_update_type step)", "", bnk->nu3, &bnk->nu3, NULL));
1132:   PetscCall(PetscOptionsReal("-tao_bnk_nu4", "(developer) threshold for very large line-search step length (-tao_bnk_update_type step)", "", bnk->nu4, &bnk->nu4, NULL));
1133:   PetscCall(PetscOptionsReal("-tao_bnk_omega1", "(developer) radius reduction factor for very small line-search step length (-tao_bnk_update_type step)", "", bnk->omega1, &bnk->omega1, NULL));
1134:   PetscCall(PetscOptionsReal("-tao_bnk_omega2", "(developer) radius reduction factor for small line-search step length (-tao_bnk_update_type step)", "", bnk->omega2, &bnk->omega2, NULL));
1135:   PetscCall(PetscOptionsReal("-tao_bnk_omega3", "(developer) radius factor for decent line-search step length (-tao_bnk_update_type step)", "", bnk->omega3, &bnk->omega3, NULL));
1136:   PetscCall(PetscOptionsReal("-tao_bnk_omega4", "(developer) radius increase factor for large line-search step length (-tao_bnk_update_type step)", "", bnk->omega4, &bnk->omega4, NULL));
1137:   PetscCall(PetscOptionsReal("-tao_bnk_omega5", "(developer) radius increase factor for very large line-search step length (-tao_bnk_update_type step)", "", bnk->omega5, &bnk->omega5, NULL));
1138:   PetscCall(PetscOptionsReal("-tao_bnk_mu1_i", "(developer) threshold for accepting very good step (-tao_bnk_init_type interpolation)", "", bnk->mu1_i, &bnk->mu1_i, NULL));
1139:   PetscCall(PetscOptionsReal("-tao_bnk_mu2_i", "(developer) threshold for accepting good step (-tao_bnk_init_type interpolation)", "", bnk->mu2_i, &bnk->mu2_i, NULL));
1140:   PetscCall(PetscOptionsReal("-tao_bnk_gamma1_i", "(developer) radius reduction factor for rejected very bad step (-tao_bnk_init_type interpolation)", "", bnk->gamma1_i, &bnk->gamma1_i, NULL));
1141:   PetscCall(PetscOptionsReal("-tao_bnk_gamma2_i", "(developer) radius reduction factor for rejected bad step (-tao_bnk_init_type interpolation)", "", bnk->gamma2_i, &bnk->gamma2_i, NULL));
1142:   PetscCall(PetscOptionsReal("-tao_bnk_gamma3_i", "(developer) radius increase factor for accepted good step (-tao_bnk_init_type interpolation)", "", bnk->gamma3_i, &bnk->gamma3_i, NULL));
1143:   PetscCall(PetscOptionsReal("-tao_bnk_gamma4_i", "(developer) radius increase factor for accepted very good step (-tao_bnk_init_type interpolation)", "", bnk->gamma4_i, &bnk->gamma4_i, NULL));
1144:   PetscCall(PetscOptionsReal("-tao_bnk_theta_i", "(developer) trust region interpolation factor (-tao_bnk_init_type interpolation)", "", bnk->theta_i, &bnk->theta_i, NULL));
1145:   PetscCall(PetscOptionsReal("-tao_bnk_mu1", "(developer) threshold for accepting very good step (-tao_bnk_update_type interpolation)", "", bnk->mu1, &bnk->mu1, NULL));
1146:   PetscCall(PetscOptionsReal("-tao_bnk_mu2", "(developer) threshold for accepting good step (-tao_bnk_update_type interpolation)", "", bnk->mu2, &bnk->mu2, NULL));
1147:   PetscCall(PetscOptionsReal("-tao_bnk_gamma1", "(developer) radius reduction factor for rejected very bad step (-tao_bnk_update_type interpolation)", "", bnk->gamma1, &bnk->gamma1, NULL));
1148:   PetscCall(PetscOptionsReal("-tao_bnk_gamma2", "(developer) radius reduction factor for rejected bad step (-tao_bnk_update_type interpolation)", "", bnk->gamma2, &bnk->gamma2, NULL));
1149:   PetscCall(PetscOptionsReal("-tao_bnk_gamma3", "(developer) radius increase factor for accepted good step (-tao_bnk_update_type interpolation)", "", bnk->gamma3, &bnk->gamma3, NULL));
1150:   PetscCall(PetscOptionsReal("-tao_bnk_gamma4", "(developer) radius increase factor for accepted very good step (-tao_bnk_update_type interpolation)", "", bnk->gamma4, &bnk->gamma4, NULL));
1151:   PetscCall(PetscOptionsReal("-tao_bnk_theta", "(developer) trust region interpolation factor (-tao_bnk_update_type interpolation)", "", bnk->theta, &bnk->theta, NULL));
1152:   PetscCall(PetscOptionsReal("-tao_bnk_min_radius", "(developer) lower bound on initial radius", "", bnk->min_radius, &bnk->min_radius, NULL));
1153:   PetscCall(PetscOptionsReal("-tao_bnk_max_radius", "(developer) upper bound on radius", "", bnk->max_radius, &bnk->max_radius, NULL));
1154:   PetscCall(PetscOptionsReal("-tao_bnk_epsilon", "(developer) tolerance used when computing actual and predicted reduction", "", bnk->epsilon, &bnk->epsilon, NULL));
1155:   PetscCall(PetscOptionsReal("-tao_bnk_as_tol", "(developer) initial tolerance used when estimating actively bounded variables", "", bnk->as_tol, &bnk->as_tol, NULL));
1156:   PetscCall(PetscOptionsReal("-tao_bnk_as_step", "(developer) step length used when estimating actively bounded variables", "", bnk->as_step, &bnk->as_step, NULL));
1157:   PetscCall(PetscOptionsInt("-tao_bnk_max_cg_its", "number of BNCG iterations to take for each Newton step", "", bnk->max_cg_its, &bnk->max_cg_its, NULL));
1158:   PetscOptionsHeadEnd();

1160:   PetscCall(TaoSetOptionsPrefix(bnk->bncg, ((PetscObject)(tao))->prefix));
1161:   PetscCall(TaoAppendOptionsPrefix(bnk->bncg, "tao_bnk_cg_"));
1162:   PetscCall(TaoSetFromOptions(bnk->bncg));

1164:   PetscCall(KSPSetOptionsPrefix(tao->ksp, ((PetscObject)(tao))->prefix));
1165:   PetscCall(KSPAppendOptionsPrefix(tao->ksp, "tao_bnk_"));
1166:   PetscCall(KSPSetFromOptions(tao->ksp));
1167:   PetscFunctionReturn(PETSC_SUCCESS);
1168: }

1170: /*------------------------------------------------------------*/

1172: PetscErrorCode TaoView_BNK(Tao tao, PetscViewer viewer)
1173: {
1174:   TAO_BNK  *bnk = (TAO_BNK *)tao->data;
1175:   PetscInt  nrejects;
1176:   PetscBool isascii;

1178:   PetscFunctionBegin;
1179:   PetscCall(PetscObjectTypeCompare((PetscObject)viewer, PETSCVIEWERASCII, &isascii));
1180:   if (isascii) {
1181:     PetscCall(PetscViewerASCIIPushTab(viewer));
1182:     PetscCall(TaoView(bnk->bncg, viewer));
1183:     if (bnk->M) {
1184:       PetscCall(MatLMVMGetRejectCount(bnk->M, &nrejects));
1185:       PetscCall(PetscViewerASCIIPrintf(viewer, "Rejected BFGS updates: %" PetscInt_FMT "\n", nrejects));
1186:     }
1187:     PetscCall(PetscViewerASCIIPrintf(viewer, "CG steps: %" PetscInt_FMT "\n", bnk->tot_cg_its));
1188:     PetscCall(PetscViewerASCIIPrintf(viewer, "Newton steps: %" PetscInt_FMT "\n", bnk->newt));
1189:     if (bnk->M) PetscCall(PetscViewerASCIIPrintf(viewer, "BFGS steps: %" PetscInt_FMT "\n", bnk->bfgs));
1190:     PetscCall(PetscViewerASCIIPrintf(viewer, "Scaled gradient steps: %" PetscInt_FMT "\n", bnk->sgrad));
1191:     PetscCall(PetscViewerASCIIPrintf(viewer, "Gradient steps: %" PetscInt_FMT "\n", bnk->grad));
1192:     PetscCall(PetscViewerASCIIPrintf(viewer, "KSP termination reasons:\n"));
1193:     PetscCall(PetscViewerASCIIPrintf(viewer, "  atol: %" PetscInt_FMT "\n", bnk->ksp_atol));
1194:     PetscCall(PetscViewerASCIIPrintf(viewer, "  rtol: %" PetscInt_FMT "\n", bnk->ksp_rtol));
1195:     PetscCall(PetscViewerASCIIPrintf(viewer, "  ctol: %" PetscInt_FMT "\n", bnk->ksp_ctol));
1196:     PetscCall(PetscViewerASCIIPrintf(viewer, "  negc: %" PetscInt_FMT "\n", bnk->ksp_negc));
1197:     PetscCall(PetscViewerASCIIPrintf(viewer, "  dtol: %" PetscInt_FMT "\n", bnk->ksp_dtol));
1198:     PetscCall(PetscViewerASCIIPrintf(viewer, "  iter: %" PetscInt_FMT "\n", bnk->ksp_iter));
1199:     PetscCall(PetscViewerASCIIPrintf(viewer, "  othr: %" PetscInt_FMT "\n", bnk->ksp_othr));
1200:     PetscCall(PetscViewerASCIIPopTab(viewer));
1201:   }
1202:   PetscFunctionReturn(PETSC_SUCCESS);
1203: }

1205: /* ---------------------------------------------------------- */

1207: /*MC
1208:   TAOBNK - Shared base-type for Bounded Newton-Krylov type algorithms.
1209:   At each iteration, the BNK methods solve the symmetric
1210:   system of equations to obtain the step direction dk:
1211:               Hk dk = -gk
1212:   for free variables only. The step can be globalized either through
1213:   trust-region methods, or a line search, or a heuristic mixture of both.

1215:     Options Database Keys:
1216: + -tao_bnk_max_cg_its - maximum number of bounded conjugate-gradient iterations taken in each Newton loop
1217: . -tao_bnk_init_type - trust radius initialization method ("constant", "direction", "interpolation")
1218: . -tao_bnk_update_type - trust radius update method ("step", "direction", "interpolation")
1219: . -tao_bnk_as_type - active-set estimation method ("none", "bertsekas")
1220: . -tao_bnk_as_tol - (developer) initial tolerance used in estimating bounded active variables (-as_type bertsekas)
1221: . -tao_bnk_as_step - (developer) trial step length used in estimating bounded active variables (-as_type bertsekas)
1222: . -tao_bnk_sval - (developer) Hessian perturbation starting value
1223: . -tao_bnk_imin - (developer) minimum initial Hessian perturbation
1224: . -tao_bnk_imax - (developer) maximum initial Hessian perturbation
1225: . -tao_bnk_pmin - (developer) minimum Hessian perturbation
1226: . -tao_bnk_pmax - (developer) aximum Hessian perturbation
1227: . -tao_bnk_pgfac - (developer) Hessian perturbation growth factor
1228: . -tao_bnk_psfac - (developer) Hessian perturbation shrink factor
1229: . -tao_bnk_imfac - (developer) initial merit factor for Hessian perturbation
1230: . -tao_bnk_pmgfac - (developer) merit growth factor for Hessian perturbation
1231: . -tao_bnk_pmsfac - (developer) merit shrink factor for Hessian perturbation
1232: . -tao_bnk_eta1 - (developer) threshold for rejecting step (-update_type reduction)
1233: . -tao_bnk_eta2 - (developer) threshold for accepting marginal step (-update_type reduction)
1234: . -tao_bnk_eta3 - (developer) threshold for accepting reasonable step (-update_type reduction)
1235: . -tao_bnk_eta4 - (developer) threshold for accepting good step (-update_type reduction)
1236: . -tao_bnk_alpha1 - (developer) radius reduction factor for rejected step (-update_type reduction)
1237: . -tao_bnk_alpha2 - (developer) radius reduction factor for marginally accepted bad step (-update_type reduction)
1238: . -tao_bnk_alpha3 - (developer) radius increase factor for reasonable accepted step (-update_type reduction)
1239: . -tao_bnk_alpha4 - (developer) radius increase factor for good accepted step (-update_type reduction)
1240: . -tao_bnk_alpha5 - (developer) radius increase factor for very good accepted step (-update_type reduction)
1241: . -tao_bnk_epsilon - (developer) tolerance for small pred/actual ratios that trigger automatic step acceptance (-update_type reduction)
1242: . -tao_bnk_mu1 - (developer) threshold for accepting very good step (-update_type interpolation)
1243: . -tao_bnk_mu2 - (developer) threshold for accepting good step (-update_type interpolation)
1244: . -tao_bnk_gamma1 - (developer) radius reduction factor for rejected very bad step (-update_type interpolation)
1245: . -tao_bnk_gamma2 - (developer) radius reduction factor for rejected bad step (-update_type interpolation)
1246: . -tao_bnk_gamma3 - (developer) radius increase factor for accepted good step (-update_type interpolation)
1247: . -tao_bnk_gamma4 - (developer) radius increase factor for accepted very good step (-update_type interpolation)
1248: . -tao_bnk_theta - (developer) trust region interpolation factor (-update_type interpolation)
1249: . -tao_bnk_nu1 - (developer) threshold for small line-search step length (-update_type step)
1250: . -tao_bnk_nu2 - (developer) threshold for reasonable line-search step length (-update_type step)
1251: . -tao_bnk_nu3 - (developer) threshold for large line-search step length (-update_type step)
1252: . -tao_bnk_nu4 - (developer) threshold for very large line-search step length (-update_type step)
1253: . -tao_bnk_omega1 - (developer) radius reduction factor for very small line-search step length (-update_type step)
1254: . -tao_bnk_omega2 - (developer) radius reduction factor for small line-search step length (-update_type step)
1255: . -tao_bnk_omega3 - (developer) radius factor for decent line-search step length (-update_type step)
1256: . -tao_bnk_omega4 - (developer) radius increase factor for large line-search step length (-update_type step)
1257: . -tao_bnk_omega5 - (developer) radius increase factor for very large line-search step length (-update_type step)
1258: . -tao_bnk_mu1_i -  (developer) threshold for accepting very good step (-init_type interpolation)
1259: . -tao_bnk_mu2_i -  (developer) threshold for accepting good step (-init_type interpolation)
1260: . -tao_bnk_gamma1_i - (developer) radius reduction factor for rejected very bad step (-init_type interpolation)
1261: . -tao_bnk_gamma2_i - (developer) radius reduction factor for rejected bad step (-init_type interpolation)
1262: . -tao_bnk_gamma3_i - (developer) radius increase factor for accepted good step (-init_type interpolation)
1263: . -tao_bnk_gamma4_i - (developer) radius increase factor for accepted very good step (-init_type interpolation)
1264: - -tao_bnk_theta_i - (developer) trust region interpolation factor (-init_type interpolation)

1266:   Level: beginner
1267: M*/

1269: PetscErrorCode TaoCreate_BNK(Tao tao)
1270: {
1271:   TAO_BNK *bnk;
1272:   PC       pc;

1274:   PetscFunctionBegin;
1275:   PetscCall(PetscNew(&bnk));

1277:   tao->ops->setup          = TaoSetUp_BNK;
1278:   tao->ops->view           = TaoView_BNK;
1279:   tao->ops->setfromoptions = TaoSetFromOptions_BNK;
1280:   tao->ops->destroy        = TaoDestroy_BNK;

1282:   /*  Override default settings (unless already changed) */
1283:   if (!tao->max_it_changed) tao->max_it = 50;
1284:   if (!tao->trust0_changed) tao->trust0 = 100.0;

1286:   tao->data = (void *)bnk;

1288:   /*  Hessian shifting parameters */
1289:   bnk->computehessian = TaoBNKComputeHessian;
1290:   bnk->computestep    = TaoBNKComputeStep;

1292:   bnk->sval  = 0.0;
1293:   bnk->imin  = 1.0e-4;
1294:   bnk->imax  = 1.0e+2;
1295:   bnk->imfac = 1.0e-1;

1297:   bnk->pmin   = 1.0e-12;
1298:   bnk->pmax   = 1.0e+2;
1299:   bnk->pgfac  = 1.0e+1;
1300:   bnk->psfac  = 4.0e-1;
1301:   bnk->pmgfac = 1.0e-1;
1302:   bnk->pmsfac = 1.0e-1;

1304:   /*  Default values for trust-region radius update based on steplength */
1305:   bnk->nu1 = 0.25;
1306:   bnk->nu2 = 0.50;
1307:   bnk->nu3 = 1.00;
1308:   bnk->nu4 = 1.25;

1310:   bnk->omega1 = 0.25;
1311:   bnk->omega2 = 0.50;
1312:   bnk->omega3 = 1.00;
1313:   bnk->omega4 = 2.00;
1314:   bnk->omega5 = 4.00;

1316:   /*  Default values for trust-region radius update based on reduction */
1317:   bnk->eta1 = 1.0e-4;
1318:   bnk->eta2 = 0.25;
1319:   bnk->eta3 = 0.50;
1320:   bnk->eta4 = 0.90;

1322:   bnk->alpha1 = 0.25;
1323:   bnk->alpha2 = 0.50;
1324:   bnk->alpha3 = 1.00;
1325:   bnk->alpha4 = 2.00;
1326:   bnk->alpha5 = 4.00;

1328:   /*  Default values for trust-region radius update based on interpolation */
1329:   bnk->mu1 = 0.10;
1330:   bnk->mu2 = 0.50;

1332:   bnk->gamma1 = 0.25;
1333:   bnk->gamma2 = 0.50;
1334:   bnk->gamma3 = 2.00;
1335:   bnk->gamma4 = 4.00;

1337:   bnk->theta = 0.05;

1339:   /*  Default values for trust region initialization based on interpolation */
1340:   bnk->mu1_i = 0.35;
1341:   bnk->mu2_i = 0.50;

1343:   bnk->gamma1_i = 0.0625;
1344:   bnk->gamma2_i = 0.5;
1345:   bnk->gamma3_i = 2.0;
1346:   bnk->gamma4_i = 5.0;

1348:   bnk->theta_i = 0.25;

1350:   /*  Remaining parameters */
1351:   bnk->max_cg_its = 0;
1352:   bnk->min_radius = 1.0e-10;
1353:   bnk->max_radius = 1.0e10;
1354:   bnk->epsilon    = PetscPowReal(PETSC_MACHINE_EPSILON, 2.0 / 3.0);
1355:   bnk->as_tol     = 1.0e-3;
1356:   bnk->as_step    = 1.0e-3;
1357:   bnk->dmin       = 1.0e-6;
1358:   bnk->dmax       = 1.0e6;

1360:   bnk->M           = NULL;
1361:   bnk->bfgs_pre    = NULL;
1362:   bnk->init_type   = BNK_INIT_INTERPOLATION;
1363:   bnk->update_type = BNK_UPDATE_REDUCTION;
1364:   bnk->as_type     = BNK_AS_BERTSEKAS;

1366:   /* Create the embedded BNCG solver */
1367:   PetscCall(TaoCreate(PetscObjectComm((PetscObject)tao), &bnk->bncg));
1368:   PetscCall(PetscObjectIncrementTabLevel((PetscObject)bnk->bncg, (PetscObject)tao, 1));
1369:   PetscCall(TaoSetType(bnk->bncg, TAOBNCG));

1371:   /* Create the line search */
1372:   PetscCall(TaoLineSearchCreate(((PetscObject)tao)->comm, &tao->linesearch));
1373:   PetscCall(PetscObjectIncrementTabLevel((PetscObject)tao->linesearch, (PetscObject)tao, 1));
1374:   PetscCall(TaoLineSearchSetType(tao->linesearch, TAOLINESEARCHMT));
1375:   PetscCall(TaoLineSearchUseTaoRoutines(tao->linesearch, tao));

1377:   /*  Set linear solver to default for symmetric matrices */
1378:   PetscCall(KSPCreate(((PetscObject)tao)->comm, &tao->ksp));
1379:   PetscCall(PetscObjectIncrementTabLevel((PetscObject)tao->ksp, (PetscObject)tao, 1));
1380:   PetscCall(KSPSetType(tao->ksp, KSPSTCG));
1381:   PetscCall(KSPGetPC(tao->ksp, &pc));
1382:   PetscCall(PCSetType(pc, PCLMVM));
1383:   PetscFunctionReturn(PETSC_SUCCESS);
1384: }