LBFGS 루틴을 활용한 함수 최소화 (포트란) by 바죠


함수 f({x})를 최소화하는 프로그램. f({x}) 이 최소가 되는 {x}를 찾는것이다. {x}는 다차원의 벡터이다. 목적함수 f({x})의 미분이 정의되어야 한다. graident가 있어야 한다. (-gradient를 계산하면 프로그램이 작동하지 않는다.) 2차미분을 요구하지 않는다. 함수, 함수의 1차미분을 요구한다. 이 때 1차미분은 해석적으로 주어져야한다. 수치적으로 계산한 미분이 아니다. 이 알고리듬보다 빨리 국소 최소화를 마무리하는 알고리듬이 있을까? 새로운 알고리듬이 극복해야할 도전의 대상이다.  특수한 함수 몇 개들에 대해서 이 보다 더 효율적인 알고리듬이 있을 수 있다. 하지만, 매우 많은 다양한 함수들에 대해서도 이 알고리듬 보다 더 좋은 효율성을 얻어 낼 수 있다면 혁신으로 불리울만하다.


global minimization 프로그램이 아니다. local minimization program이다.
http://gams.nist.gov/serve.cgi/Class/G1b1b/
핵심 루틴: LBFGS
http://www.ece.northwestern.edu/%7Enocedal/software.html#lbfgs

L-BFGS
--------------------------------------------------------------------------------
Software for Large-scale Unconstrained Optimization
L-BFGS is a limited-memory quasi-Newton code for unconstrained optimization. The code has been developed at the Optimization Technology Center, a joint venture of Argonne National Laboratory and Northwestern University.

       subroutine lbfgs_mini(object,posi,grad,nn)
! Written by In-Ho Lee, KRISS, March 3 (2003).
       implicit none
       integer nn
       real*8 object,posi(nn),grad(nn)
       integer n_local,m,msave
       real*8, allocatable :: diag(:),w(:)
       real*8 eps,xtol,gtol,t1,t2,stpmin,stpmax
       integer iprint(2),iflag,icall,mp,lp,nwork
       integer jnatom,j
       logical diagco
       real*8, allocatable :: xyz(:,:),fxyz(:,:)
!
!     The driver for LBFGS must always declare LB2 as EXTERNAL
       external lb2
       common /lb3/mp,lp,gtol,stpmin,stpmax
!
      n_local=nn
      m=5 ; msave=7 ; nwork=n_local*(2*msave+1)+2*msave
      allocate(diag(n_local),w(nwork))
      iprint(1)= 1 ; iprint(2)= 0
!
!     We do not wish to provide the diagonal matrices Hk0, and
!     therefore set DIAGCO to FALSE.
      diagco= .false. ; eps= 1.0d-4 ; xtol= 1.0d-16 ; icall=0 ; iflag=0
!
       jnatom=nn/3
       allocate(xyz(jnatom,3),fxyz(jnatom,3))
!
 20   continue
         do j=1,jnatom
         xyz(j,1)=posi(3*(j-1)+1)
         xyz(j,2)=posi(3*(j-1)+2)
         xyz(j,3)=posi(3*(j-1)+3)
         enddo
      call energy_force(xyz,fxyz,object,jnatom)
         do j=1,jnatom
         grad(3*(j-1)+1)=-fxyz(j,1)
         grad(3*(j-1)+2)=-fxyz(j,2)
         grad(3*(j-1)+3)=-fxyz(j,3)
         enddo
!
      call lbfgs(n_local,m,posi,object,grad,diagco,diag,iprint,eps,xtol,w,iflag)
!
      if(iflag <= 0) go to 50
      icall=icall + 1
!     We allow at most 2000 evaluations of Function and Gradient
      if(icall >  2000) go to 50
      go to 20
  50  continue
      deallocate(diag,w)
!
      deallocate(xyz,fxyz)
      return
      end

 


http://www.nrbook.com/a/
Numerical Recipes


cf. Runge-Kutta 방법:
http://incredible.egloos.com/3143433

SUMSL:
http://gams.nist.gov/serve.cgi/Module/CMLIB/SUMSL/2045/


--------------------------------------------------------------------
PS. 20080428
            1    7.000000000000000    
            2    1.151525471551600    
            3   0.9521410579345090    
            4   0.4270514707954163    
            5   0.2135738016136687    
            6   0.1167547769443074    
            6   3.9153102526454164E-031
   0.0000000000000000       -8.3266726846886741E-017   2.8969882048812678E-016
    1.000000000000000         1.000000000000000         1.000000000000000     
    1.000000000000000         1.000000000000000         1.000000000000000    
   0.0000000000000000       -3.3306690738754696E-016   2.6072893843931411E-015
   0.0000000000000000        0.0000000000000000        0.0000000000000000     
   0.0000000000000000        0.0000000000000000        0.0000000000000000
     

아래의 함수에 적용할 경우, (인수들의 배치를 바꾸어서 실행한 경우)
  
    subroutine energy_fff(natomxyz,energy,xxx,fff)
       IMPLICIT NONE
       integer natomxyz
       real*8 energy,xxx(natomxyz,3),fff(natomxyz,3)
       integer i
       integer itest

       itest=3
       itest=1
       itest=2

       if(itest ==1)then
       energy=0.d0
       do i=1,natomxyz
       energy=energy+0.5d0*(xxx(i,1)**2+xxx(i,2)**2+xxx(i,3)**2)
       fff(i,1)=-xxx(i,1)
       fff(i,2)=-xxx(i,2)
       fff(i,3)=-xxx(i,3)
       enddo
                    endif
       if(itest ==2)then
       energy=0.d0
       do i=1,natomxyz
       energy=energy+0.5d0*(xxx(i,1)**2+4.*xxx(i,2)**2+9.*xxx(i,3)**2)
       fff(i,1)=-xxx(i,1)
       fff(i,2)=-xxx(i,2)*4.
       fff(i,3)=-xxx(i,3)*9.
       enddo
                    endif

       return
       end


함수값만으로 최소화 시키는 경우, 즉, 함수 일차 미분이 정의되지 않는 경우에 사용할 수 있는 알고리듬.

Nelder-Mead method: http://incredible.egloos.com/4838059


핑백


최근 포토로그