1 ***********************************************************************
3 * PNET - A LIMITED MEMORY VARIABLE METRIC ALGORITHM FOR *
4 * LARGE-SCALE OPTIMIZATION. *
6 ***********************************************************************
12 The double-precision FORTRAN 77 basic subroutine PNET 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 PNET:
28 PNETU - unconstrained large-scale optimization,
29 PNETS - large-scale optimization with simple bounds.
31 All subroutines contain a description of formal parameters and
32 extensive comments. Furthermore, two test programs TNETU and TNETS 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 PNETU, PNETS:
71 ----------------------------
73 The calling sequences are
75 CALL PNETU(NF,X,IPAR,RPAR,F,GMAX,IPRNT,ITERM)
76 CALL PNETS(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)=MFG,
101 IPAR(4)=IEST, IPAR(5)=MOS1, IPAR(6)=MOS2,
103 Parameters MIT, MFV, MFG, IEST, MOS1, MOS2, MF are
104 described in Section 3 together with other parameters
105 of the subroutine PNET.
106 RPAR(9) I DOUBLE PRECISION parameters:
107 RPAR(1)=XMAX, RPAR(2)=TOLX, RPAR(3)=TOLF,
108 RPAR(4)=TOLB, RPAR(5)=TOLG, RPAR(6)=FMIN,
109 RPAR(7)-NONE, RPAR(6)-NONE, RPAR(9)-NONE.
110 Parameters XMAX, TOLX, TOLF, TOLB, TOLG, FMIN are
111 described in Section 3 together with other parameters
112 of the subroutine PNET.
113 F O DOUBLE PRECISION value of the objective function at the
115 GMAX O DOUBLE PRECISION maximum absolute value of a partial
116 derivative of the Lagrangian function.
117 IPRNT I INTEGER variable that specifies PRINT:
118 IPRNT= 0 - print is suppressed,
119 IPRNT= 1 - basic print of final results,
120 IPRNT=-1 - extended print of final results,
121 IPRNT= 2 - basic print of intermediate and final
123 IPRNT=-2 - extended print of intermediate and final
125 ITERM O INTEGER variable that indicates the cause of termination:
126 ITERM= 1 - if |X - XO| was less than or equal to TOLX
127 in two subsequent iterations,
128 ITERM= 2 - if |F - FO| was less than or equal to TOLF
129 in two subsequent iterations,
130 ITERM= 3 - if F is less than or equal to TOLB,
131 ITERM= 4 - if GMAX is less than or equal to TOLG,
132 ITERM= 6 - if termination criterion was not satisfied,
133 but the solution is probably acceptable,
134 ITERM=11 - if NIT exceeded MIT,
135 ITERM=12 - if NFV exceeded MFV,
136 ITERM=13 - if NFG exceeded MFG,
137 ITERM< 0 - if the method failed.
139 The subroutines PNETU, PNETS require the user supplied subroutines
140 OBJ and DOBJ that define the objective function and its gradient and
143 SUBROUTINE OBJ(NF,X,F)
144 SUBROUTINE DOBJ(NF,X,G)
146 The arguments of the user supplied subroutines have the following
149 Argument Type Significance
150 ----------------------------------------------------------------------
151 NF I Positive INTEGER variable that specifies the number of
152 variables of the objective function.
153 X(NF) I DOUBLE PRECISION an estimate to the solution.
154 F O DOUBLE PRECISION value of the objective function at the
156 G(NF) O DOUBLE PRECISION gradient of the objective function
163 This general subroutine is called from all subroutines described
164 in Section 2. The calling sequence is
166 CALL PNET(NF,NB,X,IX,XL,XU,GF,GN,S,XO,GO,XS,GS,XM,GM,U1,U2,XMAX,
167 & TOLX,TOLF,TOLB,TOLG,FMIN,GMAX,F,MIT,MFV,MFG,IEST,MOS1,MOS2,MF,
171 The arguments NF, NB, X, IX, XL, XU, GMAX, F, IPRNT, ITERM, have the
172 same meaning as in Section 2. Other arguments have the following meaning:
174 Argument Type Significance
175 -----------------------------------------------------------------------
176 GF(NF) A DOUBLE PRECISION gradient of the objective function.
177 GN(NF) A DOUBLE PRECISION old gradient of the objective function.
178 S(NF) A DOUBLE PRECISION direction vector.
179 XO(NF) A DOUBLE PRECISION array which contains increments of
181 GO(NF) A DOUBLE PRECISION array which contains increments of
183 XS(NF) A DOUBLE PRECISION auxiliary array.
184 GS(NF) A DOUBLE PRECISION auxiliary array.
185 XM(NF*MF) A DOUBLE PRECISION array which contains increments of
187 GM(NF*MF) A DOUBLE PRECISION array which contains increments of
189 U1(MF) A DOUBLE PRECISION auxiliary array.
190 U2(MF) A DOUBLE PRECISION auxiliary array.
191 XMAX I DOUBLE PRECISION maximum stepsize; the choice XMAX=0
192 causes that the default value 1.0D+16 will be taken.
193 TOLX I DOUBLE PRECISION tolerance for the change of the
194 coordinate vector X; the choice TOLX=0 causes that the
195 default value TOLX=1.0D-16 will be taken.
196 TOLF I DOUBLE PRECISION tolerance for the change of function
197 values; the choice TOLF=0 causes that the default
198 value TOLF=1.0D-14 will be taken.
199 TOLB I DOUBLE PRECISION minimum acceptable function value;
200 the choice TOLB=0 causes that the default value
201 TOLB=FMIN+1.0D-16 will be taken.
202 TOLG I DOUBLE PRECISION tolerance for the Lagrangian function
203 gradient; the choice TOLG=0 causes that the default
204 value TOLG=1.0D-6 will be taken.
205 FMIN I DOUBLE PRECISION lower bound for the minimum function
207 MIT I INTEGER variable that specifies the maximum number of
208 iterations; the choice MIT=0 causes that the default
209 value 5000 will be taken.
210 MFV I INTEGER variable that specifies the maximum number of
211 function evaluations; the choice MFV=0 causes that
212 the default value 5000 will be taken.
213 MFG I INTEGER variable that specifies the maximum number of
214 gradient evaluations; the choice MFG=0 causes that
215 the default value 30000 will be taken.
216 IEST I INTEGER estimation of the minimum functiom value for
218 IEST=0 - estimation is not used,
219 IEST=1 - lower bound FMIN is used as an estimation
220 for the minimum function value.
221 MOS1 I INTEGER choice of restarts after constraint change:
222 MOS1=1 - restarts are suppressed,
223 MOS1=2 - restarts with steepest descent directions are
225 MOS2 I INTEGER choice of preconditioning strategy:
226 MOS2=1 - preconditioning is not used,
227 MOS2=2 - preconditioning by the incomplete
228 Gill-Murray decomposition,
229 MOS2=3 - preconditioning by the incomplete
230 Gill-Murray decomposition combined with
231 preliminary solution of the preconditioned
233 MF I The number of limited-memory variable metric updates
234 in each iteration (they use 2*MF stored vectors).
236 The choice of parameter XMAX can be sensitive in many cases. First, the
237 objective function can be evaluated only in a relatively small region
238 (if it contains exponentials) so that the maximum stepsize is necessary.
239 Secondly, the problem can be very ill-conditioned far from the solution
240 point so that large steps can be unsuitable. Finally, if the problem has
241 more local solutions, a suitably chosen maximum stepsize can lead to
242 obtaining a better local solution.
243 The subroutine PNET requires the user supplied subroutines OBJ
244 and DOBJ which are described in Section 2.
246 4. Verification of the subroutines:
247 -----------------------------------
249 Subroutine PNETU can be verified and tested using the program
250 TNETU. This program calls the subroutines TIUD14 (initiation), TFFU14
251 (function evaluation) and TFGU14 (gradient evaluation) containing
252 22 unconstrained test problems with at most 1000 variables [2]. The
253 results obtained by the program TNETU on a PC computer with Microsoft
254 Power Station Fortran compiler have the following form.
256 NIT= 1481 NFV= 1656 NFG=26037 F= 0.117631766E-15 G= 0.354E-06 ITERM= 4
257 NIT= 132 NFV= 387 NFG= 7945 F= 0.153382199E-15 G= 0.988E-08 ITERM= 4
258 NIT= 19 NFV= 20 NFG= 110 F= 0.421204156E-09 G= 0.353E-06 ITERM= 4
259 NIT= 19 NFV= 20 NFG= 230 F= 269.499543 G= 0.779E-07 ITERM= 4
260 NIT= 12 NFV= 13 NFG= 49 F= 0.465606821E-11 G= 0.364E-06 ITERM= 4
261 NIT= 13 NFV= 14 NFG= 76 F= 0.366783327E-11 G= 0.404E-06 ITERM= 4
262 NIT= 9 NFV= 10 NFG= 37 F= 336.937181 G= 0.248E-06 ITERM= 4
263 NIT= 11 NFV= 12 NFG= 58 F= 761774.954 G= 0.155E-07 ITERM= 4
264 NIT= 7 NFV= 11 NFG= 28 F= 316.436141 G= 0.158E-07 ITERM= 4
265 NIT= 75 NFV= 153 NFG= 3213 F= -133.610000 G= 0.777E-08 ITERM= 4
266 NIT= 33 NFV= 45 NFG= 181 F= 10.7765879 G= 0.414E-07 ITERM= 4
267 NIT= 23 NFV= 30 NFG= 457 F= 982.273617 G= 0.591E-08 ITERM= 4
268 NIT= 7 NFV= 8 NFG= 16 F= 0.533593908E-15 G= 0.327E-07 ITERM= 4
269 NIT= 1 NFV= 2 NFG= 1005 F= 0.120245125E-08 G= 0.879E-07 ITERM= 4
270 NIT= 14 NFV= 15 NFG= 4033 F= 1.92401599 G= 0.468E-07 ITERM= 4
271 NIT= 13 NFV= 17 NFG= 295 F= -427.404476 G= 0.800E-08 ITERM= 4
272 NIT= 4 NFV= 5 NFG= 810 F=-0.379921091E-01 G= 0.537E-06 ITERM= 4
273 NIT= 4 NFV= 5 NFG= 1146 F=-0.245741193E-01 G= 0.425E-06 ITERM= 4
274 NIT= 10 NFV= 11 NFG= 1986 F= 59.5986241 G= 0.423E-06 ITERM= 4
275 NIT= 18 NFV= 39 NFG= 3051 F= -1.00013520 G= 0.712E-07 ITERM= 4
276 NIT= 7 NFV= 8 NFG= 4901 F= 2.13866377 G= 0.120E-08 ITERM= 4
277 NIT= 55 NFV= 145 NFG= 4760 F= 1.00000000 G= 0.206E-08 ITERM= 4
278 NITER = 1967 NFVAL = 2626 NSUCC = 22
281 The rows corresponding to individual test problems contain the number of
282 iterations NIT, the number of function evaluations NFV, the number of
283 gradient evaluations NFG, the final value of the objective function F,
284 the norm of gradient G and the cause of termination ITERM.
285 Subroutine PNETS can be verified and tested using the program
286 TNETS. This program calls the subroutines TIUD14 (initiation), TFFU14
287 (function evaluation), TFGU14 (gradient evaluation) containing 22 box
288 constrained test problems with at most 1000 variables [2]. The results
289 obtained by the program TNETS on a PC computer with Microsoft Power
290 Station Fortran compiler have the following form.
292 NIT= 1611 NFV= 1793 NFG=28524 F= 0.00000000 G= 0.000E+00 ITERM= 3
293 NIT= 259 NFV= 259 NFG= 4418 F= 3930.43956 G= 0.230E-07 ITERM= 4
294 NIT= 17 NFV= 18 NFG= 98 F= 0.158634811E-08 G= 0.954E-06 ITERM= 4
295 NIT= 12 NFV= 13 NFG= 105 F= 269.522686 G= 0.103E-07 ITERM= 4
296 NIT= 12 NFV= 13 NFG= 49 F= 0.465606821E-11 G= 0.364E-06 ITERM= 4
297 NIT= 13 NFV= 14 NFG= 76 F= 0.366783327E-11 G= 0.404E-06 ITERM= 4
298 NIT= 9 NFV= 10 NFG= 37 F= 336.937181 G= 0.248E-06 ITERM= 4
299 NIT= 40 NFV= 41 NFG= 248 F= 761925.725 G= 0.281E-06 ITERM= 4
300 NIT= 553 NFV= 555 NFG= 2056 F= 428.056916 G= 0.850E-07 ITERM= 4
301 NIT= 112 NFV= 137 NFG= 2109 F= -84.1426617 G= 0.732E-06 ITERM= 4
302 NIT= 7 NFV= 8 NFG= 17 F= 96517.2947 G= 0.112E-11 ITERM= 4
303 NIT= 133 NFV= 136 NFG= 2689 F= 4994.21410 G= 0.180E-06 ITERM= 4
304 NIT= 7 NFV= 8 NFG= 16 F= 0.533593908E-15 G= 0.327E-07 ITERM= 4
305 NIT= 1 NFV= 2 NFG= 1005 F= 0.120245125E-08 G= 0.879E-07 ITERM= 4
306 NIT= 14 NFV= 15 NFG= 4033 F= 1.92401599 G= 0.468E-07 ITERM= 4
307 NIT= 12 NFV= 13 NFG= 294 F= -427.391653 G= 0.594E-06 ITERM= 4
308 NIT= 4 NFV= 5 NFG= 810 F=-0.379921091E-01 G= 0.537E-06 ITERM= 4
309 NIT= 4 NFV= 5 NFG= 1146 F=-0.245741193E-01 G= 0.425E-06 ITERM= 4
310 NIT= 8 NFV= 9 NFG= 1902 F= 1654.94525 G= 0.690E-07 ITERM= 4
311 NIT= 16 NFV= 25 NFG= 3254 F= -1.00013520 G= 0.836E-08 ITERM= 4
312 NIT= 4 NFV= 5 NFG= 1211 F= 2.41354873 G= 0.135E-06 ITERM= 4
313 NIT= 52 NFV= 137 NFG= 4843 F= 1.00000000 G= 0.657E-06 ITERM= 4
314 NITER = 2900 NFVAL = 3221 NSUCC = 22
321 [1] Luksan L., Matonoha C., Vlcek J.: LSA: Algorithms for large-scale
322 unconstrained and box constrained optimization Technical Report V-896.
323 Prague, ICS AS CR, 2004.
325 [2] Luksan L., Vlcek J.: Sparse and partially separable test problems
326 for unconstrained and equality constrained optimization. Research
327 Report V-767, Institute of Computer Science, Academy of Sciences
328 of the Czech Republic, Prague, Czech Republic, 1998.