Optimization: Convex Sets & Functions
Optimization: Convex Sets & Functions
💡 Key Takeaways
- Define the concept of a convex set and identify convexity in common sets (e.g., line segments, balls, polyhedra).
- Define convex functions via the epigraph and inequality-based definition; distinguish convex, strictly convex, and linear functions.
- Know which operations preserve convexity: affine/linear maps preserve convexity; intersections of convex sets are convex; unions generally are not convex.
- Understand optimization implications: on a convex set with a convex objective, any local minimum is a global minimum; apply basic gradient/subgradient optimality conditions.
❓ Frequently Asked Questions
What is a convex set?
A set C ⊆ R^n is convex if, for any x,y ∈ C and any t ∈ [0,1], the point t x + (1−t) y also lies in C. Intuition: the line segment between any two points in C stays inside C.
What is a convex function?
A function f defined on a convex domain D is convex if, for all x,y ∈ D and t ∈ [0,1], f(t x + (1−t) y) ≤ t f(x) + (1−t) f(y). Intuition: the graph lies below its chords (e.g., f(x) = ||x||^2).
Why is convexity important in optimization?
If the feasible set is convex and the objective is convex (or concave for maximization), every local minimum is a global minimum. This enables efficient algorithms and guarantees (e.g., gradient methods, interior-point methods).
How can you verify convexity for sets and functions?
For a set, test closure under convex combinations: x,y ∈ C and t ∈ [0,1] imply t x + (1−t) y ∈ C. For a function, check that its Hessian is positive semidefinite (for twice-differentiable functions) or use the epigraph criterion: the set {(x,t) : t ≥ f(x)} is convex.