Witsenhausen反例

Witsenhausen反例(Witsenhausen's counterexample)是在分散随机控制中看似简单的玩具问题,是由Hans Witsenhausen英语Hans Witsenhausen在1968年所提出的反例[1]。有关集中式LQG控制系统(线性系统、有高斯噪声、其成本函数为二次函数下,会有线性的最佳控制律)的结论,一般会很自然猜想其中的重要特性可以推广到分散系统,而Witsenhausen反例即为上述猜想的反例。Witsenhausen建构了二阶段的LQG系统,其中二个控制器的决策都是根据分散性资讯所独立决策的,并且证明在此系统中,有比所有线性控制律更好的非线性控制律。现今还无法找到最佳的控制律[2]

WitsenhausenCounterexample.jpg

反例的说明

此一反例的说明如下:二个控制器试图要在恰好二个时间间隔内将状态控制到接近零的程度。第一个控制器观察最初状态 ,成本函数中有关于第一个控制器输入 的成本,也有第二个控制器状态 的成本。第二个控制器的输入 没有成本,不过是以第一个控制器状态 ,有包括噪声的观测值 为基础。第二个控制器不能和第一个控制器通讯,也无法观察到原始状态 或是第一个控制器的输入 。系统动态方程如下:

 
 

第二个控制器的估测方程为

 

目标是让期望的成本函数最小化

 

其中的期望值是在考虑初始状态 的随机以及估测噪声 下所得的,两者都是独立分布的乱数。估测噪声 假设是正态分布,而初始状态的分布则随问题的版本不同而不同。

问题是要找到控制函数

 

至少让目标函数和其他控制函数下的结果一样的好。Witsenhausen证明最佳函数  不会是线性函数。

Witsenhausen所得的结果

Witsenhausen所得的结果如下:

  • 最佳解存在(引理1)。
  • 第一个控制器的最佳控制律是让   的控制律(引理9)。
  • 实际控制律发生在二个控制器都限制在线性下的结果(引理11)。
  •  是高斯分布,至少一个控制器限制要是线性的,则二个控制器都是线性时有最佳解(引理13)。
  • 实际的非线性控制律是在 二点对称分布英语symmetric distribution的条件下(引理15)。
  •  是高斯分布,针对一些参数 的特定值时,其非线性控制律中的非最佳解,其成本函数的期望值都比线性最佳控制律下的成本函数的期望值要低(定理2)。

问题的重要性

此反例是在控制理论信息论的交集。因为此问题的难度,找最佳控制律的问题也受到理论计算机科学社群的关注。此问题的重要性在2008年在墨西哥Cancun举行的47届IEEE决策及控制研讨会(CDC)可以看出[2],其中有一整个会议就是了解此一反例,而当时距Witsenhausen最早的反例提出已有40年之久。

此问题在分散式控制的概念上很重要,证明了分散式控制器为了要让成本函数最低,彼此通讯的重要性[3]。因此分散式系统的控制行动有二个角色:控制以及通讯。

问题的难度

问题的难度是因为第二个控制器的资讯是依照第一个控制器的决策所决定[4]Tamer Basar英语Tamer Basar考虑的变体版本[5]也证明了问题的难度也是因为其性能指标的结构,以及不同决策变数的耦合。也已经证明Witsenhausen的反例,若在连接二个控制器之间外部通道的传输时延,比问题中的传播延迟要短时,问题会较简单。不过此一结果会要求通道是完美无噪声,而且是即时的[6],因此限制了实用的程度。在实务上,外部通道总是不完美的,因此无法假设在有外部通道时,分散式控制问题会比较简单。

计算机科学文献也找到了这个分散式问题困难的原因:赫里斯托斯·帕帕季米特里乌及John Tsitsiklis证明此一反例是NP完全[7]

试图求解

有许多方式试图用数值方式求解。若限制问题的参数( ),研究者已经透过离散化 以及神经网络求解[8]。进一步的研究(著名的有何毓琦的研究[9],Li, Marden和Shamma英语Jeff S. Shamma的研究[10])在相同参数范围下其成本略有改善。不同参数下的最佳数值解,包括上述所提到的数值解,都是由S.-H. Tseng 和A. Tang在2017年提出的局部搜寻法所得[11]。第一个可能近似最佳的控制策略是在2010年提出(Grover, Park, Sahai)[12],其中用信息论来了解此反例中的通讯。此反例的最佳解仍然是还没有答案的开放问题。

参考资料

  1. ^ Witsenhausen, Hans. "A counterexample in stochastic optimum control." SIAM J. Control, Volume 6, Issue 1, pp. 131–147 (February 1968)
  2. ^ 2.0 2.1 Ho, Yu-Chi, "Review of the Witsenhausen problem". Proceedings of the 47th IEEE Conference on Decision and Control (CDC), pp. 1611–1613, 2008.
  3. ^ Mitterrand and Sahai. "Information and Control: Witsenhausen revisited". Learning, control and hybrid systems, 1999, Springer.
  4. ^ Ho, Yu-Chi. "Team decision theory and information structures". Proceedings of the IEEE, Vol. 68, No.6, June 1980.
  5. ^ Basar, Tamer. "Variations on the theme of the Witsenhausen counterexample". 47th IEEE Conference on Decision and Control Cancun, Mexico, Dec. 9–11, 2008.
  6. ^ 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.
  7. ^ 赫里斯托斯·帕帕季米特里乌 and John Tsitsiklis. "Intractable problems in control theory." 24th IEEE Conference on Decision and Control, 1985
  8. ^ Baglietto, Parisini, and Zoppoli. "Numerical solutions to the Witsenhausen counterexample by approximating ne]]tworks." IEEE Trans. Automatic Control. 2001.
  9. ^ Lee, Lau, and Ho. "The Witsenhausen counterexample: A hierarchical search approach for nonconvex optimization problems." IEEE Trans. Automatic Control, 2001
  10. ^ Li, Marden, and Shamma. "Learning approaches to the Witsenhausen counterexample from a view of potential games." IEEE Conference on Decision and Control, 2009.
  11. ^ Tseng and Tang. "A Local Search Algorithm for the Witsenhausen's Counterexample." IEEE Conference on Decision and Control, 2017.
  12. ^ Grover, Sahai, and Park. "The finite-dimensional Witsenhausen counterexample." IEEE WiOpt 2010, ConCom workshop, Seoul, Korea.