Minimise the quadratic ½(θ − c)TH(θ − c) over a convex set: the ℓ1 ball |θ1| + |θ2| ≤ r written as four linear inequalities (8.111), a box, or the line θ1 + θ2 = r; or add the penalty r‖θ‖1. The exact solution is found by checking the KKT conditions (8.103)–(8.106) on every active set. At the solution the negative gradient (white arrow) equals the sum of the active constraint normals weighted by their multipliers (coloured arrows); inactive constraints get multiplier 0. The dotted path is projected gradient descent (8.122)–(8.125), or proximal gradient descent with soft thresholding (8.133) for the penalty. Click the plot to move the centre c.
The constraint rows are numbered as in (8.113): for the ℓ1 ball, g1 = θ1 + θ2 − r, g2 = θ1 − θ2 − r, g3 = −θ1 + θ2 − r, g4 = −θ1 − θ2 − r; for the box, θ1 ≤ r, θ2 ≤ r, −θ1 ≤ r, −θ2 ≤ r. The line uses the Lagrangian L + λ(θ1 + θ2 − r) as in (8.93). Gradient descent starts at (−1.5, 1.5); the projection on the ℓ1 ball is soft thresholding at the level that puts the point on the boundary.
code/ch08_optimization.py (qp_kkt, lasso2_exact, proj_l1_ball, soft_threshold, demo_problem, demo_pgd).