python - scipy优化中的整数步长最小化

Question

我想使用 scipy.optimize.minimize 调整计算机视觉算法.现在我只想调整两个参数，但参数的数量最终可能会增加，所以我想使用一种可以进行高维梯度搜索的技术。 SciPy 中的 Nelder-Mead 实现似乎很合适。

我把代码都设置好了，但似乎最小化函数真的想使用步长小于 1 的浮点值。当前的参数集都是整数，一个参数的步长为 1另一个的步长为 2(即该值必须是奇数，如果不是我要优化的东西，会将其转换为奇数)。大致一个参数是以像素为单位的窗口大小，另一个参数是阈值(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。 - 您至少可以绘制这些并查看错误情况，而无需进行任何额外的评估)