python - 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 的梯度和约束的梯度是对齐的(也许您想再次阅读有关拉格朗日乘数的内容)。所以计算你的约束函数的梯度!但那是你的功课......

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

祝你好运