寻找 Sympy 多项式的 KKT 点的最佳方法

Question

我正在尝试在受超立方体 [-1,1]^n 约束的域上，对具有 n 变量的某些低次多项式（例如 3）运行梯度下降 (GD)。我想将 GD 的终止点与使用 Sympy 计算的实际 KKT 点进行比较。 例如，我有一个包含 3 个变量 a、b 和 c（即 n=3）的 Sympy 表达式，如下所示：

0.2*a**3 - 0.1*a**2*b - 0.9*a**2*c + 0.5*a**2 - 0.1*a*b**2 - 0.4*a*b*c + 0.5*a*b - 0.6*a*c**2 - 0.5*a*c - 0.6*a - 0.1*b**3 + 0.4*b**2*c - 0.4*b**2 + 0.7*b*c**2 - 0.4*b*c + 0.9*b + 0.09*c**3 - 0.6*c**2 + 0.4*c + 0.22

在有约束的情况下找到该表达式的所有 KKT 点的最佳、最快的方法是什么：

-1 <= a <= 1
-1 <= b <= 1
-1 <= c <= 1

（理想情况下，搜索仅限于 GD 终止点附近，以节省计算时间，但我不确定如何严格执行）

Answer 1

将表达式及其雅可比行列式预编译为函数对象，然后将它们传递给

minimize

。请注意，它试图比您预期的梯度下降更聪明，这可能有帮助，也可能没有帮助；这默认为 Kraft 的顺序最小二乘规划方法。

import string

import numpy as np
import scipy.optimize
import sympy

expr_str = (
    '0.2*a**3 - 0.1*a**2*b - 0.9*a**2*c + 0.5*a**2 - 0.1*a*b**2 - 0.4*a*b*c '
    '+ 0.5*a*b - 0.6*a*c**2 - 0.5*a*c - 0.6*a - 0.1*b**3 + 0.4*b**2*c '
    '- 0.4*b**2 + 0.7*b*c**2 - 0.4*b*c + 0.9*b + 0.09*c**3 - 0.6*c**2 + 0.4*c + 0.22'
)
symbols = {
    c: sympy.Symbol(name=c, real=True, finite=True)
    for c in string.ascii_lowercase
    if c in expr_str
}
expr = sympy.parse_expr(s=expr_str, local_dict=symbols)
expr_callable = sympy.lambdify(
    args=[symbols.values()], expr=expr,
)

jac = [
    sympy.diff(expr, sym)
    for sym in symbols.values()
]
jac_callable = sympy.lambdify(
    args=[symbols.values()], expr=jac,
)

result = scipy.optimize.minimize(
    fun=expr_callable,
    jac=jac_callable,
    x0=np.zeros(len(symbols)),
    bounds=scipy.optimize.Bounds(lb=-1, ub=1),
)
assert result.success
print(result)

CONVERGENCE: NORM_OF_PROJECTED_GRADIENT_<=_PGTOL
  message: CONVERGENCE: NORM_OF_PROJECTED_GRADIENT_<=_PGTOL
  success: True
   status: 0
      fun: -4.020346688237437
        x: [ 5.139e-01 -1.000e+00 -1.000e+00]
      nit: 5
      jac: [-1.222e-08  3.839e+00  4.398e+00]
     nfev: 7
     njev: 7
 hess_inv: <3x3 LbfgsInvHessProduct with dtype=float64>