luksan/pnet.txt

   1 ***********************************************************************
   2 *                                                                     *
   3 *         PNET - A LIMITED MEMORY VARIABLE METRIC ALGORITHM FOR       *
   4 *                LARGE-SCALE OPTIMIZATION.                            *
   5 *                                                                     *
   6 ***********************************************************************
   7
   8
   9 1. Introduction:
  10 ----------------
  11
  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
  18
  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,
  24
  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:
  27
  28       PNETU - unconstrained large-scale optimization,
  29       PNETS - large-scale optimization with simple bounds.
  30
  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:
  47
  48       COMMON /STAT/ NRES,NDEC,NIN,NIT,NFV,NFG,NFH
  49
  50 The arguments have the following meaning:
  51
  52  Argument  Type Significance
  53  ----------------------------------------------------------------------
  54   NRES      O   Positive INTEGER variable that indicates the number of
  55                 restarts.
  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
  61                 iterations.
  62   NFV       O   Positive INTEGER variable that indicates the number of
  63                 function evaluations.
  64   NFG       O   Positive INTEGER variable that specifies the number of
  65                 gradient evaluations.
  66   NFH       O   Positive INTEGER variable that specifies the number of
  67                 Hessian evaluations.
  68
  69
  70 2. Subroutines PNETU, PNETS:
  71 ----------------------------
  72
  73 The calling sequences are
  74
  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)
  77
  78 The arguments have the following meaning.
  79
  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
  86                 to the minimum.
  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
  94                              initial estimate).
  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,
 102                   IPAR(7)=MF.
 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
 114                 solution X.
 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
 122                              results,
 123                   IPRNT=-2 - extended print of intermediate and final
 124                              results.
 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.
 138
 139       The subroutines PNETU, PNETS require the user supplied subroutines
 140 OBJ and DOBJ that define the objective function and its gradient and
 141 have the form
 142
 143       SUBROUTINE  OBJ(NF,X,F)
 144       SUBROUTINE DOBJ(NF,X,G)
 145
 146 The arguments of the user supplied subroutines have the following
 147 meaning.
 148
 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
 155                 point X.
 156   G(NF)     O   DOUBLE PRECISION gradient of the objective function
 157                 at the point X.
 158
 159
 160 3. Subroutine PNET:
 161 -------------------
 162
 163       This general subroutine is called from all subroutines described
 164 in Section 2. The calling sequence is
 165
 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,
 168      & IPRNT,ITERM)
 169
 170
 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:
 173
 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
 180                 variables.
 181   GO(NF)    A   DOUBLE PRECISION array which contains increments of
 182                 gradients.
 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
 186                 variables.
 187   GM(NF*MF) A   DOUBLE PRECISION array which contains increments of
 188                 gradients.
 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
 206                 value.
 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
 217                 the line search:
 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
 224                            used.
 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
 232                             system.
 233   MF        I   The number of limited-memory variable metric updates
 234                 in each iteration (they use 2*MF stored vectors).
 235
 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.
 245
 246 4. Verification of the subroutines:
 247 -----------------------------------
 248
 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.
 255
 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
 279 TIME= 0:00:06.95
 280
 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.
 291
 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
 315 TIME= 0:00:08.56
 316
 317
 318 References:
 319 -----------
 320
 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.
 324
 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.