Constrained Optimization and KKT Conditions
Constrained optimization minimizes an objective subject to equality and inequality constraints. Lagrange multipliers and the Karush-Kuhn-Tucker (KKT) conditions characterize optimality.
Key Points
- Lagrange multipliers handle equality constraints via the Lagrangian.
- KKT conditions generalize Lagrange multipliers to inequality constraints.
- Slater's condition guarantees strong duality for convex problems.
Formulas
Lagrangian
$$\mathcal{L}(x, \lambda, \nu) = f(x) + \sum_i \lambda_i g_i(x) + \sum_j \nu_j h_j(x)$$
KKT conditions
$$\nabla_x \mathcal{L} = 0, \quad g_i(x) \le 0, \quad \lambda_i \ge 0, \quad \lambda_i g_i(x) = 0$$
Strong duality (Slater)
$$\text{For convex problems with a strictly feasible point, } p^* = d^*$$
Code Example
from scipy.optimize import minimize
def f(x):
return x[0]**2 + x[1]**2
cons = {'type': 'eq', 'fun': lambda x: x[0] + x[1] - 1}
res = minimize(f, [0, 0], constraints=cons)
print(res.x) # [0.5, 0.5]