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