動態規劃與最優控制：近似動態規劃(第Ⅰ卷)（簡體書）

本書系統性介紹動態規劃與最優控制，包括動態規劃算法、確定性系統與隨機最短路問題、確定性連續時間最優控制、狀態信息完整的問題、狀態信息缺失的問題、次優與適應控制、無窮階段問題等。

賈慶山，清華大學自動化系副教授，2002年和2006年分別于清華大學自動化系獲工學學士、博士學位，同年留校任教。2006、2010、2013年分別任美國哈佛大學、香港科技大學、美國麻省理工學院訪問學者。作為負責人先后承擔國家自然科學基金青年基金、面上項目、優秀青年基金，參加國家自然科學基金重點項目、重大研究計劃培育項目和集成項目。承擔多個國際合作項目。任IEEE Transactions on Automation Science and Engineering、Discrete Event Dynamic Systems - Theory and Applications等國際期刊副編輯，IIE Transactions領域編輯。發表國際期刊論文和國際會議論文逾八十篇，合著英文專著一部，合編英文專著一部，合譯教材一本。

本書是MIT博塞克斯教授的一本力作，分兩卷，本書是第I卷，主要介紹動態規劃與最優控制的基本方法，包括最短路徑問題、精確和不精確狀態信息、有限與無限階段問題等經典模型，以及近似動態規劃等理論方法。本書體現了博塞克斯教授著作的一貫的特點，深入淺出，適于自學，相信讀者會有愉快的閱讀與學習體驗。

Dimitri P. Bertsekas是美國麻省理工學院教授、美國工程院院士，在國際優化與控制界享有盛譽。他編寫的系列教材被麻省理工學院、斯坦福大學、伊利諾伊大學香檳分校等多所世界知名大學選用。《動態規劃與最優控制 ——近似動態規劃》共兩卷，本書為第 I卷，主要介紹動態規劃與最優控制的基本方法，包括最短路徑問題、精確和不精確狀態信息、有限和無限階段問題等經典模型，以及近似動態規劃等理論方法。本書深入淺出，非常適合控制、優化、電子工程、計算機、工業工程等專業的研究生學習，也適合作為高年級本科生和本領域的研究者的參考書。《動態規劃與最優控制 ——近似動態規劃》第 II卷中譯本已于 2021年由清華大學出版社出版。希望這上下兩卷書對本領域的教師、學生、研究人員能有所益處。
特此說明：為了讀者閱讀方便 (例如參照原版書)，本書中公式、符號、參考文獻等采用原版書的格式。
賈慶山李巖
2024年 2月于北京

關于作者

Dimitri P. Bertsekas曾在希臘國立雅典技術大學學習機械與電機工程，獲得麻省理工學院系統科學博士學位。曾先后在斯坦福大學工程與經濟系統系和伊利諾伊大學香檳分校的電機工程系任教。自 1979年以來，他一直在麻省理工學院電機工程與計算機科學系任教，現任麥卡菲工程教授。
其研究涉及多個領域，包括優化、控制、大規模計算和數據通信網絡，并與其教學和著書工作聯系緊密。他撰寫了眾多論文和十四本著作，其中數本著作在麻省理工學院被用作教材。他與動態規劃之緣始自博士論文的研究，并通過學術論文、多本教材和學術專著一直延續至今。
Bertsekas教授因其（與 John Tsitsiklis合著的）著作《神經動態規劃》在 1997年榮獲 INFORMS授予的運籌學與計算機科學交叉領域的杰出研究成果獎， 2000年希臘運籌學國家獎， 2001年美國控制會議 John R. Ragazzini教育獎。2001年，他當選美國工程院院士。

序言

