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 |
|
---|