src/algs/luksan/plis.txt

   1 ***********************************************************************
   2 *                                                                     *
   3 *         PLIS - 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 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
  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 PLIS:
  27
  28       PLISU - unconstrained large-scale optimization,
  29       PLISS - large-scale optimization with simple bounds.
  30
  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:
  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 PLISU, PLISS:
  71 ----------------------------
  72
  73 The calling sequences are
  74
  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)
  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)-NONE, IPAR(6)-NONE,
 102                   IPAR(7)=MF.
 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
 113                 solution X.
 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
 121                              results,
 122                   IPRNT=-2 - extended print of intermediate and final
 123                              results.
 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.
 136
 137       The subroutines PLISU, PLISS require the user supplied subroutines
 138 OBJ and DOBJ that define the objective function and its gradient and
 139 have the form
 140
 141       SUBROUTINE  OBJ(NF,X,F)
 142       SUBROUTINE DOBJ(NF,X,G)
 143
 144 The arguments of the user supplied subroutines have the following
 145 meaning.
 146
 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
 153                 point X.
 154   G(NF)     O   DOUBLE PRECISION gradient of the objective function
 155                 at the point X.
 156
 157
 158 3. Subroutine PLIS:
 159 -------------------
 160
 161       This general subroutine is called from all subroutines described
 162 in Section 2. The calling sequence is
 163
 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)
 166
 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:
 169
 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
 175                 variables.
 176   GO(NF*MF) A   DOUBLE PRECISION array which contains increments of
 177                 gradients.
 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
 195                 value.
 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
 203                 the line search:
 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).
 209
 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.
 219
 220 4. Verification of the subroutines:
 221 -----------------------------------
 222
 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.
 229
 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
 253 TIME= 0:00:10.78
 254
 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.
 265
 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
 289 TIME= 0:00:12.39
 290
 291 References:
 292 -----------
 293
 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.
 297
 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.