如何找到具有邊界的python優化的全局最小值？

Question

我有一個帶有64個變量的Python函數，我試圖在最小化函數中使用L-BFGS-B方法對其進行優化，但是這種方法對初始猜測具有相當強的依賴性，並且未能找到全局最小值。

但我喜歡它爲變量設置邊界的能力。有沒有一種方法/函數來找到全局最小值，同時有變量的邊界？

Answer 1

調試和你的函數可視化任何優化 一些常識性的建議：

是你的目標函數和約束條件的合理？
如果目標函數是f() + g(), 的總和，則單獨打印所有x的"fx-opt.nptxt"（以下）; 如果f()是99％的總和和g() 1％，調查。

約束：如何組件的許多xfinalx_i是停留在邊界， x_i <= lo_i或>= hi_i？

---

您在全球範圍內的功能有多坎坷？
運行幾個隨機startpoints，並將結果保存到分析/劇情：

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值看起來相當不錯， 儘量靠近那些更隨機startpoints - 這肯定比純隨機更好。

如果x s是曲線或任何真實的，則繪製最佳的幾個x0和xfinal。
（經驗法則是在NSample個維度d〜5 * d或10 * d 太慢，太多的減少maxiter/maxeval，減少ftol - ？ 你不需要ftol 1E-6類似的探索這個。）

如果你想得到可重現的結果， 那麼你必須列出title 和衍生文件和圖中的所有相關參數。 否則，你會問「這個從哪裏來？」

---

你的函數在epsilon scale〜10^-6上有多不平？
中的方法近似梯度有時會返回他們的最後估計， 但如果沒有：

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備份並重新啓動。 例如，如果你在鄉間小路上迷路，首先找到 ，然後從那裏重新開始。

---

將問題調用和版本信息也放在問題中，例如，

x, f, d = fmin_l_bfgs_b(func, x0, approx_grad=1, 
      m=ntermhess, factr=factr, pgtol=pgtol, epsilon=eps) 
      # give values for these -- explicit is better than implicit 
versions: numpy 1.8.0 scipy 0.13.2 python 2.7.6 mac 10.8.3 

---

摘要：
不要指望任何暗箱優化器上的功能這是 大規模的顛簸，或ε規模的顛簸，或兩者工作。
投資測試腳手架，並以 的方式參見優化器正在做什麼。

Answer 2

非常感謝您的詳細答覆，但作爲即時通訊相當新的蟒蛇，我不完全知道如何實現的代碼我的程序，但這裏是我在最優化的嘗試：

x0=np.array((10, 13, f*2.5, 0.08, 10, f*1.5, 0.06, 20, 
      10, 14, f*2.5, 0.08, 10, f*1.75, 0.07, 20, 
      10, 15, f*2.5, 0.08, 10, f*2, 0.08, 20, 
      10, 16, f*2.5, 0.08, 10, f*2.25, 0.09, 20, 
      10, 17, f*2.5, -0.08, 10, f*2.5, -0.06, 20, 
      10, 18, f*2.5, -0.08, 10, f*2.75,-0.07, 20, 
      10, 19, f*2.5, -0.08, 10, f*3, -0.08, 20, 
      10, 20, f*2.5, -0.08, 10, f*3.25,-0.09, 20)) 

# boundary for each variable, each element in this restricts the corresponding element  above 
bnds=((1,12), (1,35), (0,f*6.75), (-0.1, 0.1),(1,35), (0,f*6.75), (-0.1, 0.1),(13, 35), 
    (1,12), (1,35), (0,f*6.75), (-0.1, 0.1),(1,35), (0,f*6.75), (-0.1, 0.1),(13, 35), 
    (1,12), (1,35), (0,f*6.75), (-0.1, 0.1),(1,35), (0,f*6.75), (-0.1, 0.1),(13, 35), 
    (1,12), (1,35), (0,f*6.75), (-0.1, 0.1),(1,35), (0,f*6.75), (-0.1, 0.1),(13, 35), 
    (1,12), (1,35), (0,f*6.75), (-0.1, 0.1),(1,35), (0,f*6.75), (-0.1, 0.1),(13, 35), 
    (1,12), (1,35), (0,f*6.75), (-0.1, 0.1),(1,35), (0,f*6.75), (-0.1, 0.1),(13, 35), 
    (1,12), (1,35), (0,f*6.75), (-0.1, 0.1),(1,35), (0,f*6.75), (-0.1, 0.1),(13, 35), 
    (1,12), (1,35), (0,f*6.75), (-0.1, 0.1),(1,35), (0,f*6.75), (-0.1, 0.1),(13, 35),) 

from scipy.optimize import basinhopping 
from scipy.optimize import minimize 

merit=a*meritoflength + b*meritofROC + c*meritofproximity +d*(distancetoceiling+distancetofloor)+e*heightorder 
minimizer_kwargs = {"method": "L-BFGS-B", "bounds": bnds, "tol":1e0} 
ret = basinhopping(merit_function, x0, minimizer_kwargs=minimizer_kwargs, niter=10, T=0.01) 

zoom = ret['x'] 
res = minimize(merit_function, zoom, method = 'L-BFGS-B', bounds=bnds, tol=1e-5) 
print res 

的優點函數將x0與一些其他值組合，形成8條曲線的6個控制點，然後計算它們的長度，曲率半徑等。它將最終的優點返回爲具有某些權重的那些參數的線性組合。

我用basinhopping低精度找到一些最小值，然後用minimize來提高最低最低值的精度。

p.s.我運行的平臺是Enthoght canopy 1.3.0，numpy 1.8.0 scipy 0.13.2 mac 10.8.3

Answer 3

這可以用scipy.optimize.basinhopping完成。 Basinhopping是一項功能，旨在查找目標函數的最小值。它使用函數scipy.optimize.minimize重複最小化，並在每次最小化之後在座標空間中採取隨機步驟。通過使用其中一個實現邊界的極小值（例如L-BFGS-B），盆地購物仍然可以尊重邊界。下面是一些代碼，顯示瞭如何做到這一點

# 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 

上面的代碼將一個簡單的情況下工作，但你仍然可以結束了在禁止區域，如果basinhopping隨機位移日常需要你。幸運的是，可以通過將使用關鍵字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