查看“︁Witsenhausen反例”︁的源代码

'''Witsenhausen反例'''（Witsenhausen's counterexample）是在[[分散控制系統|分散]][[隨機控制]]中看似簡單的[[玩具問題]]，是由{{link-en|Hans Witsenhausen|Hans Witsenhausen}}在1968年所提出的[[反例]]<ref>Witsenhausen, Hans. "A counterexample in stochastic optimum control." ''SIAM J. Control'', Volume 6, Issue 1, pp. 131–147 (February 1968)</ref>。有關集中式[[LQG控制]]系統（線性系統、有高斯雜訊、其成本函數為二次函數下，會有線性的最佳控制律）的結論，一般會很自然[[猜想]]其中的重要特性可以推廣到分散系統，而Witsenhausen反例即為上述猜想的反例。Witsenhausen建構了二階段的LQG系統，其中二個控制器的決策都是根據分散性資訊所獨立決策的，並且證明在此系統中，有比所有線性控制律更好的非線性控制律。現今還無法找到最佳的控制律<ref name=Ho>Ho, Yu-Chi, "Review of the Witsenhausen problem". ''Proceedings of the 47th IEEE Conference on Decision and Control (CDC)'', pp. 1611–1613, 2008.</ref>。

[[File:WitsenhausenCounterexample.jpg]]

==反例的說明==
此一反例的說明如下：二個控制器試圖要在恰好二個時間間隔內將狀態控制到接近零的程度。第一個控制器觀察最初狀態<math>x_0</math>，成本函數中有關於第一個控制器輸入<math>u_1</math>的成本，也有第二個控制器狀態<math>x_2</math>的成本。第二個控制器的輸入<math>u_2</math>沒有成本，不過是以第一個控制器狀態<math>x_1</math>，有包括雜訊的觀測值<math>y_1=x_1+z</math>為基礎。第二個控制器不能和第一個控制器通訊，也無法觀察到原始狀態<math>x_0</math>或是第一個控制器的輸入<math>u_1</math>。系統動態方程如下：

:<math>x_1=x_0+u_1,</math>
:<math>x_2=x_1-u_2,</math>

第二個控制器的估測方程為

:<math>y_1=x_1+z.</math>

目標是讓期望的[[损失函数|成本函數]]最小化

:<math>k^2E[u_1^2]+E[x_2^2],</math>

其中的期望值是在考慮初始狀態<math>x_0</math>的隨機以及估測雜訊<math>z</math>下所得的，兩者都是[[独立 (概率论)|独立]]分布的亂數。估測雜訊<math>z</math>假設是[[正态分布]]，而初始狀態的分佈則隨問題的版本不同而不同。

問題是要找到控制函數

:<math>u_1(x_0) \quad \text{and} \quad u_2(y_1)</math>

至少讓目標函數和其他控制函數下的結果一樣的好。Witsenhausen證明最佳函數<math> u_1(x_0)</math>和<math>u_2(y_1)</math>不會是線性函數。

==Witsenhausen所得的結果==

Witsenhausen所得的結果如下：

*最佳解存在（引理1）。
*第一個控制器的最佳控制律是讓 <math>E(x_1)=0</math> 的控制律（引理9）。
*實際控制律發生在二個控制器都限制在線性下的結果（引理11）。
*若<math>x_0</math>是高斯分佈，至少一個控制器限制要是線性的，則二個控制器都是線性時有最佳解（引理13）。
*實際的非線性控制律是在<math>x_0</math>為[[伯努利分布|二點]]{{link-en|對稱分佈|symmetric distribution}}的條件下（引理15）。
*若<math>x_0</math>是高斯分佈，針對一些參數<math>k</math>的特定值時，其非線性控制律中的非最佳解，其成本函數的期望值都比線性最佳控制律下的成本函數的期望值要低（定理2）。

==問題的重要性==
此反例是在[[控制理论]]及[[信息论]]的交集。因為此問題的難度，找最佳控制律的問題也受到[[理論計算機科學]]社群的關注。此問題的重要性在2008年在墨西哥Cancun舉行的47屆IEEE決策及控制研討會（CDC）可以看出<ref name=Ho/>，其中有一整個會議就是瞭解此一反例，而當時距Witsenhausen最早的反例提出已有40年之久。

