使用scipy.optimize.minimize查找全局最小值

Question

给定2D点p,我试图计算该点与功能曲线之间的最小距离,即找到曲线上的点,该点给出最小距离p,然后计算该距离.我正在使用的示例函数是

f(x) = 2*sin(x)

我的距离函数用于某个点p和提供的函数之间的距离

def dist(p, x, func):
    x = np.append(x, func(x))
    return sum([[i - j]**2 for i,j in zip(x,p)])

它作为输入,点p,x函数上的位置和函数句柄func.注意这是一个平方欧几里德距离(因为欧几里德空间中的最小化与平方欧几里德空间中的最小化相同).

这个的关键部分是我希望能够为我的函数提供边界,所以我真的找到了与函数段最近的距离.对于这个例子,我的界限是

bounds = [0, 2*np.pi]

我正在使用该scipy.optimize.minimize函数来最小化我的距离函数,使用边界.上述过程的结果如下图所示.

这是显示距sin函数的距离的等高线图.请注意轮廓中是否存在不连续性.为方便起见,我在不连续点和它们映射到的曲线上的"壁橱"点上绘制了几个点.

这里实际发生的是scipy函数是找到局部最小值(给出一些初始猜测),但不是全局函数,这导致了不连续性.我知道找到任何函数的全局最小值是不可能的,但我正在寻找一种更可靠的方法来找到全局最小值.

找到全局最小值的可能方法是

1. 选择一个聪明的初始猜测,但这相当于知道全局最小值开始的大致位置,这是使用问题的解决方案来解决它.
2. 使用多个初始猜测并选择达到最佳最小值的答案.然而,这似乎是一个糟糕的选择,特别是当我的函数变得更复杂(和更高维度)时.
3. 找到最小值,然后扰乱解决方案并再次找到最小值,希望我可能已将它打到更好的最小值.我希望可能有一些方法可以做到这一点,而不需要引用一些复杂的MCMC算法或类似的东西.速度计入此过程.

有关最佳方法的任何建议,或可能解决这个问题的有用功能的方向都会很棒!

Answer 1

正如评论中建议的那样,您可以尝试全局优化算法,例如scipy.optimize.differential_evolution.但是,在这种情况下,如果您具有明确且易于分析的目标函数,则可以采用半分析方法,充分利用一阶必要条件.

在下文中,第一个函数是距离度量,第二个函数是其导数wrt(的分子)x,如果在某个函数中出现最小值,则该函数应为零0<x<2*np.pi.

import numpy as np    
def d(x, p):
    return np.sum((p-np.array([x,2*np.sin(x)]))**2)

def diff_d(x, p):
    return -2 * p[0] + 2 * x - 4 * p[1] * np.cos(x) + 4 * np.sin(2*x)

现在,给定一点p,唯一可能的最小化d(x,p)是diff_d(x,p)(如果有的话)的根,以及边界点x=0和x=2*np.pi.事实证明,diff_d可能有多个根.注意到导数是一个连续函数,pychebfun库提供了一种非常有效的方法来查找所有根,避免了基于scipy根查找算法的繁琐方法.

以下函数提供d(x, p)给定点的最小值p:

import pychebfun
def min_dist(p):
    f_cheb = pychebfun.Chebfun.from_function(lambda x: diff_d(x, p), domain = (0,2*np.pi))
    potential_minimizers = np.r_[0, f_cheb.roots(), 2*np.pi]
    return np.min([d(x, p) for x in potential_minimizers])

结果如下: