Convex Optimization & KKT

Convex optimization studies problems whose objective and feasible set are both convex ($f(\theta x_1 + (1-\theta)x_2) \le \theta f(x_1) + (1-\theta)f(x_2)$ for all $\theta \in [0,1]$, so any local optimum is global). A constrained problem $\min_x f(x)$ s.t. $h_i(x) = 0,\ g_j(x) \le 0$ is converted to unconstrained form via the Lagrangian $L(x, \lambda, \mu) = f(x) + \sum_i \lambda_i h_i(x) + \sum_j \mu_j g_j(x)$, where inequality multipliers must satisfy $\mu_j \ge 0$ (dual feasibility) so that violations are penalized rather than rewarded. The KKT conditions — necessary, and sufficient under convexity + Slater's condition — are: ① stationarity $\nabla_x L = \nabla f + \sum_i \lambda_i\nabla h_i + \sum_j \mu_j\nabla g_j = 0$; ② primal feasibility $h_i(x) = 0,\ g_j(x) \le 0$; ③ dual feasibility $\mu_j \ge 0$; ④ complementary slackness $\mu_j g_j(x) = 0$. Intuition: an inactive constraint ($g_j < 0$, solution strictly inside the feasible set) forces $\mu_j = 0$, while $\mu_j > 0$ means the constraint is active ($g_j = 0$) and pins the solution to the boundary.

SVM duality derivations, norm-constrained regularization (e.g. the ball form of L1), constrained policy optimization, and any interview follow-up on solving constrained problems. Classic example: $\min \frac{1}{2}(x-2)^2$ s.t. $x \le 1$. KKT: $x - 2 + \mu = 0$, $x \le 1$, $\mu \ge 0$, $\mu(x-1) = 0$. If $\mu = 0$ then $x = 2$ violates the constraint, so $x = 1$ and $\mu = 1$ — the unconstrained optimum 2 lies outside the feasible set, so the solution is pushed onto the boundary.

constrained optimization becomes an algebraic system without explicitly sweeping the feasible boundary; duality gives weak duality $\min_x \max_{\mu\ge0} L \ge \max_{\mu\ge0} \min_x L$, and under Slater's condition (an interior feasible point exists) strong duality $f^* = d^*$ holds, letting models like SVM be solved via the dual and making KKT necessary-and-sufficient for optimality.

Test Your Knowledge: Practice Questions for "Convex Optimization & KKT"

Single choice pitfall questions with instant feedback and mistake tracking.