计算科学 - 使对数约束的差异凸出 - 吾爱随笔录

使对数约束的差异凸出

计算科学凸优化约束优化约束

2021-12-17 21:03:54

我有离散似然估计问题 $\max \sum m_i\log p_i$ 其中 $m$ 是长度为 $n$ 的给定向量。约束是 $0 \preceq p \preceq 1$ ， $\sum_{i=1}^n p_i = 1,$ 以及一个非凸的最终约束：

\log p_{i} \geq \frac{1}{2} (\log p_{i - 1} + \log p_{i + 1}); i = 2, \dots, n - 1.

$\log p_i \geq \frac{1}{2}(\log p_{i-1} + \log p_{i+1}); \quad i = 2, \dots, n-1.$

此约束确保概率分布是对数凹的。

我试图使这个约束成为我可以放入凸程序的东西。我尝试了一些基本的替换和组合术语，但这并没有证明是富有成效的。

例如，如果我写，那么我不知道如何根据重写目标. $x_i = \frac{p_i^2}{p_{i-1}p_{i+1}}$ $x_i$

2个回答

约束不是凸的。考虑下面的示例，其中 x1 和 x2 分别是满足所讨论不等式的 3 个元素的向量，如图所示。0.5(x1 + x2) 不满足不等式，从而证明它不是凸的。

>> x1 = [0.868417827606570   0.121582145814843 0.010000025679806];
>> x2 = [0.017508300926335 0.264007818119070 0.718483881445100];
>> x3 = 0.5*(x1 + x2)
x3 =
   0.442963064266453   0.192794981966956   0.364241953562453
>> log(x1(2)) - 0.5*(log(x1(1)) + log(x1(3)))
ans =
   0.265959817560572
>> log(x2(2)) - 0.5*(log(x2(1)) + log(x2(3)))
ans =
   0.856069527413664
>> log(x3(2)) - 0.5*(log(x3(1)) + log(x3(3)))
ans =
  -0.734025017605155

为了使用凸编程方法，您可以执行诸如凸函数编程的差异之类的操作。这将需要对非凸约束中的右侧项的当前（或初始）值进行一阶（线性）扩展。您只能使用一阶展开，因为相对于具有整体凸约束，二次项会朝着错误的方向发展。您将需要使用初始值（扩展点）开始迭代。然后用刚刚求解的凸程序的最优值更新每个后续迭代的扩展点。无法保证收敛到任何东西，更不用说局部或全局最优了。

或者，您可以将其放入全局优化器中，例如 BARON，可能使用 p 的稍微正的下限，以避免在 0 时遇到困难。

让（即之外，一切都变为线性约束，你可以放松到因为它在最优时会很紧（假设为正）。 $z_i = \log p_i$ $p_i = e^{z_i}$ $\sum e^{z_i} = 1$ $\sum e^{z_i} \leq 1$ $m_i$

其它你可能感兴趣的问题

上一篇在捕获粒子的晶格上执行随机游走下一篇积分非线性常微分方程