scipy.optimize.minimize(SLSQP)太慢，当给定2000个维变量时

Question

我有一个有约束和上下界的非透镜优化问题，所以对于scipy，我必须使用SLSQP。这个问题显然不是凸的。 我得到了目标函数和约束函数的jacobian函数，使其能够正确工作（结果良好/快速，最多300个输入向量）。所有函数都被矢量化并调整为运行速度非常快。问题是，使用1000+的输入向量需要很长时间，尽管我可以看到最小化程序并没有经常调用我的函数（目标/约束/渐变），而且似乎大部分的处理时间都是在内部进行的。我在某处读到SLSQP的perf是O（n^3）。在

对于python这类问题，是否有更好/更快的SLSQP实现或其他方法？我尝试了nlopt，但由于与scipy中使用的函数完全相同（使用了一个包装器来适应它的方法签名），所以返回了错误的结果。我也未能将ipopt与pyipopt包一起使用，无法获取正在工作的ipopt二进制文件来使用python包装器。在

更新：如果有帮助的话，我的输入变量基本上是（x，y）元组的向量或二维曲面中表示坐标的点。有了1000个点，我得到了一个2000维的输入向量。我要优化的函数考虑到它们之间的关系和其他约束来计算点之间的最佳位置。所以问题并不稀松。在

谢谢。。。在

Answer 1

我们对这款车型了解不多，但以下是一些注意事项：

1. SLSQP实际上是为小型（密集）的模型而设计的。在
2. SLSQP是一个局部求解器。它接受非凸问题，但只提供局部解。在
3. 我怀疑SLSQP是否存在这种复杂性。不管怎么说，它对某个特定问题的表现并没有多大影响。在
4. IPOPT是一种大型稀疏内点求解器。它会找到当地的解决办法。它可以解决非常大的模型。在
5. 像BARON、ANTIGONE和COUENNE这样的全局解算器可以找到全局解（或者，如果您不耐烦并过早停止，则可以对解决方案的质量进行限制）。这些解算器（大多数情况下）比本地解算器慢。我不知道直接的Python链接。在
6. 如果你有一个好的起点，一个局部解算器可能正是你需要的。使用多阶段策略有助于找到更好的解决方案（不是被证明是全局最优的，但是你有信心没有找到真正糟糕的局部最优解）。在
7. Python框架PYOMO提供了对许多求解器的访问。但是你需要重写模型。PYOMO具有自动微分功能：不需要提供梯度。在
8. 对于测试，您可以尝试在AMPL或GAMS中转录模型，并通过NEOS在线求解。这将允许您尝试许多解算器。AMPL和GAMS都具有自动微分功能。在

Answer 2

在我看来小规模为优化提供直观的界面。我发现加快成本函数（最终是梯度函数）可以给你很好的加速。在

例如，以N维Rosenbrock函数为例：

import numpy as np
from scipy.optimize import minimize


def rosenbrock(x, N):
    out = 0.0
    for i in range(N-1):
        out += 100.0 * (x[i+1] - x[i]**2)**2 + (1 - x[i])**2
    return out

# slow optimize
N = 20
x_0 = - np.ones(N)
%timeit minimize(rosenbrock, x_0, args=(N,), method='SLSQP', options={'maxiter': 1e4})
res = minimize(rosenbrock, x_0, args=(N,), method='SLSQP', options={'maxiter': 1e4})
print(res.message)

优化的时间安排

^{pr2}$

现在可以使用numba加快目标函数的速度，并提供一个简单的函数来计算梯度，如下所示：

from numba import jit, float64, int64

@jit(float64(float64[:], int64), nopython=True, parallel=True)
def fast_rosenbrock(x, N):
    out = 0.0
    for i in range(N-1):
        out += 100.0 * (x[i+1] - x[i]**2)**2 + (1 - x[i])**2
    return out


@jit(float64[:](float64[:], int64), nopython=True, parallel=True)
def fast_jac(x, N):
    h = 1e-9
    jac = np.zeros_like(x)
    f_0 = fast_rosenbrock(x, N)
    for i in range(N):
        x_d = np.copy(x)
        x_d[i] += h
        f_d = fast_rosenbrock(x_d, N)
        jac[i] = (f_d - f_0) / h
    return jac

基本上就是在目标函数中添加一个修饰符，允许并行计算。现在我们可以再次计时优化：

print('with fast jacobian')
%timeit minimize(fast_rosenbrock, x_0, args=(N,), method='SLSQP', options={'maxiter': 1e4}, jac=fast_jac)
print('without fast jacobian')
%timeit minimize(fast_rosenbrock, x_0, args=(N,), method='SLSQP', options={'maxiter': 1e4})
res = minimize(fast_rosenbrock, x_0, args=(N,), method='SLSQP', options={'maxiter': 1e4}, jac=fast_jac)
print(res.message)

尝试两者，有或没有提供快速雅可比函数。其输出为：

with fast jacobian
9.67 ms ± 488 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
without fast jacobian
27.2 ms ± 2.4 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
Optimization terminated successfully.

这是一个约10倍的加速，很少的努力。你能用它来实现的改进很大程度上取决于你的成本函数的低效。我有一个成本函数，里面有几个计算，可以得到大约10^2-10^3的加速。在

这种方法的优点是它的工作量很小，而且您可以继续使用scipy及其漂亮的接口。在

Answer 3

令人惊讶的是，我发现了一个相对不错的解决方案，使用了一个深度学习框架的优化器Tensorflow，使用了基本的梯度下降（实际上是RMSProp，动量梯度下降），在我改变代价函数，包括不等式约束和边界约束作为惩罚（我想这和拉格朗日方法相同）。该算法训练速度快，在约束罚函数上采用适当的lambda参数，收敛速度快。我甚至不必重写雅各比表，因为TF在没有太多速度影响的情况下处理这些问题。在

在此之前，我设法让NLOPT工作，它比scipy/SLSQP快得多，但在更高的维度上仍然很慢。此外，NLOPT/AUGLANG速度非常快，但收敛性较差。在

也就是说，在20k变量下，它仍然很慢。部分原因是内存交换和代价函数至少为O（n^2）（与广播一起使用（x-x.t）^2+（y-y.t）^2）。所以仍然不是最佳的。在