计算科学 - 向优化问题添加额外变量的缺点 - 吾爱随笔录

计算科学优化数值分析

2021-11-27 03:14:40

假设我们有一个优化问题

x = (x_{1}, x_{2}, \dots, x_{m}) = \arg min_{x \in R^{m}} f (x)

$\mathbf{x} = (x_1, x_2, \ldots, x_m) = \arg\!\min_{\mathbf{x}\in \mathbb{R}^m}f(\mathbf{x})$ 第二个相关问题：因为我们有关系和和。

y = (y_{1}, y_{2}, \dots, y_{n}) = \arg min_{y \in R^{n}} g (y)

$\mathbf{y} = (y_1, y_2, \ldots, y_n) = \arg\!\min_{\mathbf{y}\in \mathbb{R}^n}g(\mathbf{y})$

x = t (y)

$\mathbf{x} = \mathbf{t}(\mathbf{y})$

f (t (y)) = g (y)

$f(\mathbf{t}(\mathbf{y})) = g(\mathbf{y})$

n > m

$n>m$

我的问题是：如果使用数值优化器，解决第二个问题而不是第一个问题有什么缺点？

举个例子：以一个函数为例，它只依赖于和。所以最小化等价于最小化 $g(\mathbf{y})$

x_{1} = y_{1} + y_{2}

$x_1 = y_1 + y_2$

x_{2} = y_{1} + y_{3}

$x_2 = y_1+y_3$

x_{3} = y_{1} + y_{4}

$x_3 = y_1 + y_4$

x_{4} = y_{1} + y_{5}

$x_4 =y_1+y_5$

g (y)

$g(\mathbf{y})$

f (x) = g (0, x_{1}, x_{2}, x_{3}, x_{4})

$f(\mathbf{x}) = g(0,x_1,x_2,x_3,x_4)$

解决更大的问题对优化问题有害吗？数值优化器是否有可能在解决更大的问题时遇到更多麻烦，即使它提供的所有额外解决方案中的哪一个都没有关系？

编辑：我使用 Nelder-Mead 算法。

更新：在某些情况下，优化器指示退化 Nelder mead simplex的问题。问题的根源是否在额外变量中？

2个回答

一般而言，将单个变量添加到连续优化问题不会显着降低算法性能。这类操作经常发生，将明显“困难”的问题转化为“简单的”；例如，通过添加变量和约束来平滑地重新制定最大函数或绝对值。其他类型的操作会增加稀疏性，或者可以使用更有效的算法，在这些情况下，与解决问题的原始公式相比，重新公式会减少执行时间。

使用全局优化算法时，NP-hard 问题的类别除外，例如混合整数（线性或非线性）程序。这些算法的最坏情况缩放是指数级的，因此您可以看到，例如，在二进制变量的混合整数问题中，添加二进制变量时执行时间加倍。但是，在使用二进制混合整数线性程序的重新公式化时，我没有看到由于添加变量而导致求解时间急剧增加。

在黑盒算法的情况下，如果添加一个或两个变量会大大增加执行时间，我不会感到惊讶。退化的 Nelder-Mead 单纯形迭代的问题可能是您通过添加变量重新制定的结果。

根据您的问题，添加更多变量可以使问题非常容易解决。一切都取决于您的问题的结构。

例如，LP 问题是使用约束矩阵的 LU 分解来解决的。如果分解容易，问题就会很快解决。

总和的例子。您可能会遇到一个问题，即您直接得到对角线下只有 1 的总和。如果将具有值和总和的问题的大小加倍，那么假设您递归地计算总和，那么您只有 2 个单位矩阵一个挨着另一个。

这个问题可以在 ao(N) 中解决，其中第一个问题将在 o(N³) 中。

然后，在这种情况下，虽然大小是稀疏矩阵的两倍，但会大大减少求解的总时间。

其它你可能感兴趣的问题