不可微的全局优化问题

计算科学 优化
2021-12-02 18:31:17

我正在尝试以不同的变体解决社区中众所周知的以下测试问题：

在 3-dim 中放置 N = 15 个点。单位立方体，使得它们之间的最小距离最大，例如在排斥但受限电子的情况下。以下是要优化的函数的类似 Matlab 的非矢量化/矢量化形式（我们假设 n = 3*N）：

---- 非矢量化 -------------------------------------------------------- ------

function d = balls(x)
  d = 2.0;
  for i = 1:14
    for j = (i+1):15
      s = (x(i)-x(j))^2 + (x(i+15)-x(j+15))^2 + (x(i+30)-x(j+30))^2;
      s = sqrt(s);
      if s < d, d = s; end
    end
  end
  d = -d;
end

---- 向量化 --------------------------------------------- --------

function d = balls(x)
X = reshape(x, [], 3);
d = -min(pdist(X));
end

函数是连续的，但不是平滑的；基于梯度的方法将不起作用。多起点和随机方法也有问题，因为 45 维的搜索空间已经相当大了。边界也是一个问题，例如与将电子放置在没有边界的球体上的问题相比。

它将有许多局部最小值，例如置换球指数或互换尺寸。我猜所有这些局部最小值都具有相同的函数值，例如始终以相似配置结束的能级（这是真的吗？）。我只对这个最小值感兴趣，因此准确可靠地计算一个局部最小值就足够了。

通过多次重新启动应用 Matlab 的 fmincon()，我知道最小值将低于 -0.62 ......我仍然想更准确地计算这个值，并且只使用开源软件！请不要提示强大的商业求解器。

2个回答

顺利重新制定

正如 Sid 指出的那样，没有必要将这个问题视为不顺利，因为你只会让自己变得更难。

让我们假设为了记号x1,…,x15∈[0,1]3⊂R3是单位立方体中 15 个粒子的坐标。正如 Sid 所建议的，以标准形式（用于非线性规划）呈现的平滑公式将是：

minx1,…,x15∈[0,1]3−Es.t.E−‖xi−xj‖2≤0,i,j=1,…,15,i≠j

在哪里E是最小距离的代表，我假设它与最小化某种能量有关。可能有一种方法可以将这个问题重新表述为等效的凸问题，但我认为没有。

这个公式可能不是凸的，因为非线性约束的左侧不是凸的，所以你需要使用非凸非线性规划求解器来确保全局最优解（除非你可以证明凸可行集，但我对此表示怀疑）。适用于非凸问题的确定性全局求解器包括（但不限于）：

  • BARON （这是商业的，但您可以通过威斯康星大学麦迪逊分校运行的NEOS 优化服务器免费提交作业）
  • LINDOGlobal（也可商用，也可通过 NEOS 优化服务器获得）
  • Couenne（开源，COIN-OR开源求解器套件的一部分）
  • Bonmin（也是 COIN-OR 的一部分）
  • LaGO（再次，COIN-OR 的一部分）
  • icos（可作为开源或通过 NEOS 获得）

重要的是要注意，一个解决者可能会解决您的问题，而其他解决者则不会。BARON 通常被认为是最好的，但它很容易出错，并且在某些情况下，例如，Couenne 会解决（epsilon）全局最优性问题，但 BARON 不会（反之亦然）。

解决非光滑问题

让我们假设您（如 Hans）想要解决一个非光滑的非线性规划问题。这类问题不是我的专业领域，但我知道一些参考资料。

该领域最著名的人（据我所知，他早期开发了该理论中最重要的部分）是弗兰克·H·克拉克。非平滑优化的要点似乎是：用克拉克的广义梯度替换梯度。使用克拉克的广义梯度，您应该能够制定牛顿方法的非平滑模拟，以及优化算法。他的理论教科书（Frank H. Clarke的优化和非平滑分析；链接到亚马逊）被认为是经典之作。

在软件方面，我能找到的最佳链接是Napsu Karmitsa 的主页；她开发了几个非平滑优化求解器，并链接到其他非平滑优化求解器。我最常听到的方法称为捆绑方法，应该是确定性的。（我更喜欢确定性方法而不是随机方法。）更多非平滑代码的链接可以在这里找到；您的里程可能会有所不同，因为就像我说的，我不使用这些方法。

我确实知道，仅仅因为一种方法是为非光滑问题开发的，并不意味着它适用于非光滑、非凸问题，所以你需要确保你选择的求解器可以同时处理非光滑和非凸问题。非凸性。

最后，正如汉斯在评论中指出的那样，科学和工程中经常出现非光滑公式。然而，作为优化领域的人，我的第一直觉是尝试找到一个等效的平滑重构，因为解决平滑问题的方法通常比解决非平滑方法的方法快得多（实验室成员使用非平滑求解器，并且已经这个观察）。如果您可以将问题重新表述为平滑优化问题，那么您通常应该这样做。

您可能希望在我的网页 http://www.mat.univie.ac.at/~neum/glopt/software_l.html#nonsm上尝试 使用多个起点来全球化搜索的（本地）非平滑求解器之一。

我发现 CMA-ES 在高达 50 的维度上非常强大。（尽管当维度很大时它会变得非常慢。）

其它你可能感兴趣的问题
上一篇数值计算第二类斯特林数的有效方法？ 下一篇选择可扩展线性求解器时应遵循哪些准则？