Karush-Kuhn-Tucker(KKT)条件和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

fsolve求解器基于函数渐变的搜索.你试图用有限差分找出你似乎近似的一阶导数的零点？请不要.f的梯度只是(2*x1,2*x2)

因此,一阶导数仅在原点处为零.

KKT条件告诉您,在局部极值中,f的梯度和约束的梯度是对齐的(可能您想再次阅读拉格朗日乘数).因此,计算约束函数的梯度!但那是你的功课......

另请注意,所有这些算法都倾向于依赖本地搜索.所以起点相当重要:-)

祝好运