這套書是基于我在斯坦福大學、伊利諾伊大學香檳分校和麻省理工學院逾二十年時間里給一年級研究生講授“動態規劃和最優控制”課程的基礎上完成的。這門課程通常由工程學、運籌學、經濟學和應用數學專業的學生選修。相應地，這套書的主要目的是面向廣大讀者統一介紹這個領域。特別地，具有連續性的問題，比如在現代控制理論中很普遍的隨機控制問題，與具有離散特點的問題將被一并討論，比如在運籌學中很普遍的馬爾可夫決策問題。進一步，源自多個領域的實際應用和例子也將被討論。
這本書可被視作由本人所著、 Prentice-Hall出版社于 1987年出版的《動態規劃：確定與隨機的模型》一書的擴充以及從教育學角度改進的版本。本書中增加了許多關于確定性與隨機性最短路徑問題的新內容，新增一章討論從動態規劃視角討論的連續時間最優控制問題和龐特里亞金最大值原理。同時也增加了動態規劃所用的基于仿真的近似技術的相當多的內容。這些技術，通常被稱作 “神經動態規劃 ”或者 “強化學習 ”，代表了將動態規劃實際應用于具有大維度和缺乏精確數學模型描述的復雜問題時的一項突破性進展。其他內容也都加以擴充，全面修訂，并更新。
然而，增加這些新內容之后，這本書的頁數也大幅增加，以至于需要分成兩卷：一卷討論有限階段的問題，另一卷討論無限階段的問題。這一劃分方法不僅在頁數上是一種自然的劃分，而且在形式和內容上也是自然的。第 I卷更側重建模，第 II卷更側重數學分析和計算。在第 I卷中增加了最后一章介紹無限階段問題，旨在讓第 I卷可供教師在一門課程中主要側重建模、概念和有限階段問題，同時涵蓋適度的無限階段問題。
本書的許多內容是相互獨立的。比如，第 I卷的第 2章討論最短路徑問題，可被跳過而不失上下文的連貫性；第 I卷的第 3章討論連續時間最優控制問題，也可類似處理。所以，本書可用于講授幾種不同類型的課程。
(a)兩學期的課程涵蓋兩卷。

(b)一學期的課程主要講授第 I卷中的有限階段問題。

(c)一學期的課程主要講授涵蓋第 I卷第 1，4，5，6章和第 II卷第 1，2，4章內容的隨機最優控制問題。

(d)一學期的課程涵蓋第 I卷第 1章、第 2～ 6章內容的約一半，第 II卷第 1，2，4章內容的 70%。這是在麻省理工學院通常講授的課程 I。

(e)一學期的工學課程涵蓋第 I卷前三章以及第 4～ 6章的一部分內容。

(f)一學期的更側重數學的課程涵蓋第 II卷的無限階段問題。

本書所需的數學先修內容包括高等代數、概率論導論和矩陣向量代數。附錄中總結了這些內容。動態系統理論、控制、優化或者運籌學的相關知識將有助于讀者，但以筆者的經驗，書中的相關內容是自我完備的。
書中包含了大量習題。認真的讀者將通過這些習題深深受益。這些習題的答案已匯編成冊，
動態規劃與最優控制——近似動態規劃 (第 I卷)
教師可直接聯系作者獲得。這本參考答案得益于多人長時間的貢獻，特別是 Steven Shreve、Eric Loiederman、Lakis Polymenakos和 Cynara Wu，在此特別致謝。
動態規劃是一項概念簡單的技術，可以用基礎的分析方法解釋得足夠清楚。不過對于一般的動態規劃的嚴格的數學分析需要使用復雜的測度論和概率論。作者選擇避免使用復雜的數學，盡量讓敘述通俗易懂，僅當所涉及的概率空間是可數時才進行嚴格的討論。對該領域的嚴格的數學討論在筆者的另一本與 Steven Shreve合著由 Academic Press于 1978年出版的學術專著《隨機最優控制：離散時間的情形》中進行了討論。那本學術專著與本書的內容互補，為本書敘述不夠嚴謹的內容提供了堅實的基礎。
最后，我要感謝許多為本書做出貢獻的個人和集體。我對這一領域的理解通過與 Steven Shreve合著的 1978年的專著變得更加深刻。我與 John Tsitsiklis在隨機最短路徑和近似動態規劃的合作與交流卓有成效。 Michael Caraanis、Emmanuel Fernandez-Gaucherand、Pierre Humblet、Lennart Ljung和 John Tsitsiklis曾使用本書的多種版本授課，并貢獻了若干關鍵性的意見以及習題。一些同事提供了有價值的觀點和信息，特別是， David Castanon、Eugene Feinberg和 Krishna Pattipati。美國國家科學基金會提供了研究經費的支持。 Prentice-Hall慷慨地允許我使用 1987年所著書的內容。教學工作以及與麻省理工學院學生的交互讓我保持了對這一領域的興趣與快樂。
Dimitri P. Bertsekas
1995年春

