计算科学 - 不等式约束分离的优化 - 吾爱随笔录 - 问答

不等式约束分离的优化

计算科学约束优化

2021-11-25 16:15:42

我想解决

min_{x} f (x) s.t. g_{i} (x) \geq 0 or h_{i} (x) \geq 0

$\min_x f(x)\qquad \textrm{s.t.}\qquad g_i(x) \geq 0\ \ \textrm{or}\ \ h_i(x) \geq 0$ 对于。

i = 1, \dots, m

$i=1,\ldots,m$

显然，如果不等式约束将可行集拆分为不相连的分量，则没有希望获得有效的数值解。但就我而言，我知道只有一个可行的连通分量（例如考虑一对约束，和）。 $2^m$ $g(x,y) = x$ $h(x,y) = y$

是否有一些技巧可以将这些约束转换为黑盒（非线性、非凸）优化软件支持的不等式约束的标准结合？替换约束，但由于的梯度不是连续的，我不太希望这个想法在实践中有效。 $k_i = \max(g_i,h_i)$ $k_i$

编辑：另一个想法（感谢与 Bernard Mourrain 的快速讨论）是引入松弛变量并求解现在只有约束的连接，尽管增加了约束和变量的数量。这种方法可行吗？ $y_i$

min_{x, y} f (x) s.t. [g_{i} (x) - y_{i}] [h_{i} (x) - y_{i}] = 0, y_{i} \geq 0

$\min_{x,y} f(x)\quad \textrm{s.t.}\quad [g_i(x)-y_i][h_i(x)-y_i]=0,\ y_i \geq 0$

1个回答

是否有一些技巧可以将这些约束转换为黑盒（非线性、非凸）优化软件支持的不等式约束的标准结合？

您可以为每个逻辑语句引入二进制变量。例如，你为每个并有使得，其中如果约束满足，如果约束很满意。产生的问题将是混合整数，因此您需要使用 MINLP 求解器。 $z_{i}$ $i = 1, \ldots, m$ $\min_{x, z}f(x)$ $g_{i}(x)z_{i} + h_{i}(x)(1-z_{i}) \geq 0$ $z_{i} = 1$ $g_{i}$ $z_{i} = 0$ $h_{i}$

例如，可以尝试用替换约束，但由于的梯度不连续，我不太希望这个想法在实践中有效。 $k_{i}=\max(g_{i},h_i)$ $k_i$

我同意。我不是非平滑方法的专家，但似乎有比非平滑优化求解器更多的 MILP 和 MINLP 求解器可用。如果您选择使用非平滑公式，Overton 有一些论文描述了 BFGS 方法在实践中如何表现得相当好，并且他为适当的步长提供了线搜索标准。然而，他和他的合著者解决的问题往往不超过 2000 个变量。对于非平滑问题，这个数字令人印象深刻，但我知道实际应用程序中存在更大的问题实例。

其它你可能感兴趣的问题

上一篇如何将 PDE 求解器中的误差与非均匀网格进行比较？下一篇Poisson-Boltzmann 求解器的表面电荷边界条件