Warning, /lsopt/lsopt_doc.txt is written in an unsupported language. File is not indexed.
view on githubraw file Latest commit 4cee17c1 on 2002-11-15 04:03:25 UTC
4cee17c1be Patr*0001
0002 Description of large scale optimization package, Version 2.1.0
0003 ##############################################################
0004 Patrick Heimbach, MIT/EAPS, 02-Mar-2000
0005
0006 reference:
0007 #########
0008
0009 J.C. Gilbert & C. Lemarechal
0010 Some numerical experiments with variable-storage quasi-Newton algorithms
0011 Mathematical Programming 45 (1989), pp. 407-435
0012
0013 flow chart
0014 ##########
0015
0016 lsopt_top
0017 |
0018 |---- check arguments
0019 |---- CALL INSTORE
0020 | |
0021 | |---- determine whether OPWARMI available:
0022 | * if no: cold start: create OPWARMI
0023 | * if yes: warm start: read from OPWARMI
0024 | create or open OPWARMD
0025 |
0026 |---- check consistency between OPWARMI and model parameters
0027 |
0028 |---- >>> if COLD start: <<<
0029 | | first simulation with f.g. xx_0; output: first ff_0, gg_0
0030 | | set first preconditioner value xdiff_0 to 1
0031 | | store xx(0), gg(0), xdiff(0) to OPWARMD (first 3 entries)
0032 | |
0033 | >>> else: WARM start: <<<
0034 | read xx(i), gg(i) from OPWARMD (first 2 entries)
0035 | for first warm start after cold start, i=0
0036 |
0037 |
0038 |
0039 |---- /// if ITMAX > 0: perform optimization (increment loop index i)
0040 | (
0041 | )---- save current values of gg(i-1) -> gold(i-1), ff -> fold(i-1)
0042 | (---- CALL LSUPDXX
0043 | ) |
0044 | ( |---- >>> if jmax=0 <<<
0045 | ) | | first optimization after cold start:
0046 | ( | | preconditioner estimated via ff_0 - ff_(first guess)
0047 | ) | | dd(i-1) = -gg(i-1)*preco
0048 | ( | |
0049 | ) | >>> if jmax > 0 <<<
0050 | ( | dd(i-1) = -gg(i-1)
0051 | ) | CALL HESSUPD
0052 | ( | |
0053 | ) | |---- dd(i-1) modified via Hessian approx.
0054 | ( |
0055 | ) |---- >>> if <dd,gg> >= 0 <<<
0056 | ( | ifail = 4
0057 | ) |
0058 | ( |---- compute step size: tact(i-1)
0059 | ) |---- compute update: xdiff(i) = xx(i-1) + tact(i-1)*dd(i-1)
0060 | (
0061 | )---- >>> if ifail = 4 <<<
0062 | ( goto 1000
0063 | )
0064 | (---- CALL OPTLINE / LSLINE
0065 | ) |
0066 | ( |
0067 | ) |
0068 | ( |---- /// loop over simulations
0069 | ) (
0070 | ( )---- CALL SIMUL
0071 | ) ( |
0072 | ( ) |---- input: xdiff(i)
0073 | ) ( |---- output: ff(i), gg(i)
0074 | ( ) |---- >>> if ONLINE <<<
0075 | ) ( runs model and adjoint
0076 | ( ) >>> if OFFLINE <<<
0077 | ) ( reads those values from file
0078 | ( )
0079 | ) (---- 1st Wolfe test:
0080 | ( ) ff(i) <= tact*xpara1*<gg(i-1),dd(i-1)>
0081 | ) (
0082 | ( )---- 2nd Wolfe test:
0083 | ) ( <gg(i),dd(i-1)> >= xpara2*<gg(i-1),dd(i-1)>
0084 | ( )
0085 | ) (---- >>> if 1st and 2nd Wolfe tests ok <<<
0086 | ( ) | 320: update xx: xx(i) = xdiff(i)
0087 | ) ( |
0088 | ( ) >>> else if 1st Wolfe test not ok <<<
0089 | ) ( | 500: INTERpolate new tact:
0090 | ( ) | barr*tact < tact < (1-barr)*tact
0091 | ) ( | CALL CUBIC
0092 | ( ) |
0093 | ) ( >>> else if 2nd Wolfe test not ok <<<
0094 | ( ) 350: EXTRApolate new tact:
0095 | ) ( (1+barmin)*tact < tact < 10*tact
0096 | ( ) CALL CUBIC
0097 | ) (
0098 | ( )---- >>> if new tact > tmax <<<
0099 | ) ( | ifail = 7
0100 | ( ) |
0101 | ) (---- >>> if new tact < tmin OR tact*dd < machine precision <<<
0102 | ( ) | ifail = 8
0103 | ) ( |
0104 | ( )---- >>> else <<<
0105 | ) ( update xdiff for new simulation
0106 | ( )
0107 | ) \\\ if nfunc > 1: use inter-/extrapolated tact and xdiff
0108 | ( for new simulation
0109 | ) N.B.: new xx is thus not based on new gg, but
0110 | ( rather on new step size tact
0111 | )
0112 | (
0113 | )
0114 | (---- store new values xx(i), gg(i) to OPWARMD (first 2 entries)
0115 | )---- >>> if ifail = 7,8,9 <<<
0116 | ( goto 1000
0117 | )
0118 | (---- compute new pointers jmin, jmax to include latest values
0119 | ) gg(i)-gg(i-1), xx(i)-xx(i-1) to Hessian matrix estimate
0120 | (---- store gg(i)-gg(i-1), xx(i)-xx(i-1) to OPWARMD
0121 | ) (entries 2*jmax+2, 2*jmax+3)
0122 | (
0123 | )---- CALL DGSCALE
0124 | ( |
0125 | ) |---- call dostore
0126 | ( | |
0127 | ) | |---- read preconditioner of previous iteration diag(i-1)
0128 | ( | from OPWARMD (3rd entry)
0129 | ) |
0130 | ( |---- compute new preconditioner diag(i), based upon diag(i-1),
0131 | ) | gg(i)-gg(i-1), xx(i)-xx(i-1)
0132 | ( |
0133 | ) |---- call dostore
0134 | ( |
0135 | ) |---- write new preconditioner diag(i) to OPWARMD (3rd entry)
0136 | (
0137 |---- \\\ end of optimization iteration loop
0138 |
0139 |
0140 |
0141 |---- CALL OUTSTORE
0142 | |
0143 | |---- store gnorm0, ff(i), current pointers jmin, jmax, iterabs to OPWARMI
0144 |
0145 |---- >>> if OFFLINE version <<<
0146 | xx(i+1) needs to be computed as input for offline optimization
0147 | |
0148 | |---- CALL LSUPDXX
0149 | | |
0150 | | |---- compute dd(i), tact(i) -> xdiff(i+1) = x(i) + tact(i)*dd(i)
0151 | |
0152 | |---- CALL WRITE_CONTROL
0153 | | |
0154 | | |---- write xdiff(i+1) to special file for offline optim.
0155 |
0156 |---- print final information
0157 |
0158 O
0159
0160
0161
0162 Remarks:
0163 #######
0164
0165 1. Difference between offline/online version
0166 --------------------------------------------
0167
0168 - Offline version: Every call to simul refers to a read procedure which
0169 reads the result of an offline forward and adjoint run
0170 Therefore, only one call to simul is allowed,
0171 itmax = 0, for cold start
0172 itmax = 1, for warm start
0173 Also, at the end, x(i+1) needs to be computed and saved
0174 to be available for the offline model and adjoint run
0175
0176 - Online version: Every call to simul refers to an execution of the forward and adjoint model.
0177 Several iterations of optimization may thus be performed within
0178 a single run of the main program (main_lsopt).
0179 The following cases may occur:
0180 - cold start only (no optimization)
0181 - cold start & one or several iterations of optimization
0182 - warm start from previous cold start with one or several iterations
0183 - warm start from previous warm start with one or several iterations
0184
0185 In order to achieve minimum difference between the online and offline code
0186 xdiff(i+1) is stored to file at the end of an (offline) iteration,
0187 but recomputed identically at the beginning of the next iteration.
0188
0189 2. Number of iterations vs. number of simulations
0190 -------------------------------------------------
0191
0192 - itmax: controls the max. number of iterations
0193 - nfunc: controls the max. number of simulations within one iteration
0194
0195 Summary: From one iteration to the next the descent direction changes.
0196 Within one iteration more than one forward and adjoint run may be performed.
0197 The updated control used as input for these simulations uses the same
0198 descent direction, but different step sizes.
0199
0200 In detail:
0201 From one iteration to the next the descent direction dd changes using
0202 the result for the adjoint vector gg of the previous iteration.
0203 In lsline the updated control xdiff(i,1) = xx(i-1) + tact(i-1,1)*dd(i-1) serves as input for
0204 a forward and adjoint model run yielding a new gg(i,1).
0205 In general, the new solution passes the 1st and 2nd Wolfe tests
0206 so xdiff(i,1) represents the solution sought: xx(i) = xdiff(i,1).
0207 If one of the two tests fails, an inter- or extrapolation is invoked to determine
0208 a new step size tact(i-1,2).
0209 If more than one function call is permitted, the new step size is used together
0210 with the "old" descent direction dd(i-1) (i.e. dd is not updated using the new gg(i)),
0211 to compute a new xdiff(i,2) = xx(i-1) + tact(i-1,2)*dd(i-1) that serves as input
0212 in a new forward and adjoint run, yielding gg(i,2).
0213 If now, both Wolfe tests are successfull, the updated solution is given by
0214 xx(i) = xdiff(i,2) = xx(i-1) + tact(i-1,2)*dd(i-1).
0215
0216 3. Double-usage of fields dd and xdiff
0217 --------------------------------------
0218
0219 In order to save memory both the fields dd and xdiff have a double usage.
0220
0221 - xdiff: in lsopt_top: used as x(i) - x(i-1) for Hessian update
0222 in lsline: intermediate result for control update x = x + tact*dd
0223
0224 - dd : in lsopt_top, lsline: descent vector, dd = -gg & hessupd
0225 in dgscale: intermediate result to compute new preconditioner
0226
0227 4. Notice for user of old code
0228 ------------------------------
0229
0230 Three relevant changes needed to switch to new version:
0231
0232 (i): OPWARMI file: two variables added:
0233 gnorm0 : norm of first (cold start) gradient
0234 iabsiter: total number of iterations with respect to cold start
0235
0236 (ii): routine names that are referenced by main_lsopt.f
0237 lsoptv1 -> lsopt_top
0238 lsline1 -> lsline
0239
0240 (iii): parameter list of lsopt_top
0241 logical loffline included
0242
0243 parameter file lsopt.par
0244 ########################
0245
0246 The optimization is controlled by a set of parameters
0247 provided through the standard input file lsopt.par,
0248 which is generated within the job script.
0249
0250 NUPDATE : max. no. of update pairs (gg(i)-gg(i-1), xx(i)-xx(i-1))
0251 to be stored in OPWARMD to estimate Hessian
0252 [pair of current iter. is stored in (2*jmax+2, 2*jmax+3)
0253 jmax must be > 0 to access these entries]
0254 Presently NUPDATE must be > 0
0255 (i.e. iteration without reference to previous
0256 iterations through OPWARMD has not been tested)
0257 EPSX : relative precision on xx bellow which xx should not be improved
0258 EPSG : relative precision on gg below which optimization is considered successful
0259 IPRINT : controls verbose (>=1) or non-verbose output
0260 NUMITER : max. number of iterations of optimisation
0261 NUMTER = 0: cold start only, no optimization
0262 ITER_NUM : index of new restart file to be created (not necessarily = NUMITER!)
0263 NFUNC : max. no. of simulations per iteration
0264 (must be > 0)
0265 is used if step size tact is inter-/extrapolated;
0266 in this case, if NFUNC > 1, a new simulation is performed with
0267 same gradient but "improved" step size
0268 FMIN : first guess cost function value
0269 (only used as long as first iteration not completed,
0270 i.e. for jmax <= 0)
0271
0272 OPWARMI, OPWARMD files
0273 ######################
0274
0275 Two files retain values of previous iterations which are
0276 used in latest iteration to update Hessian.
0277 OPWARMI: contains index settings and scalar variables
0278 OPWARMD: contains vectors
0279
0280 Structure of OPWARMI file:
0281 -------------------------
0282
0283 n, fc, isize, m, jmin, jmax, gnorm0, iabsiter
0284
0285 n = nn : no. of control variables
0286 fc = ff : cost value of last iteration
0287 isize : no. of bytes per record in OPWARMD
0288 m = nupdate : max. no. of updates for Hessian
0289 jmin, jmax : pointer indices for OPWARMD file (cf. below)
0290 gnorm0 : norm of first (cold start) gradient gg
0291 iabsiter : total number of iterations with respect to cold start
0292
0293 Structure of OPWARMD file:
0294 -------------------------
0295 entry
0296 1 : xx(i) : control vector of latest iteration
0297 2 : gg(i) : gradient of latest iteration
0298 3 : xdiff(i), diag: preconditioning vector; (1,...,1) for cold start
0299 ---
0300 2*jmax+2 : gold = g(i) - g(i-1) for last update (jmax)
0301 2*jmax+3 : xdiff = tact * d = xx(i) - xx(i-1) for last update (jmax)
0302
0303 if jmax = 0: cold start; no Hessian update used to compute dd
0304 if jmax > nupdate, old positions are overwritten, starting
0305 with position pair (4,5)
0306
0307 Example 1: jmin = 1, jmax = 3, mupd = 5
0308
0309 1 2 3 | 4 5 6 7 8 9 empty empty
0310 |___|___|___| | |___|___| |___|___| |___|___| |___|___| |___|___|
0311 0 | 1 2 3
0312
0313 Example 2: jmin = 3, jmax = 7, mupd = 5 ---> jmax = 2
0314
0315 1 2 3 |
0316 |___|___|___| | |___|___| |___|___| |___|___| |___|___| |___|___|
0317 | 6 7 3 4 5
0318
0319
0320
0321 Error handling
0322 ##############
0323
0324 ifail | description
0325 --------+----------------------------------------------------------
0326 < 0 | should not appear (flag indic in simul.F not used)
0327 0 | normal mode during execution
0328 1 | an input argument is wrong
0329 2 | warm start file is corrupted
0330 3 | the initial gradient is too small
0331 4 | the search direction is not a descent one
0332 5 | maximal number of iterations reached
0333 6 | maximal number of simulations reached (handled passively)
0334 7 | the linesearch failed
0335 8 | the function could not be improved
0336 9 | optline parameters wrong
0337 10 | cold start, no optimization done
0338 11 | convergence achieved within precision
0339
0340
