Actual source code: projectedarmijo.c

      1: #include "projectedarmijo.h"

      3: #define REPLACE_FIFO 1
      4: #define REPLACE_MRU  2

      6: #define REFERENCE_MAX 1
      7: #define REFERENCE_AVE 2
      8: #define REFERENCE_MEAN 3

     10: static int TaoSetOptions_ProjectedArmijo(TAO_SOLVER,void*);
     11: static int TaoView_ProjectedArmijo(TAO_SOLVER,void*);
     12: static int TaoApply_ProjectedArmijo(TAO_SOLVER,TaoVec*,TaoVec*,TaoVec*,TaoVec*,
     13:                            double*,double*,int*,void*);
     14: static int TaoDestroy_ProjectedArmijo(TAO_SOLVER,void*);

     16: /* ---------------------------------------------------------- */
     19: static int TaoDestroy_ProjectedArmijo(TAO_SOLVER tao, void*ctx)
     20: {
     21:   TAO_PROJECTEDARMIJO *ls = (TAO_PROJECTEDARMIJO *)ctx;
     22:   int info;

     24:   TaoFunctionBegin;
     25:   if (ls->work != TAO_NULL) {
     26:     delete ls->work;
     27:   }
     28:   if (ls->GG != TAO_NULL) {
     29:     delete ls->GG;
     30:   }

     32:   if (ls->memory != TAO_NULL) {
     33:     info = TaoFree(ls->memory); CHKERRQ(info);
     34:     ls->memory = TAO_NULL;
     35:   }
     36:   info = TaoFree(ls); CHKERRQ(info);
     37:   TaoFunctionReturn(0);
     38: }

     40: /*------------------------------------------------------------*/
     43: static int TaoSetOptions_ProjectedArmijo(TAO_SOLVER tao, void*ctx)
     44: {
     45:   TAO_PROJECTEDARMIJO *ls = (TAO_PROJECTEDARMIJO *)ctx;
     46:   int info;

     48:   TaoFunctionBegin;
     49:   info = TaoOptionsHead("Projected Armijo linesearch options");CHKERRQ(info);
     50:   info = TaoOptionDouble("-tao_projected_armijo_alpha", "initial reference constant", "", ls->alpha, &ls->alpha, 0); CHKERRQ(info);
     51:   info = TaoOptionDouble("-tao_projected_armijo_beta", "decrease constant", "", ls->beta, &ls->beta, 0); CHKERRQ(info);
     52:   info = TaoOptionDouble("-tao_projected_armijo_sigma", "acceptance constant", "", ls->sigma, &ls->sigma, 0); CHKERRQ(info);
     53:   info = TaoOptionInt("-tao_projected_armijo_memory_size", "number of historical elements", "", ls->memorySize, &ls->memorySize, 0); CHKERRQ(info);
     54:   info = TaoOptionDouble("-tao_projected_armijo_minimum_step", "minimum acceptable step", "", ls->minimumStep, &ls->minimumStep, 0); CHKERRQ(info);
     55:   info = TaoOptionInt("-tao_projected_armijo_reference_policy", "policy for updating reference value", "", ls->referencePolicy, &ls->referencePolicy, 0); CHKERRQ(info);
     56:   info = TaoOptionInt("-tao_projected_armijo_replacement_policy", "policy for updating memory", "", ls->replacementPolicy, &ls->replacementPolicy, 0); CHKERRQ(info);
     57:   info = TaoOptionsTail();CHKERRQ(info);
     58:   TaoFunctionReturn(0);
     59: }
     60: /*------------------------------------------------------------*/

     64: static int TaoView_ProjectedArmijo(TAO_SOLVER tao, void *ctx)
     65: {
     66:   TAO_PROJECTEDARMIJO *ls = (TAO_PROJECTEDARMIJO *)ctx;
     67:   int info;

     69:   TaoFunctionBegin;

     71:   info=TaoPrintDouble(tao,"  Projected Armijo linesearch: alpha=%g",ls->alpha);CHKERRQ(info);
     72:   info=TaoPrintDouble(tao," beta=%g ",ls->beta);CHKERRQ(info);
     73:   info=TaoPrintDouble(tao,"sigma=%g ",ls->sigma);CHKERRQ(info);
     74:   info=TaoPrintDouble(tao,"minstep=%g,",ls->minimumStep);CHKERRQ(info);
     75:   info=TaoPrintInt(tao,"memsize=%d\n",ls->memorySize);CHKERRQ(info);

     77:   TaoFunctionReturn(0);
     78: }

     82: static int TaoApply_PreProjectedArmijo(TAO_SOLVER tao, TAO_PROJECTEDARMIJO *ls,
     83:                                        double f, double step,
     84:                                        double *ref, int *idx, int *info2)
     85: {
     86:   int info, i;

     88:   TaoFunctionBegin;

     90:   *info2 = 0;

     92:   // Check linesearch parameters
     93:   if (step < 0) {
     94:     info = PetscLogInfo((tao, "TaoApply_ProjectedArmijo:Line search error: step (%g) < 0\n", step)); CHKERRQ(info);
     95:     *info2 = -1;
     96:     TaoFunctionReturn(0);
     97:   } else if (ls->alpha < 1) {
     98:     info = PetscLogInfo((tao,"TaoApply_ProjectedArmijo:Line search error: alpha (%g) < 1\n", ls->alpha)); CHKERRQ(info);
     99:     *info2 = -2;
    100:     TaoFunctionReturn(0);
    101:   } else if ((ls->beta <= 0) || (ls->beta >= 1)) {
    102:     info = PetscLogInfo((tao,"TaoApply_ProjectedArmijo:Line search error: beta (%g) invalid\n", ls->beta)); CHKERRQ(info);
    103:     *info2 = -3;
    104:     TaoFunctionReturn(0);
    105:   } else if ((ls->sigma <= 0) || (ls->sigma >= 0.5)) {
    106:     info = PetscLogInfo((tao,"TaoApply_ProjectedArmijo:Line search error: sigma (%g) invalid\n", ls->sigma)); CHKERRQ(info);
    107:     *info2 = -4;
    108:     TaoFunctionReturn(0);
    109:   } else if (ls->minimumStep <= 0) {
    110:     info = PetscLogInfo((tao,"TaoApply_ProjectedArmijo:Line search error: minimum_step (%g) <= 0\n", ls->minimumStep)); CHKERRQ(info);
    111:     *info2 = -5;
    112:     TaoFunctionReturn(0);
    113:   } else if (ls->memorySize < 1) {
    114:     info = PetscLogInfo((tao,"TaoApply_ProjectedArmijo:Line search error: memory_size (%d) < 1\n", ls->memorySize)); CHKERRQ(info);
    115:     *info2 = -6;
    116:     TaoFunctionReturn(0);
    117:   } else if ((ls->referencePolicy != REFERENCE_MAX) &&
    118:              (ls->referencePolicy != REFERENCE_AVE) &&
    119:              (ls->referencePolicy != REFERENCE_MEAN)){
    120:     info = PetscLogInfo((tao,"TaoApply_ProjectedArmijo:Line search error: reference_policy invalid\n")); CHKERRQ(info);
    121:     *info2 = -7;
    122:     TaoFunctionReturn(0);
    123:   } else if ((ls->replacementPolicy != REPLACE_FIFO) &&
    124:              (ls->replacementPolicy != REPLACE_MRU)) {
    125:     info = PetscLogInfo((tao,"TaoApply_ProjectedArmijo:Line search error: replacement_policy invalid\n")); CHKERRQ(info);
    126:     *info2 = -8;
    127:     TaoFunctionReturn(0);
    128:   }

    130:   // Check to see of the memory has been allocated.  If not, allocate
    131:   // the historical array and populate it with the initial function
    132:   // values.

    134:   if (ls->memory == TAO_NULL) {
    135:     info = TaoMalloc(sizeof(double)*ls->memorySize, &ls->memory);CHKERRQ(info);
    136:     info = PetscLogObjectMemory(tao, sizeof(double)*ls->memorySize); CHKERRQ(info);
    137:   }

    139:   if (tao->iter == 0) {
    140:     for (i = 0; i < ls->memorySize; i++) {
    141:       ls->memory[i] = ls->alpha*(f);
    142:     }

    144:     ls->current = 0;
    145:     ls->lastReference = ls->memory[0];
    146:   }

    148:   // Calculate reference value (MAX)
    149:   *ref = ls->memory[0];
    150:   *idx = 0;

    152:   for (i = 1; i < ls->memorySize; i++) {
    153:     if (ls->memory[i] > *ref) {
    154:       *ref = ls->memory[i];
    155:       *idx = i;
    156:     }
    157:   }

    159:   if (ls->referencePolicy == REFERENCE_AVE) {
    160:     *ref = 0;
    161:     for (i = 0; i < ls->memorySize; i++) {
    162:       *ref += ls->memory[i];
    163:     }
    164:     *ref = *ref / ls->memorySize;
    165:     *ref = TaoMax(*ref, ls->memory[ls->current]);
    166:   } else if (ls->referencePolicy == REFERENCE_MEAN) {
    167:     *ref = TaoMin(*ref, 0.5*(ls->lastReference + ls->memory[ls->current]));
    168:   }

    170:   TaoFunctionReturn(0);
    171: }

    175: static int TaoApply_PostProjectedArmijo(TAO_SOLVER tao, TAO_PROJECTEDARMIJO *ls,
    176:                                         double f, double step,
    177:                                         double ref, int idx, int *info2)
    178: {
    179:   int info;
    180:   TaoFunctionBegin;

    182:   *info2 = 0;

    184:   // Check termination
    185:   if (step < ls->minimumStep) {
    186:     info = PetscLogInfo((tao, "TaoApply_ProjectedArmijo:Step is at lower bound.\n")); CHKERRQ(info);
    187:     *info2 = 1;
    188:     TaoFunctionReturn(0);
    189:   }

    191:   // Successful termination, update memory
    192:   ls->lastReference = ref;
    193:   if (ls->replacementPolicy == REPLACE_FIFO) {
    194:     ls->memory[ls->current++] = f;
    195:     if (ls->current >= ls->memorySize) {
    196:       ls->current = 0;
    197:     }
    198:   } else {
    199:     ls->current = idx;
    200:     ls->memory[idx] = f;
    201:   }
    202:   TaoFunctionReturn(0);
    203: }

    205: /* ---------------------------------------------------------- */
    208: /* @ TaoApply_ProjectedArmijo - This routine performs a linesearch. It
    209:    backtracks until the (nonmonotone) Projected Armijo conditions are satisfied.

    211:    Input Parameters:
    212: +  tao - TAO_SOLVER context
    213: .  X - current iterate (on output X contains new iterate, X + step*S)
    214: .  S - search direction
    215: .  f - merit function evaluated at X
    216: .  G - gradient of merit function evaluated at X
    217: .  W - work vector
    218: -  step - initial estimate of step length

    220:    Output parameters:
    221: +  f - merit function evaluated at new iterate, X + step*S
    222: .  G - gradient of merit function evaluated at new iterate, X + step*S
    223: .  X - new iterate
    224: -  step - final step length

    226:    Info is set to one of:
    227: .   0 - the line search succeeds; the sufficient decrease
    228:    condition and the directional derivative condition hold

    230:    negative number if an input parameter is invalid
    231: -   -1 -  step < 0

    233:    positive number > 1 if the line search otherwise terminates
    234: +    1 -  Step is at the lower bound, stepmin.
    235: @ */

    237: static int TaoApply_ProjectedArmijo(TAO_SOLVER tao, TaoVec *X, TaoVec *G,
    238:                                     TaoVec *S, TaoVec *W,
    239:                                     double *f, double *step,
    240:                                     int *info2, void *ctx)
    241: {
    242:   TAO_PROJECTEDARMIJO *ls = (TAO_PROJECTEDARMIJO *)ctx;
    243:   TaoVec *GG, *L, *U, *work;
    244:   double ref, innerd, t;
    245:   int idx, info;
    246:   TaoTruth flag;

    248:   TaoFunctionBegin;

    250:   info = TaoApply_PreProjectedArmijo(tao, ls, *f, *step, &ref, &idx, info2);
    251:   if (*info2) {
    252:     TaoFunctionReturn(0);
    253:   }

    255:   if (ls->work!=TAO_NULL){
    256:     info=X->Compatible(ls->work,&flag); CHKERRQ(info);
    257:     if (flag==TAO_FALSE){
    258:       info=TaoVecDestroy(ls->work); CHKERRQ(info);
    259:       ls->work=TAO_NULL;
    260:     }
    261:   }

    263:   if (ls->work == TAO_NULL) {
    264:      G->Clone(&(ls->work));
    265:   }
    266:   if (ls->GG == TAO_NULL) {
    267:      G->Clone(&(ls->GG));
    268:   }
    269:   GG=ls->GG;

    271:   info = TaoGetVariableBounds(tao, &L, &U);
    272:   work = ls->work;

    274:   const double sigma = ls->sigma;
    275:   const double beta = ls->beta;

    277:   t = *step;
    278:   while (t >= ls->minimumStep) {
    279:     // Calculate iterate
    280:     info = W->Waxpby(1.0, X, t, S); CHKERRQ(info);
    281:     info = W->PointwiseMaximum(W, L); CHKERRQ(info);
    282:     info = W->PointwiseMinimum(W, U); CHKERRQ(info);

    284:     info = work->Waxpby(1.0, X, -1.0, W); CHKERRQ(info);
    285:     info = work->Dot(G, &innerd); CHKERRQ(info);

    287:     if (innerd > 0) {
    288:       // Calculate function at new iterate
    289:       //      info = TaoComputeMeritFunction(tao, W, f); CHKERRQ(info);
    290:       info = TaoComputeMeritFunctionGradient(tao, W, f, GG); CHKERRQ(info);

    292:       // Check descent condition
    293:       if (*f <= ref - sigma*innerd) {
    294:         break;
    295:       }
    296:     }

    298:     t *= beta;
    299:   }

    301:   info = TaoApply_PostProjectedArmijo(tao, ls, *f, t, ref, idx, info2);

    303:   // Update iterate and compute gradient
    304:   *step = t;
    305:   info = G->CopyFrom(GG); CHKERRQ(info);
    306:   info = X->CopyFrom(W); CHKERRQ(info);
    307:   //info = TaoComputeMeritFunctionGradient(tao, X, f, G); CHKERRQ(info);

    309:   // Finish computations
    310:   info = PetscLogInfo((tao,"TaoApply_ProjectedArmijo:step = %10.4f\n",*step)); CHKERRQ(info);
    311:   TaoFunctionReturn(0);
    312: }

    314: /* ---------------------------------------------------------- */
    317: /* @ TaoApply_NDProjectedArmijo - This routine performs a linesearch. It
    318:    backtracks until the (nonmonotone) Projected Armijo conditions are
    319:    satisfied.  This is a modified version for a nondifferentiable function.

    321:    Input Parameters:
    322: +  tao - TAO_SOLVER context
    323: .  X - current iterate (on output X contains new iterate, X + step*S)
    324: .  S - search direction
    325: .  f - merit function evaluated at X
    326: -  step - initial estimate of step length

    328:    Output parameters:
    329: +  f - merit function evaluated at new iterate, X + step*S
    330: .  X - new iterate
    331: -  step - final step length

    333:    Info is set to one of:
    334: .   0 - the line search succeeds; the sufficient decrease
    335:    condition and the directional derivative condition hold

    337:    negative number if an input parameter is invalid
    338: -   -1 -  step < 0

    340:    positive number > 1 if the line search otherwise terminates
    341: +    1 -  Step is at the lower bound, stepmin.
    342: @ */

    344: static int TaoApply_NDProjectedArmijo(TAO_SOLVER tao, TaoVec *X, TaoVec *G,
    345:                                       TaoVec *S, TaoVec *W,
    346:                                       double *f, double *step,
    347:                                       int *info2, void *ctx)
    348: {
    349:   TAO_PROJECTEDARMIJO *ls = (TAO_PROJECTEDARMIJO *)ctx;
    350:   TaoVec *L, *U;
    351:   double ref, t;
    352:   int idx, info;

    354:   TaoFunctionBegin;

    356:   info = TaoApply_PreProjectedArmijo(tao, ls, *f, *step, &ref, &idx, info2);
    357:   if (*info2) {
    358:     TaoFunctionReturn(0);
    359:   }

    361:   info = TaoGetVariableBounds(tao, &L, &U);

    363:   const double sigma = ls->sigma;
    364:   const double beta = ls->beta;

    366:   t = *step;
    367:   while (t >= ls->minimumStep) {
    368:     // Calculate iterate
    369:     info = W->Waxpby(1.0, X, t, S); CHKERRQ(info);
    370:     info = W->PointwiseMaximum(W, L); CHKERRQ(info);
    371:     info = W->PointwiseMinimum(W, U); CHKERRQ(info);

    373:     // Calculate function at new iterate
    374:     //    info = TaoComputeMeritFunction(tao, W, f); CHKERRQ(info);
    375:     info = TaoComputeMeritFunctionGradient(tao, W, f, G); CHKERRQ(info);

    377:     // Check descent condition
    378:     if (*f <= (1 - sigma*t)*ref) {
    379:         break;
    380:     }
    381:
    382:     t *= beta;
    383:   }

    385:   info = TaoApply_PostProjectedArmijo(tao, ls, *f, t, ref, idx, info2);

    387:   // Update iterate and compute gradient
    388:   *step = t;
    389:   info = X->CopyFrom(W); CHKERRQ(info);
    390:   //    info = TaoComputeMeritFunctionGradient(tao, X, f, G); CHKERRQ(info);

    392:   // Finish computations
    393:   info = PetscLogInfo((tao,"TaoApply_NDProjectedArmijo:step = %10.4f\n",*step)); CHKERRQ(info);
    394:   TaoFunctionReturn(0);
    395: }

    397: /* ---------------------------------------------------------- */
    400: /*@
    401:    TaoCreateProjectedArmijoLineSearch - Create a non-monotone projected linesearch

    403:    Input Parameters:
    404: .  tao - TAO_SOLVER context

    407:    Note:
    408:    This algorithm is taken from the following references --

    410:    Armijo, "Minimization of Functions Having Lipschitz Continuous
    411:      First-Partial Derivatives," Pacific Journal of Mathematics, volume 16,
    412:      pages 1-3, 1966.
    413:    Ferris and Lucidi, "Nonmonotone Stabilization Methods for Nonlinear
    414:      Equations," Journal of Optimization Theory and Applications, volume 81,
    415:      pages 53-71, 1994.
    416:    Grippo, Lampariello, and Lucidi, "A Nonmonotone Line Search Technique
    417:      for Newton's Method," SIAM Journal on Numerical Analysis, volume 23,
    418:      pages 707-716, 1986.
    419:    Grippo, Lampariello, and Lucidi, "A Class of Nonmonotone Stabilization
    420:      Methods in Unconstrained Optimization," Numerische Mathematik, volume 59,
    421:      pages 779-805, 1991.

    423:    Note:
    424:    This line seach enforces non-monotone Armijo descent conditions for
    425:    bounds constrained optimization.  This routine is used within the
    426:    following TAO solvers: feasible semismooth with linesearch (tao_ssfls).

    428:    Level: developer

    430: .keywords: TAO_SOLVER, linesearch
    431: @*/
    432: int TaoCreateProjectedArmijoLineSearch(TAO_SOLVER tao)
    433: {
    434:   TAO_PROJECTEDARMIJO *ls;
    435:   int info;

    437:   TaoFunctionBegin;

    439:   info = TaoNew(TAO_PROJECTEDARMIJO,&ls); CHKERRQ(info);
    440:   info = PetscLogObjectMemory(tao,sizeof(TAO_PROJECTEDARMIJO)); CHKERRQ(info);

    442:   ls->GG = TAO_NULL;
    443:   ls->work = TAO_NULL;
    444:   ls->memory = TAO_NULL;
    445:   ls->alpha = 1.0;
    446:   ls->beta = 0.5;
    447:   ls->sigma = 1e-4;
    448:   ls->minimumStep = TAO_EPSILON;
    449:   ls->memorySize = 1;
    450:   ls->referencePolicy = REFERENCE_MAX;
    451:   ls->replacementPolicy = REPLACE_MRU;

    453:   info = TaoSetLineSearch(tao,0,
    454:                           TaoSetOptions_ProjectedArmijo,
    455:                           TaoApply_ProjectedArmijo,
    456:                           TaoView_ProjectedArmijo,
    457:                           TaoDestroy_ProjectedArmijo,
    458:                           (void *) ls);CHKERRQ(info);

    460:   TaoFunctionReturn(0);
    461: }

    463: /* ---------------------------------------------------------- */
    466: /*@
    467:    TaoCreateNDProjectedArmijoLineSearch - Create a non-monotone projected linesearch
    468:      for a nondifferentiable function

    470:    Input Parameters:
    471: .  tao - TAO_SOLVER context

    474:    Note:
    475:    This algorithm is taken from the following references --

    477:    Armijo, "Minimization of Functions Having Lipschitz Continuous
    478:      First-Partial Derivatives," Pacific Journal of Mathematics, volume 16,
    479:      pages 1-3, 1966.
    480:    Ferris and Lucidi, "Nonmonotone Stabilization Methods for Nonlinear
    481:      Equations," Journal of Optimization Theory and Applications, volume 81,
    482:      pages 53-71, 1994.
    483:    Grippo, Lampariello, and Lucidi, "A Nonmonotone Line Search Technique
    484:      for Newton's Method," SIAM Journal on Numerical Analysis, volume 23,
    485:      pages 707-716, 1986.
    486:    Grippo, Lampariello, and Lucidi, "A Class of Nonmonotone Stabilization
    487:      Methods in Unconstrained Optimization," Numerische Mathematik, volume 59,
    488:      pages 779-805, 1991.

    490:    Note:
    491:    This line seach enforces non-monotone Armijo descent conditions for
    492:    bounds constrained optimization.  This routine is used within the
    493:    following TAO solvers: feasible semismooth with linesearch (tao_ssfls).

    495:    Level: developer

    497: .keywords: TAO_SOLVER, linesearch
    498: @*/
    499: int TaoCreateNDProjectedArmijoLineSearch(TAO_SOLVER tao)
    500: {
    501:   TAO_PROJECTEDARMIJO *ls;
    502:   int info;

    504:   TaoFunctionBegin;

    506:   info = TaoNew(TAO_PROJECTEDARMIJO,&ls); CHKERRQ(info);
    507:   info = PetscLogObjectMemory(tao,sizeof(TAO_PROJECTEDARMIJO));CHKERRQ(info);

    509:   ls->work = TAO_NULL;
    510:   ls->memory = TAO_NULL;
    511:   ls->alpha = 1.0;
    512:   ls->beta = 0.5;
    513:   ls->sigma = 1e-4;
    514:   ls->minimumStep = TAO_EPSILON;
    515:   ls->memorySize = 1;
    516:   ls->referencePolicy = REFERENCE_MAX;
    517:   ls->replacementPolicy = REPLACE_MRU;

    519:   info = TaoSetLineSearch(tao,0,
    520:                           TaoSetOptions_ProjectedArmijo,
    521:                           TaoApply_NDProjectedArmijo,
    522:                           TaoView_ProjectedArmijo,
    523:                           TaoDestroy_ProjectedArmijo,
    524:                           (void *) ls);CHKERRQ(info);

    526:   TaoFunctionReturn(0);
    527: }