Hamilton–Jacobi–Bellman equation

<h2 id="optimal-control-problems">Optimal Control Problems</h2>
Consider the following problem in deterministic optimal control over the time period 
 
 
 
 [
 0
 ,
 T
 ]
 
 
 {\displaystyle [0,T]}
 
:

V
        (
        x
        (
        0
        )
        ,
        0
        )
        =
        
          min
          
            u
          
        
        
          {
          
            
              ∫
              
                0
              
              
                T
              
            
            C
            [
            x
            (
            t
            )
            ,
            u
            (
            t
            )
            ]
            
            d
            t
            +
            D
            [
            x
            (
            T
            )
            ]
          
          }
        
      
    
    {\displaystyle V(x(0),0)=\min _{u}\left\{\int _{0}^{T}C[x(t),u(t)]\,dt+D[x(T)]\right\}}

where 
 
 
 
 C
 [
 ⋅
 ]
 
 
 {\displaystyle C[\cdot ]}
 
 is the scalar cost rate function and 
 
 
 
 D
 [
 ⋅
 ]
 
 
 {\displaystyle D[\cdot ]}
 
 is a function that gives the <a href="/facts/Bequest_value/J92mW8gR">bequest value</a> at the final state, 
 
 
 
 x
 (
 t
 )
 
 
 {\displaystyle x(t)}
 
 is the system state vector, 
 
 
 
 x
 (
 0
 )
 
 
 {\displaystyle x(0)}
 
 is assumed given, and 
 
 
 
 u
 (
 t
 )
 
 
 {\displaystyle u(t)}
 
 for 
 
 
 
 0
 ≤
 t
 ≤
 T
 
 
 {\displaystyle 0\leq t\leq T}
 
 is the control vector that we are trying to find. Thus, 
 
 
 
 V
 (
 x
 ,
 t
 )
 
 
 {\displaystyle V(x,t)}
 
 is the <a href="/facts/Value_function/mx1w3z2R">value function</a>.
The system must also be subject to

x
              ˙
            
          
        
        (
        t
        )
        =
        F
        [
        x
        (
        t
        )
        ,
        u
        (
        t
        )
        ]
        
      
    
    {\displaystyle {\dot {x}}(t)=F[x(t),u(t)]\,}

where 
 
 
 
 F
 [
 ⋅
 ]
 
 
 {\displaystyle F[\cdot ]}
 
 gives the vector determining physical evolution of the state vector over time.

<h2 id="the-partial-differential-equation">The Partial Differential Equation</h2>
For this simple system, the Hamilton–Jacobi–Bellman partial differential equation is

∂
              V
              (
              x
              ,
              t
              )
            
            
              ∂
              t
            
          
        
        +
        
          min
          
            u
          
        
        
          {
          
            
              
                
                  ∂
                  V
                  (
                  x
                  ,
                  t
                  )
                
                
                  ∂
                  x
                
              
            
            ⋅
            F
            (
            x
            ,
            u
            )
            +
            C
            (
            x
            ,
            u
            )
          
          }
        
        =
        0
      
    
    {\displaystyle {\frac {\partial V(x,t)}{\partial t}}+\min _{u}\left\{{\frac {\partial V(x,t)}{\partial x}}\cdot F(x,u)+C(x,u)\right\}=0}

subject to the terminal condition

V
        (
        x
        ,
        T
        )
        =
        D
        (
        x
        )
        ,
        
      
    
    {\displaystyle V(x,T)=D(x),\,}

As before, the unknown scalar function 
 
 
 
 V
 (
 x
 ,
 t
 )
 
 
 {\displaystyle V(x,t)}
 
 in the above partial differential equation is the Bellman <a href="/facts/Value_function/mx1w3z2R">value function</a>, which represents the cost incurred from starting in state 
 
 
 
 x
 
 
 {\displaystyle x}
 
 at time 
 
 
 
 t
 
 
 {\displaystyle t}
 
 and controlling the system optimally from then until time 
 
 
 
 T
 
 
 {\displaystyle T}
 
