scipy.optimize.minimize('SLSQP') 给定 2000 个暗淡变量时太慢

我有一个带有约束和上/下界的非线性优化问题，所以使用 scipy 我必须使用 SLSQP。问题显然不是凸的。 我让雅可比函数的目标函数和约束函数都能正常工作（结果很好/快，最多 300 个输入向量）。所有功能均经过矢量化并调整为运行速度非常快。问题是使用 1000 多个输入向量需要很长时间，尽管我可以看到最小化器没有大量调用我的函数（目标/约束/梯度）并且似乎将大部分处理时间花费在内部。我在某处读到 SLSQP 的性能是 O(n^3)。

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

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

谢谢...

在我看来 scipy.minimze 提供了一个直观的优化界面。我发现加速成本函数（最终是梯度函数）可以给你带来很好的加速。

以 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)

优化收益的时机

102 ms ± 1.86 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
Optimization terminated successfully.

现在您可以使用以下命令加速目标函数numba http://numba.pydata.org，并提供一个简单的函数来计算梯度，如下所示：

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 及其漂亮的界面。