在scipy整數步長優化最小化

Question

我有一個計算機視覺算法，我想調整使用scipy.optimize.minimize。現在我只想調整兩個參數，但最終參數的數量可能會增加，所以我想使用可以進行高維梯度搜索的技術。 SciPy中的Nelder-Mead實現看起來很合適。

我得到了所有設置的代碼，但似乎最小化函數真的想要使用小於1的步長大小的浮點值。當前的一組參數都是整數，其中一個步長爲一個和另一個具有兩個步長（即，值必須是奇數，如果它不是我想優化的東西將它轉換爲奇數）。大致一個參數是以像素爲單位的窗口大小，另一個參數是閾值（0-255之間的值）。

爲什麼值得我使用git repo的scipy新版本。有誰知道如何告訴scipy爲每個參數使用特定的步長？有什麼方法可以滾動我自己的漸變功能嗎？有沒有可以幫助我的scipy旗幟？我知道這可以通過簡單的參數掃描來完成，但我最終希望將此代碼應用於更大的參數集。

代碼本身是死的簡單：

import numpy as np 
from scipy.optimize import minimize 
from ScannerUtil import straightenImg 
import bson 

def doSingleIteration(parameters): 
    # do some machine vision magic 
    # return the difference between my value and the truth value 

parameters = np.array([11,10]) 
res = minimize(doSingleIteration, parameters, method='Nelder-Mead',options={'xtol': 1e-2, 'disp': True,'ftol':1.0,}) #not sure if these params do anything 
print "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~" 
print res 

這是我的輸出樣子。正如你所看到的，我們正在重複很多次運行，並沒有在最小化的任何地方。

*+++++++++++++++++++++++++++++++++++++++++ 
[ 11. 10.] <-- Output from scipy minimize 
{'block_size': 11, 'degree': 10} <-- input to my algorithm rounded and made int 
+++++++++++++++++++++++++++++++++++++++++ 
120 <-- output of the function I am trying to minimize 
+++++++++++++++++++++++++++++++++++++++++ 
[ 11.55 10. ] 
{'block_size': 11, 'degree': 10} 
+++++++++++++++++++++++++++++++++++++++++ 
120 
+++++++++++++++++++++++++++++++++++++++++ 
[ 11. 10.5] 
{'block_size': 11, 'degree': 10} 
+++++++++++++++++++++++++++++++++++++++++ 
120 
+++++++++++++++++++++++++++++++++++++++++ 
[ 11.55 9.5 ] 
{'block_size': 11, 'degree': 9} 
+++++++++++++++++++++++++++++++++++++++++ 
120 
+++++++++++++++++++++++++++++++++++++++++ 
[ 11.1375 10.25 ] 
{'block_size': 11, 'degree': 10} 
+++++++++++++++++++++++++++++++++++++++++ 
120 
+++++++++++++++++++++++++++++++++++++++++ 
[ 11.275 10. ] 
{'block_size': 11, 'degree': 10} 
+++++++++++++++++++++++++++++++++++++++++ 
120 
+++++++++++++++++++++++++++++++++++++++++ 
[ 11. 10.25] 
{'block_size': 11, 'degree': 10} 
+++++++++++++++++++++++++++++++++++++++++ 
120 
+++++++++++++++++++++++++++++++++++++++++ 
[ 11.275 9.75 ] 
{'block_size': 11, 'degree': 9} 
+++++++++++++++++++++++++++++++++++++++++ 
120 
+++++++++++++++++++++++++++++++++++++++++ 
~~~ 
SNIP 
~~~ 
+++++++++++++++++++++++++++++++++++++++++ 
[ 11.   10.0078125] 
{'block_size': 11, 'degree': 10} 
+++++++++++++++++++++++++++++++++++++++++ 
120 
Optimization terminated successfully. 
     Current function value: 120.000000 
     Iterations: 7 
     Function evaluations: 27 
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 
    status: 0 
    nfev: 27 
success: True 
    fun: 120.0 
     x: array([ 11., 10.]) 
message: 'Optimization terminated successfully.' 
    nit: 7* 

Answer 1