.

<h2 id="deriving-the-equation">Deriving the Equation</h2>
Intuitively, the HJB equation can be derived as follows. If 
 
 
 
 V
 (
 x
 (
 t
 )
 ,
 t
 )
 
 
 {\displaystyle V(x(t),t)}
 
 is the optimal cost-to-go function (also called the 'value function'), then by Richard Bellman's <a href="/facts/Principle_of_optimality/Qh2gKSMH">principle of optimality</a>, going from time t to t + dt, we have

V
        (
        x
        (
        t
        )
        ,
        t
        )
        =
        
          min
          
            u
          
        
        
          {
          
            V
            (
            x
            (
            t
            +
            d
            t
            )
            ,
            t
            +
            d
            t
            )
            +
            
              ∫
              
                t
              
              
                t
                +
                d
                t
              
            
            C
            (
            x
            (
            s
            )
            ,
            u
            (
            s
            )
            )
            
            d
            s
          
          }
        
        .
      
    
    {\displaystyle V(x(t),t)=\min _{u}\left\{V(x(t+dt),t+dt)+\int _{t}^{t+dt}C(x(s),u(s))\,ds\right\}.}

Note that the <a href="/facts/Taylor_expansion/M0aTuftH">Taylor expansion</a> of the first term on the right-hand side is

V
        (
        x
        (
        t
        +
        d
        t
        )
        ,
        t
        +
        d
        t
        )
        =
        V
        (
        x
        (
        t
        )
        ,
        t
        )
        +
        
          
            
              ∂
              V
              (
              x
              ,
              t
              )
            
            
              ∂
              t
            
          
        
        
        d
        t
        +
        
          
            
              ∂
              V
              (
              x
              ,
              t
              )
            
            
              ∂
              x
            
          
        
        ⋅
        
          
            
              x
              ˙
            
          
        
        (
        t
        )
        
        d
        t
        +
        
          
            o
          
        
        (
        d
        t
        )
        ,
      
    
    {\displaystyle V(x(t+dt),t+dt)=V(x(t),t)+{\frac {\partial V(x,t)}{\partial t}}\,dt+{\frac {\partial V(x,t)}{\partial x}}\cdot {\dot {x}}(t)\,dt+{\mathcal {o}}(dt),}

where 
 
 
 
 
 
 o
 
 
 (
 d
 t
 )
 
 
 {\displaystyle {\mathcal {o}}(dt)}
 
 denotes the terms in the Taylor expansion of higher order than one in <a href="/facts/Little-o_notation/weFFjSWg">little-o notation</a>. Then if we subtract 
 
 
 
 V
 (
 x
 (
 t
 )
 ,
 t
 )
 
 
 {\displaystyle V(x(t),t)}
 
 from both sides, divide by dt, and take the limit as dt approaches zero, we obtain the HJB equation defined above.

<h2 id="solving-the-equation">Solving the Equation</h2>
The HJB equation is usually <a href="/facts/Backward_induction/x4DwF49D">solved backwards in time</a>, starting from 
 
 
 
 t
 =
 T
 
 
 {\displaystyle t=T}
 
 and ending at 
 
 
 
 t
 =
 0
 
 
 {\displaystyle t=0}
 
.<a class="footnote-ref" id="fnref:11" href="#fn:11">11</a>
When solved over the whole of state space and 
 
 
 
 V
 (
 x
 )
 
 
 {\displaystyle V(x)}
 
 is continuously differentiable, the HJB equation is a <a href="/facts/Necessary_and_sufficient_condition/G45aDCY9">necessary and sufficient condition</a> for an optimum when the terminal state is unconstrained.<a class="footnote-ref" id="fnref:12" href="#fn:12">12</a> If we can solve for 
 
 
 
 V
 
 
 {\displaystyle V}
 
 then we can find from it a control 
 
 
 
 u
 
 
 {\displaystyle u}
 
 that achieves the minimum cost.
