Karush-Kuhn-Tucker (KKT) Conditions

The gradient of the Lagrangian function must vanish at the optimal point. This ensures no feasible direction exists that can improve the objective.

• Lagrangian Function: L(x, λ, μ) = f(x) + Σλᵢgᵢ(x) + Σμⱼhⱼ(x)
• Gradient Requirement: ∇f(x*) + Σλᵢ∇gᵢ(x*) + Σμⱼ∇hⱼ(x*) = 0
• Interpretation: At the optimum, the gradient of the objective is a linear combination of the active constraint gradients.
• Necessity: Without stationarity, a descent direction within the feasible region would exist.

The candidate solution must satisfy all original constraints of the optimization problem. This is a non-negotiable requirement for any point to be considered optimal.

• Inequality Constraints: gᵢ(x*) ≤ 0 for all i = 1, ..., m
• Equality Constraints: hⱼ(x*) = 0 for all j = 1, ..., p
• Domain Membership: x* must belong to the feasible set X
• Practical Check: Violating any constraint immediately disqualifies a point, regardless of objective value.

All Lagrange multipliers associated with inequality constraints must be non-negative. This condition ensures the Lagrangian provides a lower bound on the optimal objective value.

• Sign Restriction: λᵢ ≥ 0 for all inequality constraints i = 1, ..., m
• Economic Interpretation: λᵢ represents the shadow price of relaxing constraint gᵢ; it cannot be negative.
• Contrast with Equalities: Multipliers μⱼ for equality constraints are unrestricted in sign.
• Violation Consequence: A negative multiplier would imply the objective could be improved by tightening a binding constraint.

For each inequality constraint, either the constraint is active (binding) or its associated multiplier is zero. This encodes the logic that only binding constraints influence the optimum.

• Mathematical Form: λᵢ · gᵢ(x*) = 0 for all i = 1, ..., m
• Two Cases: If gᵢ(x*) < 0 (inactive), then λᵢ must be 0. If λᵢ > 0, then gᵢ(x*) must equal 0 (active).
• Sparsity Implication: Many multipliers will be exactly zero, identifying which constraints actually restrict the solution.
• Analogy: You only pay a price (λᵢ > 0) for resources that are fully consumed (gᵢ = 0).

A regularity condition that must hold for the KKT conditions to be necessary. It ensures the linearized feasible directions accurately represent the true feasible set geometry.

• Linear Independence (LICQ): The gradients of active constraints are linearly independent.
• Mangasarian-Fromovitz (MFCQ): A weaker condition requiring a feasible interior direction for inequalities.
• Slater's Condition: For convex problems, existence of a strictly feasible point suffices.
• Failure Mode: Without qualification, KKT may fail at an optimum (e.g., cusp points where gradients are dependent).

When the objective function is convex and the feasible region is a convex set, the KKT conditions become both necessary and sufficient for global optimality.

• Convex Objective: f(x) is convex if its Hessian is positive semidefinite everywhere.
• Convex Constraints: gᵢ(x) must be convex functions; hⱼ(x) must be affine.
• Global Guarantee: Any KKT point in a convex problem is a global minimum.
• Non-Convex Warning: In non-convex problems, KKT points may be local minima, maxima, or saddle points. Second-order conditions are then required.

The direct predecessor to KKT conditions, handling equality constraints only. Introduces the concept of a Lagrangian function that combines the objective and constraints weighted by multipliers (λ). At optimality, the gradient of the Lagrangian vanishes. KKT generalizes this by adding complementary slackness and dual feasibility to handle inequality constraints (g(x) ≤ 0). Understanding Lagrange multipliers is a prerequisite for grasping the KKT framework.

A special class of optimization where the objective is a convex function and the feasible region is a convex set. In convex problems, KKT conditions are both necessary and sufficient for global optimality—a powerful guarantee. For non-convex problems, KKT is only necessary; a point satisfying KKT may be a saddle point or local minimum. Key properties:

• Local minima are global minima
• Duality gap is zero under constraint qualifications
• Solved efficiently via interior-point methods

Regularity conditions that must hold for KKT to be valid at a local optimum. Without them, KKT may fail even at optimal points. Common qualifications:

• Linear Independence Constraint Qualification (LICQ): Gradients of active constraints are linearly independent
• Slater's Condition: Exists a strictly feasible point for convex problems
• Mangasarian-Fromovitz (MFCQ): A weaker alternative to LICQ Violation typically occurs at cusps or degenerate boundaries of the feasible region.

KKT conditions bridge primal and dual problems. The Lagrange multipliers (λ, μ) are the dual variables. Key relationships:

• Weak Duality: Dual optimum ≤ Primal optimum (always)
• Strong Duality: Equality holds when KKT conditions are satisfied under convexity and constraint qualifications
• Complementary Slackness: λᵢgᵢ(x) = 0 for all inequality constraints—either the constraint is active (gᵢ=0) or its multiplier is zero The dual often simplifies the original problem structure.

Modern algorithms for solving KKT systems numerically. Instead of active-set methods that guess which constraints bind, interior-point methods use a barrier function to keep iterates strictly feasible. The primal-dual variant solves the KKT conditions directly via Newton's method applied to a perturbed system. Dominates large-scale convex optimization (linear, quadratic, semidefinite) and is the engine behind solvers like IPOPT and Gurobi's barrier solver.

The most distinctive KKT condition: λᵢgᵢ(x) = 0* for each inequality constraint i. This encodes a logical OR:

• If constraint is inactive (gᵢ(x*) < 0), then λᵢ = 0 (constraint doesn't matter)
• If constraint is active (gᵢ(x*) = 0), then λᵢ ≥ 0 (constraint binds, multiplier measures sensitivity) This condition makes the KKT system combinatorial—identifying the correct active set is the central computational challenge in SQP and active-set methods.