Actual source code: owlqn.c

      1: #include <petsctaolinesearch.h>
      2: #include <../src/tao/unconstrained/impls/owlqn/owlqn.h>

      4: #define OWLQN_BFGS                0
      5: #define OWLQN_SCALED_GRADIENT     1
      6: #define OWLQN_GRADIENT            2

      8: static PetscErrorCode ProjDirect_OWLQN(Vec d, Vec g)
      9: {
     10:   PetscErrorCode  ierr;
     11:   const PetscReal *gptr;
     12:   PetscReal       *dptr;
     13:   PetscInt        low,high,low1,high1,i;

     16:   ierr=VecGetOwnershipRange(d,&low,&high);
     17:   ierr=VecGetOwnershipRange(g,&low1,&high1);

     19:   VecGetArrayRead(g,&gptr);
     20:   VecGetArray(d,&dptr);
     21:   for (i = 0; i < high-low; i++) {
     22:     if (dptr[i] * gptr[i] <= 0.0) {
     23:       dptr[i] = 0.0;
     24:     }
     25:   }
     26:   VecRestoreArray(d,&dptr);
     27:   VecRestoreArrayRead(g,&gptr);
     28:   return(0);
     29: }

     31: static PetscErrorCode ComputePseudoGrad_OWLQN(Vec x, Vec gv, PetscReal lambda)
     32: {
     33:   PetscErrorCode  ierr;
     34:   const PetscReal *xptr;
     35:   PetscReal       *gptr;
     36:   PetscInt        low,high,low1,high1,i;

     39:   ierr=VecGetOwnershipRange(x,&low,&high);
     40:   ierr=VecGetOwnershipRange(gv,&low1,&high1);

     42:   VecGetArrayRead(x,&xptr);
     43:   VecGetArray(gv,&gptr);
     44:   for (i = 0; i < high-low; i++) {
     45:     if (xptr[i] < 0.0)               gptr[i] = gptr[i] - lambda;
     46:     else if (xptr[i] > 0.0)          gptr[i] = gptr[i] + lambda;
     47:     else if (gptr[i] + lambda < 0.0) gptr[i] = gptr[i] + lambda;
     48:     else if (gptr[i] - lambda > 0.0) gptr[i] = gptr[i] - lambda;
     49:     else                             gptr[i] = 0.0;
     50:   }
     51:   VecRestoreArray(gv,&gptr);
     52:   VecRestoreArrayRead(x,&xptr);
     53:   return(0);
     54: }

     56: static PetscErrorCode TaoSolve_OWLQN(Tao tao)
     57: {
     58:   TAO_OWLQN                    *lmP = (TAO_OWLQN *)tao->data;
     59:   PetscReal                    f, fold, gdx, gnorm;
     60:   PetscReal                    step = 1.0;
     61:   PetscReal                    delta;
     62:   PetscErrorCode               ierr;
     63:   PetscInt                     stepType;
     64:   PetscInt                     iter = 0;
     65:   TaoLineSearchConvergedReason ls_status = TAOLINESEARCH_CONTINUE_ITERATING;

     68:   if (tao->XL || tao->XU || tao->ops->computebounds) {
     69:     PetscInfo(tao,"WARNING: Variable bounds have been set but will be ignored by owlqn algorithm\n");
     70:   }

     72:   /* Check convergence criteria */
     73:   TaoComputeObjectiveAndGradient(tao, tao->solution, &f, tao->gradient);
     74:   VecCopy(tao->gradient, lmP->GV);
     75:   ComputePseudoGrad_OWLQN(tao->solution,lmP->GV,lmP->lambda);
     76:   VecNorm(lmP->GV,NORM_2,&gnorm);
     77:   if (PetscIsInfOrNanReal(f) || PetscIsInfOrNanReal(gnorm)) SETERRQ(PetscObjectComm((PetscObject)tao),PETSC_ERR_USER, "User provided compute function generated Inf or NaN");

     79:   tao->reason = TAO_CONTINUE_ITERATING;
     80:   TaoLogConvergenceHistory(tao,f,gnorm,0.0,tao->ksp_its);
     81:   TaoMonitor(tao,iter,f,gnorm,0.0,step);
     82:   (*tao->ops->convergencetest)(tao,tao->cnvP);
     83:   if (tao->reason != TAO_CONTINUE_ITERATING) return(0);

     85:   /* Set initial scaling for the function */
     86:   delta = 2.0 * PetscMax(1.0, PetscAbsScalar(f)) / (gnorm*gnorm);
     87:   MatLMVMSetJ0Scale(lmP->M, delta);

     89:   /* Set counter for gradient/reset steps */
     90:   lmP->bfgs = 0;
     91:   lmP->sgrad = 0;
     92:   lmP->grad = 0;

     94:   /* Have not converged; continue with Newton method */
     95:   while (tao->reason == TAO_CONTINUE_ITERATING) {
     96:     /* Call general purpose update function */
     97:     if (tao->ops->update) {
     98:       (*tao->ops->update)(tao, tao->niter, tao->user_update);
     99:     }

    101:     /* Compute direction */
    102:     MatLMVMUpdate(lmP->M,tao->solution,tao->gradient);
    103:     MatSolve(lmP->M, lmP->GV, lmP->D);

    105:     ProjDirect_OWLQN(lmP->D,lmP->GV);

    107:     ++lmP->bfgs;

    109:     /* Check for success (descent direction) */
    110:     VecDot(lmP->D, lmP->GV , &gdx);
    111:     if ((gdx <= 0.0) || PetscIsInfOrNanReal(gdx)) {

    113:       /* Step is not descent or direction produced not a number
    114:          We can assert bfgsUpdates > 1 in this case because
    115:          the first solve produces the scaled gradient direction,
    116:          which is guaranteed to be descent

    118:          Use steepest descent direction (scaled) */
    119:       ++lmP->grad;

    121:       delta = 2.0 * PetscMax(1.0, PetscAbsScalar(f)) / (gnorm*gnorm);
    122:       MatLMVMSetJ0Scale(lmP->M, delta);
    123:       MatLMVMReset(lmP->M, PETSC_FALSE);
    124:       MatLMVMUpdate(lmP->M, tao->solution, tao->gradient);
    125:       MatSolve(lmP->M,lmP->GV, lmP->D);

    127:       ProjDirect_OWLQN(lmP->D,lmP->GV);

    129:       lmP->bfgs = 1;
    130:       ++lmP->sgrad;
    131:       stepType = OWLQN_SCALED_GRADIENT;
    132:     } else {
    133:       if (1 == lmP->bfgs) {
    134:         /* The first BFGS direction is always the scaled gradient */
    135:         ++lmP->sgrad;
    136:         stepType = OWLQN_SCALED_GRADIENT;
    137:       } else {
    138:         ++lmP->bfgs;
    139:         stepType = OWLQN_BFGS;
    140:       }
    141:     }

    143:     VecScale(lmP->D, -1.0);

    145:     /* Perform the linesearch */
    146:     fold = f;
    147:     VecCopy(tao->solution, lmP->Xold);
    148:     VecCopy(tao->gradient, lmP->Gold);

    150:     TaoLineSearchApply(tao->linesearch, tao->solution, &f, lmP->GV, lmP->D, &step,&ls_status);
    151:     TaoAddLineSearchCounts(tao);

    153:     while (((int)ls_status < 0) && (stepType != OWLQN_GRADIENT)) {

    155:       /* Reset factors and use scaled gradient step */
    156:       f = fold;
    157:       VecCopy(lmP->Xold, tao->solution);
    158:       VecCopy(lmP->Gold, tao->gradient);
    159:       VecCopy(tao->gradient, lmP->GV);

    161:       ComputePseudoGrad_OWLQN(tao->solution,lmP->GV,lmP->lambda);

    163:       switch(stepType) {
    164:       case OWLQN_BFGS:
    165:         /* Failed to obtain acceptable iterate with BFGS step
    166:            Attempt to use the scaled gradient direction */

    168:         delta = 2.0 * PetscMax(1.0, PetscAbsScalar(f)) / (gnorm*gnorm);
    169:         MatLMVMSetJ0Scale(lmP->M, delta);
    170:         MatLMVMReset(lmP->M, PETSC_FALSE);
    171:         MatLMVMUpdate(lmP->M, tao->solution, tao->gradient);
    172:         MatSolve(lmP->M, lmP->GV, lmP->D);

    174:         ProjDirect_OWLQN(lmP->D,lmP->GV);

    176:         lmP->bfgs = 1;
    177:         ++lmP->sgrad;
    178:         stepType = OWLQN_SCALED_GRADIENT;
    179:         break;

    181:       case OWLQN_SCALED_GRADIENT:
    182:         /* The scaled gradient step did not produce a new iterate;
    183:            attempt to use the gradient direction.
    184:            Need to make sure we are not using a different diagonal scaling */
    185:         MatLMVMSetJ0Scale(lmP->M, 1.0);
    186:         MatLMVMReset(lmP->M, PETSC_FALSE);
    187:         MatLMVMUpdate(lmP->M, tao->solution, tao->gradient);
    188:         MatSolve(lmP->M, lmP->GV, lmP->D);

    190:         ProjDirect_OWLQN(lmP->D,lmP->GV);

    192:         lmP->bfgs = 1;
    193:         ++lmP->grad;
    194:         stepType = OWLQN_GRADIENT;
    195:         break;
    196:       }
    197:       VecScale(lmP->D, -1.0);

    199:       /* Perform the linesearch */
    200:       TaoLineSearchApply(tao->linesearch, tao->solution, &f, lmP->GV, lmP->D, &step, &ls_status);
    201:       TaoAddLineSearchCounts(tao);
    202:     }

    204:     if ((int)ls_status < 0) {
    205:       /* Failed to find an improving point*/
    206:       f = fold;
    207:       VecCopy(lmP->Xold, tao->solution);
    208:       VecCopy(lmP->Gold, tao->gradient);
    209:       VecCopy(tao->gradient, lmP->GV);
    210:       step = 0.0;
    211:     } else {
    212:       /* a little hack here, because that gv is used to store g */
    213:       VecCopy(lmP->GV, tao->gradient);
    214:     }

    216:     ComputePseudoGrad_OWLQN(tao->solution,lmP->GV,lmP->lambda);

    218:     /* Check for termination */

    220:     VecNorm(lmP->GV,NORM_2,&gnorm);

    222:     iter++;
    223:     TaoLogConvergenceHistory(tao,f,gnorm,0.0,tao->ksp_its);
    224:     TaoMonitor(tao,iter,f,gnorm,0.0,step);
    225:     (*tao->ops->convergencetest)(tao,tao->cnvP);

    227:     if ((int)ls_status < 0) break;
    228:   }
    229:   return(0);
    230: }

    232: static PetscErrorCode TaoSetUp_OWLQN(Tao tao)
    233: {
    234:   TAO_OWLQN      *lmP = (TAO_OWLQN *)tao->data;
    235:   PetscInt       n,N;

    239:   /* Existence of tao->solution checked in TaoSetUp() */
    240:   if (!tao->gradient) {VecDuplicate(tao->solution,&tao->gradient);  }
    241:   if (!tao->stepdirection) {VecDuplicate(tao->solution,&tao->stepdirection);  }
    242:   if (!lmP->D) {VecDuplicate(tao->solution,&lmP->D);  }
    243:   if (!lmP->GV) {VecDuplicate(tao->solution,&lmP->GV);  }
    244:   if (!lmP->Xold) {VecDuplicate(tao->solution,&lmP->Xold);  }
    245:   if (!lmP->Gold) {VecDuplicate(tao->solution,&lmP->Gold);  }

    247:   /* Create matrix for the limited memory approximation */
    248:   VecGetLocalSize(tao->solution,&n);
    249:   VecGetSize(tao->solution,&N);
    250:   MatCreateLMVMBFGS(((PetscObject)tao)->comm,n,N,&lmP->M);
    251:   MatLMVMAllocate(lmP->M,tao->solution,tao->gradient);
    252:   return(0);
    253: }

    255: /* ---------------------------------------------------------- */
    256: static PetscErrorCode TaoDestroy_OWLQN(Tao tao)
    257: {
    258:   TAO_OWLQN      *lmP = (TAO_OWLQN *)tao->data;

    262:   if (tao->setupcalled) {
    263:     VecDestroy(&lmP->Xold);
    264:     VecDestroy(&lmP->Gold);
    265:     VecDestroy(&lmP->D);
    266:     MatDestroy(&lmP->M);
    267:     VecDestroy(&lmP->GV);
    268:   }
    269:   PetscFree(tao->data);
    270:   return(0);
    271: }

    273: /*------------------------------------------------------------*/
    274: static PetscErrorCode TaoSetFromOptions_OWLQN(PetscOptionItems *PetscOptionsObject,Tao tao)
    275: {
    276:   TAO_OWLQN      *lmP = (TAO_OWLQN *)tao->data;

    280:   PetscOptionsHead(PetscOptionsObject,"Orthant-Wise Limited-memory method for Quasi-Newton unconstrained optimization");
    281:   PetscOptionsReal("-tao_owlqn_lambda", "regulariser weight","", 100,&lmP->lambda,NULL);
    282:   PetscOptionsTail();
    283:   TaoLineSearchSetFromOptions(tao->linesearch);
    284:   return(0);
    285: }

    287: /*------------------------------------------------------------*/
    288: static PetscErrorCode TaoView_OWLQN(Tao tao, PetscViewer viewer)
    289: {
    290:   TAO_OWLQN      *lm = (TAO_OWLQN *)tao->data;
    291:   PetscBool      isascii;

    295:   PetscObjectTypeCompare((PetscObject)viewer, PETSCVIEWERASCII, &isascii);
    296:   if (isascii) {
    297:     PetscViewerASCIIPushTab(viewer);
    298:     PetscViewerASCIIPrintf(viewer, "BFGS steps: %D\n", lm->bfgs);
    299:     PetscViewerASCIIPrintf(viewer, "Scaled gradient steps: %D\n", lm->sgrad);
    300:     PetscViewerASCIIPrintf(viewer, "Gradient steps: %D\n", lm->grad);
    301:     PetscViewerASCIIPopTab(viewer);
    302:   }
    303:   return(0);
    304: }

    306: /* ---------------------------------------------------------- */
    307: /*MC
    308:   TAOOWLQN - orthant-wise limited memory quasi-newton algorithm

    310: . - tao_owlqn_lambda - regulariser weight

    312:   Level: beginner
    313: M*/

    316: PETSC_EXTERN PetscErrorCode TaoCreate_OWLQN(Tao tao)
    317: {
    318:   TAO_OWLQN      *lmP;
    319:   const char     *owarmijo_type = TAOLINESEARCHOWARMIJO;

    323:   tao->ops->setup = TaoSetUp_OWLQN;
    324:   tao->ops->solve = TaoSolve_OWLQN;
    325:   tao->ops->view = TaoView_OWLQN;
    326:   tao->ops->setfromoptions = TaoSetFromOptions_OWLQN;
    327:   tao->ops->destroy = TaoDestroy_OWLQN;

    329:   PetscNewLog(tao,&lmP);
    330:   lmP->D = NULL;
    331:   lmP->M = NULL;
    332:   lmP->GV = NULL;
    333:   lmP->Xold = NULL;
    334:   lmP->Gold = NULL;
    335:   lmP->lambda = 1.0;

    337:   tao->data = (void*)lmP;
    338:   /* Override default settings (unless already changed) */
    339:   if (!tao->max_it_changed) tao->max_it = 2000;
    340:   if (!tao->max_funcs_changed) tao->max_funcs = 4000;

    342:   TaoLineSearchCreate(((PetscObject)tao)->comm,&tao->linesearch);
    343:   PetscObjectIncrementTabLevel((PetscObject)tao->linesearch, (PetscObject)tao, 1);
    344:   TaoLineSearchSetType(tao->linesearch,owarmijo_type);
    345:   TaoLineSearchUseTaoRoutines(tao->linesearch,tao);
    346:   TaoLineSearchSetOptionsPrefix(tao->linesearch,tao->hdr.prefix);
    347:   return(0);
    348: }