Project 51: Convex Optimization and KKT Solver

A self-contained deep-dive from the canonical Math from Foundations to Machine Learning curriculum.

  • Difficulty: Level 4: Expert
  • Time: 2-3 weeks
  • Language: Python
  • Prerequisites: Projects 20, 26, 33-34, and 36
  • Source: ML-Math P25

What You Will Build

Implement a small constrained convex-optimization system that reports mathematical certificates, not only a low objective value. Support at least two problem families, such as L2-regularized logistic regression under an L1 budget and a convex quadratic program with affine inequalities. Validate declared problem structure, run a projected, primal-dual, or barrier-based method, and record primal/dual objectives, feasibility, stationarity, complementary slackness, and duality gap each iteration. Include deliberately infeasible and non-convex inputs so the solver distinguishes bad models from failed convergence.

Real World Outcome

A run returns a candidate solution plus a certificate report: objective values, duality gap, every KKT residual, active constraints, stopping reason, and pass/fail tolerance. Convergence plots show whether optimization, feasibility, and certification improve together; infeasible cases receive explicit diagnostics.

Core Question

How can you certify that a constrained solution is genuinely optimal rather than merely the best point your algorithm happened to find?

Concepts You Must Understand First

  • Convex sets/functions and composition rules — Boyd and Vandenberghe, Convex Optimization.
  • Lagrangians, dual functions, weak/strong duality, and Slater’s condition.
  • KKT stationarity, primal feasibility, dual feasibility, and complementary slackness.
  • Projected/primal-dual gradient methods, line search, and stopping criteria.
  • Conditioning and stable linear solves — Projects 29-30.

Build Milestones

  1. Define typed objectives/constraints with gradient, shape, and convexity checks.
  2. Implement one solver and test it first on a one- or two-dimensional problem with known optimum.
  3. Derive dual quantities and compute normalized KKT residuals and duality gap every iteration.
  4. Add a second constrained ML problem plus infeasible and invalid-problem cases.
  5. Compare solutions with a trusted solver and generate a certificate-focused report.

Hints in Layers

  1. Separate “candidate generation” from “candidate certification” so either component can be tested alone.
  2. Normalize residuals by relevant data/solution scales before comparing them with tolerances.
  3. Plot objective and feasibility together; objective improvement can hide constraint violation.

Common Pitfalls and Debugging

  • Objective falls while the answer remains invalid: feasibility is ignored. Track maximum constraint violation and reject uncertified output.
  • KKT residual stays large near a trusted optimum: Lagrangian sign or multiplier convention is inconsistent. Verify a hand-solvable inequality case.
  • Duality gap is negative unexpectedly: primal/dual formulas or numerical tolerances are wrong. Recheck minimization bounds and report tiny roundoff separately.

Definition of Done

  • Two constrained convex problem families are supported and validated.
  • Every run reports all KKT components, primal/dual values, and stopping reason.
  • Known analytic examples and a trusted solver agree within justified tolerances.
  • Infeasible and non-convex inputs do not receive false optimality claims.
  • Convergence plots distinguish objective, feasibility, residual, and gap behavior.
  • The tolerance/certification policy is documented with scale-aware reasoning.

Previous: Project 50 · Complete learning path · Next: Project 52