1 ***********************************************************************
3 * PLIS - A LIMITED MEMORY VARIABLE METRIC ALGORITHM FOR *
4 * LARGE-SCALE OPTIMIZATION. *
6 ***********************************************************************
12 The double-precision FORTRAN 77 basic subroutine PLIS is designed
13 to find a close approximation to a local minimum of a nonlinear
14 function F(X) with simple bounds on variables. Here X is a vector of NF
15 variables and F(X) is a smooth function. We suppose that NF is large
16 but the sparsity pattern of the Hessian matrix is not known (or the
17 Hessian matrix is dense). Simple bounds are assumed in the form
19 X(I) unbounded if IX(I) = 0,
20 XL(I) <= X(I) if IX(I) = 1,
21 X(I) <= XU(I) if IX(I) = 2,
22 XL(I) <= X(I) <= XU(I) if IX(I) = 3,
23 XL(I) = X(I) = XU(I) if IX(I) = 5,
25 where 1 <= I <= NF. To simplify user's work, two additional easy to use
26 subroutines are added. They call the basic general subroutine PLIS:
28 PLISU - unconstrained large-scale optimization,
29 PLISS - large-scale optimization with simple bounds.
31 All subroutines contain a description of formal parameters and
32 extensive comments. Furthermore, two test programs TLISU and TLISS are
33 included, which contain several test problems (see e.g. [2]). These
34 test programs serve as examples for using the subroutines, verify their
35 correctness and demonstrate their efficiency.
36 In this short guide, we describe all subroutines which can be
37 called from the user's program. A detailed description of the method is
38 given in [1]. In the description of formal parameters, we introduce a
39 type of the argument that specifies whether the argument must have a
40 value defined on entry to the subroutine (I), whether it is a value
41 which will be returned (O), or both (U), or whether it is an auxiliary
42 value (A). Note that the arguments of the type I can be changed on
43 output under some circumstances, especially if improper input values
44 were given. Besides formal parameters, we can use a COMMON /STAT/ block
45 containing statistical information. This block, used in each subroutine
46 has the following form:
48 COMMON /STAT/ NRES,NDEC,NIN,NIT,NFV,NFG,NFH
50 The arguments have the following meaning:
52 Argument Type Significance
53 ----------------------------------------------------------------------
54 NRES O Positive INTEGER variable that indicates the number of
56 NDEC O Positive INTEGER variable that indicates the number of
57 matrix decompositions.
58 NIN O Positive INTEGER variable that indicates the number of
59 inner iterations (for solving linear systems).
60 NIT O Positive INTEGER variable that indicates the number of
62 NFV O Positive INTEGER variable that indicates the number of
64 NFG O Positive INTEGER variable that specifies the number of
66 NFH O Positive INTEGER variable that specifies the number of
70 2. Subroutines PLISU, PLISS:
71 ----------------------------
73 The calling sequences are
75 CALL PLISU(NF,X,IPAR,RPAR,F,GMAX,IPRNT,ITERM)
76 CALL PLISS(NF,X,IX,XL,XU,IPAR,RPAR,F,GMAX,IPRNT,ITERM)
78 The arguments have the following meaning.
80 Argument Type Significance
81 ----------------------------------------------------------------------
82 NF I Positive INTEGER variable that specifies the number of
83 variables of the objective function.
84 X(NF) U On input, DOUBLE PRECISION vector with the initial
85 estimate to the solution. On output, the approximation
87 IX(NF) I On input (significant only if NB>0) INTEGER vector
88 containing the simple bounds types:
89 IX(I)=0 - the variable X(I) is unbounded,
90 IX(I)=1 - the lower bound X(I) >= XL(I),
91 IX(I)=2 - the upper bound X(I) <= XU(I),
92 IX(I)=3 - the two side bound XL(I) <= X(I) <= XU(I),
93 IX(I)=5 - the variable X(I) is fixed (given by its
95 XL(NF) I DOUBLE PRECISION vector with lower bounds for variables
96 (significant only if NB>0).
97 XU(NF) I DOUBLE PRECISION vector with upper bounds for variables
98 (significant only if NB>0).
99 IPAR(7) I INTEGER parameters:
100 IPAR(1)=MIT, IPAR(2)=MFV, IPAR(3)-NONE,
101 IPAR(4)=IEST, IPAR(5)-NONE, IPAR(6)-NONE,
103 Parameters MIT, MFV, IEST, MF are described in Section 3
104 together with other parameters of the subroutine PLIS.
105 RPAR(9) I DOUBLE PRECISION parameters:
106 RPAR(1)=XMAX, RPAR(2)=TOLX, RPAR(3)=TOLF,
107 RPAR(4)=TOLB, RPAR(5)=TOLG, RPAR(6)=FMIN,
108 RPAR(7)-NONE, RPAR(6)-NONE, RPAR(9)-NONE.
109 Parameters XMAX, TOLX, TOLF, TOLB, TOLG, FMIN are
110 described in Section 3 together with other parameters
111 of the subroutine PLIS.
112 F O DOUBLE PRECISION value of the objective function at the
114 GMAX O DOUBLE PRECISION maximum absolute value of a partial
115 derivative of the Lagrangian function.
116 IPRNT I INTEGER variable that specifies PRINT:
117 IPRNT= 0 - print is suppressed,
118 IPRNT= 1 - basic print of final results,
119 IPRNT=-1 - extended print of final results,
120 IPRNT= 2 - basic print of intermediate and final
122 IPRNT=-2 - extended print of intermediate and final
124 ITERM O INTEGER variable that indicates the cause of termination:
125 ITERM= 1 - if |X - XO| was less than or equal to TOLX
126 in two subsequent iterations,
127 ITERM= 2 - if |F - FO| was less than or equal to TOLF
128 in two subsequent iterations,
129 ITERM= 3 - if F is less than or equal to TOLB,
130 ITERM= 4 - if GMAX is less than or equal to TOLG,
131 ITERM= 6 - if termination criterion was not satisfied,
132 but the solution is probably acceptable,
133 ITERM=11 - if NIT exceeded MIT,
134 ITERM=12 - if NFV exceeded MFV,
135 ITERM< 0 - if the method failed.
137 The subroutines PLISU, PLISS require the user supplied subroutines
138 OBJ and DOBJ that define the objective function and its gradient and
141 SUBROUTINE OBJ(NF,X,F)
142 SUBROUTINE DOBJ(NF,X,G)
144 The arguments of the user supplied subroutines have the following
147 Argument Type Significance
148 ----------------------------------------------------------------------
149 NF I Positive INTEGER variable that specifies the number of
150 variables of the objective function.
151 X(NF) I DOUBLE PRECISION an estimate to the solution.
152 F O DOUBLE PRECISION value of the objective function at the
154 G(NF) O DOUBLE PRECISION gradient of the objective function
161 This general subroutine is called from all subroutines described
162 in Section 2. The calling sequence is
164 CALL PLIS(NF,NB,X,IX,XL,XU,GF,S,XO,GO,UO,VO,XMAX,TOLX,TOLF,TOLB,
165 & TOLG,FMIN,GMAX,F,MIT,MFV,IEST,MF,IPRNT,ITERM)
167 The arguments NF, NB, X, IX, XL, XU, GMAX, F, IPRNT, ITERM, have the
168 same meaning as in Section 2. Other arguments have the following meaning:
170 Argument Type Significance
171 ----------------------------------------------------------------------
172 GF(NF) A DOUBLE PRECISION gradient of the objective function.
173 S(NF) A DOUBLE PRECISION direction vector.
174 XO(NF*MF) A DOUBLE PRECISION array which contains increments of
176 GO(NF*MF) A DOUBLE PRECISION array which contains increments of
178 UO(MF) A DOUBLE PRECISION Auxiliary array.
179 VO(MF) A DOUBLE PRECISION Auxiliary array.
180 XMAX I DOUBLE PRECISION maximum stepsize; the choice XMAX=0
181 causes that the default value 1.0D+16 will be taken.
182 TOLX I DOUBLE PRECISION tolerance for the change of the
183 coordinate vector X; the choice TOLX=0 causes that the
184 default value TOLX=1.0D-16 will be taken.
185 TOLF I DOUBLE PRECISION tolerance for the change of function
186 values; the choice TOLF=0 causes that the default
187 value TOLF=1.0D-14 will be taken.
188 TOLB I DOUBLE PRECISION minimum acceptable function value;
189 the choice TOLB=0 causes that the default value
190 TOLB=FMIN+1.0D-16 will be taken.
191 TOLG I DOUBLE PRECISION tolerance for the Lagrangian function
192 gradient; the choice TOLG=0 causes that the default
193 value TOLG=1.0D-6 will be taken.
194 FMIN I DOUBLE PRECISION lower bound for the minimum function
196 MIT I INTEGER variable that specifies the maximum number of
197 iterations; the choice MIT=0 causes that the default
198 value 9000 will be taken.
199 MFV I INTEGER variable that specifies the maximum number of
200 function evaluations; the choice MFV=0 causes that
201 the default value 9000 will be taken.
202 IEST I INTEGER estimation of the minimum functiom value for
204 IEST=0 - estimation is not used,
205 IEST=1 - lower bound FMIN is used as an estimation
206 for the minimum function value.
207 MF I The number of limited-memory variable metric updates
208 in each iteration (they use 2*MF stored vectors).
210 The choice of parameter XMAX can be sensitive in many cases. First, the
211 objective function can be evaluated only in a relatively small region
212 (if it contains exponentials) so that the maximum stepsize is necessary.
213 Secondly, the problem can be very ill-conditioned far from the solution
214 point so that large steps can be unsuitable. Finally, if the problem has
215 more local solutions, a suitably chosen maximum stepsize can lead to
216 obtaining a better local solution.
217 The subroutine PLIS requires the user supplied subroutines OBJ
218 and DOBJ which are described in Section 2.
220 4. Verification of the subroutines:
221 -----------------------------------
223 Subroutine PLISU can be verified and tested using the program
224 TLISU. This program calls the subroutines TIUD14 (initiation), TFFU14
225 (function evaluation) and TFGU14 (gradient evaluation) containing
226 22 unconstrained test problems with at most 1000 variables [2]. The
227 results obtained by the program TLISU on a PC computer with Microsoft
228 Power Station Fortran compiler have the following form.
230 NIT= 4988 NFV= 5554 NFG= 5554 F= 0.963780013E-14 G= 0.891E-06 ITERM= 4
231 NIT= 425 NFV= 454 NFG= 454 F= 14.9944763 G= 0.773E-05 ITERM= 2
232 NIT= 74 NFV= 78 NFG= 78 F= 0.655101686E-09 G= 0.539E-06 ITERM= 4
233 NIT= 103 NFV= 112 NFG= 112 F= 269.499543 G= 0.899E-06 ITERM= 4
234 NIT= 24 NFV= 26 NFG= 26 F= 0.130639280E-11 G= 0.671E-06 ITERM= 4
235 NIT= 30 NFV= 31 NFG= 31 F= 0.216102227E-10 G= 0.946E-06 ITERM= 4
236 NIT= 38 NFV= 43 NFG= 43 F= 335.137433 G= 0.730E-06 ITERM= 4
237 NIT= 29 NFV= 33 NFG= 33 F= 761774.954 G= 0.432E-03 ITERM= 2
238 NIT= 13 NFV= 16 NFG= 16 F= 316.436141 G= 0.369E-06 ITERM= 4
239 NIT= 1540 NFV= 1582 NFG= 1582 F= -124.630000 G= 0.124E-04 ITERM= 2
240 NIT= 114 NFV= 138 NFG= 138 F= 10.7765879 G= 0.380E-06 ITERM= 4
241 NIT= 248 NFV= 267 NFG= 267 F= 982.273617 G= 0.123E-04 ITERM= 2
242 NIT= 7 NFV= 8 NFG= 8 F= 0.165734137E-12 G= 0.453E-06 ITERM= 4
243 NIT= 10 NFV= 12 NFG= 12 F= 0.128729169E-08 G= 0.916E-06 ITERM= 4
244 NIT= 2830 NFV= 2929 NFG= 2929 F= 1.92401599 G= 0.936E-06 ITERM= 4
245 NIT= 196 NFV= 210 NFG= 210 F= -427.404476 G= 0.991E-05 ITERM= 2
246 NIT= 1007 NFV= 1032 NFG= 1032 F=-0.379921091E-01 G= 0.876E-06 ITERM= 4
247 NIT= 1449 NFV= 1474 NFG= 1474 F=-0.245741193E-01 G= 0.862E-06 ITERM= 4
248 NIT= 1393 NFV= 1431 NFG= 1431 F= 59.5986241 G= 0.259E-05 ITERM= 2
249 NIT= 2129 NFV= 2191 NFG= 2191 F= -1.00013520 G= 0.908E-06 ITERM= 4
250 NIT= 2120 NFV= 2169 NFG= 2169 F= 2.13866377 G= 0.927E-06 ITERM= 4
251 NIT= 1305 NFV= 1346 NFG= 1346 F= 1.00000000 G= 0.982E-06 ITERM= 4
252 NITER =20072 NFVAL =21136 NSUCC = 22
255 The rows corresponding to individual test problems contain the number of
256 iterations NIT, the number of function evaluations NFV, the number of
257 gradient evaluations NFG, the final value of the objective function F,
258 the norm of gradient G and the cause of termination ITERM.
259 Subroutine PLISS can be verified and tested using the program
260 TLISS. This program calls the subroutines TIUD14 (initiation), TFFU14
261 (function evaluation), TFGU14 (gradient evaluation) containing 22 box
262 constrained test problems with at most 1000 variables [2]. The results
263 obtained by the program TLISS on a PC computer with Microsoft Power
264 Station Fortran compiler have the following form.
266 NIT= 5063 NFV= 5738 NFG= 5738 F= 0.00000000 G= 0.000E+00 ITERM= 3
267 NIT= 3167 NFV= 4664 NFG= 4664 F= 3926.45961 G= 0.626E-04 ITERM= 2
268 NIT= 113 NFV= 124 NFG= 124 F= 0.459503394E-12 G= 0.600E-06 ITERM= 4
269 NIT= 59 NFV= 64 NFG= 64 F= 269.522686 G= 0.838E-06 ITERM= 4
270 NIT= 24 NFV= 26 NFG= 26 F= 0.130639280E-11 G= 0.671E-06 ITERM= 4
271 NIT= 30 NFV= 31 NFG= 31 F= 0.216102227E-10 G= 0.946E-06 ITERM= 4
272 NIT= 33 NFV= 40 NFG= 40 F= 337.722479 G= 0.592E-06 ITERM= 4
273 NIT= 50 NFV= 55 NFG= 55 F= 761925.725 G= 0.240E-03 ITERM= 2
274 NIT= 505 NFV= 508 NFG= 508 F= 428.056916 G= 0.334E-07 ITERM= 4
275 NIT= 1167 NFV= 1227 NFG= 1227 F= -81.0913589 G= 0.100E-04 ITERM= 2
276 NIT= 20 NFV= 26 NFG= 26 F= 96517.2947 G= 0.745E-05 ITERM= 2
277 NIT= 91 NFV= 109 NFG= 109 F= 4994.21410 G= 0.104E-04 ITERM= 2
278 NIT= 7 NFV= 8 NFG= 8 F= 0.165734137E-12 G= 0.453E-06 ITERM= 4
279 NIT= 10 NFV= 12 NFG= 12 F= 0.128729169E-08 G= 0.916E-06 ITERM= 4
280 NIT= 2830 NFV= 2929 NFG= 2929 F= 1.92401599 G= 0.936E-06 ITERM= 4
281 NIT= 178 NFV= 184 NFG= 184 F= -427.391653 G= 0.107E-04 ITERM= 2
282 NIT= 1007 NFV= 1032 NFG= 1032 F=-0.379921091E-01 G= 0.876E-06 ITERM= 4
283 NIT= 1449 NFV= 1474 NFG= 1474 F=-0.245741193E-01 G= 0.862E-06 ITERM= 4
284 NIT= 1561 NFV= 1595 NFG= 1595 F= 1654.94525 G= 0.112E-04 ITERM= 2
285 NIT= 2075 NFV= 2121 NFG= 2121 F= -1.00013520 G= 0.916E-06 ITERM= 4
286 NIT= 1361 NFV= 1389 NFG= 1389 F= 2.41354873 G= 0.709E-06 ITERM= 4
287 NIT= 1562 NFV= 1598 NFG= 1598 F= 1.00000000 G= 0.786E-06 ITERM= 4
288 NITER =22362 NFVAL =24954 NSUCC = 22
294 [1] Luksan L., Matonoha C., Vlcek J.: LSA: Algorithms for large-scale
295 unconstrained and box constrained optimization Technical Report V-896.
296 Prague, ICS AS CR, 2004.
298 [2] Luksan L., Vlcek J.: Sparse and partially separable test problems
299 for unconstrained and equality constrained optimization. Research
300 Report V-767, Institute of Computer Science, Academy of Sciences
301 of the Czech Republic, Prague, Czech Republic, 1998.