python求解KKT及对偶问题的代码

以下是使用CVXPY库求解KKT条件和对偶问题的Python代码示例：

import cvxpy as cp
import numpy as np

# 定义原始问题的变量和参数
x = cp.Variable(2)
y = cp.Variable()
c = np.array([-1, -2])
A = np.array([[1, 1], [1, -1]])
b = np.array([1, 0])
t = cp.Parameter(nonneg=True)

# 定义原始问题的目标函数和约束条件
objective = cp.Minimize(c.T @ x + y)
constraints = [A @ x + y <= b, x >= 0, y >= 0]

# 求解原始问题
problem = cp.Problem(objective, constraints)
problem.solve()

# 输出原始问题的解和目标函数值
print("x =", x.value)
print("y =", y.value)
print("Objective value =", problem.value)

# 定义对偶问题的变量和参数
lambda_var = cp.Variable(2)
mu_var = cp.Variable()
dual_objective = cp.Maximize(b.T @ lambda_var - mu_var)
dual_constraints = [A.T @ lambda_var + mu_var * np.array([1, -1]) == c, lambda_var >= 0, mu_var >= 0]

# 求解对偶问题
dual_problem = cp.Problem(dual_objective, dual_constraints)
dual_problem.solve()

# 输出对偶问题的解和目标函数值
print("lambda =", lambda_var.value)
print("mu =", mu_var.value)
print("Dual objective value =", dual_problem.value)

# 检验KKT条件
x_star = x.value
y_star = y.value
lambda_star = lambda_var.value
mu_star = mu_var.value
grad_L = np.array([-1, -2]) + np.dot(np.array([[1, 1], [1, -1]]), lambda_star)
assert np.allclose(grad_L, np.zeros(2), atol=1e-8)
assert np.allclose(A @ x_star + y_star - b, np.zeros(2), atol=1e-8)
assert np.allclose(lambda_star * (A @ x_star + y_star - b), np.zeros(2), atol=1e-8)
assert np.allclose(mu_star * np.array([1, -1]), np.zeros(2), atol=1e-8)
assert mu_star >= 0
assert np.allclose(lambda_star, np.maximum(np.zeros(2), lambda_star), atol=1e-8)

代码中，我们首先定义了原始问题的变量和参数，然后使用CVXPY库定义了原始问题的目标函数和约束条件，并求解了原始问题。接着，我们定义了对偶问题的变量和参数，使用CVXPY库定义了对偶问题的目标函数和约束条件，并求解了对偶问题。最后，我们检验了KKT条件是否满足。

需要注意的是，在检验KKT条件时，由于存在等式约束 $A x + y = b$，所以我们需要将该约束条件拆分为两个不等式约束 $A x + y \leq b$ 和 $-A x - y \leq -b$，并分别检验它们是否满足。同时，由于存在非负约束 $x \geq 0$ 和 $y \geq 0$，我们还需要检验对应的KKT条件是否满足。