luksan/plip.txt

   1 ***********************************************************************
   2 *                                                                     *
   3 *         PLIP - 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 PLIP 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 PLIP:
  27
  28       PLIPU - unconstrained large-scale optimization,
  29       PLIPS - large-scale optimization with simple bounds.
  30
  31 All subroutines contain a description of formal parameters and
  32 extensive comments. Furthermore, two test programs TLIPU and TLIPS 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 PLIPU, PLIPS:
  71 ----------------------------
  72
  73 The calling sequences are
  74
  75       CALL PLIPU(NF,X,IPAR,RPAR,F,GMAX,IPRNT,ITERM)
  76       CALL PLIPS(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)-NONE,
 101                   IPAR(4)=IEST, IPAR(5)-MET, IPAR(6)-NONE,
 102                   IPAR(7)=MF.
 103                 Parameters MIT, MFV, IEST, MET, MF are described
 104                 in Section 3 together with other parameters of the
 105                 subroutine PLIP.
 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 PLIP.
 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< 0 - if the method failed.
 137
 138       The subroutines PLIPU, PLIPS require the user supplied subroutines
 139 OBJ and DOBJ that define the objective function and its gradient and
 140 have the form
 141
 142       SUBROUTINE  OBJ(NF,X,F)
 143       SUBROUTINE DOBJ(NF,X,G)
 144
 145 The arguments of the user supplied subroutines have the following
 146 meaning.
 147
 148  Argument  Type Significance
 149  ----------------------------------------------------------------------
 150   NF        I   Positive INTEGER variable that specifies the number of
 151                 variables of the objective function.
 152   X(NF)     I   DOUBLE PRECISION an estimate to the solution.
 153   F         O   DOUBLE PRECISION value of the objective function at the
 154                 point X.
 155   G(NF)     O   DOUBLE PRECISION gradient of the objective function
 156                 at the point X.
 157
 158
 159 3. Subroutine PLIP:
 160 -------------------
 161
 162       This general subroutine is called from all subroutines described
 163 in Section 2. The calling sequence is
 164
 165       CALL PLIP(NF,NB,X,IX,XL,XU,GF,S,XO,GO,SO,XM,XR,GR,XMAX,TOLX,TOLF,
 166      & TOLB,TOLG,FMIN,GMAX,F,MIT,MFV,IEST,MET,MF,IPRNT,ITERM)
 167
 168 The arguments NF, NB, X, IX, XL, XU, GMAX, F, IPRNT, ITERM, have the
 169 same meaning as in Section 2. Other arguments have the following meaning:
 170
 171  Argument  Type Significance
 172  ----------------------------------------------------------------------
 173   GF(NF)    A   DOUBLE PRECISION gradient of the objective function.
 174   S(NF)     A   DOUBLE PRECISION direction vector.
 175   XO(NF)    A   DOUBLE PRECISION array which contains increments of
 176                 variables.
 177   GO(NF)    A   DOUBLE PRECISION array which contains increments of
 178                 gradients.
 179   SO(NF)    A   DOUBLE PRECISION auxiliary array.
 180   XM(NF*MF) A   DOUBLE PRECISION array which contains columns
 181                 of the updated matrix stored in the product form.
 182   XR(MF)    A   DOUBLE PRECISION array which contains reduced
 183                 increments of variables.
 184   GR(MF)    A   DOUBLE PRECISION array which contains reduced
 185                 increments of gradients.
 186   XMAX      I   DOUBLE PRECISION maximum stepsize; the choice XMAX=0
 187                 causes that the default value 1.0D+16 will be taken.
 188   TOLX      I   DOUBLE PRECISION tolerance for the change of the
 189                 coordinate vector X; the choice TOLX=0 causes that the
 190                 default value TOLX=1.0D-16 will be taken.
 191   TOLF      I   DOUBLE PRECISION tolerance for the change of function
 192                 values; the choice TOLF=0 causes that the default
 193                 value TOLF=1.0D-14 will be taken.
 194   TOLB      I   DOUBLE PRECISION minimum acceptable function value;
 195                 the choice TOLB=0 causes that the default value
 196                 TOLB=FMIN+1.0D-16 will be taken.
 197   TOLG      I   DOUBLE PRECISION tolerance for the Lagrangian function
 198                 gradient; the choice TOLG=0 causes that the default
 199                 value TOLG=1.0D-6 will be taken.
 200   FMIN      I   DOUBLE PRECISION lower bound for the minimum function
 201                 value.
 202   MIT       I   INTEGER variable that specifies the maximum number of
 203                 iterations; the choice MIT=0 causes that the default
 204                 value 9000 will be taken.
 205   MFV       I   INTEGER variable that specifies the maximum number of
 206                 function evaluations; the choice MFV=0 causes that
 207                 the default value 9000 will be taken.
 208   IEST      I   INTEGER estimation of the minimum functiom value for
 209                 the line search:
 210                   IEST=0 - estimation is not used,
 211                   IEST=1 - lower bound FMIN is used as an estimation
 212                            for the minimum function value.
 213   MET       I   INTEGER variable that specifies the limited-memory
 214                 method:
 215                   MET=1 - rank-one method,
 216                   MET=2 - rank-two method.
 217                 The choice MET=0 causes that the default value MET=2
 218                 will be taken.
 219   MF        I   The number of limited-memory variable metric updates
 220                 in each iteration (they use MF stored vectors).
 221
 222 The choice of parameter XMAX can be sensitive in many cases. First, the
 223 objective function can be evaluated only in a relatively small region
 224 (if it contains exponentials) so that the maximum stepsize is necessary.
 225 Secondly, the problem can be very ill-conditioned far from the solution
 226 point so that large steps can be unsuitable. Finally, if the problem has
 227 more local solutions, a suitably chosen maximum stepsize can lead to
 228 obtaining a better local solution.
 229       The subroutine PLIP requires the user supplied subroutines OBJ
 230 and DOBJ which are described in Section 2.
 231
 232 4. Verification of the subroutines:
 233 -----------------------------------
 234
 235       Subroutine PLIPU can be verified and tested using the program
 236 TLIPU. This program calls the subroutines TIUD14 (initiation), TFFU14
 237 (function evaluation) and TFGU14 (gradient evaluation) containing
 238 22 unconstrained test problems with at most 1000 variables [2]. The
 239 results obtained by the program TLIPU on a PC computer with Microsoft
 240 Power Station Fortran compiler have the following form.
 241
 242 NIT= 5383  NFV= 5417  NFG= 5417  F= 0.601022658E-13  G= 0.599E-06  ITERM=  4
 243 NIT=  530  NFV=  557  NFG=  557  F=  3.57276719      G= 0.124E-05  ITERM=  2
 244 NIT=  125  NFV=  128  NFG=  128  F= 0.338270284E-12  G= 0.518E-06  ITERM=  4
 245 NIT=  109  NFV=  114  NFG=  114  F=  269.499543      G= 0.669E-06  ITERM=  4
 246 NIT=   26  NFV=   27  NFG=   27  F= 0.710072396E-11  G= 0.951E-06  ITERM=  4
 247 NIT=   35  NFV=   36  NFG=   36  F= 0.142942272E-10  G= 0.737E-06  ITERM=  4
 248 NIT=   36  NFV=   41  NFG=   41  F=  336.937181      G= 0.956E-06  ITERM=  4
 249 NIT=   33  NFV=   36  NFG=   36  F=  761774.954      G= 0.192E-02  ITERM=  2
 250 NIT=   15  NFV=   18  NFG=   18  F=  316.436141      G= 0.264E-06  ITERM=  4
 251 NIT= 2003  NFV= 2030  NFG= 2030  F= -124.950000      G= 0.116E-04  ITERM=  2
 252 NIT=  157  NFV=  175  NFG=  175  F=  10.7765879      G= 0.299E-06  ITERM=  4
 253 NIT=  337  NFV=  350  NFG=  350  F=  982.273617      G= 0.145E-04  ITERM=  2
 254 NIT=    9  NFV=   10  NFG=   10  F= 0.230414406E-14  G= 0.642E-07  ITERM=  4
 255 NIT=    8  NFV=   10  NFG=   10  F= 0.128834241E-08  G= 0.977E-06  ITERM=  4
 256 NIT= 1226  NFV= 1256  NFG= 1256  F=  1.92401599      G= 0.970E-06  ITERM=  4
 257 NIT=  237  NFV=  246  NFG=  246  F= -427.404476      G= 0.501E-04  ITERM=  2
 258 NIT=  598  NFV=  604  NFG=  604  F=-0.379921091E-01  G= 0.908E-06  ITERM=  4
 259 NIT=  989  NFV=  998  NFG=  998  F=-0.245741193E-01  G= 0.975E-06  ITERM=  4
 260 NIT= 1261  NFV= 1272  NFG= 1272  F=  59.5986241      G= 0.410E-05  ITERM=  2
 261 NIT= 2045  NFV= 2058  NFG= 2058  F= -1.00013520      G= 0.911E-06  ITERM=  4
 262 NIT= 2175  NFV= 2196  NFG= 2196  F=  2.13866377      G= 0.996E-06  ITERM=  4
 263 NIT= 1261  NFV= 1292  NFG= 1292  F=  1.00000000      G= 0.927E-06  ITERM=  4
 264 NITER =18598    NFVAL =18871    NSUCC =   22
 265 TIME= 0:00:10.63
 266
 267 The rows corresponding to individual test problems contain the number of
 268 iterations NIT, the number of function evaluations NFV, the number of
 269 gradient evaluations NFG, the final value of the objective function F,
 270 the norm of gradient G and the cause of termination ITERM.
 271       Subroutine PLIPS can be verified and tested using the program
 272 TLIPS. This program calls the subroutines TIUD14 (initiation), TFFU14
 273 (function evaluation), TFGU14 (gradient evaluation) containing 22 box
 274 constrained test problems with at most 1000 variables [2]. The results
 275 obtained by the program TLIPS on a PC computer with Microsoft Power
 276 Station Fortran compiler have the following form.
 277
 278 NIT= 5263  NFV= 5321  NFG= 5321  F= 0.530131995E-13  G= 0.370E-05  ITERM=  2
 279 NIT= 2293  NFV= 2447  NFG= 2447  F=  3930.43962      G= 0.251E-04  ITERM=  2
 280 NIT=  127  NFV=  132  NFG=  132  F= 0.210550150E-12  G= 0.437E-06  ITERM=  4
 281 NIT=   70  NFV=   72  NFG=   72  F=  269.522686      G= 0.794E-06  ITERM=  4
 282 NIT=   26  NFV=   27  NFG=   27  F= 0.710072396E-11  G= 0.951E-06  ITERM=  4
 283 NIT=   35  NFV=   36  NFG=   36  F= 0.142942272E-10  G= 0.737E-06  ITERM=  4
 284 NIT=   37  NFV=   43  NFG=   43  F=  336.937181      G= 0.133E-05  ITERM=  2
 285 NIT=   59  NFV=   65  NFG=   65  F=  761925.725      G= 0.399E-03  ITERM=  2
 286 NIT=  508  NFV=  510  NFG=  510  F=  428.056916      G= 0.776E-06  ITERM=  4
 287 NIT= 1253  NFV= 1277  NFG= 1277  F= -82.5400568      G= 0.120E-04  ITERM=  2
 288 NIT=   13  NFV=   19  NFG=   19  F=  96517.2947      G= 0.150E-04  ITERM=  2
 289 NIT=   95  NFV=  102  NFG=  102  F=  4994.21410      G= 0.790E-04  ITERM=  2
 290 NIT=    9  NFV=   10  NFG=   10  F= 0.230414406E-14  G= 0.642E-07  ITERM=  4
 291 NIT=    8  NFV=   10  NFG=   10  F= 0.128834241E-08  G= 0.977E-06  ITERM=  4
 292 NIT= 1226  NFV= 1256  NFG= 1256  F=  1.92401599      G= 0.970E-06  ITERM=  4
 293 NIT=  227  NFV=  228  NFG=  228  F= -427.391653      G= 0.952E-05  ITERM=  2
 294 NIT=  598  NFV=  604  NFG=  604  F=-0.379921091E-01  G= 0.908E-06  ITERM=  4
 295 NIT=  989  NFV=  998  NFG=  998  F=-0.245741193E-01  G= 0.975E-06  ITERM=  4
 296 NIT= 1367  NFV= 1383  NFG= 1383  F=  1654.94525      G= 0.105E-04  ITERM=  2
 297 NIT= 2274  NFV= 2303  NFG= 2303  F= -1.00013520      G= 0.798E-06  ITERM=  4
 298 NIT= 1196  NFV= 1211  NFG= 1211  F=  2.41354873      G= 0.975E-06  ITERM=  4
 299 NIT= 1361  NFV= 1381  NFG= 1381  F=  1.00000000      G= 0.962E-06  ITERM=  4
 300 NITER =19034    NFVAL =19435    NSUCC =   22
 301 TIME= 0:00:11.09
 302
 303 References:
 304 -----------
 305
 306 [1] Luksan L., Matonoha C., Vlcek J.: LSA: Algorithms for large-scale
 307     unconstrained and box constrained optimization Technical Report V-896.
 308     Prague, ICS AS CR, 2004.
 309
 310 [2] Luksan L., Vlcek J.: Sparse and partially separable test problems
 311     for unconstrained and equality constrained optimization. Research
 312     Report V-767, Institute of Computer Science, Academy of Sciences
 313     of the Czech Republic, Prague, Czech Republic, 1998.