Convex Sets

Optimization · Axiom Academy

Understanding the fundamental building blocks of convex optimization 1. Definition: The Line Segment Test A set C is convex if for any two points x and y in C , and any value of between 0 and 1, the point x + (1- )y is also in C . Watch the animation to see the line segment test in action. The blue points are in the set, and the line segment between them must also be in the set for it to be convex. Many important mathematical structures are convex sets. Understanding these examples helps build intuition for working with convex optimization problems. Balls: Euclidean balls x : ||x - x c || r Polyhedra: Intersections of half-spaces The animation shows a circle (ball), a half-space, and a polyhedron - all convex sets where any line segment between two points stays inside. To understand convexity, it's equally important to recognize when a set is not convex. A set fails to be convex if we can find even one pair of points whose connecting line segment leaves the set. Donuts (Annuli): Regions with holes violate convexity Stars: Non-convex polygons with concave vertices Disconnected regions: Multiple separate components Watch how the line segment between two points leaves the set, proving non-convexity. 4. Operations Preserving Convexity: Intersection One of the most powerful properties of convex sets is that their intersection is always convex. This allows us to construct complex convex sets from simpler ones.

This is the written version of the interactive lesson above. See the full Optimization course.