Actual source code: armijo.c

      1: #include "armijo.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_Armijo(TAO_SOLVER,void*);
     11: static int TaoView_Armijo(TAO_SOLVER,void*);
     12: static int TaoApply_Armijo(TAO_SOLVER,TaoVec*,TaoVec*,TaoVec*,TaoVec*,
     13:                            double*,double*,int*,void*);
     14: static int TaoDestroy_Armijo(TAO_SOLVER,void*);

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

     24:   TaoFunctionBegin;

     26:   if (ls->memory != TAO_NULL) {
     27:     info = TaoFree(ls->memory); CHKERRQ(info);
     28:     ls->memory = TAO_NULL;
     29:   }
     30:   info = TaoFree(ls); CHKERRQ(info);
     31:   TaoFunctionReturn(0);
     32: }

     34: /*------------------------------------------------------------*/
     37: static int TaoSetOptions_Armijo(TAO_SOLVER tao, void* ctx)
     38: {
     39:   TAO_ARMIJO *ls = (TAO_ARMIJO *)tao->linectx;
     40:   int info;

     42:   TaoFunctionBegin;
     43:   info = TaoOptionsHead("Armijo linesearch options");CHKERRQ(info);
     44:   info = TaoOptionDouble("-tao_armijo_alpha", "initial reference constant", "", ls->alpha, &ls->alpha, 0); CHKERRQ(info);
     45:   info = TaoOptionDouble("-tao_armijo_beta", "decrease constant", "", ls->beta, &ls->beta, 0); CHKERRQ(info);
     46:   info = TaoOptionDouble("-tao_armijo_sigma", "acceptance constant", "", ls->sigma, &ls->sigma, 0); CHKERRQ(info);
     47:   info = TaoOptionInt("-tao_armijo_memory_size", "number of historical elements", "", ls->memorySize, &ls->memorySize, 0); CHKERRQ(info);
     48:   info = TaoOptionDouble("-tao_armijo_minimum_step", "minimum acceptable step", "", ls->minimumStep, &ls->minimumStep, 0); CHKERRQ(info);
     49:   info = TaoOptionInt("-tao_projected_armijo_reference_policy", "policy for updating reference value", "", ls->referencePolicy, &ls->referencePolicy, 0); CHKERRQ(info);
     50:   info = TaoOptionInt("-tao_projected_armijo_replacement_policy", "policy for updating memory", "", ls->replacementPolicy, &ls->replacementPolicy, 0); CHKERRQ(info);
     51:   info = TaoOptionsTail();CHKERRQ(info);
     52:   TaoFunctionReturn(0);
     53: }
     54: /*------------------------------------------------------------*/

     58: static int TaoView_Armijo(TAO_SOLVER tao, void*ctx)
     59: {
     60:   TAO_ARMIJO *ls = (TAO_ARMIJO *)ctx;
     61:   int info;

     63:   TaoFunctionBegin;
     64:
     65:   info=TaoPrintDouble(tao,"  Projected Armijo linesearch: alpha=%g",ls->alpha);CHKERRQ(info);
     66:   info=TaoPrintDouble(tao," beta=%g ",ls->beta);CHKERRQ(info);
     67:   info=TaoPrintDouble(tao,"sigma=%g ",ls->sigma);CHKERRQ(info);
     68:   info=TaoPrintDouble(tao,"minstep=%g,",ls->minimumStep);CHKERRQ(info);
     69:   info=TaoPrintInt(tao,"memsize=%d\n",ls->memorySize);CHKERRQ(info);
     70:
     71:   TaoFunctionReturn(0);
     72: }

     76: static int TaoApply_PreArmijo(TAO_SOLVER tao, TAO_ARMIJO *ls,
     77:                               double f, double step,
     78:                               double *ref, int *idx, int *info2)
     79: {
     80:   int i,info;

     82:   TaoFunctionBegin;

     84:   *info2 = 0;

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

    124:   // Check to see of the memory has been allocated.  If not, allocate
    125:   // the historical array and populate it with the initial function
    126:   // values.
    127:   if (ls->memory == TAO_NULL) {
    128:     info = TaoMalloc(sizeof(double)*ls->memorySize, &ls->memory ); CHKERRQ(info);
    129:
    130:     info = PetscLogObjectMemory(tao, sizeof(double)*ls->memorySize); CHKERRQ(info);
    131:   }

    133:   if (tao->iter == 0) {
    134:     for (i = 0; i < ls->memorySize; i++) {
    135:       ls->memory[i] = ls->alpha*(f);
    136:     }

    138:     ls->current = 0;
    139:     ls->lastReference = ls->memory[0];
    140:   }

    142:   // Calculate reference value (MAX)
    143:   *ref = ls->memory[0];
    144:   *idx = 0;

    146:   for (i = 1; i < ls->memorySize; i++) {
    147:     if (ls->memory[i] > *ref) {
    148:       *ref = ls->memory[i];
    149:       *idx = i;
    150:     }
    151:   }

    153:   if (ls->referencePolicy == REFERENCE_AVE) {
    154:     *ref = 0;
    155:     for (i = 0; i < ls->memorySize; i++) {
    156:       *ref += ls->memory[i];
    157:     }
    158:     *ref = *ref / ls->memorySize;
    159:     *ref = TaoMax(*ref, ls->memory[ls->current]);
    160:   } else if (ls->referencePolicy == REFERENCE_MEAN) {
    161:     *ref = TaoMin(*ref, 0.5*(ls->lastReference + ls->memory[ls->current]));
    162:   }

    164:   TaoFunctionReturn(0);
    165: }

    169: static int TaoApply_PostArmijo(TAO_SOLVER tao, TAO_ARMIJO *ls,
    170:                                double f, double step,
    171:                                double ref, int idx, int *info2)
    172: {
    173:   int info;
    174:   TaoFunctionBegin;

    176:   *info2 = 0;

    178:   // Check termination
    179:   if (step < ls->minimumStep) {
    180:     info = PetscLogInfo((tao, "TaoApply_Armijo:Step is at lower bound.\n")); CHKERRQ(info);
    181:     *info2 = 1;
    182:     TaoFunctionReturn(0);
    183:   }

    185:   // Successful termination, update memory
    186:   ls->lastReference = ref;
    187:   if (ls->replacementPolicy == REPLACE_FIFO) {
    188:     ls->memory[ls->current++] = f;
    189:     if (ls->current >= ls->memorySize) {
    190:       ls->current = 0;
    191:     }
    192:   } else {
    193:     ls->current = idx;
    194:     ls->memory[idx] = f;
    195:   }
    196:   TaoFunctionReturn(0);
    197: }

    199: /* ---------------------------------------------------------- */
    202: /* @ TaoApply_Armijo - This routine performs a linesearch. It
    203:    backtracks until the (nonmonotone) Armijo conditions are satisfied.

    205:    Input Parameters:
    206: +  tao - TAO_SOLVER context
    207: .  X - current iterate (on output X contains new iterate, X + step*S)
    208: .  S - search direction
    209: .  f - merit function evaluated at X
    210: .  G - gradient of merit function evaluated at X
    211: .  W - work vector
    212: -  step - initial estimate of step length

    214:    Output parameters:
    215: +  f - merit function evaluated at new iterate, X + step*S
    216: .  G - gradient of merit function evaluated at new iterate, X + step*S
    217: .  X - new iterate
    218: -  step - final step length

    220:    Info is set to one of:
    221: .   0 - the line search succeeds; the sufficient decrease
    222:    condition and the directional derivative condition hold

    224:    negative number if an input parameter is invalid
    225: -   -1 -  step < 0

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

    231: static int TaoApply_Armijo(TAO_SOLVER tao, TaoVec *X, TaoVec *G, TaoVec *S,
    232:                            TaoVec *W, double *f, double *step,
    233:                            int *info2, void *ctx)
    234: {
    235:   TAO_ARMIJO *ls = (TAO_ARMIJO *)ctx;
    236:   double ref, t, gdx;
    237:   int idx, info;

    239:   TaoFunctionBegin;
    240:   info = S->Dot(G,&gdx); CHKERRQ(info);
    241:   info = TaoApply_PreArmijo(tao, ls, *f, *step, &ref, &idx, info2);
    242:   if (*info2) {
    243:     TaoFunctionReturn(0);
    244:   }

    246:   const double fact = (gdx)*ls->sigma;
    247:   const double beta = ls->beta;

    249:   t = *step;
    250:   while (t >= ls->minimumStep) {
    251:     // Calculate iterate
    252:     info = W->Waxpby(1.0, X, t, S); CHKERRQ(info);

    254:     // Calculate function at new iterate
    255:     info = TaoComputeMeritFunction(tao, W, f); CHKERRQ(info);
    256:
    257:     // Check descent condition
    258:     if (*f <= ref + t*fact) {
    259:       break;
    260:     }

    262:     t *= beta;
    263:   }

    265:   info = TaoApply_PostArmijo(tao, ls, *f, t, ref, idx, info2);

    267:   // Update iterate and compute gradient
    268:   *step = t;
    269:   info = X->CopyFrom(W); CHKERRQ(info);
    270:   info = TaoComputeMeritFunctionGradient(tao, X, f, G); CHKERRQ(info);

    272:   // Finish computations
    273:   info = PetscLogInfo((tao, "TaoApply_Armijo:step = %10.4f\n",*step)); CHKERRQ(info);
    274:   TaoFunctionReturn(0);
    275: }

    277: /* ---------------------------------------------------------- */
    280: /* @ TaoApply_NDArmijo - This routine performs a linesearch. It
    281:    backtracks until the (nonmonotone) Armijo conditions are satisfied.
    282:    This is modified for a nondifferentiable function.

    284:    Input Parameters:
    285: +  tao - TAO_SOLVER context
    286: .  X - current iterate (on output X contains new iterate, X + step*S)
    287: .  S - search direction
    288: .  f - merit function evaluated at X
    289: -  step - initial estimate of step length

    291:    Output parameters:
    292: +  f - merit function evaluated at new iterate, X + step*S
    293: .  X - new iterate
    294: -  step - final step length

    296:    Info is set to one of:
    297: .   0 - the line search succeeds; the sufficient decrease
    298:    condition and the directional derivative condition hold

    300:    negative number if an input parameter is invalid
    301: -   -1 -  step < 0

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

    307: static int TaoApply_NDArmijo(TAO_SOLVER tao, TaoVec *X, TaoVec *G, TaoVec *S,
    308:                              TaoVec *W, double *f, double *step,
    309:                              int *info2, void *ctx)
    310: {
    311:   TAO_ARMIJO *ls = (TAO_ARMIJO *)ctx;
    312:   double ref, t;
    313:   int idx, info;

    315:   TaoFunctionBegin;

    317:   info = TaoApply_PreArmijo(tao, ls, *f, *step, &ref, &idx, info2);
    318:   if (*info2) {
    319:     TaoFunctionReturn(0);
    320:   }

    322:   const double fact = ls->sigma;
    323:   const double beta = ls->beta;

    325:   t = *step;
    326:   while (t >= ls->minimumStep) {
    327:     // Calculate iterate
    328:     info = W->Waxpby(1.0, X, t, S); CHKERRQ(info);

    330:     // Calculate function at new iterate
    331:     info = TaoComputeMeritFunction(tao, W, f); CHKERRQ(info);
    332:
    333:     // Check descent condition
    334:     if (*f <= (1 - fact*t)*ref) {
    335:       break;
    336:     }

    338:     t *= beta;
    339:   }

    341:   info = TaoApply_PostArmijo(tao, ls, *f, t, ref, idx, info2);

    343:   // Update iterate and compute gradient
    344:   *step = t;
    345:   info = X->CopyFrom(W); CHKERRQ(info);

    347:   // Finish computations
    348:   info = PetscLogInfo((tao, "TaoApply_NDArmijo:step = %10.4f\n",*step)); CHKERRQ(info);
    349:   TaoFunctionReturn(0);
    350: }

    352: /* ---------------------------------------------------------- */
    355: /*@C
    356:    TaoCreateArmijoLineSearch - Create a non-monotone linesearch

    358:    Input Parameters:
    359: .  tao - TAO_SOLVER context

    362:    Note:
    363:    This algorithm is taken from the following references --

    365:    Armijo, "Minimization of Functions Having Lipschitz Continuous
    366:      First-Partial Derivatives," Pacific Journal of Mathematics, volume 16,
    367:      pages 1-3, 1966.
    368:    Ferris and Lucidi, "Nonmonotone Stabilization Methods for Nonlinear
    369:      Equations," Journal of Optimization Theory and Applications, volume 81,
    370:      pages 53-71, 1994.
    371:    Grippo, Lampariello, and Lucidi, "A Nonmonotone Line Search Technique
    372:      for Newton's Method," SIAM Journal on Numerical Analysis, volume 23,
    373:      pages 707-716, 1986.
    374:    Grippo, Lampariello, and Lucidi, "A Class of Nonmonotone Stabilization
    375:      Methods in Unconstrained Optimization," Numerische Mathematik, volume 59,
    376:      pages 779-805, 1991.

    378:    Note:
    379:    This line seach enforces non-monotone Armijo descent conditions for
    380:    unconstrained optimization.  This routine is used within the following
    381:    TAO solvers: infeasible semismooth with linesearch (tao_ssils).

    383:    Level: developer

    385: .keywords: TAO_SOLVER, linesearch
    386: @*/
    387: int TaoCreateArmijoLineSearch(TAO_SOLVER tao)
    388: {
    389:   TAO_ARMIJO *ls;
    390:   int info;

    392:   TaoFunctionBegin;

    394:   info = TaoNew(TAO_ARMIJO, &ls);CHKERRQ(info);
    395:   info = PetscLogObjectMemory(tao,sizeof(TAO_ARMIJO)); CHKERRQ(info);

    397:   ls->memory = TAO_NULL;
    398:   ls->alpha = 1.0;
    399:   ls->beta = 0.5;
    400:   ls->sigma = 1e-4;
    401:   ls->minimumStep = TAO_EPSILON;
    402:   ls->memorySize = 1;
    403:   ls->referencePolicy = REFERENCE_MAX;
    404:   ls->replacementPolicy = REPLACE_MRU;

    406:   info = TaoSetLineSearch(tao,0,
    407:                           TaoSetOptions_Armijo,
    408:                           TaoApply_Armijo,
    409:                           TaoView_Armijo,
    410:                           TaoDestroy_Armijo,
    411:                           (void *) ls);CHKERRQ(info);

    413:   TaoFunctionReturn(0);
    414: }

    416: /* ---------------------------------------------------------- */
    419: /*@C
    420:    TaoCreateNDArmijoLineSearch - Create a non-monotone linesearch for a
    421:      nondifferentiable function

    423:    Input Parameters:
    424: .  tao - TAO_SOLVER context

    427:    Note:
    428:    This algorithm is taken from the following references --

    430:    Armijo, "Minimization of Functions Having Lipschitz Continuous
    431:      First-Partial Derivatives," Pacific Journal of Mathematics, volume 16,
    432:      pages 1-3, 1966.
    433:    Ferris and Lucidi, "Nonmonotone Stabilization Methods for Nonlinear
    434:      Equations," Journal of Optimization Theory and Applications, volume 81,
    435:      pages 53-71, 1994.
    436:    Grippo, Lampariello, and Lucidi, "A Nonmonotone Line Search Technique
    437:      for Newton's Method," SIAM Journal on Numerical Analysis, volume 23,
    438:      pages 707-716, 1986.
    439:    Grippo, Lampariello, and Lucidi, "A Class of Nonmonotone Stabilization
    440:      Methods in Unconstrained Optimization," Numerische Mathematik, volume 59,
    441:      pages 779-805, 1991.

    443:    Note:
    444:    This line seach enforces non-monotone Armijo descent conditions for
    445:    unconstrained optimization.  This routine is used within the following
    446:    TAO solvers: infeasible semismooth with linesearch (tao_ssils).

    448:    Level: developer

    450: .keywords: TAO_SOLVER, linesearch
    451: @*/
    452: int TaoCreateNDArmijoLineSearch(TAO_SOLVER tao)
    453: {
    454:   TAO_ARMIJO *ls;
    455:   int info;

    457:   TaoFunctionBegin;

    459:   info = TaoNew(TAO_ARMIJO, &ls);CHKERRQ(info);
    460:   info = PetscLogObjectMemory(tao,sizeof(TAO_ARMIJO)); CHKERRQ(info);

    462:   ls->memory = TAO_NULL;
    463:   ls->alpha = 1.0;
    464:   ls->beta = 0.5;
    465:   ls->sigma = 1e-4;
    466:   ls->minimumStep = TAO_EPSILON;
    467:   ls->memorySize = 1;
    468:   ls->referencePolicy = REFERENCE_MAX;
    469:   ls->replacementPolicy = REPLACE_MRU;

    471:   info = TaoSetLineSearch(tao,0,
    472:                           TaoSetOptions_Armijo,
    473:                           TaoApply_NDArmijo,
    474:                           TaoView_Armijo,
    475:                           TaoDestroy_Armijo,
    476:                           (void *) ls);CHKERRQ(info);

    478:   TaoFunctionReturn(0);
    479: }