Project 25: Convex Optimization and KKT Constraint Solver

Build a constrained convex solver with certificate-grade KKT and dual-gap diagnostics.

Quick Reference

Attribute Value
Difficulty Level 4: Expert (The Systems Architect)
Time Estimate 2-3 weeks
Main Programming Language Python
Alternative Programming Languages Julia, MATLAB, Rust
Coolness Level Level 5: Pure Magic (Super Cool)
Business Potential 2. The “Micro-SaaS / Pro Tool” (Solo-Preneur Potential)
Knowledge Area Convex Optimization / Theoretical ML
Main Book “Convex Optimization” by Boyd and Vandenberghe

1. Learning Objectives

  1. Model convex objectives and constraints correctly.
  2. Implement a primal-dual or projected method with residual tracking.
  3. Verify stationarity, feasibility, and complementary slackness.
  4. Use duality gap to decide solver quality and stopping.

2. All Theory Needed (Per-Concept Breakdown)

Concept A: Convex Geometry

Fundamentals Convexity guarantees no deceptive local minima for convex objectives over convex sets.

Deep Dive into the concept Convexity is a structural property, not a solver feature. Before coding, validate whether your objective and constraints preserve convexity under composition and regularization.

Concept B: Duality

Fundamentals The dual problem provides lower bounds (for minimization) and often tractable certificates.

Deep Dive into the concept Dual variables encode sensitivity to constraints. Monitoring primal and dual values provides convergence evidence beyond objective decrease.

Concept C: KKT Conditions

Fundamentals KKT combines stationarity, feasibility, and complementary slackness.

Deep Dive into the concept For many convex problems with regularity conditions, KKT is necessary and sufficient. That makes residuals a production-grade validation layer.

3. Build Blueprint

  1. Implement at least one constrained convex ML objective.
  2. Add solver iterations with line-search or fixed schedule.
  3. Compute KKT residuals and duality gap each iteration.
  4. Emit certificate report with pass/fail thresholds.

4. Real-World Outcome (Target)

$ python convex_kkt_solver.py --problem l2_logreg --constraint l1_budget<=5

Primal objective: 0.58214
Dual objective:   0.58193
Duality gap:      2.1e-4
KKT residuals: stationarity=8.4e-5, slackness=1.1e-5
Verdict: certified solution within tolerance

5. Core Design Notes from Main Guide

Core Question

“How do we certify optimization quality rather than just hope the objective is low enough?”

Common Pitfalls

  • Treating non-convex objectives as convex accidentally
  • Ignoring infeasibility while objective decreases
  • Reporting only primal objective without certificates

Definition of Done

  • Supports two constrained convex problem families
  • Emits KKT residuals and duality gap per run
  • Includes infeasibility and non-convexity diagnostics
  • Documents tolerance policy for certification

6. Extensions

  1. Add interior-point baseline for comparison.
  2. Add warm-start policy across regularization sweeps.
  3. Add constraint sensitivity report from dual variables.