第 1章動態規劃算法 1

11概述 1

12基本問題 8

13算法12

14狀態增廣和其他重新建模24

15一些數學問題 29

16動態規劃和極小化極大控制 32

17注釋、參考文獻和習題 35

第 2章確定性系統和最短路徑問題 44

21有限狀態系統和最短路徑44

22一些最短路徑的應用 47

221關鍵路徑分析 47

222隱馬爾可夫模型和瓦特比算法48

23最短路徑算法 53

231標簽糾正方法 55

232標簽糾正變形-A＊算法 60

233分支定界61

234約束與多目標問題 63

24注釋、參考文獻和習題 67

第 3章確定性連續時間最優控制 72

31連續時間最優控制72

32哈密爾頓-雅可比-貝爾曼方程 74

33龐特里亞金最小值原理 79

331使用 HJB方程的非正式推導 79

332一種基于變分思想的推導 86

333離散時間問題的最小值原理 89

34最小值原理推廣 90

341固定的末端狀態91

342自由初始狀態 93

343自由終止時間 94

344時變系統與費用97

動態規劃與最優控制——近似動態規劃 (第 I卷)
345奇異問題97

35注釋、參考文獻和習題 99

第 4章具有精確狀態信息的問題 103

41線性系統和二次型費用 103

42庫存控制 112

43動態資本分析 119

44最優停止問題 122

45調度與交換的理由 130

46不確定性的集合隸屬度描述 133

461集合隸屬度估計 133

462具有未知且有界擾動的控制 138

47注釋、參考文獻和習題 140

第 5章不精確狀態信息的問題 152

51化簡為精確信息的情形 152

52線性系統和二次型費用 160

53線性系統的最小方差控制 165

54充分統計量 176

541條件狀態分布 177

542有限狀態系統 180

55注釋、參考文獻和習題 190

第 6章近似動態規劃 198

61確定性等價和自適應控制 199

611謹慎、探測和對偶控制 203

612兩階段控制和識別能力 204

613確定性等價控制和可辨識性 205

614自調節調節器 209

62開環反饋控制 210

63有限前瞻策略 213

631有限前瞻策略的性能界 214

632有限前瞻中的計算問題 217

633問題近似——強化分解 219

634集結 223

635后續費用的參數化近似 227

64滾動算法 234

641離散確定性問題 239

642由仿真評價的 Q-因子 251

目錄 IX
643 Q-因子近似 253

65模型預測控制及相關方法 255

651滾動時段近似 255

652模型預測控制中的穩定性問題 257

653結構受限的策略 262

66近似動態規劃中的額外主題 266

661離散化 266

662其他近似方法 268

67注釋、參考文獻和習題 269

第 7章無限階段問題介紹 280

71概覽 280

72隨機最短路徑問題 282

73折扣問題 290

74每階段平均費用問題 293

75半馬爾可夫問題 303

76注釋、參考文獻和習題 310

附錄 A數學知識復習 320

A1集合 320

A2歐氏空間 321

A3矩陣 321

A4分析 324

A5凸集和凸函數 325

附錄 B優化理論 327

B1最優解 327

B2最優性條件 328

B3二次型最小化 329

附錄 C概率論 330

C1概率空間 330

C2隨機變量 330

C3條件概率 331

附錄 D關于有限狀態馬爾可夫鏈 333

D1平穩馬爾可夫鏈 333

D2狀態分類 334

D3極限概率 334

動態規劃與最優控制——近似動態規劃 (第 I卷)
D4首達時間 335

附錄 E卡爾曼濾波 336

E1最小二乘估計 336

E2線性最小二乘估計 337

E3狀態估計——卡爾曼濾波器 342

E4穩定性方面 346

E5高斯-馬爾可夫估計器 347

E6確定性最小二乘估計 349

附錄 F隨機線性系統模型 351

F1具有隨機輸入的線性系統 351

F2具有有理數譜的過程 352

F3 ARMAX模型 353

附錄 G不確定性下的決策問題建模 354

G1不確定性下的決策問題 354

G2期望效用理論和風險 357

G3隨機最優控制問題 365

參考文獻 369