CPBS 7620 - Lecture 18 - Convex Optimization

Overview

Nicholas Dwork introduces convex sets, convex functions, and convex optimization, then explains disciplined convex programming (DCP) as a rule-based way to build problems that solvers can verify and solve. He demonstrates CVX and CVXPY workflows, including status checks, a LASSO objective, and reformulations that make otherwise unrecognized or nonconvex-looking expressions DCP-compliant.

Key takeaways

A convex optimization problem combines a convex objective with convex inequality constraints and affine equalities, so every local minimum is also a global minimum.
The epigraph criterion connects function convexity to set convexity: a function is convex exactly when the region above its graph is a convex set.
DCP rules let CVXPY verify convexity compositionally, but an equivalent expression may be accepted or rejected depending on whether it uses recognized atoms.
The expression sqrt(1 + z^2) is not recognized directly in the example, but rewriting it as the norm of [1, z] makes its convex structure recognizable to DCP.
Algebraic substitutions can expose convex structure: for positive x and y, xy ≥ 4 is equivalent to 4/x ≤ y.
Introducing t as a reciprocal denominator and variables y₁ = tx₁ and y₂ = tx₂ can linearize a fractional objective and convert its constraints into a DCP-compliant form.

Chapters

0:00 Convex Sets, Functions, and Optimization Problem Definitions

A set is convex when every line segment between two of its points stays inside it; intersections of any number of convex sets remain convex.
A function is convex when its epigraph, the set of points above its graph, is convex; sums, pointwise maxima, and positive scalar multiples preserve convexity.
Dwork defines convex optimization using a convex objective, convex inequality constraints, and affine equalities, then distinguishes the feasible set from the optimal set.
Examples include the squared L2 residual plus an L1 penalty used in LASSO, and the perspective and indicator-function constructions.

5:18 DCP Composition Rules and CVXPY Solver Workflows

Disciplined convex programming builds problems from recognized function atoms using composition rules, and Dwork identifies CVX for MATLAB and CVXPY for Python as implementations.
For convex outer function H, composition with affine G is convex; composition also works when H is nonincreasing and G concave, or H is nondecreasing and G convex.
In CVXPY, minimizing (x - 3)^2 subject to x ≥ 5 returns the optimal point x = 5 and objective value 4.
CVXPY reports optimal, optimal inaccurate, infeasible, or unbounded; DCP recognition is sufficient but not necessary, as sqrt(1 + z^2) is accepted when rewritten as the norm of [1, z].

9:58 Reformulating LASSO and Difficult Constraints for CVXPY

The LASSO example minimizes a squared L2 residual plus λ times an L1 norm, and a loop can solve the problem repeatedly for different λ values.
For positive x and y, the constraint xy ≥ 4 can be rewritten as 4/x ≤ y; the inverse-positive function is a recognized convex atom in CVXPY.
A fractional objective can be made linear by introducing t as the reciprocal of its denominator and substituting y₁ = tx₁ and y₂ = tx₂.
The substitutions transform the original constraints into convex inequalities and an affine equality involving t, y₁, and y₂, producing a DCP-compliant problem.

Summary, takeaways, and chapters were generated by AI from the video's transcript and may contain errors. The video belongs to its creator, Nicholas Dwork.