Unit 5.4 · about 6 h
83 / 324Constraints, KKT conditions and proximal methods
Constraints and nonsmooth penalties need more than a zero ordinary gradient. KKT residuals and proximal fixed points provide certificates that an optimizer's loss curve cannot.
- derive
You can now
- Derive a small quadratic program's Lagrangian, dual lower bound and KKT certificate by hand.
- Explain complementary slackness and where convexity and a constraint qualification enter optimality claims.
- Derive soft thresholding and the proximal-gradient update for the lasso, then check both examples against independent answers.
Covers
- Constrained optimization, Lagrangians and KKT conditions
- Regularization and proximal intuition
Study, in this order
4 steps
- Lagrangian lower bounds and KKT certificatesConvex Optimization
Sections 5.1.1 to 5.1.3 (pp. 215 to 216), 5.2.2 to 5.2.3 (pp. 225 to 227), and 5.5.1 to 5.5.3 (pp. 241 to 245)
Depth · Stop 5.5.3 after Example 5.1 on p. 244. Keep only the duality needed to explain weak duality, Slater's condition and the small QP; leave broader duality theory aside.
- Solver status and dual valuesCVXPY basic and DCP tutorials
Changing the problem, Infeasible and unbounded problems, and Other problem statuses
Depth · Use the solver only after deriving the analytic solution. Accept neither
optimal_inaccuratenor an iteration cap as an unchecked certificate. - Read multipliers from the solver answerCVXPY basic and DCP tutorials
Dual variables:
constraint.dual_valueand the two-scalar exampleDepth · Read this heading only; none of the other advanced features are assigned.
- Proximal maps, soft thresholding and lassoProximal Algorithms
Sections 1.1 (p. 124), 4.2 (pp. 148 to 151), 6.5.2 (p. 188, equation 6.9), and 7.1's lasso formulation (p. 196)
Depth · In 4.2 read the basic update and quadratic upper-model interpretation. Skip accelerated methods and ADMM. In 6.5.2 stop before projection onto the \(\ell_1\) ball. Skip 7.1.1 on p. 197: it prints \(\operatorname{prox}_{\gamma g}=S_\gamma\) although \(g=\gamma\|x\|_1\); the correct general scaling is \(\operatorname{prox}_{\eta g}=S_{\eta\gamma}\). Its Gram rewrite with \(\tilde{b}=A^\top b\) also fails to preserve the linear term, already for \(A=[2]\), \(b=[1]\). Derive lasso's update from 4.2 and 6.5.2 instead.
Focus on
- Write inequalities as \(f_i(x)\le 0\) and attach nonnegative multipliers. The dual function minimizes the Lagrangian over \(x\) without imposing the original constraints; weak duality gives a lower bound.
- KKT comprises primal feasibility, dual feasibility, stationarity and complementary slackness. For a differentiable convex problem with affine equalities, KKT is sufficient; Slater's condition supplies necessity and dual attainment when a primal optimum exists.
- For \(0.5\|Aw-b\|_2^2+\lambda\|w\|_1\), proximal gradient takes \(u=w-\eta A^\top(Aw-b)\), then \(w+=\operatorname{sign}(u)\max(|u|-\eta\lambda,0)\). The threshold scales with \(\eta\), not just \(\lambda\).
- At zero, the \(\ell_1\) subgradient is the interval \([-1,1]\). Derive the three scalar cases instead of pretending \(\operatorname{abs}\) has a unique derivative there. For the smooth part, \(\eta\le 1/\|A\|_2^2\) gives the quadratic upper-model descent argument.
Reproduce closed-book
float64 a, z=cp.Variable(2), constraints=[z>=0,cp.sum(z)==1], objective=cp.Minimize(0.5*cp.sum_squares(z-a)); form prob=cp.Problem(objective,constraints) and call prob.solve(solver='CLARABEL',tol_gap_abs=1e-10,tol_gap_rel=1e-10,tol_feas=1e-10,max_iter=100). Read lam=constraints[0].dual_value and nu=constraints[1].dual_value; lam represents the mathematical \(\lambda\), and use z.value for numerical checks. Status is optimal. Measured residuals: max(0,max(-z.value))=8.08e-13, abs(sum(z.value)-1)=1.11e-16, max(0,max(-lam))=0, np.linalg.norm(z.value-a-lam+nu, np.inf)=1.22e-11 and np.linalg.norm(lam*z.value, np.inf)=4.56e-11. np.linalg.norm(z.value-(1,0), np.inf)=8.08e-13. Require every residual and the solution difference \(\le 10^{-9}\), rather than exact feasibility. Then derive the scalar soft-threshold map and work \(A=I_2\), \(b=(2,-0.25)\), \(\lambda=0.5\) by hand: \(w^*=(1.5,0)\). From \(w_0=(0,0)\), take 30 NumPy float64 proximal steps with \(\eta=0.5\); the infinity-norm error against this closed form is 1.40e-9, allowed \(\le 2\times 10^{-9}\). No random draws are needed.Traps
- Giving \(x\ge 0\) the wrong multiplier sign. Its standard-form constraint is \(-x\le 0\), so stationarity contains \(-\lambda\).
- Inferring a positive multiplier from an active constraint. Complementary slackness only says a positive multiplier implies activity, not the converse.
- Using ridge's shrinkage as lasso's proximal operator. Ridge scales coordinates continuously; lasso thresholds a whole interval to zero.
Practice
The section mini-project covers this: derive and solve a changed two-coordinate QP, record all KKT residuals and solver status, and derive soft thresholding before checking a lasso proximal loop against a closed form and a solver oracle.
Self-test
-
Where does each assumption enter the KKT sufficiency proof?
Convex objective and inequality functions, affine equalities, and nonnegative multipliers make \(L\) convex in \(x\). Differentiability and stationarity therefore minimize \(L\) globally. Feasibility and complementary slackness make \(L(x^*)=f(x^*)\). The dual infimum is then \(f(x^*)\), so weak duality certifies optimality. Slater is not needed for sufficiency. -
Does this QP satisfy Slater's condition?
Yes. \(x=(0.5,0.5)\) strictly satisfies \(-x<0\) and satisfies the affine equality. This supplies the constraint qualification; the strictly convex objective also makes the primal optimizer unique. -
Why is the proximal minimizer zero when \(|u|\le\eta\lambda\)?
At \(w=0\) the stationarity inclusion is \(0\in -u+\eta\lambda[-1,1]\), exactly that inequality. The quadratic term is strictly convex, so this condition identifies the unique minimizer, including both threshold endpoints. -
How can you check a lasso answer without knowing w*?
Let \(h=A^\top(Aw-b)\). Nonzero coordinates need \(h_i+\lambda\operatorname{sign}(w_i)=0\); zero coordinates need \(|h_i|\le\lambda\). Check these residuals with a stated numerical zero threshold, or use \(\|w-S_{\eta\lambda}(w-\eta h)\|/\eta\) as a proximal-gradient residual.
Completion criterion
Stop when
You can derive the QP certificate and threshold endpoints unaided, and your NumPy and solver checks pass their stated infinity-norm and feasibility tolerances.
Mark passed, then open 5.5 Only mark this when you can do it without notes.Leads to
- 2.2 Conditioning, basis expansions, ridge, lasso and elastic net Contrast ridge's smooth penalty with lasso's nonsmooth sparsity mechanism.
Resources for this unit
- Convex Optimization Read Chapters 1-5 and 9 with the course; use Chapter 10 only for equality-constrained Newton steps.
- CVXPY basic and DCP tutorials Use as the solver oracle after deriving a constrained problem and its KKT conditions by hand.
- Proximal Algorithms Read Sections 1.1, 4.2 and the elementwise soft-thresholding formula in 6.5.2, then the lasso formulation on p. 196. Skip 7.1.1's penalty-scaling and Gram-rewrite errors on p. 197; derive the update from 4.2 and 6.5.2.
Also in this section
- Stanford EE364a - Convex Optimization Follow lectures 1-9 and 15-16; use lecture 17 only for KKT systems. Leave full interior-point treatment for later.
- D2L - Optimization Algorithms Use the convexity, GD, SGD, minibatch, momentum, AdaGrad, RMSProp, Adam and scheduler sections for ML derivations and code.
- Fundamentals of Numerical Computation Study §§1.1-1.4, 2.7-2.8, 3.2-3.4 and 4.2-4.3 for floating point, conditioning, stability, least squares and iteration error, in the Python edition.
- PyTorch optimizer and gradient-clipping contracts Use AdamW's algorithm and
clip_grad_norm_'s parameters to locate weight decay and clipping precisely. Inspectstate_dictfor optimizer restart; no network training is assigned. - SciPy minimize: BFGS Read the BFGS method description and
gtol,maxiter,c1andc2options. Supply an analytic gradient and compare residuals and evaluation counts, not just iterations. - PyTorch numerical type information Read
torch.finfo'seps,maxandsmallest_normalfields and its subnormal note; inspectfloat64,float32,float16andbfloat16on CPU. - The Accuracy of Floating Point Summation Read Section 2's recursive-sum error bound and Section 3's pairwise and compensated summation algorithms. Leave the statistical error models and historical machine details aside.
- Accurately computing running variance Read the Welford mean and centered-sum recurrences. Prove the centered-sum invariant and translate the recurrence to NumPy; skip the C++ class.