Davidon–Fletcher–Powell formula

The Davidon–Fletcher–Powell formula (or DFP; named after <a href="/facts/William_C._Davidon/heAXvQcN">William C. Davidon</a>, <a href="/facts/Roger_Fletcher_(mathematician)/gHFBdewX">Roger Fletcher</a>, and <a href="/facts/Michael_J._D._Powell/rcNKU74P">Michael J. D. Powell</a>) finds the solution to the secant equation that is closest to the current estimate and satisfies the curvature condition. It was the first <a href="/facts/Quasi-Newton_method/1YX1vMRa">quasi-Newton method</a> to generalize the <a href="/facts/Secant_method/tkNV8Rzk">secant method</a> to a multidimensional problem. This update maintains the symmetry and positive definiteness of the <a href="/facts/Hessian_matrix/RguMNr3m">Hessian matrix</a>.
Given a function 
 
 
 
 f
 (
 x
 )
 
 
 {\displaystyle f(x)}
 
, its <a href="/facts/Gradient/TsR7uukj">gradient</a> (
 
 
 
 ∇
 f
 
 
 {\displaystyle \nabla f}
 
), and <a href="/facts/Positive-definite_matrix/Hbr6AuPS">positive-definite</a> <a href="/facts/Hessian_matrix/RguMNr3m">Hessian matrix</a> 
 
 
 
 B
 
 
 {\displaystyle B}
 
, the <a href="/facts/Taylor_series/M0aTuftH">Taylor series</a> is

f
        (
        
          x
          
            k
          
        
        +
        
          s
          
            k
          
        
        )
        =
        f
        (
        
          x
          
            k
          
        
        )
        +
        ∇
        f
        (
        
          x
          
            k
          
        
        
          )
          
            T
          
        
        
          s
          
            k
          
        
        +
        
          
            1
            2
          
        
        
          s
          
            k
          
          
            T
          
        
        
          B
        
        
          s
          
            k
          
        
        +
        …
        ,
      
    
    {\displaystyle f(x_{k}+s_{k})=f(x_{k})+\nabla f(x_{k})^{T}s_{k}+{\frac {1}{2}}s_{k}^{T}{B}s_{k}+\dots ,}

and the <a href="/facts/Taylor_series/M0aTuftH">Taylor series</a> of the gradient itself (secant equation)

∇
        f
        (
        
          x
          
            k
          
        
        +
        
          s
          
            k
          
        
        )
        =
        ∇
        f
        (
        
          x
          
            k
          
        
        )
        +
        B
        
          s
          
            k
          
        
        +
        …
      
    
    {\displaystyle \nabla f(x_{k}+s_{k})=\nabla f(x_{k})+Bs_{k}+\dots }

is used to update 
 
 
 
 B
 
 
 {\displaystyle B}
 
. 
The DFP formula finds a solution that is symmetric, positive-definite and closest to the current approximate value of 
 
 
 
 
 B
 
 k
 
 
 
 
 {\displaystyle B_{k}}
 
:

B
          
            k
            +
            1
          
        
        =
        (
        I
        −
        
          γ
          
            k
          
        
        
          y
          
            k
          
        
        
          s
          
            k
          
          
            T
          
        
        )
        
          B
          
            k
          
        
        (
        I
        −
        
          γ
          
            k
          
        
        
          s
          
            k
          
        
        
          y
          
            k
          
          
            T
          
        
        )
        +
        
          γ
          
            k
          
        
        
          y
          
            k
          
        
        
          y
          
            k
          
          
            T
          
        
        ,
      
    
    {\displaystyle B_{k+1}=(I-\gamma _{k}y_{k}s_{k}^{T})B_{k}(I-\gamma _{k}s_{k}y_{k}^{T})+\gamma _{k}y_{k}y_{k}^{T},}

where

y
          
            k
          
        
        =
        ∇
        f
        (
        
          x
          
            k
          
        
        +
        
          s
          
            k
          
        
        )
        −
        ∇
        f
        (
        
          x
          
            k
          
        
        )
        ,
      
    
    {\displaystyle y_{k}=\nabla f(x_{k}+s_{k})-\nabla f(x_{k}),}

γ
          
            k
          
        
        =
        
          
            1
            
              
                y
                
                  k
                
                
                  T
                
              
              
                s
                
                  k
                
              
            
          
        
        ,
      
    
    {\displaystyle \gamma _{k}={\frac {1}{y_{k}^{T}s_{k}}},}

and 
 
 
 
 
 B
 
 k
 
 
 
 
 {\displaystyle B_{k}}
 
 is a symmetric and <a href="/facts/Positive-definite_matrix/Hbr6AuPS">positive-definite matrix</a>.
The corresponding update to the inverse Hessian approximation 
 
 
 
 
 H
 
 k
 
 
 =
 
 B
 
 k
 
 
 −
 1
 
 
 
 
 {\displaystyle H_{k}=B_{k}^{-1}}
 
 is given by

H
          
            k
            +
            1
          
        
        =
        
          H
          
            k
          
        
        −
        
          
            
              
                H
                
                  k
                
              
              
                y
                
                  k
                
              
              
                y
                
                  k
                
                
                  T
                
              
              
                H
                
                  k
                
              
            
            
              
                y
                
                  k
                
                
                  T
                
              
              
                H
                
                  k
                
              
              
                y
                
                  k
                
              
            
          
        
        +
        
          
            
              
                s
                
                  k
                
              
              
                s
                
                  k
                
                
                  T
                
              
            
            
              
                y
                
                  k
                
                
                  T
                
              
              
                s
                
                  k
                
              
            
          
        
        .
      
    
    {\displaystyle H_{k+1}=H_{k}-{\frac {H_{k}y_{k}y_{k}^{T}H_{k}}{y_{k}^{T}H_{k}y_{k}}}+{\frac {s_{k}s_{k}^{T}}{y_{k}^{T}s_{k}}}.}

B
 
 
 {\displaystyle B}
 
 is assumed to be positive-definite, and the vectors 
 
 
 
 
 s
 
 k
 
 
 T
 
 
 
 
 {\displaystyle s_{k}^{T}}
 
 and 
 
 
 
 y
 
 
 {\displaystyle y}
 
 must satisfy the curvature condition

s
          
            k
          
          
            T
          
        
        
          y
          
            k
          
        
        =
        
          s
          
            k
          
          
            T
          
        
        B
        
          s
          
            k
          
        
        >
        0.
      
    
    {\displaystyle s_{k}^{T}y_{k}=s_{k}^{T}Bs_{k}>0.}

The DFP formula is quite effective, but it was soon superseded by the <a href="/facts/Broyden%25E2%2580%2593Fletcher%25E2%2580%2593Goldfarb%25E2%2580%2593Shanno_algorithm/aA6KXo6h">Broyden–Fletcher–Goldfarb–Shanno formula</a>, which is its <a href="/facts/Duality_(mathematics)/8jGuyQIU">dual</a> (interchanging the roles of y and s).

Davidon–Fletcher–Powell formula open-in-new

Davidon–Fletcher–Powell formula