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），其中用信息论来了解此反例中的通讯。此反例的最佳解仍然是还没有答案的开放问题。