forked from emmt/Algorithms
-
Notifications
You must be signed in to change notification settings - Fork 0
/
lbfgsb.h
386 lines (377 loc) · 16.6 KB
/
lbfgsb.h
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
/*
* lbfgsb.h -
*
* Definitions for C wrapper of L-BFGS-B FORTRAN routines.
*
*-----------------------------------------------------------------------------
*
* This software is licensed under the MIT "Expat" License.
*
* Copyright (C) 2002-2005, 2015: Éric Thiébaut <[email protected]>
*
*-----------------------------------------------------------------------------
*/
#ifndef _LBFGSB_H
#define _LBFGSB_H 1
/* The following macros may be redefined to establish FORTRAN-C data types
equivalences. */
#define lbfgsb_integer_t int /* FORTRAN "INTEGER" type */
#define lbfgsb_logical_t int /* FORTRAN "LOGICAL" type */
#define lbfgsb_strlen_t lbfgsb_integer_t /* length of strings */
/* Length of TASK and CSAVE arrays in LBFGSB. */
#define LBFGSB_TASK_LENGTH 60
/* C++ needs to know that types and declarations are C, not C++. */
#ifdef __cplusplus
# define _LBFGSB_BEGIN_DECLS extern "C" {
# define _LBFGSB_END_DECLS }
#else
# define _LBFGSB_BEGIN_DECLS /* empty */
# define _LBFGSB_END_DECLS /* empty */
#endif
_LBFGSB_BEGIN_DECLS
/* Values returned by lbfgsb. */
#define LBFGSB_START 0
#define LBFGSB_FG 1
#define LBFGSB_NEW_X 2
#define LBFGSB_CONVERGENCE 3
#define LBFGSB_WARNING 4
#define LBFGSB_ERROR 5
extern int lbfgsb(lbfgsb_integer_t n, lbfgsb_integer_t m,
double x[], double* f, double g[],
const double l[], const double u[],
const lbfgsb_integer_t bnd[], double factr, double pgtol,
char task[], char csave[], lbfgsb_integer_t isave[],
double dsave[], lbfgsb_integer_t iprint);
/*
* This subroutine uses the limited memory BFGS method to solve a bound
* constrained optimization problem.
*
* N is the dimension of the problem.
*
* M is the maximum number of variable metric corrections
* used to define the limited memory matrix.
*
* X is a double precision array of dimension N.
* On entry X is an approximation to the solution.
* On exit X is the current approximation.
*
* F is a double precision variable.
* On first entry F is unspecified.
* On final exit F is the value of the function at X.
*
* G is a double precision array of dimension N.
* On first entry G is unspecified.
* On final exit G is the value of the gradient at X.
*
* L is a double precision array of dimension N.
* On entry L is the lower bound on X.
* On exit L is unchanged.
*
* U is a double precision array of dimension N.
* On entry U is the upper bound on X.
* On exit U is unchanged.
*
* BND is an integer array of dimension N.
* On entry BND represents the type of bounds imposed on the
* variables, and must be specified as follows:
* BND(i)=0 if X(i) is unbounded,
* 1 if X(i) has only a lower bound,
* 2 if X(i) has both lower and upper bounds, and
* 3 if X(i) has only an upper bound.
* On exit BND is unchanged.
*
* FACTR is a double precision variable.
* On entry FACTR >= 0 is specified by the user. The iteration
* will stop when
*
* (F^k - F^{k+1})/max{|F^k|,|F^{k+1}|,1} <= FACTR*EPSMCH
*
* where EPSMCH is the machine precision, which is automatically
* generated by the code. Typical values for FACTR: 1.d+12 for
* low accuracy; 1.d+7 for moderate accuracy; 1.d+1 for extremely
* high accuracy.
* On exit FACTR is unchanged.
*
* PGTOL is a double precision variable.
* On entry PGTOL >= 0 is specified by the user. The iteration
* will stop when
*
* max{|PG(i)|; i = 1, ..., n} <= PGTOL
*
* where PG(i) is the i-th component of the projected gradient.
* On exit PGTOL is unchanged.
*
* TASK is a working array of characters of length 61 indicating
* the current job when entering and quitting this subroutine.
* TASK must be initialized to "START" upon first call, then TASK
* must not be modified between calls.
*
* CSAVE is a working array of characters of length 61. CSAVE must not
* be modified between calls.
*
* ISAVE is an integer working array of length 48 + 3*N.
* ISAVE must not be modified between calls. On exit with
* TASK = "NEW_X", the following information is available:
* ISAVE[0] = the total number of intervals explored in the
* search of Cauchy points;
* ISAVE[4] = the total number of skipped BFGS updates before
* the current iteration;
* ISAVE[8] = the number of current iteration;
* ISAVE[9] = the total number of BFGS updates prior the current
* iteration;
* ISAVE[11] = the number of intervals explored in the search of
* Cauchy point in the current iteration;
* ISAVE[12] = the total number of function and gradient
* evaluations;
* ISAVE[14] = the number of function value or gradient
* evaluations in the current iteration;
* if ISAVE[15] = 0, then the subspace argmin is within the box;
* if ISAVE[15] = 1, then the subspace argmin is beyond the box;
* ISAVE[16] = number of free variables in the current iteration;
* ISAVE[17] = number of active constraints in the current iteration;
* N + 1 - ISAVE[18] = number of variables leaving the set of active
* constraints in the current iteration;
* ISAVE[19] = number of variables entering the set of active
* constraints in the current iteration.
* if ISAVE[23] = TRUE, then the initial X has been replaced by
* its projection in the feasible set;
* if ISAVE[24] = TRUE, then the problem is constrained;
* if ISAVE[25] = TRUE, then each variable has upper and lower bounds;
*
* DSAVE is a double precision working array of length
* 29 + 2*M*N + 5*N + 11*M*M + 8*M
* DSAVE must not be modified between calls. On exit with
* TASK = "NEW_X", the following information is available:
* DSAVE[0] = current 'THETA' in the BFGS matrix;
* DSAVE[1] = F(X) in the previous iteration;
* DSAVE[2] = FACTR*EPSMCH;
* DSAVE[3] = 2-norm of the line search direction vector;
* DSAVE[4] = the machine precision epsmch generated by the code;
* DSAVE[6] = the accumulated time spent on searching for Cauchy points;
* DSAVE[7] = the accumulated time spent on subspace minimization;
* DSAVE[8] = the accumulated time spent on line search;
* DSAVE[10] = the slope of the line search function at the current
* point of line search;
* DSAVE[11] = the maximum relative step length imposed in line search;
* DSAVE[12] = the infinity norm of the projected gradient;
* DSAVE[13] = the relative step length in the line search;
* DSAVE[14] = the slope of the line search function at the starting
* point of the line search;
* DSAVE[15] = the square of the 2-norm of the line search direction
* vector.
*
* IPRINT is an integer variable that must be set by the user.
* It controls the frequency and type of output generated:
* IPRINT<0 no output is generated;
* IPRINT=0 print only one line at the last iteration;
* 0<IPRINT<99 print also F and |proj G| every IPRINT iterations;
* IPRINT=99 print details of every iteration except N-vectors;
* IPRINT=100 print also the changes of active set and final X;
* IPRINT>100 print details of every iteration including X and G;
* When IPRINT > 0, the file iterate.dat will be created to
* summarize the iteration.
*
* The returned value can be used as a shortcut to the value of TASK:
* return value = 0 if TASK = "START"
* 1 "FG"
* 2 "NEW_X"
* 3 "CONVERGENCE"
* 4 "WARNING"
* 5 "ERROR"
*
*
* References:
*
* [1] R. H. Byrd, P. Lu, J. Nocedal and C. Zhu, ``A limited
* memory algorithm for bound constrained optimization'',
* SIAM J. Scientific Computing 16 (1995), no. 5, pp. 1190--1208.
*
* [2] C. Zhu, R.H. Byrd, P. Lu, J. Nocedal, ``L-BFGS-B: a
* limited memory FORTRAN code for solving bound constrained
* optimization problems'', Tech. Report, NAM-11, EECS Department,
* Northwestern University, 1994.
*
* (Postscript files of these papers are available via anonymous
* ftp to ece.nwu.edu in the directory pub/lbfgs/lbfgs_bcm.)
*
* * * *
*
* NEOS, November 1994. (Latest revision April 1997.)
* Optimization Technology Center.
* Argonne National Laboratory and Northwestern University.
* Written by
* Ciyou Zhu
* in collaboration with R.H. Byrd, P. Lu-Chen and J. Nocedal.
*
* * * *
*/
/*
* This subroutine uses the limited memory BFGS method to solve a bound
* constrained optimization problem.
*
* N is an integer variable.
* On entry N is the dimension of the problem.
* On exit N is unchanged.
*
* M is an integer variable.
* On entry M is the maximum number of variable metric corrections
* used to define the limited memory matrix.
* On exit M is unchanged.
*
* X is a double precision array of dimension N.
* On entry X is an approximation to the solution.
* On exit X is the current approximation.
*
* F is a double precision variable.
* on first entry F is unspecified.
* On final exit F is the value of the function at X.
*
* G is a double precision array of dimension N.
* On first entry G is unspecified.
* On final exit G is the value of the gradient at X.
*
* L is a double precision array of dimension N.
* On entry L is the lower bound on X.
* On exit L is unchanged.
*
* U is a double precision array of dimension N.
* On entry U is the upper bound on X.
* On exit U is unchanged.
*
* BND is an integer array of dimension N.
* On entry BND represents the type of bounds imposed on the
* variables, and must be specified as follows:
* BND(i)=0 if X(i) is unbounded,
* 1 if X(i) has only a lower bound,
* 2 if X(i) has both lower and upper bounds, and
* 3 if X(i) has only an upper bound.
* On exit BND is unchanged.
*
* FACTR is a double precision variable.
* On entry FACTR >= 0 is specified by the user. The iteration
* will stop when
*
* (F^k - F^{k+1})/max{|F^k|,|F^{k+1}|,1} <= FACTR*EPSMCH
*
* where EPSMCH is the machine precision, which is automatically
* generated by the code. Typical values for FACTR: 1.d+12 for
* low accuracy; 1.d+7 for moderate accuracy; 1.d+1 for extremely
* high accuracy.
* On exit FACTR is unchanged.
*
* PGTOL is a double precision variable.
* On entry PGTOL >= 0 is specified by the user. The iteration
* will stop when
*
* max{|PG(i)|; i = 1, ..., n} <= PGTOL
*
* where PG(i) is the i-th component of the projected gradient.
* On exit PGTOL is unchanged.
*
* TASK is a working array of characters of length 60 indicating
* the current job when entering and quitting this subroutine.
* TASK must be initialized to "START" upon first call, then TASK
* must not be modified between calls.
*
* CSAVE is a working array of characters of length 60. CSAVE must not
* be modified between calls.
*
* ISAVE is an integer working array of length 3*N + 27.
* ISAVE must not be modified between calls. On exit with
* TASK = "NEW_X", the following information is available:
* ISAVE[0] = the total number of intervals explored in the
* search of Cauchy points;
* ISAVE[4] = the total number of skipped BFGS updates before
* the current iteration;
* ISAVE[8] = the number of current iteration;
* ISAVE[9] = the total number of BFGS updates prior the current
* iteration;
* ISAVE[11] = the number of intervals explored in the search of
* Cauchy point in the current iteration;
* ISAVE[12] = the total number of function and gradient
* evaluations;
* ISAVE[14] = the number of function value or gradient
* evaluations in the current iteration;
* if ISAVE[15] = 0, then the subspace argmin is within the box;
* if ISAVE[15] = 1, then the subspace argmin is beyond the box;
* ISAVE[16] = number of free variables in the current iteration;
* ISAVE[17] = number of active constraints in the current iteration;
* N + 1 - ISAVE[18] = number of variables leaving the set of active
* constraints in the current iteration;
* ISAVE[19] = number of variables entering the set of active
* constraints in the current iteration.
* if ISAVE[23] = TRUE, then the initial X has been replaced by
* its projection in the feasible set;
* if ISAVE[24] = TRUE, then the problem is constrained;
* if ISAVE[25] = TRUE, then each variable has upper and lower bounds;
*
* DSAVE is a double precision working array of length
* (2*M + 4)*N + (11*M + 8)*M + 29
* DSAVE must not be modified between calls. On exit with
* TASK = "NEW_X", the following information is available:
* DSAVE[0] = current 'THETA' in the BFGS matrix;
* DSAVE[1] = F(X) in the previous iteration;
* DSAVE[2] = FACTR*EPSMCH;
* DSAVE[3] = 2-norm of the line search direction vector;
* DSAVE[4] = the machine precision epsmch generated by the code;
* DSAVE[6] = the accumulated time spent on searching for Cauchy points;
* DSAVE[7] = the accumulated time spent on subspace minimization;
* DSAVE[8] = the accumulated time spent on line search;
* DSAVE[10] = the slope of the line search function at the current
* point of line search;
* DSAVE[11] = the maximum relative step length imposed in line search;
* DSAVE[12] = the infinity norm of the projected gradient;
* DSAVE[13] = the relative step length in the line search;
* DSAVE[14] = the slope of the line search function at the starting
* point of the line search;
* DSAVE[15] = the square of the 2-norm of the line search direction
* vector.
*
* IPRINT is an integer variable that must be set by the user.
* It controls the frequency and type of output generated:
* IPRINT<0 no output is generated;
* IPRINT=0 print only one line at the last iteration;
* 0<IPRINT<99 print also F and |proj G| every IPRINT iterations;
* IPRINT=99 print details of every iteration except N-vectors;
* IPRINT=100 print also the changes of active set and final X;
* IPRINT>100 print details of every iteration including X and G;
* When IPRINT > 0, the file iterate.dat will be created to
* summarize the iteration.
*
* The returned value can be used as a shortcut to the value of TASK:
* return value = 0 if TASK = "START"
* 1 "FG"
* 2 "NEW_X"
* 3 "CONVERGENCE"
* 4 "WARNING"
* 5 "ERROR"
*
*
* References:
*
* [1] R. H. Byrd, P. Lu, J. Nocedal and C. Zhu, ``A limited
* memory algorithm for bound constrained optimization'',
* SIAM J. Scientific Computing 16 (1995), no. 5, pp. 1190--1208.
*
* [2] C. Zhu, R.H. Byrd, P. Lu, J. Nocedal, ``L-BFGS-B: a
* limited memory FORTRAN code for solving bound constrained
* optimization problems'', Tech. Report, NAM-11, EECS Department,
* Northwestern University, 1994.
*
* (Postscript files of these papers are available via anonymous
* ftp to ece.nwu.edu in the directory pub/lbfgs/lbfgs_bcm.)
*
* * * *
*
* NEOS, November 1994. (Latest revision April 1997.)
* Optimization Technology Center.
* Argonne National Laboratory and Northwestern University.
* Written by
* Ciyou Zhu
* in collaboration with R.H. Byrd, P. Lu-Chen and J. Nocedal.
*
* * * *
*/
_LBFGSB_END_DECLS
#endif /* _LBFGSB_H */
/*---------------------------------------------------------------------------*/