使用 scipy.optimize.minimize 查找全局最小值
Find global minimum using scipy.optimize.minimize
给定一个二维点 p
,我正在尝试计算该点与函数曲线之间的最小距离,即找到曲线上与 [=14 的距离最小的点=],然后计算那个距离。我使用的示例函数是
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
作为输入。请注意,这是一个平方欧几里德距离(因为欧几里德 space 中的最小化与欧几里德平方 space 中的最小化相同)。
其中的关键部分是我希望能够为我的函数提供边界,所以我实际上是在寻找到函数段的最近距离。对于这个例子,我的界限是
bounds = [0, 2*np.pi]
我正在使用 scipy.optimize.minimize
函数来最小化我的距离函数,使用边界。上述过程的结果如下图所示。
这是一个等高线图,显示了与 sin 函数的距离。请注意轮廓中似乎存在不连续性。为方便起见,我在该不连续点周围绘制了几个点以及它们映射到的曲线上的 [=50=] 点。
这里实际发生的是 scipy 函数正在寻找局部最小值(给定一些初始猜测),但不是全局最小值,这导致了不连续性。我知道找到任何函数的全局最小值是不可能的,但我正在寻找一种更可靠的方法来找到全局最小值。
寻找全局最小值的可能方法是
- 选择一个聪明的初始猜测,但这相当于大致知道全局最小值从哪里开始,这就是使用问题的解决方案来解决它。
- 使用多个初始猜测并选择达到最佳最小值的答案。然而,这似乎是一个糟糕的选择,尤其是当我的函数变得更复杂(和更高维度)时。
- 找到最小值,然后扰动解并再次找到最小值,希望我可能已经把它敲到了更好的最小值。我希望也许有一些方法可以简单地做到这一点,而无需调用一些复杂的 MCMC 算法或类似的算法。此过程的速度很重要。
任何有关解决此问题的最佳方法的建议,或者可能解决此问题的有用功能的可能指导都很棒!
正如评论中所建议的,您可以尝试全局优化算法,例如 scipy.optimize.differential_evolution
。但是,在这种情况下,如果您有一个定义明确且分析上易于处理的 objective 函数,您可以采用半分析方法,最大限度地利用一阶必要条件。
在下文中,第一个函数是距离度量,第二个函数是其导数(的分子)w.r.t。 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
根查找算法的繁琐方法。
以下函数为给定点 p
提供 d(x, 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])
结果如下:
给定一个二维点 p
,我正在尝试计算该点与函数曲线之间的最小距离,即找到曲线上与 [=14 的距离最小的点=],然后计算那个距离。我使用的示例函数是
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
作为输入。请注意,这是一个平方欧几里德距离(因为欧几里德 space 中的最小化与欧几里德平方 space 中的最小化相同)。
其中的关键部分是我希望能够为我的函数提供边界,所以我实际上是在寻找到函数段的最近距离。对于这个例子,我的界限是
bounds = [0, 2*np.pi]
我正在使用 scipy.optimize.minimize
函数来最小化我的距离函数,使用边界。上述过程的结果如下图所示。
这是一个等高线图,显示了与 sin 函数的距离。请注意轮廓中似乎存在不连续性。为方便起见,我在该不连续点周围绘制了几个点以及它们映射到的曲线上的 [=50=] 点。
这里实际发生的是 scipy 函数正在寻找局部最小值(给定一些初始猜测),但不是全局最小值,这导致了不连续性。我知道找到任何函数的全局最小值是不可能的,但我正在寻找一种更可靠的方法来找到全局最小值。
寻找全局最小值的可能方法是
- 选择一个聪明的初始猜测,但这相当于大致知道全局最小值从哪里开始,这就是使用问题的解决方案来解决它。
- 使用多个初始猜测并选择达到最佳最小值的答案。然而,这似乎是一个糟糕的选择,尤其是当我的函数变得更复杂(和更高维度)时。
- 找到最小值,然后扰动解并再次找到最小值,希望我可能已经把它敲到了更好的最小值。我希望也许有一些方法可以简单地做到这一点,而无需调用一些复杂的 MCMC 算法或类似的算法。此过程的速度很重要。
任何有关解决此问题的最佳方法的建议,或者可能解决此问题的有用功能的可能指导都很棒!
正如评论中所建议的,您可以尝试全局优化算法,例如 scipy.optimize.differential_evolution
。但是,在这种情况下,如果您有一个定义明确且分析上易于处理的 objective 函数,您可以采用半分析方法,最大限度地利用一阶必要条件。
在下文中,第一个函数是距离度量,第二个函数是其导数(的分子)w.r.t。 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
根查找算法的繁琐方法。
以下函数为给定点 p
提供 d(x, 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])
结果如下: