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: }