In general case, the HJB equation does not have a classical (smooth) solution. Several notions of generalized solutions have been developed to cover such situations, including <a href="/facts/Viscosity_solution/3S8q3rUo">viscosity solution</a> (<a href="/facts/Pierre-Louis_Lions/Uv4vtB0k">Pierre-Louis Lions</a> and <a href="/facts/Michael_G._Crandall/tHIx3C7h">Michael Crandall</a>),<a class="footnote-ref" id="fnref:13" href="#fn:13">13</a> <a href="/facts/Minimax_solution/VMjmmzGE">minimax solution</a> (Andrei Izmailovich Subbotin [ru]), and others.
Approximate dynamic programming has been introduced by <a href="/facts/Dimitri_Bertsekas/uLJEULS4">D. P. Bertsekas</a> and <a href="/facts/John_Tsitsiklis/TggfM5wA">J. N. Tsitsiklis</a> with the use of <a href="/facts/Artificial_neural_network/6V1jMlkx">artificial neural networks</a> (<a href="/facts/Multilayer_perceptron/jkq4t7Gy">multilayer perceptrons</a>) for approximating the Bellman function in general.<a class="footnote-ref" id="fnref:14" href="#fn:14">14</a> This is an effective mitigation strategy for reducing the impact of dimensionality by replacing the memorization of the complete function mapping for the whole space domain with the memorization of the sole neural network parameters. In particular, for continuous-time systems, an approximate dynamic programming approach that combines both policy iterations with neural networks was introduced.<a class="footnote-ref" id="fnref:15" href="#fn:15">15</a> In discrete-time, an approach to solve the HJB equation combining value iterations and neural networks was introduced.<a class="footnote-ref" id="fnref:16" href="#fn:16">16</a>
Alternatively, it has been shown that <a href="/facts/Sum-of-squares_optimization/wz5NPbeB">sum-of-squares optimization</a> can yield an approximate polynomial solution to the Hamilton–Jacobi–Bellman equation arbitrarily well with respect to the 
 
 
 
 
 L
 
 1
 
 
 
 
 {\displaystyle L^{1}}
 
 norm.<a class="footnote-ref" id="fnref:17" href="#fn:17">17</a>

<h2 id="extension-to-stochastic-problems">Extension to Stochastic Problems</h2>
The idea of solving a control problem by applying Bellman's principle of optimality and then working out backwards in time an optimizing strategy can be generalized to stochastic control problems. Consider similar as above

min
          
            u
          
        
        
          E
        
        
          {
          
            
              ∫
              
                0
              
              
                T
              
            
            C
            (
            t
            ,
            
              X
              
                t
              
            
            ,
            
              u
              
                t
              
            
            )
            
            d
            t
            +
            D
            (
            
              X
              
                T
              
            
            )
          
          }
        
      
    
    {\displaystyle \min _{u}\mathbb {E} \left\{\int _{0}^{T}C(t,X_{t},u_{t})\,dt+D(X_{T})\right\}}

now with 
 
 
 
 (
 
 X
 
 t
 
 
 
 )
 
 t
 ∈
 [
 0
 ,
 T
 ]
 
 
 
 
 
 
 {\displaystyle (X_{t})_{t\in [0,T]}\,\!}
 
 the stochastic process to optimize and 
 
 
 
 (
 
 u
 
 t
 
 
 
 )
 
 t
 ∈
 [
 0
 ,
 T
 ]
 
 
 
 
 
 
 {\displaystyle (u_{t})_{t\in [0,T]}\,\!}
 
 the steering. By first using Bellman and then expanding 
 
 
 
 V
 (
 
 X
 
 t
 
 
 ,
 t
 )
 
 
 {\displaystyle V(X_{t},t)}
 
 with <a href="/facts/It%25C3%25B4_calculus/2uSR02fY">Itô's rule</a>, one finds the stochastic HJB equation

min
          
            u
          
        
        
          {
          
            
              
                A
              
            
            V
            (
            x
            ,
            t
            )
            +
            C
            (
            t
            ,
            x
            ,
            u
            )
          
          }
        
        =
        0
        ,
      
    
    {\displaystyle \min _{u}\left\{{\mathcal {A}}V(x,t)+C(t,x,u)\right\}=0,}

