-
貝爾曼方程
鎖定
貝爾曼方程(Bellman Equation)也被稱作動態規劃方程(Dynamic Programming Equation),由理查·貝爾曼(Richard Bellman)發現。
貝爾曼方程是動態規劃(Dynamic Programming)這些數學最佳化方法能夠達到最佳化的必要條件。此方程把“決策問題在特定時間怎麼的值”以“來自初始選擇的報酬比從初始選擇衍生的決策問題的值”的形式表示。藉此這個方式把動態最佳化問題變成簡單的子問題,而這些子問題遵守從貝爾曼所提出來的“最佳化還原理”。
- 中文名
- 貝爾曼方程
- 外文名
- Bellman Equation
- 別 名
- 動態規劃方程
- 基本原理
- 最優化原理和嵌入原理
- 提出者
- 理查·貝爾曼(Richard Bellman)
- 學 科
- 數學、經濟學
- 類 型
- 數學術語
目錄
貝爾曼方程來源
貝爾曼方程最早應用在工程領域的控制理論和其他應用數學領域,而後成為經濟學上的重要工具。
幾乎所有的可以用最佳控制理論(Optimal Control Theory)解決的問題也可以通過分析合適的貝爾曼方程得到解決。然而,貝爾曼方程通常指離散時間(discrete-time)最佳化問題的動態規劃方程。
處理連續時間(continuous-time)最佳化問題上,也有類似那些偏微分方程,稱作漢密爾頓-雅克比-貝爾曼方程(Hamilton–Jacobi–Bellman Equation,HJB Equation)。
貝爾曼方程簡介
特點和應用範圍 :
若多階段決策過程為連續型,則動態規劃與變分法處理的問題有共同之處。動態規劃原理可用來將變分法問題歸結為多階段決策過程,用動態規劃的貝爾曼方程求解。在最優控制理論中動態規劃方法比極大值原理更為適用
[1]
,但動態規劃還缺少嚴格的邏輯基礎。
60年代,В.Г.沃爾昌斯基對動態規劃方法作了數學論證。
動態規劃方法的五個特點:
①在策略變量較多時,與策略窮舉法相比可降低維數;
②在給定的定義域或限制條件下很難用微分方法求極值的函數,可用動態規劃方法求極值;
④動態規劃方法可以解決古典方法不能處理的問題,如兩點邊值問題和隱變分問題等;
⑤許多數學規劃問題均可用動態規劃方法來解決,例如,含有隨時間或空間變化的因素的經濟問題。
貝爾曼方程解析概念
動態規劃
[3]
是把一個規劃問題轉化為抽象狀態之間的轉移,因此,它需要追蹤決策背景情況隨時間的變化。作正確決策所需要當前情況的信息被稱作是狀態(State)(貝爾曼,1957,Ch. III.2)。例如,為了決定每一個時間要花一些錢,人們必須要知道他們初始財富的量,此例中財富就是一種狀態變數(State Variables),或簡稱狀態(State),當然也可能還有其他的種類。
控制變數(Control Variables)是控制理論中描述輸入的變量
[1]
,簡稱控制(Control)。例如給還是當前所具有的財富(狀態),人們便可以用以取決還是當下的消費(控制變數)。靠選當下的控制變數能被視為挑選下狀態,廣義而語言,下狀態受到當下控制變數比其他因數的影響。
舉一個簡單的例子:當前的財富(狀態)比消費(控制變數)會決定未來的財富(新的狀態),雖然通常也還有其他的因素可以影響未來的財富(例如獲得意外之財)。
動態規劃方法中最佳化的步驟可以被描述為“找某種規則告訴我們各可能狀態下的(最佳)控制為何。例如:假如消費(c)的與財富(W)相關,我們想要找到一套規則c(W)來以財富描述消費。
這些“把控制(Controls)表示成狀態(States)的函數”的規則被稱為策略函數(Policy Function)。
貝爾曼方程動態規劃與最優控制的關係
不同的是,漢密爾頓函數是通過取任意一個時點實現最優從而求取整個動態過程的最優,而貝爾曼方程是通過將多級最優決策轉化為多個單級最優決策從而求取整個動態過程的最優,所以貝爾曼方程還叫做動態規劃的基本遞推方程。
此外,貝爾曼方程還能用於處理非線性的動態優化,這是漢密爾頓函數做不到的。
貝爾曼方程基本原理
最優化原理體現了動態規劃方法的基本思想。
貝爾曼方程嵌入原理
一個具有已知初始狀態和固定步數的過程總可以看作是初始狀態和步數均不確定的一族過程中的一個特殊情況。這種把所研究的過程嵌入一個過程族的原理稱為嵌入原理。
通過研究過程族的最優策略族的共同性質得出一般通解,此通解自然也適用於原來的特殊問題。動態規劃的基本方法就是根據嵌入原理把一個多步決策問題化為一系列較簡單的一步決策問題,可顯著降低數學處理上的難度。
貝爾曼方程貝爾曼方程的基本形式
問題的基本形式可以描述為:
Max ∑β^tF(X(t),U(t))
s.t. X(t+1)=G(X(t),U(t)),t=0,1,2,3……
X(t=0)=X0,初始狀態給定,而其後任意時間的狀態變量數值都是可變的。
定義值函數為:
V(X(t),t)=Max ∑β^tF(X(t),U(t)),β∈(0,1)
所以,任意階段t的貝爾曼方程就可以表示為
U(X(t),t)=Max F(X(t),U(t))+βV(X(t+1),t+1)
貝爾曼方程解的基本形式直接給出,證明過程太複雜,此處不詳列。
∂F/∂U(t)+β(∂V/∂X(t+1))(∂G/∂U(t+1))=0
此方程還可以轉化成為動態規劃最優化條件的歐拉方程,方法是將貝爾曼方程的解與貝爾曼方程對X(t+1)求偏導的結果聯立求解。