• Overview
• Details
• Exercises

Convex optimization minimizes a convex objective over a convex feasible set. Karush–Kuhn–Tucker (KKT) conditions characterize optimality for constrained problems. Lagrangian duality yields lower bounds, certificates of optimality, and algorithmic insights; under Slater’s condition, strong duality holds.

• Canonical forms: unconstrained min f(x); inequality g_i(x) ≤ 0; equality h_j(x) = 0; convexity of f, g_i, and affine h_j.
• Lagrangian L(x, λ, ν) = f(x) + ∑_i λ_i g_i(x) + ∑_j ν_j h_j(x); dual function φ(λ, ν) = inf_x L(x, λ, ν).
• Dual problem: maximize φ(λ, ν) subject to λ ≥ 0; weak duality gives lower bounds; duality gap ≥ 0.
• KKT conditions (convex case):
  • Primal feasibility: g_i(x*) ≤ 0, h_j(x*) = 0
  • Dual feasibility: λ*_i ≥ 0
  • Complementary slackness: λ*_i g_i(x*) = 0
  • Stationarity: ∇f(x*) + ∑_i λ*_i ∇g_i(x*) + ∑_j ν*_j ∇h_j(x*) = 0
• Slater’s condition: strict feasibility implies strong duality (zero gap) for convex problems; KKT becomes necessary and sufficient.
• Examples: quadratic program (QP) with PSD Hessian; L1-regularized least squares (LASSO) via variable splitting.

1. Derive KKT conditions for min 1/2 x^T Q x + c^T x s.t. Ax ≤ b, with Q ⪰ 0. Show how to recover x*, λ* from stationarity and complementary slackness.
2. Prove strong duality for a convex problem that satisfies Slater’s condition. Give a counterexample when Slater fails.
3. Formulate the dual of LASSO via variable splitting; write KKT and interpret sparsity via complementary slackness.