where 
 
 
 
 
 
 A
 
 
 
 
 {\displaystyle {\mathcal {A}}}
 
 represents the <a href="/facts/Infinitesimal_generator_(stochastic_processes)/EUHczpU5">stochastic differentiation operator</a>, and subject to the terminal condition

V
        (
        x
        ,
        T
        )
        =
        D
        (
        x
        )
        
        
        .
      
    
    {\displaystyle V(x,T)=D(x)\,\!.}

Note that the randomness has disappeared. In this case a solution 
 
 
 
 V
 
 
 
 
 {\displaystyle V\,\!}
 
 of the latter does not necessarily solve the primal problem, it is a candidate only and a further verifying argument is required. This technique is widely used in Financial Mathematics to determine optimal investment strategies in the market (see for example <a href="/facts/Merton%2527s_portfolio_problem/WtewGQk1">Merton's portfolio problem</a>).

<h3>Application to LQG-Control</h3>
As an example, we can look at a system with linear stochastic dynamics and quadratic cost. If the system dynamics is given by

d
        
          x
          
            t
          
        
        =
        (
        a
        
          x
          
            t
          
        
        +
        b
        
          u
          
            t
          
        
        )
        d
        t
        +
        σ
        d
        
          w
          
            t
          
        
        ,
      
    
    {\displaystyle dx_{t}=(ax_{t}+bu_{t})dt+\sigma dw_{t},}

and the cost accumulates at rate 
 
 
 
 C
 (
 
 x
 
 t
 
 
 ,
 
 u
 
 t
 
 
 )
 =
 r
 (
 t
 )
 
 u
 
 t
 
 
 2
 
 
 
 /
 
 2
 +
 q
 (
 t
 )
 
 x
 
 t
 
 
 2
 
 
 
 /
 
 2
 
 
 {\displaystyle C(x_{t},u_{t})=r(t)u_{t}^{2}/2+q(t)x_{t}^{2}/2}
 
, the HJB equation is given by

−
        
          
            
              ∂
              V
              (
              x
              ,
              t
              )
            
            
              ∂
              t
            
          
        
        =
        
          
            1
            2
          
        
        q
        (
        t
        )
        
          x
          
            2
          
        
        +
        
          
            
              ∂
              V
              (
              x
              ,
              t
              )
            
            
              ∂
              x
            
          
        
        a
        x
        −
        
          
            
              b
              
                2
              
            
            
              2
              r
              (
              t
              )
            
          
        
        
          
            (
            
              
                
                  ∂
                  V
                  (
                  x
                  ,
                  t
                  )
                
                
                  ∂
                  x
                
              
            
            )
          
          
            2
          
        
        +
        
          
            
              σ
              
                2
              
            
            2
          
        
        
          
            
              
                ∂
                
                  2
                
              
              V
              (
              x
              ,
              t
              )
            
            
              ∂
              
                x
                
                  2
                
              
            
          
        
        .
      
    
    {\displaystyle -{\frac {\partial V(x,t)}{\partial t}}={\frac {1}{2}}q(t)x^{2}+{\frac {\partial V(x,t)}{\partial x}}ax-{\frac {b^{2}}{2r(t)}}\left({\frac {\partial V(x,t)}{\partial x}}\right)^{2}+{\frac {\sigma ^{2}}{2}}{\frac {\partial ^{2}V(x,t)}{\partial x^{2}}}.}

with optimal action given by

u
          
            t
          
        
        =
        −
        
          
            b
            
              r
              (
              t
              )
            
          
        
        
          
            
              ∂
              V
              (
              x
              ,
              t
              )
            
            
              ∂
              x
            
          
        
      
    
    {\displaystyle u_{t}=-{\frac {b}{r(t)}}{\frac {\partial V(x,t)}{\partial x}}}

Assuming a quadratic form for the value function, we obtain the usual <a href="/facts/Riccati_equation/PeEqV5Lw">Riccati equation</a> for the Hessian of the value function as is usual for <a href="/facts/Linear-quadratic-Gaussian_control/3sI4R7zA">Linear-quadratic-Gaussian control</a>.

<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/Bellman_equation/Qh2gKSMH">Bellman equation</a>, discrete-time counterpart of the Hamilton–Jacobi–Bellman equation.</li>
<li><a href="/facts/Pontryagin%2527s_maximum_principle/gEVJ1sjc">Pontryagin's maximum principle</a>, necessary but not sufficient condition for optimum, by maximizing a <a href="/facts/Hamiltonian_(control_theory)/cPcyjLhU">Hamiltonian</a>, but this has the advantage over HJB of only needing to be satisfied over the single trajectory being considered.</li></ul>

<h2 id="further-reading">Further reading</h2>
<ul><li><a href="/facts/Dimitri_P._Bertsekas/uLJEULS4">Bertsekas, Dimitri P.</a> (2005). Dynamic Programming and Optimal Control. Athena Scientific.</li>
<li>Pham, Huyên (2009). <a href="https://books.google.com/books?id=xBsagiBp1SYC&pg=PA37">"The Classical PDE Approach to Dynamic Programming"</a>. Continuous-time Stochastic Control and Optimization with Financial Applications. Springer. pp. 37–60. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-3-540-89499-5.</li>
<li>Stengel, Robert F. (1994). <a href="https://books.google.com/books?id=jDjPxqm7Lw0C&pg=PA201">"Conditions for Optimality"</a>. Optimal Control and Estimation. New York: Dover. pp. 201–222. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 0-486-68200-5.</li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1">Kirk, Donald E. (1970). Optimal Control Theory: An Introduction. Englewood Cliffs, NJ: Prentice-Hall. pp. 86–90. ISBN 0-13-638098-0. <a href="0-13-638098-0" target="_blank">0-13-638098-0</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">Yong, Jiongmin; Zhou, Xun Yu (1999). "Dynamic Programming and HJB Equations". Stochastic Controls : Hamiltonian Systems and HJB Equations. Springer. pp. 157–215 [p. 163]. ISBN 0-387-98723-1. <a href="0-387-98723-1" target="_blank">0-387-98723-1</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">Naidu, Desineni S. (2003). "The Hamilton–Jacobi–Bellman Equation". Optimal Control Systems. Boca Raton: CRC Press. pp. 277–283 [p. 280]. ISBN 0-8493-0892-5. <a href="0-8493-0892-5" target="_blank">0-8493-0892-5</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
<li id="fn:4">Bellman, R. E. (1954). "Dynamic Programming and a new formalism in the calculus of variations". Proc. Natl. Acad. Sci. 40 (4): 231–235. Bibcode:1954PNAS...40..231B. doi:10.1073/pnas.40.4.231. PMC 527981. PMID 16589462. <a href="https://www.ncbi.nlm.nih.gov/pmc/articles/PMC527981" target="_blank">https://www.ncbi.nlm.nih.gov/pmc/articles/PMC527981</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></li>
<li id="fn:5">Bellman, R. E. (1957). Dynamic Programming. Princeton, NJ: Princeton University Press. <a href="#fnref:5" class="footnote-back-ref">↩</a></li>
<li id="fn:6">Bellman, R.; Dreyfus, S. (1959). "An Application of Dynamic Programming to the Determination of Optimal Satellite Trajectories". J. Br. Interplanet. Soc. 17: 78–83. <a href="#fnref:6" class="footnote-back-ref">↩</a></li>
<li id="fn:7">Kálmán, Rudolf E. (1963). "The Theory of Optimal Control and the Calculus of Variations". In Bellman, Richard (ed.). Mathematical Optimization Techniques. Berkeley: University of California Press. pp. 309–331. OCLC 1033974. <a href="/wiki/OCLC_(identifier)" target="_blank">/wiki/OCLC_(identifier)</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></li>
<li id="fn:8">Kemajou-Brown, Isabelle (2016). "Brief History of Optimal Control Theory and Some Recent Developments". In Budzban, Gregory; Hughes, Harry Randolph; Schurz, Henri (eds.). Probability on Algebraic and Geometric Structures. Contemporary Mathematics. Vol. 668. pp. 119–130. doi:10.1090/conm/668/13400. ISBN 9781470419455. <a href="9781470419455" target="_blank">9781470419455</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></li>
<li id="fn:9">Chang, Fwu-Ranq (2004). Stochastic Optimization in Continuous Time. Cambridge, UK: Cambridge University Press. pp. 113–168. ISBN 0-521-83406-6. <a href="0-521-83406-6" target="_blank">0-521-83406-6</a> <a href="#fnref:9" class="footnote-back-ref">↩</a></li>
<li id="fn:10">Bardi, Martino; Capuzzo-Dolcetta, Italo (1997). Optimal Control and Viscosity Solutions of Hamilton–Jacobi–Bellman Equations. Boston: Birkhäuser. ISBN 0-8176-3640-4. <a href="0-8176-3640-4" target="_blank">0-8176-3640-4</a> <a href="#fnref:10" class="footnote-back-ref">↩</a></li>
<li id="fn:11">Lewis, Frank L.; Vrabie, Draguna; Syrmos, Vassilis L. (2012). Optimal Control (3rd ed.). Wiley. p. 278. ISBN 978-0-470-63349-6. <a href="978-0-470-63349-6" target="_blank">978-0-470-63349-6</a> <a href="#fnref:11" class="footnote-back-ref">↩</a></li>
<li id="fn:12">Bertsekas, Dimitri P. (2005). Dynamic Programming and Optimal Control. Athena Scientific. <a href="#fnref:12" class="footnote-back-ref">↩</a></li>
<li id="fn:13">Bardi, Martino; Capuzzo-Dolcetta, Italo (1997). Optimal Control and Viscosity Solutions of Hamilton-Jacobi-Bellman Equations. Boston: Birkhäuser. ISBN 0-8176-3640-4. <a href="0-8176-3640-4" target="_blank">0-8176-3640-4</a> <a href="#fnref:13" class="footnote-back-ref">↩</a></li>
<li id="fn:14">Bertsekas, Dimitri P.; Tsitsiklis, John N. (1996). Neuro-dynamic Programming. Athena Scientific. ISBN 978-1-886529-10-6. <a href="978-1-886529-10-6" target="_blank">978-1-886529-10-6</a> <a href="#fnref:14" class="footnote-back-ref">↩</a></li>
<li id="fn:15">Abu-Khalaf, Murad; Lewis, Frank L. (2005). "Nearly optimal control laws for nonlinear systems with saturating actuators using a neural network HJB approach". Automatica. 41 (5): 779–791. doi:10.1016/j.automatica.2004.11.034. S2CID 14757582. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:15" class="footnote-back-ref">↩</a></li>
<li id="fn:16">Al-Tamimi, Asma; Lewis, Frank L.; Abu-Khalaf, Murad (2008). "Discrete-Time Nonlinear HJB Solution Using Approximate Dynamic Programming: Convergence Proof". IEEE Transactions on Systems, Man, and Cybernetics - Part B: Cybernetics. 38 (4): 943–949. doi:10.1109/TSMCB.2008.926614. PMID 18632382. S2CID 14202785. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:16" class="footnote-back-ref">↩</a></li>
<li id="fn:17">Jones, Morgan; Peet, Matthew (2020). "Polynomial Approximation of Value Functions and Nonlinear Controller Design with Performance Bounds". arXiv:2010.06828 [math.OC]. <a href="/wiki/ArXiv_(identifier)" target="_blank">/wiki/ArXiv_(identifier)</a> <a href="#fnref:17" class="footnote-back-ref">↩</a></li>
</ol>

Hamilton–Jacobi–Bellman equation open-in-new

Hamilton–Jacobi–Bellman equation