M1-027M1: Mathematics & Statistics FundamentalsConvex Optimization & KKTMedium
⚡Flashcard Drill➔Mastery:

Formulate the Karush-Kuhn-Tucker (KKT) Conditions and Explain the Physical Meaning of Complementary Slackness

🎯 Active Recall Self-Check (Draft First, Verify After)
Login-free practice tracker: recall core answer, audit pitfalls, and log review status.
Step 1 · Draft your concise answer & assumptions
Step 2 · Check Pitfalls & Follow-up Inquiries
Next: M1-028 →
📐 Mathematical Definition
∇f+∑iμi∇gi=0,gi≤0,μi≥0,μigi=0\nabla f+\sum_i\mu_i\nabla g_i=0,\quad g_i\le0,\quad \mu_i\ge0,\quad \mu_i g_i=0
⚡ One-Sentence Core Answer
KKT conditions are necessary first-order optimality criteria for constrained optimization, with complementary slackness λigi(x)=0\lambda_i g_i(x)=0 dictating that inactive constraints have zero shadow price.

📌 Key Takeaways

  • •
    Stationarity: ∇f(x∗)+∑iλi∗∇gi(x∗)+∑jνj∗∇hj(x∗)=0\nabla f(x^*) + \sum_{i} \lambda_i^* \nabla g_i(x^*) + \sum_{j} \nu_j^* \nabla h_j(x^*) = 0.
  • •
    Primal & Dual Feasibility: gi(x∗)≤0,hj(x∗)=0g_i(x^*) \le 0, h_j(x^*) = 0, and λi∗≥0\lambda_i^* \ge 0.
  • •
    Complementary Slackness: λi∗gi(x∗)=0\lambda_i^* g_i(x^*) = 0; either the constraint is binding (gi=0g_i=0) or its multiplier vanishes (λi=0\lambda_i=0).

📐 Mathematical Derivations

For general problem min⁡f(x)\min f(x) s.t. gi(x)≤0,hj(x)=0g_i(x) \le 0, h_j(x) = 0, the Lagrangian is L(x,λ,ν)=f(x)+∑λigi(x)+∑νjhj(x)\mathcal{L}(x, \lambda, \nu) = f(x) + \sum \lambda_i g_i(x) + \sum \nu_j h_j(x). At optimal (x∗,λ∗,ν∗)(x^*, \lambda^*, \nu^*) with zero duality gap: f(x∗)=g(λ∗,ν∗)=inf⁡xL(x,λ∗,ν∗)≤L(x∗,λ∗,ν∗)=f(x∗)+∑λi∗gi(x∗)+∑νj∗hj(x∗)f(x^*) = g(\lambda^*, \nu^*) = \inf_x \mathcal{L}(x, \lambda^*, \nu^*) \le \mathcal{L}(x^*, \lambda^*, \nu^*) = f(x^*) + \sum \lambda_i^* g_i(x^*) + \sum \nu_j^* h_j(x^*). Since hj(x∗)=0h_j(x^*)=0, we have ∑λi∗gi(x∗)≥0\sum \lambda_i^* g_i(x^*) \ge 0. However, primal feasibility requires gi(x∗)≤0g_i(x^*) \le 0 and dual feasibility λi∗≥0\lambda_i^* \ge 0, which implies every term λi∗gi(x∗)≤0\lambda_i^* g_i(x^*) \le 0. Thus, their sum can only be ≥0\ge 0 if each individual term is strictly zero: λi∗gi(x∗)=0\lambda_i^* g_i(x^*) = 0.

🏭 Production Trade-offs

In Support Vector Machines (SVM), complementary slackness explains why SVM solutions are sparse: αi[yi(wTxi+b)−1]=0\alpha_i [y_i(w^T x_i + b) - 1] = 0. For any training sample strictly outside the margin (yi(wTxi+b)>1y_i(w^T x_i + b) > 1), its multiplier αi\alpha_i must be 0, meaning it exerts zero influence on the decision boundary. Only data points exactly on the margin boundary have αi>0\alpha_i > 0 (the support vectors), dramatically reducing inference complexity.
⚠️ Common Interview Pitfalls
  • ✕
    Assuming KKT conditions are sufficient without convexity and Slater's constraint qualification.
  • ✕
    Allowing inequality multipliers λi\lambda_i to take negative values (dual feasibility strictly requires λi≥0\lambda_i \ge 0).
🎯 Interviewer Follow-up Inquiries
  • ?
    Under what conditions do KKT conditions become both necessary and sufficient?
  • ?
    How do interior-point methods (barrier methods) enforce complementary slackness via perturbation λigi(x)=−μ\lambda_i g_i(x) = -\mu as μ→0\mu \to 0?
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔
📚

Associated Knowledge Base Guides & Mindmaps

← PreviousM1-026: Define Convex Sets and Convex Functions, and Explain Why Convexity Guarantees Global Optimality📋 Back to BankNext →M1-028: Define Strong Duality and Slater's Condition, and Explain the Practical Utility of Dual Formulations