Karush-Kuhn-Tucker (KKT) Conditions & Complementary Slackness
“The Four KKT conditions: Stationarity, Primal feasibility, Dual feasibility, and Complementary slackness in Support Vector Machines.”
1.The Karush-Kuhn-Tucker (KKT) Theorem
§ 4.1.The Karush-Kuhn-Tucker (KKT) conditions extend the method of Lagrange multipliers to problems with inequality constraints: min f_0(x) s.t. f_i(x) <= 0 and h_j(x) = 0.
The Four KKT Conditions:
1. Stationarity: grad f_0(x) + Sum_{i=1}^m lambda_i grad f_i(x) + Sum_{j=1}^p nu_j grad h_j(x*) = 0.
2. Primal Feasibility: f_i(x) <= 0 for all i, and h_j(x) = 0 for all j.
3. Dual Feasibility: lambda_i* >= 0 for all inequality multipliers.
4. Complementary Slackness: lambda_i f_i(x*) = 0 for all i.
Geometric Meaning of Complementary Slackness:
Either the constraint boundary is reached (f_i(x) = 0), meaning the constraint actively holds back the objective, OR the constraint is loose (f_i(x) < 0), in which case its multiplier vanishes (lambda_i* = 0).
2. Worked Practice Problem: Constrained Quadratic Program via KKT Case Analysis
Test both active (lambda > 0) and inactive (lambda = 0) constraint cases systematically.
Problem: Minimize f(x, y) = (x - 3)^2 + (y - 3)^2 subject to the inequality constraint x + y <= 4, with x >= 0, y >= 0.
Step 1: Rewrite constraint in standard form f1(x, y) <= 0:
f1(x, y) = x + y - 4 <= 0.
Step 2: Set up Lagrangian with multiplier lambda >= 0:
L(x, y, lambda) = (x - 3)^2 + (y - 3)^2 + lambda * (x + y - 4).
Step 3: Write KKT conditions:
1. Stationarity: dL/dx = 2*(x - 3) + lambda = 0 => x = 3 - lambda / 2.
dL/dy = 2*(y - 3) + lambda = 0 => y = 3 - lambda / 2.
2. Primal Feasibility: x + y - 4 <= 0.
3. Dual Feasibility: lambda >= 0.
4. Complementary Slackness: lambda * (x + y - 4) = 0.
Step 4: Case 1 - Inactive Constraint (lambda = 0):
If lambda = 0, then x = 3, y = 3.
Check Primal Feasibility: x + y = 3 + 3 = 6 > 4 (Violated!).
Case 1 is infeasible.
Step 5: Case 2 - Active Constraint (lambda > 0 => x + y - 4 = 0):
Substitute x = 3 - lambda / 2 and y = 3 - lambda / 2 into x + y = 4:
(3 - lambda / 2) + (3 - lambda / 2) = 4
6 - lambda = 4 => lambda = 2.
Check Dual Feasibility: lambda = 2 >= 0 (Satisfied!).
Optimal point: x = 3 - 2/2 = 2; y = 3 - 2/2 = 2.
Check Primal Feasibility: 2 + 2 = 4 <= 4 (Satisfied!).
Check Complementary Slackness: 2 (2 + 2 - 4) = 2 0 = 0 (Satisfied!).
Step 6: Compute optimal objective value:
f(2, 2) = (2 - 3)^2 + (2 - 3)^2 = (-1)^2 + (-1)^2 = 1 + 1 = 2.
Conclusion: The optimal constrained point is (2, 2) with multiplier lambda = 2 and minimum value f = 2.
Primary Academic References & Exam Sources
Every concept in Notes From a B.Tech Brain is synthesized from authoritative academic texts, seminal peer-reviewed research, verified exam archives, and renowned university lectures.