如何在带有边界的python优化中找到全局最小值？

Question

我有一个包含64个变量的Python函数,我尝试在最小化函数中使用L-BFGS-B方法对其进行优化,但是这种方法非常依赖于初始猜测,并且未能找到全局最小值.

但我喜欢它为变量设置界限的能力.是否存在一种方法/函数来查找全局最小值,同时具有变量的边界？

Answer 1

这可以通过以下方式完成scipy.optimize.basinhopping.流域购物是一种旨在找到目标函数的全局最小值的函数.它使用函数重复最小化,scipy.optimize.minimize并在每次最小化后在坐标空间中进行随机步骤.通过使用实现边界的最小化器之一(例如L-BFGS-B),Basinhopping仍然可以尊重边界.以下是一些显示如何执行此操作的代码

# an example function with multiple minima
def f(x): return x.dot(x) + sin(np.linalg.norm(x) * np.pi)

# the starting point
x0 = [10., 10.]

# the bounds
xmin = [1., 1.]
xmax = [11., 11.]

# rewrite the bounds in the way required by L-BFGS-B
bounds = [(low, high) for low, high in zip(xmin, xmax)]

# use method L-BFGS-B because the problem is smooth and bounded
minimizer_kwargs = dict(method="L-BFGS-B", bounds=bounds)
res = basinhopping(f, x0, minimizer_kwargs=minimizer_kwargs)
print res

上面的代码适用于一个简单的情况,但是如果盆地随机位移例程将你带到那里,你仍然可以最终进入一个禁区.幸运的是,可以通过传递使用关键字的例程的自定义步骤来覆盖它take_step

class RandomDisplacementBounds(object):
    """random displacement with bounds"""
    def __init__(self, xmin, xmax, stepsize=0.5):
        self.xmin = xmin
        self.xmax = xmax
        self.stepsize = stepsize

    def __call__(self, x):
        """take a random step but ensure the new position is within the bounds"""
        while True:
            # this could be done in a much more clever way, but it will work for example purposes
            xnew = x + np.random.uniform(-self.stepsize, self.stepsize, np.shape(x))
            if np.all(xnew < self.xmax) and np.all(xnew > self.xmin):
                break
        return xnew

# define the new step taking routine and pass it to basinhopping
take_step = RandomDisplacementBounds(xmin, xmax)
result = basinhopping(f, x0, niter=100, minimizer_kwargs=minimizer_kwargs,
                      take_step=take_step)
print result

Answer 2

有关调试和可视化函数上任何优化程序的一些常识性建议：

您的目标功能和约束是否合理？
如果目标函数是一个总和发言权f() + g()，单独打印那些对所有的x在"fx-opt.nptxt"（下面）; 如果f()为总数的99％和g()1％，请进行调查。

限制：有多少成分x_i中xfinal都停留在边界， x_i <= lo_i还是>= hi_i？

您的职能在全球范围内有多坎?？
以几个随机起点运行，并保存结果以进行分析/绘制：

title = "%s  n %d  ntermhess %d  nsample %d  seed %d" % (  # all params!
    __file__, n, ntermhess, nsample, seed )
print title
...
np.random.seed(seed)  # for reproducible runs
np.set_printoptions( threshold=100, edgeitems=10, linewidth=100,
        formatter = dict( float = lambda x: "%.3g" % x ))  # float arrays %.3g

lo, hi = bounds.T  # vecs of numbers or +- np.inf
print "lo:", lo
print "hi:", hi

fx = []  # accumulate all the final f, x
for jsample in range(nsample):
        # x0 uniformly random in box lo .. hi --
    x0 = lo + np.random.uniform( size=n ) * (hi - lo)

    x, f, d = fmin_l_bfgs_b( func, x0, approx_grad=1,
                m=ntermhess, factr=factr, pgtol=pgtol )
    print "f: %g  x: %s  x0: %s" % (f, x, x0)
    fx.append( np.r_[ f, x ])

fx = np.array(fx)  # nsample rows, 1 + dim cols
np.savetxt( "fx-opt.nptxt", fx, fmt="%8.3g", header=title )  # to analyze / plot

ffinal = fx[:,0]
xfinal = fx[:,1:]
print "final f values, sorted:", np.sort(ffinal)
jbest = ffinal.argmin()
print "best x:", xfinal[jbest]

如果某些ffinal值看起来相当不错，请在这些值附近尝试更多随机起点-这肯定比纯随机更好。

如果xs是曲线或任何实数，则绘制最佳数x0和xfinal。
（经验法则是尺寸为nsample〜5 * d或10 * d d。太慢了，太多了？reduce maxiter/ maxeval，reduce- ftol您不需要ftol1e-6这样的探索。）

如果要获得可重复的结果，则必须在title 和派生文件和图中列出所有相关参数。否则，您会问“ 这是从哪里来的？”

您的功能在epsilon量级〜10 ^ -6上有多颠簸？
近似梯度的方法有时会返回其最后的估计值，但如果没有，则：

from scipy.optimize._numdiff import approx_derivative  # 3-point, much better than
## from scipy.optimize import approx_fprime
for eps in [1e-3, 1e-6]:
    grad = approx_fprime( x, func, epsilon=eps )
    print "approx_fprime eps %g: %s" % (eps, grad)

但是，如果在优化器退出之前梯度估计不佳/颠簸，您将不会看到。然后，您还必须保存所有中间体[f, x, approx_fprime] 才能观看它们。在python中很容易-询问是否不清楚。

在某些问题区域，通常从所谓的进行备份和重新启动xmin。例如，如果您迷失在一条乡村道路上，请先找到一条主要道路，然后从那里重新开始。

简介：
不要期望任何黑盒优化器都能在大型颠簸或epsilon颠簸或两者兼而有之的功能上工作。
投资测试脚手架，并以方式查看优化器的工作方式。