| 1 | ! **************************************************************
|
|---|
| 2 | !
|
|---|
| 3 | ! This file contains the subroutines: minqsn,mc11a,mc11e
|
|---|
| 4 | !
|
|---|
| 5 | ! Copyright 2003-2005 Frank Eisenmenger, U.H.E. Hansmann,
|
|---|
| 6 | ! Shura Hayryan, Chin-Ku
|
|---|
| 7 | ! Copyright 2007 Frank Eisenmenger, U.H.E. Hansmann,
|
|---|
| 8 | ! Jan H. Meinke, Sandipan Mohanty
|
|---|
| 9 | !
|
|---|
| 10 | ! **************************************************************
|
|---|
| 11 |
|
|---|
| 12 | subroutine minqsn(n,mxn,x,f,g,scal,acur,h,d,w,xa,ga,xb,gb,maxfun,
|
|---|
| 13 | & nfun)
|
|---|
| 14 |
|
|---|
| 15 | ! .............................................................
|
|---|
| 16 | ! PURPOSE: Quasi-Newton minimizer
|
|---|
| 17 | !
|
|---|
| 18 | ! Unconstrained local minimization of function FUNC
|
|---|
| 19 | ! vs. N variables by quasi-Newton method using BFGS-
|
|---|
| 20 | ! formula to update hessian matrix; approximate line
|
|---|
| 21 | ! searches performed using cubic extra-/interpolation
|
|---|
| 22 | ! [see Gill P.E., Murray W., Wright M.H., Practical
|
|---|
| 23 | ! Optimization, Ch. 2.2.5.7, 4.3.2.1 ff.,4.4.2.2.,
|
|---|
| 24 | ! 4.5.2.1]
|
|---|
| 25 | !
|
|---|
| 26 | ! INPUT: X,F,G - variables, value of FUNC, gradient at START
|
|---|
| 27 | ! SCAL - factors to reduce(increase) initial step &
|
|---|
| 28 | ! its lower bound for line searches, diagonal
|
|---|
| 29 | ! elements of initial hessian matrix
|
|---|
| 30 | ! MXN - maximal overall number of function calls
|
|---|
| 31 | !
|
|---|
| 32 | ! OUTPUT: X,F,G - variables, value of FUNC, gradient at MINIMUM
|
|---|
| 33 | ! NFUN - overall number of function calls used
|
|---|
| 34 | !
|
|---|
| 35 | ! ARRAYS: H - approximate hessian matrix in symmetric storage
|
|---|
| 36 | ! (dimension N(N+1)/2)
|
|---|
| 37 | ! W,D,XA,XB,GA,GB - dimension N
|
|---|
| 38 | !
|
|---|
| 39 | ! CALLS: MOVE - external to calculate function for current X
|
|---|
| 40 | ! and its gradients
|
|---|
| 41 | ! MC11E- solve system H*D=-G for search direction D, where
|
|---|
| 42 | ! H is given in Cholesky-factorization
|
|---|
| 43 | ! MC11A- update H using BFGS formula, factorizise new H
|
|---|
| 44 | ! according to Cholesky (modified to maintain its
|
|---|
| 45 | ! positive definiteness)
|
|---|
| 46 | !
|
|---|
| 47 | ! PARAMETERS:
|
|---|
| 48 | !
|
|---|
| 49 | ! EPS1 - checks reduction of FUNC during line search
|
|---|
| 50 | ! ( 0.0001 <= EPS1 < 0.5 )
|
|---|
| 51 | ! EPS2 - controls accuracy of line search (reduce to increase
|
|---|
| 52 | ! accuracy; EPS1 < EPS2 <= 0.9 )
|
|---|
| 53 | ! ACUR - fractional precision for determination of variables
|
|---|
| 54 | ! (should not be smaller than sqrt of machine accuracy)
|
|---|
| 55 | ! TINY - prevent division by zero during cubic extrapolation
|
|---|
| 56 | ! .............................................................
|
|---|
| 57 |
|
|---|
| 58 | implicit real*8 (a-h,o-z)
|
|---|
| 59 | implicit integer*4 (i-n)
|
|---|
| 60 |
|
|---|
| 61 | parameter ( eps1=0.1d0,
|
|---|
| 62 | & eps2=0.7d0,
|
|---|
| 63 | & tiny=1.d-32,
|
|---|
| 64 |
|
|---|
| 65 | & zero=0.d0,
|
|---|
| 66 | & izero=0,
|
|---|
| 67 | & ione=1 )
|
|---|
| 68 |
|
|---|
| 69 | dimension x(mxn),g(mxn),scal(mxn),h(mxn*(mxn+1)/2),d(mxn),w(mxn),
|
|---|
| 70 | & xa(mxn),ga(mxn),xb(mxn),gb(mxn)
|
|---|
| 71 |
|
|---|
| 72 | nfun=0
|
|---|
| 73 | itr=0
|
|---|
| 74 | dff=0.
|
|---|
| 75 | ! _______________ hessian to a diagonal matrix depending on scale
|
|---|
| 76 | c=0.
|
|---|
| 77 | do i=1,n
|
|---|
| 78 | c=max(c,abs(g(i)*scal(i)))
|
|---|
| 79 | enddo
|
|---|
| 80 | if (c.le.0.) c=1.
|
|---|
| 81 |
|
|---|
| 82 | n1=n+1
|
|---|
| 83 | i1=(n*n1)/2
|
|---|
| 84 | do i=1,i1
|
|---|
| 85 | h(i)=0.
|
|---|
| 86 | enddo
|
|---|
| 87 |
|
|---|
| 88 | j=1
|
|---|
| 89 | do i=1,n
|
|---|
| 90 | h(j)=.01*c/scal(i)**2
|
|---|
| 91 | j=j+n1-i
|
|---|
| 92 | enddo
|
|---|
| 93 |
|
|---|
| 94 | 1 isfv=1 ! Re-start Search from Best Point so far
|
|---|
| 95 |
|
|---|
| 96 | fa=f
|
|---|
| 97 | do i=1,n
|
|---|
| 98 | xa(i)=x(i)
|
|---|
| 99 | ga(i)=g(i)
|
|---|
| 100 | enddo
|
|---|
| 101 |
|
|---|
| 102 | 2 itr=itr+1 ! Start New Line-search from A
|
|---|
| 103 |
|
|---|
| 104 | ! ______________ search direction of the iteration
|
|---|
| 105 | do i=1,n
|
|---|
| 106 | d(i)=-ga(i)
|
|---|
| 107 | enddo
|
|---|
| 108 | call MC11E (h,n,mxn,d,w,n)
|
|---|
| 109 |
|
|---|
| 110 | c=0.
|
|---|
| 111 | dga=0.
|
|---|
| 112 | do i=1,n
|
|---|
| 113 | di=d(i)
|
|---|
| 114 | c=max(c,abs(di/scal(i)))
|
|---|
| 115 | dga=dga+ga(i)*di ! directional derivative
|
|---|
| 116 | enddo
|
|---|
| 117 | c=1./c
|
|---|
| 118 |
|
|---|
| 119 | if (dga.ge.0.) goto 5 ! search is uphill
|
|---|
| 120 |
|
|---|
| 121 | fmin=fa
|
|---|
| 122 | gmin=dga
|
|---|
| 123 | stmin=0.
|
|---|
| 124 |
|
|---|
| 125 | stepub=0. ! initial upper and
|
|---|
| 126 | steplb=acur*c ! lower bound on step
|
|---|
| 127 |
|
|---|
| 128 | ! ________________________ initial step of the line search
|
|---|
| 129 | if (dff.gt.0.) then
|
|---|
| 130 | step=min(1.d0,(dff+dff)/(-dga))
|
|---|
| 131 | else
|
|---|
| 132 | step=min(1.d0,c)
|
|---|
| 133 | endif
|
|---|
| 134 |
|
|---|
| 135 | 3 if (nfun.ge.maxfun) then
|
|---|
| 136 | !c write (*,*) ' minfor> exceeded max. number of function calls'
|
|---|
| 137 | return
|
|---|
| 138 | endif
|
|---|
| 139 |
|
|---|
| 140 | c=stmin+step ! Step along Search direction A->B
|
|---|
| 141 | do i=1,n
|
|---|
| 142 | xb(i)=xa(i)+c*d(i)
|
|---|
| 143 | enddo
|
|---|
| 144 |
|
|---|
| 145 | nfun=nfun+1
|
|---|
| 146 | call MOVE(nfun,n,fb,xb,gb)
|
|---|
| 147 |
|
|---|
| 148 | isfv=min(2,isfv)
|
|---|
| 149 |
|
|---|
| 150 | if (fb.le.f) then
|
|---|
| 151 | if (fb.eq.f) then
|
|---|
| 152 | gl1=0.
|
|---|
| 153 | gl2=0.
|
|---|
| 154 | do i=1,n
|
|---|
| 155 | si=scal(i)**2
|
|---|
| 156 | gl1=gl1+si*g(i)**2
|
|---|
| 157 | gl2=gl2+si*gb(i)**2
|
|---|
| 158 | enddo
|
|---|
| 159 | if (gl2.ge.gl1) goto 4
|
|---|
| 160 | endif
|
|---|
| 161 | ! ______________ store function value if it is smallest so far
|
|---|
| 162 | f=fb
|
|---|
| 163 | do i=1,n
|
|---|
| 164 | x(i)=xb(i)
|
|---|
| 165 | g(i)=gb(i)
|
|---|
| 166 | enddo
|
|---|
| 167 |
|
|---|
| 168 | isfv=3
|
|---|
| 169 | endif
|
|---|
| 170 |
|
|---|
| 171 | 4 dgb=0.
|
|---|
| 172 | do i=1,n
|
|---|
| 173 | dgb=dgb+gb(i)*d(i) ! directional derivative at B
|
|---|
| 174 | enddo
|
|---|
| 175 |
|
|---|
| 176 | if (fb-fa.le.eps1*c*dga) then ! sufficient reduction of F
|
|---|
| 177 |
|
|---|
| 178 | stmin=c
|
|---|
| 179 | fmin=fb
|
|---|
| 180 | gmin=dgb
|
|---|
| 181 |
|
|---|
| 182 | stepub=stepub-step ! new upper bound on step
|
|---|
| 183 |
|
|---|
| 184 | ! _______________________________ next step by extrapolation
|
|---|
| 185 | if (stepub.gt.0.) then
|
|---|
| 186 | step=.5*stepub
|
|---|
| 187 | else
|
|---|
| 188 | step=9.*stmin
|
|---|
| 189 | endif
|
|---|
| 190 | c=dga+3.*dgb-4.*(fb-fa)/stmin
|
|---|
| 191 | if (c.gt.0.) step=min(step,stmin*max(1.d0,-dgb/c))
|
|---|
| 192 |
|
|---|
| 193 | if (dgb.lt.eps2*dga) goto 3 ! line minimization still not
|
|---|
| 194 | ! accurate enough -> further step
|
|---|
| 195 | isfv=4-isfv
|
|---|
| 196 |
|
|---|
| 197 | if (stmin+step.gt.steplb) then ! line minim. complete ->
|
|---|
| 198 | ! update Hessian
|
|---|
| 199 | do i=1,n
|
|---|
| 200 | xa(i)=xb(i)
|
|---|
| 201 | xb(i)=ga(i)
|
|---|
| 202 | d(i)=gb(i)-ga(i)
|
|---|
| 203 | ga(i)=gb(i)
|
|---|
| 204 | enddo
|
|---|
| 205 |
|
|---|
| 206 | ir=-n
|
|---|
| 207 | sig=1./dga
|
|---|
| 208 | call MC11A (h,n,mxn,xb,sig,w,ir,ione,zero)
|
|---|
| 209 | ir=-ir
|
|---|
| 210 | sig=1./(stmin*(dgb-dga))
|
|---|
| 211 | call MC11A (h,n,mxn,d,sig,d,ir,izero,zero)
|
|---|
| 212 |
|
|---|
| 213 | if (ir.eq.n) then ! Start new line search
|
|---|
| 214 | dff=fa-fb
|
|---|
| 215 | fa=fb
|
|---|
| 216 | goto 2
|
|---|
| 217 | else ! rank of new matrix is deficient
|
|---|
| 218 | write (*,*) ' minfor> rank of hessian < number of variables'
|
|---|
| 219 | return
|
|---|
| 220 | endif
|
|---|
| 221 |
|
|---|
| 222 | endif
|
|---|
| 223 |
|
|---|
| 224 | else if (step.gt.steplb) then ! insufficient reduction of F:
|
|---|
| 225 | ! new step by cubic interpolation
|
|---|
| 226 | stepub=step ! new upper bound
|
|---|
| 227 |
|
|---|
| 228 | c=gmin+dgb-3.*(fb-fmin)/step
|
|---|
| 229 | c=c+gmin-sqrt(c*c-gmin*dgb) !! may be sqrt ( <0 )
|
|---|
| 230 | if (abs(c).lt.tiny) then ! prevent division by zero
|
|---|
| 231 | step=.1*step
|
|---|
| 232 | else
|
|---|
| 233 | step=step*max(.1d0,gmin/c)
|
|---|
| 234 | endif
|
|---|
| 235 | goto 3 ! -> reduced step along search direction
|
|---|
| 236 |
|
|---|
| 237 | endif
|
|---|
| 238 |
|
|---|
| 239 | 5 if (isfv.ge.2) goto 1 ! -> Restart from best point so far
|
|---|
| 240 |
|
|---|
| 241 | nfun=nfun+1
|
|---|
| 242 | call MOVE(nfun,n,f,x,g)
|
|---|
| 243 |
|
|---|
| 244 | return
|
|---|
| 245 | end
|
|---|
| 246 | ! ***********************************************
|
|---|
| 247 | subroutine mc11a(a,n,mxn,z,sig,w,ir,mk,eps)
|
|---|
| 248 | !
|
|---|
| 249 | ! CALLS: none
|
|---|
| 250 | !
|
|---|
| 251 | implicit real*8 (a-h,o-z)
|
|---|
| 252 | implicit integer*4 (i-n)
|
|---|
| 253 |
|
|---|
| 254 | dimension a(mxn*(mxn+1)/2),z(mxn),w(mxn)
|
|---|
| 255 |
|
|---|
| 256 | if (n.gt.1) then
|
|---|
| 257 | if (sig.eq.0..or.ir.eq.0) return
|
|---|
| 258 | np=n+1
|
|---|
| 259 | if (sig.lt.0.) then
|
|---|
| 260 | ti=1./sig
|
|---|
| 261 | ij=1
|
|---|
| 262 | if (mk.eq.0) then
|
|---|
| 263 | do i=1,n
|
|---|
| 264 | w(i)=z(i)
|
|---|
| 265 | enddo
|
|---|
| 266 | do i=1,n
|
|---|
| 267 | if (a(ij).gt.0.) then
|
|---|
| 268 | v=w(i)
|
|---|
| 269 | ti=ti+v**2/a(ij)
|
|---|
| 270 | if (i.lt.n) then
|
|---|
| 271 | do j=i+1,n
|
|---|
| 272 | ij=ij+1
|
|---|
| 273 | w(j)=w(j)-v*a(ij)
|
|---|
| 274 | enddo
|
|---|
| 275 | endif
|
|---|
| 276 | ij=ij+1
|
|---|
| 277 | else
|
|---|
| 278 | w(i)=0.
|
|---|
| 279 | ij=ij+np-i
|
|---|
| 280 | endif
|
|---|
| 281 | enddo
|
|---|
| 282 | else
|
|---|
| 283 | do i=1,n
|
|---|
| 284 | if (a(ij).ne.0.) ti=ti+w(i)**2/a(ij)
|
|---|
| 285 | ij=ij+np-i
|
|---|
| 286 | enddo
|
|---|
| 287 | endif
|
|---|
| 288 | if (ir.le.0) then
|
|---|
| 289 | ti=0.
|
|---|
| 290 | ir=-ir-1
|
|---|
| 291 | else if (ti.gt.0.) then
|
|---|
| 292 | if (eps.ne.0.) then
|
|---|
| 293 | ti=eps/sig
|
|---|
| 294 | else
|
|---|
| 295 | ir=ir-1
|
|---|
| 296 | ti=0.
|
|---|
| 297 | endif
|
|---|
| 298 | else if (mk.le.1) then
|
|---|
| 299 | goto 1
|
|---|
| 300 | endif
|
|---|
| 301 | mm=1
|
|---|
| 302 | tim=ti
|
|---|
| 303 | do i=1,n
|
|---|
| 304 | j=np-i
|
|---|
| 305 | ij=ij-i
|
|---|
| 306 | if (a(ij).ne.0.) tim=ti-w(j)**2/a(ij)
|
|---|
| 307 | w(j)=ti
|
|---|
| 308 | ti=tim
|
|---|
| 309 | enddo
|
|---|
| 310 | goto 2
|
|---|
| 311 | endif
|
|---|
| 312 | 1 mm=0
|
|---|
| 313 | tim=1./sig
|
|---|
| 314 | 2 ij=1
|
|---|
| 315 | do i=1,n
|
|---|
| 316 | v=z(i)
|
|---|
| 317 | if (a(ij).gt.0.) then
|
|---|
| 318 | al=v/a(ij)
|
|---|
| 319 | if (mm.le.0) then
|
|---|
| 320 | ti=tim+v*al
|
|---|
| 321 | else
|
|---|
| 322 | ti=w(i)
|
|---|
| 323 | endif
|
|---|
| 324 | r=ti/tim
|
|---|
| 325 | a(ij)=a(ij)*r
|
|---|
| 326 | if (r.eq.0..or.i.eq.n) goto 3
|
|---|
| 327 | b=al/ti
|
|---|
| 328 | if (r.gt.4.) then
|
|---|
| 329 | gm=tim/ti
|
|---|
| 330 | do j=i+1,n
|
|---|
| 331 | ij=ij+1
|
|---|
| 332 | y=a(ij)
|
|---|
| 333 | a(ij)=b*z(j)+y*gm
|
|---|
| 334 | z(j)=z(j)-v*y
|
|---|
| 335 | enddo
|
|---|
| 336 | else
|
|---|
| 337 | do j=i+1,n
|
|---|
| 338 | ij=ij+1
|
|---|
| 339 | z(j)=z(j)-v*a(ij)
|
|---|
| 340 | a(ij)=a(ij)+b*z(j)
|
|---|
| 341 | enddo
|
|---|
| 342 | endif
|
|---|
| 343 | tim=ti
|
|---|
| 344 | ij=ij+1
|
|---|
| 345 | else if (ir.gt.0.or.sig.lt.0..or.v.eq.0.) then
|
|---|
| 346 | ti=tim
|
|---|
| 347 | ij=ij+np-i
|
|---|
| 348 | else
|
|---|
| 349 | ir=1-ir
|
|---|
| 350 | a(ij)=v**2/tim
|
|---|
| 351 | if (i.eq.n) return
|
|---|
| 352 | do j=i+1,n
|
|---|
| 353 | ij=ij+1
|
|---|
| 354 | a(ij)=z(j)/v
|
|---|
| 355 | enddo
|
|---|
| 356 | return
|
|---|
| 357 | endif
|
|---|
| 358 | enddo
|
|---|
| 359 | 3 if (ir.lt.0) ir=-ir
|
|---|
| 360 | else
|
|---|
| 361 | a(1)=a(1)+sig*z(1)**2
|
|---|
| 362 | ir=1
|
|---|
| 363 | if (a(1).gt.0.) return
|
|---|
| 364 | a(1)=0.
|
|---|
| 365 | ir=0
|
|---|
| 366 | endif
|
|---|
| 367 |
|
|---|
| 368 | return
|
|---|
| 369 | end
|
|---|
| 370 | ! ************************************
|
|---|
| 371 | subroutine mc11e(a,n,mxn,z,w,ir)
|
|---|
| 372 | !
|
|---|
| 373 | ! CALLS: none
|
|---|
| 374 | !
|
|---|
| 375 | implicit real*8 (a-h,o-z)
|
|---|
| 376 | implicit integer*4 (i-n)
|
|---|
| 377 |
|
|---|
| 378 | dimension a(mxn*(mxn+1)/2),z(mxn),w(mxn)
|
|---|
| 379 |
|
|---|
| 380 | if (ir.lt.n) return ! rank of matrix deficient
|
|---|
| 381 |
|
|---|
| 382 | w(1)=z(1)
|
|---|
| 383 | if (n.gt.1) then
|
|---|
| 384 | do i=2,n
|
|---|
| 385 | ij=i
|
|---|
| 386 | i1=i-1
|
|---|
| 387 | v=z(i)
|
|---|
| 388 | do j=1,i1
|
|---|
| 389 | v=v-a(ij)*z(j)
|
|---|
| 390 | ij=ij+n-j
|
|---|
| 391 | enddo
|
|---|
| 392 | z(i)=v
|
|---|
| 393 | w(i)=v
|
|---|
| 394 | enddo
|
|---|
| 395 | z(n)=z(n)/a(ij)
|
|---|
| 396 | np=n+1
|
|---|
| 397 | do nip=2,n
|
|---|
| 398 | i=np-nip
|
|---|
| 399 | ii=ij-nip
|
|---|
| 400 | v=z(i)/a(ii)
|
|---|
| 401 | ip=i+1
|
|---|
| 402 | ij=ii
|
|---|
| 403 | do j=ip,n
|
|---|
| 404 | ii=ii+1
|
|---|
| 405 | v=v-a(ii)*z(j)
|
|---|
| 406 | enddo
|
|---|
| 407 | z(i)=v
|
|---|
| 408 | enddo
|
|---|
| 409 | else
|
|---|
| 410 | z(1)=z(1)/a(1)
|
|---|
| 411 | endif
|
|---|
| 412 |
|
|---|
| 413 | return
|
|---|
| 414 | end
|
|---|
| 415 |
|
|---|
