CPBS 7620 - Lecture 18 - Convex Optimization
Watch on YouTube →
Overview
Nicholas Dwork introduces convex sets and functions, then explains how convexity makes optimization problems tractable and how disciplined convex programming (DCP) turns recognized mathematical building blocks into solvable models. He demonstrates CVXPY in Python, including a constrained quadratic, lasso, and reformulations that make initially unrecognized expressions DCP-compliant.
Key takeaways
- Convexity of the objective and constraint functions gives a structured optimization problem that can be handled by convex optimization methods.
- The epigraph test connects function convexity to set convexity: a function is convex exactly when the points on or above its graph form a convex set.
- DCP rules are a practical verification system, not a complete test for convexity; equivalent expressions such as sqrt(1 + z²) and ||[1, z]|| can receive different DCP recognition.
- CVXPY reports four key outcomes: optimal, optimal inaccurate, infeasible, and unbounded, which distinguish trusted solutions from numerical uncertainty and failures of feasibility or boundedness.
- Algebraic reformulation can turn non-DCP models into solvable ones, as shown by replacing xy ≥ 4 with 4/x ≤ y for positive variables and by introducing t and y variables for a fractional objective.
Chapters
- A set is convex when every line segment connecting two points in the set remains inside it; intersections of any number of convex sets are also convex.
- A function is convex when chords between points on its graph lie above the graph, equivalently when its epigraph is a convex set.
- Convexity-preserving rules include summing convex functions, taking their pointwise maximum, and multiplying by a nonnegative scalar; the perspective of a convex function is also convex.
- A convex optimization problem minimizes a convex objective subject to convex inequality functions and affine equalities; its feasible set contains all constraint-satisfying points, and its optimal set contains the minimizers.
- Disciplined convex programming combines known function atoms using composition rules, including convex functions of affine inputs and monotonicity-compatible convex or concave compositions.
- CVX has implementations for MATLAB, Python, and Julia; Dwork uses CVXPY to declare variables, objectives, constraints, and solve problems.
- For minimizing (x - 3)² subject to x ≥ 5, CVXPY returns x = 5 and objective value 4.
- DCP is sufficient but not necessary: sqrt(1 + z²) is not recognized in its naive form, while the equivalent norm of [1, z] is DCP-compliant; solver statuses include optimal, optimal inaccurate, infeasible, and unbounded.
- The lasso objective combines the squared L2 residual norm, ||Ax - b||₂², with λ||x||₁; a CVXPY loop can solve it repeatedly for different λ values.
- The bilinear constraint xy ≥ 4 is not DCP as written, but for positive x and y it is equivalent to 4/x ≤ y, using the convex reciprocal function on positive inputs.
- A fractional objective can be linearized with a change of variables: set t = 1/(1 + 0.5x₁ + x₂) and yᵢ = txᵢ, turning the objective into the linear expression -3y₁ - 2y₂.
- The change of variables also transforms constraints, including x₁ + x₂ ≤ 1 into y₁ + y₂ ≤ t, and the denominator definition into t + 0.5y₁ + y₂ = 1, yielding a DCP model.
Transcript excerpt
0:00 Hi, I'm Nicholas Twork, and in this lecture, we'll discuss convex optimization. Recall a convex set S is one where the line segment connecting any two points in the set lies in the set. So, for example, this set is convex, and if we choose any two points in the set and connect them with a line, the whole line is within the set. This set is not convex. We can find two points where if we connect those two points with a line segment, then at least part of the segment lies outside of the set. The intersection of convex sets is convex. So, here's a simple example. And we needn't restrict the number of sets that we're intersecting to two. We can add a third, and in fact, this statement is true for an infinite number of convex sets. Recall that a convex function is one where the line connecting any two points
0:48 on the function lies above the function. So, here's one example. If we choose any two points on this function, the line segment lies above the function, so this example is convex. Here's a different example. In this case, we can choose two points that lie on the function where the line segment connecting those two points lies below the function in at least one location. So, this example is not convex. And here's the rigorous definition for a convex function. Recall that the epigraph of a function is the set of all points that lie above the function. And a function is convex if and only if its epigraph is a convex set. We have rules for convex functions that let us make more interesting convex functions out of more basic ones. One is
1:35 that the sum of two convex functions defined on the same domain is convex.
This is the start of the transcript. Save this video free for the whole transcript, searchable and time-coded.
Related notes
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.