机器算法验证 - 使用 MCMC 进行随机规划 - 吾爱随笔录

虽然解决确定性 LP 问题（例如内点算法）有很多更好的方法，但MCMC可以用来解决它们的随机变体吗？

所谓随机，我的意思是，例如，系数和/或约束的分布，并获得解决方案的后验概率，表示：

考虑到系数/约束的不确定性，解决方案的不确定性
考虑到 MCMC 为您提供估计，解决方案的不确定性

例如：

\begin{array}{rrl} x^{*} = \underset{x}{arg min} & E (c_{1} x_{1} - 3 x_{2}) \\ s.t. & - x_{1} + x_{2} & \leq b_{1} \\ x_{1}, x_{2} & \geq 0 \end{array}

$\begin{equation*} \begin{array}{rrl} \mathbf{x}^* = \underset{\mathbf{x}}{\text{arg}\;\text{min}} & \mathbb{E}\,(c_1x_1 -3x_2)\\ \mbox{s.t.} & -x_1 +x_2 & \le b_1 \\ & x_1, x_2 & \geq 0 \end{array} \end{equation*}$

以及在哪里：

$c_1 \sim N(2,0.5)$
$b_1 \sim N(0,3)$

我倾向于相信我们可以使用 MRF 势来表示约束和目标函数，但不确定如何制定有助于近似方程的解决方案的采样问题。以上。

c1 = pm.Normal('c1', mu=2, tau=.5**-2) c2 = -3 b1 = pm.Normal('b1', mu=0, tau=3.**-2) @pm.deterministic def x(c1=c1, c2=c2, b1=b1): # use an LP solver here for a complex problem arg_min = np.empty(2) min_val = np.inf for x1,x2 in [[0,0], [0, b1], [-b1, 0]]: # there are only three possible extreme points, if -x1 + x2 <= b1 and x1 >= 0 and x2 >= 0: # so check obj value at each valid one val = c1*x1 + c2*x2 if val < min_val: min_val = val arg_min = [x1,x2] return np.array(arg_min, dtype=float)