Karush–Kuhn–Tucker (KKT) conditions and SciPy

Question

如何使用 SciPy 解决这样的非线性优化问题（https://en.wikipedia.org/wiki/Karush%E2%80%93Kuhn%E2%80%93Tucker_conditions）：

优化：f（X） = x1^2 + x2^2

约束函数： x1>= 0; x2

>= 0; x1 + 2*x2 <= 4

我写了这个：

import numpy as np
def func(X):
    x = X[0]
    y = X[1]
    L = X[2]
    return x**2 + y**2 + L * (x + 2*y - 4)
def dfunc(X):
    dLambda = np.zeros(len(X))
    h = 1e-3
    for i in range(len(X)):
        dX = np.zeros(len(X))
        dX[i] = h
        dLambda[i] = (func(X+dX)-func(X-dX))/(2*h);
    return dLambda
import scipy
from scipy.optimize import fsolve
X1 = fsolve(dfunc, [1, 1, 0])
print X1

我只找到一个解决方案：0.8，1.6

但还有更多：

0，0 4，0 0，2

如何使用 SciPy 找到它？

Answer 1

求解器基于函数梯度之后的搜索。你试图找到一阶导数的零点，你似乎用有限差分近似？请不要。f 的梯度仅为 （2*x1， 2*x2）

因此，一阶导数仅在原点为零。

KKT 条件告诉您，在局部极值中，f 的梯度和约束的梯度是对齐的（也许您想再次阅读有关拉格朗日乘数的信息）。因此，计算约束函数的梯度！但那是你的功课...

另请注意，所有这些算法都倾向于依赖本地搜索。所以起点相当关键：-）

祝你好运