有什么算法可以找到函数的局部/全局极小值的代表性样本？

Question

我在做一个多目标优化项目，我偶然发现了一种算法的必要性，这种算法把一个函数作为一个输入，它可以存储任意有限的次数（受计算能力的限制），可以返回一个均匀分布的采样值，这个采样值是函数的局部或全局极小值。你知道吗

如果您没有最喜欢的语言，我更喜欢Python，并将任何建议移植到Python中供我自己使用。否则，任何带或不带代码的答案都是可以接受的。你知道吗

这类似于许多更容易回答的问题，因此我有一些更明确的细节：

1。示例用法/API

我们将定义一个具有已知局部极小值的函数来生成一个简单的测试用例。你知道吗

import numpy as np

def f(x: np.ndarray):
    """If x has shape (2,) returns distance from line y=x"""
    return np.abs(np.diff(x))

def minima_sample(f, bounds, sample_size):
    """TODO"""

当我们试图在单位方格中找到3个均匀分布、覆盖良好的点时，这些点位于f（可以被视为一个oracle）的局部（或全局…对我的应用程序来说并不重要）最小值，最好的方法是返回线段的两个端点，这两个端点代表所有的极小值，以及直接位于两者之间的点。同样得4分。你知道吗

>>> print(minima_sample(f, [(0,1), (0,1)], 3))
array([[0. , 0. ],
       [0.5, 0.5],
       [1. , 1. ]])

>>> print(minima_sample(f, [(0,1), (0,1)], 4))
array([[0.        , 0.        ],
       [0.33333333, 0.33333333],
       [0.66666667, 0.66666667],
       [1.        , 1.        ]])

2。非答案

有两类算法与此问题密切相关：

2.1局部解算器

例子包括梯度下降法，各种各样的拟牛顿法，基于blob的不可微搜索算子等等。有趣的是，它们实际上可以相对容易地用来回答这个问题。只需在随机起始点运行局部解算器，直到解的边界大小大致不增加，然后继续运行，直到有足够的点均匀分布在该边界中。把精力集中在空旷的地方，以提高效率。你知道吗

从技术上讲，这些方法可以用来建立一个答案，但这是一个相当低效的策略。您至少需要与所请求的点一样多的局部最小化步骤（如果函数表现不好，则需要更多），并且在局部最小化之间丢弃所有信息，这样您就不能使用一个最小值的位置来指导另一个最小值的查找。也许这实际上是最佳的，但我怀疑有更好的东西存在。你知道吗

2.2全局解算器

例如碱化法、模拟退火法等。从表面上看，他们似乎是正确的方法，因为他们检查了大量的局部极小值，并最终解决了其中最小的。我们可以简单地返回得到的局部极小值的一个合适的子集。然而，通过设计，他们选择局部极小值的方式很可能是走向全局极小值。根据定义，这试图偏向搜索和样本的局部极小不均匀。你知道吗

三。附加信息

出于个人好奇心，我对你认为可能适用的任何算法都感兴趣。作为一个实际问题，一个优化例程的效率很大程度上取决于它对特定问题的定制程度。我想到的特定函数有很多约束和特殊属性，它们可能会产生不同：

1. 忽略数值误差，我要优化的函数具有这样的性质：所有局部极小实际上都是全局极小。你知道吗
2. 除了一些病理输入，我要优化的函数还有一个附加属性，即全局最小值为0。你知道吗
3. 该函数可以假定为n个变量的无穷可微标量函数（如果需要特定的编程语言，则表示为平面numpy数组）。你知道吗
4. 求函数的雅可比矩阵及其Hessian与任何向量的乘积都可以在O（n^2）时间内完成。你知道吗
5. 计算雅可比矩阵需要大约3倍于单个函数计算的时间。你知道吗
6. 评估Hessian向量积需要大约2倍的时间来进行一次Jacobian评估评估
7. 计算高阶微分形式的代价高得令人望而却步（目前…我认为，如果我再努力一点/再努力一点，自动微分就可以解决这个问题）。你知道吗
8. 除病理情况外，极小值位于低维流形的并集上。这是我期待的事情非常重要，因为它提供了相当多的信息，在哪里寻找新的极小给定位置的旧极小。你知道吗
9. 函数在选定的有界域上是有界的，但该界不一定提前知道。你知道吗
10. 对于10000+输入的较大问题，一些中间计算往往会增加数值不稳定性。在这些情况下，我提到的任何数量（函数、雅可比、黑森）都不能超过5或6位小数，因此理想情况下，任何解决方案都不需要更高的精度。你知道吗
11. 预期应用有数万个输入，需要50-2000个点的采样覆盖局部极小值。你知道吗
12. 计算的一个副作用是，对于每个函数求值，我们在降维空间中得到它的一个有用表示。这可能无关紧要，但对于计算（如接近度）使用低维（2-10D）表示可能有用，而不是10000+维输入。你知道吗
13. 在重要的情况下，我们所期望的最小值的函数是我们正在优化的相同n维输入的特定m维函数的雅可比矩阵的潜在非零奇异值中的最小值。上面提到的缩减空间是m维函数的输出。你知道吗

第四条。当前的尝试和想法

• 我目前已经实现了2.1中提到的随机重启方法。从技术上讲，它是可行的，但它比我想要的慢。从算法的角度来看，它也不优雅，也不令人满意。

• 随机重启动方法采样不均匀，但通过修改起始位置，尝试推导出现有解的边界，并填充这些解中的空洞（使用缩减空间进行邻近计算），可以得到合理的覆盖。计算雅可比数和黑森数，对于简单问题，每个样本点使用~5个函数求值；对于复杂问题，每个样本点使用~80个函数求值。我们的目标是利用我们目前丢弃的一些额外信息，将80%的信息减少到更易于管理的程度。我希望最大的加速比是16倍（或者在硬币的另一面是处理更大问题的能力）。

• 我的一个想法是找到一个单一的局部极小值，然后“跟随”流形，它恰好是通过方向导数为0的方向移动（因为局部极小值和全局极小值都是0）。这对于1D流形来说是很容易实现的，但是我还没有找到一个令人满意的方法来处理更复杂的搜索空间而不需要加倍。

• 我突然想到，进化算法的人口与牛顿为基础的局部搜索组件的个人可能是有效的。进化算法与随机搜索的关系以及对参数的极端敏感性让我很警惕。

五。最后

有没有一个标准的方法来解决这样的问题？如果没有，是否有一个短/长的适用算法列表，我可以权衡其优缺点？我的Google foo出现了问题，我最初的预感并没有产生好的结果。在处理这个问题时，我还有什么需要考虑的吗？即使是书籍/参考资料/博客/播客推荐也总比什么都没有好。你知道吗

事先谢谢你的努力。你知道吗