A Linear Programming Approach to Sequential Hypothesis Testing
A Linear Programming Approach to Sequential Hypothesis Testing
复制标题
顺序假设检验的线性规划方法
DOI：
10.1080/07474946.2015.1030981
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
A. Zoubir
中科院分区：
文献类型：
--
作者：
Michael Fauss;A. Zoubir
在一些温和的马尔可夫假设下，证明了两个简单假设的最优序列检验设计问题可以表述为一个线性规划。该结果是通过研究序列测试问题的拉格朗日对偶得到的，该问题是一个依赖于两个未知拉格朗日乘子的无约束最优停止问题。结果表明，最优代价函数对这些乘子的导数与相应序列检验的误差概率一致。利用这一性质，提出了一个成本函数和拉格朗日乘子共同线性的优化问题，并且可以用现成的算法对两者进行求解。为了说明该过程，推导了具有不同依赖结构的高斯随机序列的最优顺序测试，包括高斯AR(1)过程。
Abstract Under some mild Markov assumptions it is shown that the problem of designing optimal sequential tests for two simple hypotheses can be formulated as a linear program. This result is derived by investigating the Lagrangian dual of the sequential testing problem, which is an unconstrained optimal stopping problem depending on two unknown Lagrangian multipliers. It is shown that the derivative of the optimal cost function, with respect to these multipliers, coincides with the error probabilities of the corresponding sequential test. This property is used to formulate an optimization problem that is jointly linear in the cost function and the Lagrangian multipliers and can be solved for both with off-the-shelf algorithms. To illustrate the procedure, optimal sequential tests for Gaussian random sequences with different dependency structures are derived, including the Gaussian AR(1) process.