A linear programming relaxation for stochastic control problems with non-classical information patterns
A linear programming relaxation for stochastic control problems with non-classical information patterns
复制标题
非经典信息模式随机控制问题的线性规划松弛
DOI：
10.1109/cdc.2015.7403121
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
Ankur A. Kulkarni
中科院分区：
文献类型：
--
作者：
Sharu Theresa Jose;Ankur A. Kulkarni
最近[1]表明，具有非经典信息模式的随机控制问题可以等效地施放为非凸优化问题，并且可以通过使用信息理论数据处理不平等来创建凸松弛度来获得下限。我们为这些问题提供了线性编程放松。这为获得下限并产生了最大的已知逆最佳成本功能类别提供了新的途径。线性编程松弛改善了基于信息理论的放松，因为它保留在其一组极端点，这是原始非凸问题的所有极端点。可以通过为放松双重构造可行的点来找到原始非概念问题最佳成本的下限。我们表明，对于最大程度地减少二元源对1和2块长度的二进制不记忆对称通道的预期失真的问题，我们的放松很紧。将数据处理不等式纳入线性编程松弛中，我们获得了最大的已知逆最佳成本函数类别。
It was shown recently [1] that stochastic control problems with non-classical information patterns can be cast equivalently as nonconvex optimization problems and that lower bounds could be obtained by using the information-theoretic data processing inequality for creating convex relaxations. We present a linear programming relaxation to these problems. This provides a new avenue for obtaining lower bounds and yields the largest known class of inverse optimal cost functions. The linear programming relaxation improves on information theory based relaxations since it retains in its set of extreme points, all the extreme points of the original nonconvex problem. Lower bounds on the optimal cost of the original nonconvex problem can be found by constructing feasible points for the dual of the relaxation. We show that our relaxation is tight for the problem of minimizing the expected distortion of a binary source over binary memoryless symmetric channel for block length of 1 and 2. This gives a new, direct and non-communication-theoretic proof of the optimal distortion. Incorporating the data processing inequality in the linear programming relaxation, we obtain the largest known class of inverse optimal cost functions.