Witsenhausen反例

Witsenhausen反例（Witsenhausen's counterexample）是在分散隨機控制中看似簡單的玩具問題，是由Hans Witsenhausen在1968年所提出的反例。有關集中式LQG控制系統（線性系統、有高斯雜訊、其成本函數為二次函數下，會有線性的最佳控制律）的結論，一般會很自然猜想其中的重要特性可以推廣到分散系統，而Witsenhausen反例即為上述猜想的反例。Witsenhausen建構了二階段的LQG系統，其中二個控制器的決策都是根據分散性資訊所獨立決策的，並且證明在此系統中，有比所有線性控制律更好的非線性控制律。現今還無法找到最佳的控制律。

反例的說明

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

$x_{1}=x_{0}+u_{1},$

$x_{2}=x_{1}-u_{2},$

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

$y_{1}=x_{1}+z.$

目標是讓期望的成本函數最小化

$k^{2}E[u_{1}^{2}]+E[x_{2}^{2}],$

其中的期望值是在考慮初始狀態$x_{0}$的隨機以及估測雜訊$z$下所得的，兩者都是獨立分布的亂數。估測雜訊$z$假設是常態分布，而初始狀態的分佈則隨問題的版本不同而不同。

問題是要找到控制函數

$u_{1}(x_{0})\quad {\text{and}}\quad u_{2}(y_{1})$

至少讓目標函數和其他控制函數下的結果一樣的好。Witsenhausen證明最佳函數$u_{1}(x_{0})$和$u_{2}(y_{1})$不會是線性函數。

Witsenhausen所得的結果

Witsenhausen所得的結果如下：

• 最佳解存在（引理1）。
• 第一個控制器的最佳控制律是讓 $E(x_{1})=0$ 的控制律（引理9）。
• 實際控制律發生在二個控制器都限制在線性下的結果（引理11）。
• 若$x_{0}$是高斯分佈，至少一個控制器限制要是線性的，則二個控制器都是線性時有最佳解（引理13）。
• 實際的非線性控制律是在$x_{0}$為二點對稱分佈的條件下（引理15）。
• 若$x_{0}$是高斯分佈，針對一些參數$k$的特定值時，其非線性控制律中的非最佳解，其成本函數的期望值都比線性最佳控制律下的成本函數的期望值要低（定理2）。

問題的重要性

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

此問題在分散式控制的概念上很重要，證明了分散式控制器為了要讓成本函數最低，彼此通訊的重要性。因此分散式系統的控制行動有二個角色：控制以及通訊。

問題的難度

問題的難度是因為第二個控制器的資訊是依照第一個控制器的決策所決定。Tamer Basar考慮的變體版本也證明了問題的難度也是因為其性能指標的結構，以及不同決策變數的耦合。也已經證明Witsenhausen的反例，若在連接二個控制器之間外部通道的傳輸時延，比問題中的傳播延遲要短時，問題會較簡單。不過此一結果會要求通道是完美無雜訊，而且是即時的，因此限制了實用的程度。在實務上，外部通道總是不完美的，因此無法假設在有外部通道時，分散式控制問題會比較簡單。

計算機科學文獻也找到了這個分散式問題困難的原因：赫里斯托斯·帕帕季米特里烏及John Tsitsiklis證明此一反例是NP完全。

試圖求解

有許多方式試圖用數值方式求解。若限制問題的參數（$(k=0.2,\;\sigma _{0}=5)$），研究者已經透過離散化 以及神經網路求解。進一步的研究（著名的有何毓琦的研究，Li, Marden和Shamma的研究）在相同參數範圍下其成本略有改善。不同參數下的最佳數值解，包括上述所提到的數值解，都是由S.-H. Tseng 和A. Tang在2017年提出的局部搜尋法所得。第一個可能近似最佳的控制策略是在2010年提出（Grover, Park, Sahai），其中用資訊理論來了解此反例中的通訊。此反例的最佳解仍然是還沒有答案的開放問題。