假設最小化函數是任意複雜的（非線性），這是一般非常困難的問題。除非您嘗試所有可能的選擇，否則無法保證最佳解決方案。我做而不是知道是否有任何整數約束非線性優化器（有點懷疑它），我會假設你知道，如果Nelder-Mead是一個連續函數，它應該可以正常工作。

編輯：考慮來自@Dougal的評論我會在這裏添加一下：首先設置一個粗糙+細網格搜索，如果你覺得想嘗試如果你的Nelder-Mead工作（並收斂得更快），下面的點可能會幫助...

但也許一些點，有助於：

1. 考慮到整個整數約束如何是非常困難的，也許這將是做一些簡單的插值來幫助優化的選項。它應該仍然收斂到一個整數解決方案。當然這需要計算額外的點數，但它可能解決許多其他問題。 （即使在線性整數編程中它​​的共同點解決無約束系統第一個AFAIK）
2. Nelder-Mead以N + 1個點開始，它們在scipy（至少較老的版本）中以硬連線到(1+0.05) * x0[j]（對於所有維度的j，除非x0[j]爲0），您將在第一個評估步驟中看到它。也許這些可以以更新的版本提供，否則你可以改變/複製scipy代碼（它是純Python）並將其設置爲更合理的。或者，如果你覺得這樣更簡單，則縮小所有輸入變量，以便（1 + 0.05）* x0具有合理的大小。
3. 也許你應該緩存所有的函數評估，因爲如果你使用Nelder-Mead，我猜你總是可以進行重複評估（至少在最後）。
4. 你必須檢查Nelder-Mead可能會縮小到單個值並放棄的可能性，因爲它總是找到相同的結果。
5. 您通常必須檢查您的函數是否表現良好......如果函數在參數空間中不平滑，即使如此，如果您應該擁有這些優化函數。 （因爲你緩存所有的評價 - 看2 - 你至少那些情節和看看錯誤的風景，而無需做任何額外的evluations）

Answer 2

捕捉你的花車X，Y（又名使用winsize，門檻）爲整數電網內你的功能，如：

def func(x, y): 
    x = round(x) 
    y = round((y - 1)/2) * 2 + 1 # 1 3 5 ... 
    ... 

然後內爾德 - 米德只能看到對電網的函數值，並且應該給你接近整數X，Y。

（如果你關心發佈您的代碼的某個地方，我在尋找測試用例的內爾德 - 米德 與重啓。）

Answer 3

不幸的是，SciPy的內置的優化工具不能輕易讓爲了這。但不要害怕;這聽起來像你有一個凸起的問題，所以你應該能夠找到一個獨特的最佳，即使它不會在數學上漂亮。

我針對不同問題實施的兩個選項是創建自定義漸變下降算法，並在一系列單變量問題上使用二分法。如果您在調整過程中進行交叉驗證，則不幸的是，您的損失函數不會平滑（因爲來自不同數據集上的交叉驗證的噪音），但通常是凸的。

要實現數值梯度下降（沒有用於評估梯度的分析方法），請選擇一個測試點，並在所有維度中遠離測試點的第二個點爲delta。在這兩點評估你的損失函數可以讓你用數字計算一個局部子梯度。 delta必須足夠大，以至於它跨越由交叉驗證噪聲創建的局部最小值。

速度較慢但潛在更強大的替代方法是對您正在測試的每個參數實施二等分。如果知道在兩個參數中共同出現問題（或參數參數），則可以將此分解爲單變量優化問題，並編寫遞歸地插入最優參數的二分算法。這可以幫助處理某些類型的擬凸（例如，如果您的損失函數對其部分域採用背景噪聲值，並且在另一個區域中爲凸），但需要對初始迭代的邊界進行很好的猜測。

如果單純管理單元所請求的x值的整數網格無固定​​xtol映射到該gridsize，你的風險具有解算器請求的網格單元內的兩個點，在接收到相同的輸出值，並且得出的結論是它是在最低限度。

不幸的是，沒有簡單的答案。

Answer 4

Nelder-Mead最小化方法現在允許您指定初始單純形頂點，因此您應該能夠將單純形點設置得相距甚遠，然後單純形將隨後翻轉並找到最小值並收斂，低於1.

https://docs.scipy.org/doc/scipy/reference/optimize.minimize-neldermead.html#optimize-minimize-neldermead