← Back to Projects
From-Scratch Optimization Solvers for Constrained Convex Problems
Implementing and benchmarking four constrained optimization algorithms — Projected Gradient, Uzawa's Algorithm, Quadratic Penalty, and Newton methods — with convergence proofs and comparative analysis.
Amini, A., Soleimany, A., Karaman, S., & Rus, D. (2018). Spatial Uncertainty Sampling for End-to-End Control. arXiv Preprint arXiv:1805.04829.
- Implemented Projected Gradient Descent from scratch with a linear convergence proof via spectral decomposition — converged in 20-36 iterations (under 1ms) for nonnegative least squares, matching MATLAB's lsqnonneg to machine precision across problem sizes up to (512, 64).
- Built a Quadratic Penalty framework with adaptive inner solvers (gradient descent + Armijo for NNLS, Newton + Sherman-Morrison for entropy minimization) — achieved a 20× speedup on the entropy Hessian solve by exploiting its diagonal-plus-rank-1 structure for O(n) complexity instead of O(n³).
- Implemented Uzawa's Algorithm via Newton's method on the reduced scalar dual for entropy minimization — derived a closed-form dual reduction showing the KKT system collapses to a 1D concave maximization, achieving quadratic convergence in 6-10 iterations with sub-millisecond wall times.
- Implemented quasi-Newton from scratch for the unconstrained inner solves — the same mathematical foundation powering PyTorch's L-BFGS optimizer, bridging classical optimization theory to modern deep learning practice.
- Systematically benchmarked all solver-problem combinations against MATLAB's fmincon, with rigorous perturbation analysis showing no degradation in accuracy across three orders of magnitude of data noise.