[bd2278d] | 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 | ! **************************************************************
|
---|
[e40e335] | 11 |
|
---|
| 12 | subroutine minqsn(n,mxn,x,f,g,scal,acur,h,d,w,xa,ga,xb,gb,maxfun,
|
---|
[bd2278d] | 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 | ! .............................................................
|
---|
[e40e335] | 57 |
|
---|
| 58 | implicit real*8 (a-h,o-z)
|
---|
| 59 | implicit integer*4 (i-n)
|
---|
| 60 |
|
---|
| 61 | parameter ( eps1=0.1d0,
|
---|
[bd2278d] | 62 | & eps2=0.7d0,
|
---|
| 63 | & tiny=1.d-32,
|
---|
[e40e335] | 64 |
|
---|
[bd2278d] | 65 | & zero=0.d0,
|
---|
| 66 | & izero=0,
|
---|
| 67 | & ione=1 )
|
---|
[e40e335] | 68 |
|
---|
| 69 | dimension x(mxn),g(mxn),scal(mxn),h(mxn*(mxn+1)/2),d(mxn),w(mxn),
|
---|
[bd2278d] | 70 | & xa(mxn),ga(mxn),xb(mxn),gb(mxn)
|
---|
[e40e335] | 71 |
|
---|
| 72 | nfun=0
|
---|
| 73 | itr=0
|
---|
| 74 | dff=0.
|
---|
[bd2278d] | 75 | ! _______________ hessian to a diagonal matrix depending on scale
|
---|
[e40e335] | 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 |
|
---|
[bd2278d] | 104 | ! ______________ search direction of the iteration
|
---|
[e40e335] | 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 |
|
---|
[bd2278d] | 128 | ! ________________________ initial step of the line search
|
---|
[e40e335] | 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
|
---|
[bd2278d] | 136 | !c write (*,*) ' minfor> exceeded max. number of function calls'
|
---|
[e40e335] | 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
|
---|
[bd2278d] | 161 | ! ______________ store function value if it is smallest so far
|
---|
[e40e335] | 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 |
|
---|
[bd2278d] | 184 | ! _______________________________ next step by extrapolation
|
---|
[e40e335] | 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
|
---|
[bd2278d] | 246 | ! ***********************************************
|
---|
[e40e335] | 247 | subroutine mc11a(a,n,mxn,z,sig,w,ir,mk,eps)
|
---|
[bd2278d] | 248 | !
|
---|
| 249 | ! CALLS: none
|
---|
| 250 | !
|
---|
[e40e335] | 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
|
---|
[bd2278d] | 370 | ! ************************************
|
---|
[e40e335] | 371 | subroutine mc11e(a,n,mxn,z,w,ir)
|
---|
[bd2278d] | 372 | !
|
---|
| 373 | ! CALLS: none
|
---|
| 374 | !
|
---|
[e40e335] | 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 |
|
---|