此問題在分散式控制的概念上很重要，證明了分散式控制器為了要讓成本函數最低，彼此通訊的重要性<ref>Mitterrand and Sahai. "Information and Control: Witsenhausen revisited". ''Learning, control and hybrid systems'', 1999, Springer.</ref>。因此分散式系統的控制行動有二個角色：控制以及通訊。

==問題的難度==
問題的難度是因為第二個控制器的資訊是依照第一個控制器的決策所決定<ref>Ho, Yu-Chi. "Team decision theory and information structures". ''Proceedings of the IEEE'', Vol. 68, No.6, June 1980.</ref>。{{link-en|Tamer Basar|Tamer Basar}}考慮的變體版本<ref>Basar, Tamer. "Variations on the theme of the Witsenhausen counterexample". ''47th IEEE Conference on Decision and Control Cancun'', Mexico, Dec. 9–11, 2008.</ref>也證明了問題的難度也是因為其性能指標的結構，以及不同決策變數的耦合。也已經證明Witsenhausen的反例，若在連接二個控制器之間外部通道的[[传输时延]]，比問題中的[[傳播延遲]]要短時，問題會較簡單。不過此一結果會要求通道是完美無雜訊，而且是即時的<ref>Rotkowitz, M.; Cogill, R.; Lall, S.; , "A Simple Condition for the Convexity of Optimal Control over Networks with Delays," ''Decision and Control'', 2005 and 2005 ''European Control Conference. CDC-ECC '05. 44th IEEE Conference on'' , pp. 6686–6691, 12–15 December 2005.</ref>，因此限制了實用的程度。在實務上，外部通道總是不完美的，因此無法假設在有外部通道時，分散式控制問題會比較簡單。

計算機科學文獻也找到了這個分散式問題困難的原因：[[赫里斯托斯·帕帕季米特里乌]]及John Tsitsiklis證明此一反例是[[NP完全]]<ref><!-- [[Christos Papadimitriou]] -->[[赫里斯托斯·帕帕季米特里乌]] and John Tsitsiklis.  "Intractable problems in control theory." ''24th IEEE Conference on Decision and Control'', 1985</ref>。

==試圖求解==
有許多方式試圖用數值方式求解。若限制問題的參數（<math>(k=0.2,\;\sigma_0=5)</math>），研究者已經透過[[离散化]] 以及[[人工神經網路|神經網路]]求解<ref>Baglietto, Parisini, and Zoppoli. "Numerical solutions to the Witsenhausen counterexample by approximating ne]]tworks." ''IEEE Trans. Automatic Control''. 2001.</ref>。進一步的研究（著名的有[[何毓琦]]的研究<ref>Lee, Lau, and Ho. "The Witsenhausen counterexample: A hierarchical search approach for nonconvex optimization problems." '' IEEE Trans. Automatic Control'', 2001</ref>，Li, Marden和{{link-en|Jeff S. Shamma|Jeff S. Shamma|Shamma}}的研究<ref>Li, Marden, and Shamma. "Learning approaches to the Witsenhausen counterexample from a view of potential games." '' IEEE Conference on Decision and Control'', 2009.</ref>）在相同參數範圍下其成本略有改善。不同參數下的最佳數值解，包括上述所提到的數值解，都是由S.-H. Tseng 和A. Tang在2017年提出的局部搜尋法所得<ref>Tseng and Tang. "A Local Search Algorithm for the Witsenhausen's Counterexample." '' IEEE Conference on Decision and Control'', 2017.</ref>。第一個可能近似最佳的控制策略是在2010年提出（Grover, Park, Sahai）<ref>Grover, Sahai, and Park. "The finite-dimensional Witsenhausen counterexample." ''IEEE WiOpt 2010, ConCom workshop'', Seoul, Korea.</ref>，其中用[[信息论]]來了解此反例中的通訊。此反例的最佳解仍然是還沒有答案的開放問題。

==參考資料==
{{Reflist}}

[[Category:控制理论]]
[[Category:隨機控制]]