貝爾曼方程

貝爾曼方程

貝爾曼方程(Bellman Equation)也被稱作動態規劃方程(Dynamic Programming Equation),由理查·貝爾曼(Richard Bellman)發現。 貝爾曼方程是動態規劃(Dynamic Programming)這些數學最佳化方法能夠達到最佳化的必要條件。此方程把“決策問題在特定時間怎么的值”以“來自初始選擇的報酬比從初始選擇衍生的決策問題的值”的形式表示。藉此這個方式把動態最佳化問題變成簡單的子問題,而這些子問題遵守從貝爾曼所提出來的“最佳化還原理”。

來源

貝爾曼方程最早套用在工程領域的控制理論和其他套用數學領域,而後成為經濟學上的重要工具。

幾乎所有的可以用最佳控制理論(Optimal Control Theory)解決的問題也可以通過分析合適的貝爾曼方程得到解決。然而,貝爾曼方程通常指離散時間(discrete-time)最佳化問題的動態規劃方程。

處理連續時間(continuous-time)最佳化問題上,也有類似那些偏微分方程,稱作漢密爾頓-雅克比-貝爾曼方程(Hamilton–Jacobi–Bellman Equation,HJB Equation)。

簡介

貝爾曼方程是關於未知函式(目標函式)的函式方程組。套用最最佳化原理和嵌入原理建立函式方程組的方法稱為函式方程法。在實際運用中要按照具體問題尋求特殊解法。動態規劃理論開拓了函式方程理論中許多新的領域。

特點和套用範圍 :

若多階段決策過程為連續型,則動態規劃與變分法處理的問題有共同之處。動態規劃原理可用來將變分法問題歸結為多階段決策過程,用動態規劃的貝爾曼方程求解。在最優控制理論中動態規劃方法比極大值原理更為適用 ,但動態規劃還缺少嚴格的邏輯基礎。

60年代,В.Г.沃爾昌斯基對動態規劃方法作了數學論證。

動態規劃方法的五個特點:

①在策略變數較多時,與策略窮舉法相比可降低維數;

②在給定的定義域或限制條件下很難用微分方法求極值的函式,可用動態規劃方法求極值;

③對於不能用解析形式表達的函式,可給出遞推關係求數值解;

④動態規劃方法可以解決古典方法不能處理的問題,如兩點邊值問題和隱變分問題等;

⑤許多數學規劃問題均可用動態規劃方法來解決,例如,含有隨時間或空間變化的因素的經濟問題。

投資問題、庫存問題、生產計畫、資源分配、設備更新、最優搜尋、馬爾可夫決策過程,以及最優控制和自適應控制等問題,均可用動態規劃方法來處理。

解析概念

想了解貝爾曼方程,先要了解許多相關概念。首先,任何最佳化問題 都有目標:旅行時間最小化、成本最小化、利潤最大化、效用最大化等。用來描述目標的數學函式就稱為目標函式。

動態規劃 把一期規劃問題轉為不和時間怎么上開簡單的步驟,因此,它需要追蹤決策背景情況隨時間的變化。作正確決策所需要當前情況的信息被稱作是狀態(State)(貝爾曼,1957,Ch. III.2)。例如,為了決定每一個時間要花一些錢,人們必須要知道他們初始財富的量,此例中財富就是一種狀態變數(State Variables),或簡稱狀態(State),當然也可能還有其他的種類。

控制變數(Control Variables)是控制理論中描述輸入的變數 ,簡稱控制(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)求偏導的結果聯立求解。

相關詞條

相關搜尋

熱門詞條

聯絡我們