🔎Convex Geometry Unit 1 – Introduction to Convex Sets

What are Convex Sets?

• Convex sets are fundamental objects in convex geometry and optimization
• A set $C$ in a real vector space is convex if for any two points $x, y \in C$, the line segment connecting $x$ and $y$ is entirely contained within $C$
• Formally, $C$ is convex if $\lambda x + (1-\lambda)y \in C$ for all $x, y \in C$ and $\lambda \in [0, 1]$
• Convex sets are closed under convex combinations, meaning any weighted average of points in the set also belongs to the set
• The intersection of any collection of convex sets is also convex
• Convex sets can be unbounded (e.g., a half-space) or bounded (e.g., a closed ball)
• The empty set and singleton sets are considered convex

Key Properties of Convex Sets

• Convex sets are connected, meaning there exists a path between any two points in the set that lies entirely within the set
• The closure, interior, and relative interior of a convex set are also convex
• Convex sets are path-connected, implying any two points can be joined by a continuous path within the set
• The projection of a convex set onto a subspace is convex
• Convex sets are invariant under affine transformations, such as translations, rotations, and scaling
• The Minkowski sum of two convex sets (i.e., the set of all pairwise sums) is convex
• Supporting hyperplanes exist at every boundary point of a convex set

Examples and Non-Examples

• Examples of convex sets include balls, ellipsoids, polyhedra, and half-spaces
  • A closed ball $B(x, r) = \{y : \|y - x\| \leq r\}$ is convex
  • A half-space $H = \{x : a^Tx \leq b\}$ is convex
• Non-examples include annuli, star-shaped sets, and disconnected sets
  • An annulus $A = \{x : r_1 \leq \|x\| \leq r_2\}$ is not convex
  • A star-shaped set $S = \{x : \exists y \in S, \lambda x + (1-\lambda)y \in S, \forall \lambda \in [0, 1]\}$ may not be convex
• The union of two convex sets is generally not convex, unless one set contains the other
• The complement of a convex set is generally not convex, except in special cases (e.g., half-spaces)

Convex Combinations and Convex Hulls

• A convex combination of points $x_1, \ldots, x_n$ is a weighted average $\sum_{i=1}^n \lambda_i x_i$, where $\lambda_i \geq 0$ and $\sum_{i=1}^n \lambda_i = 1$
• The set of all convex combinations of points in a set $S$ is called the convex hull of $S$, denoted $\text{conv}(S)$
• The convex hull is the smallest convex set containing $S$, and is the intersection of all convex sets containing $S$
• For a finite set of points, the convex hull is a convex polytope
  • A convex polytope is the convex hull of a finite set of points
• Carathéodory's theorem states that any point in the convex hull of a set $S \subseteq \mathbb{R}^n$ can be expressed as a convex combination of at most $n+1$ points in $S$

Separation Theorems

• Separation theorems are fundamental results in convex geometry that describe conditions under which two convex sets can be separated by a hyperplane
• The Hyperplane Separation Theorem states that if $A$ and $B$ are disjoint nonempty convex sets, then there exists a hyperplane that separates them
  • A hyperplane $H = \{x : a^Tx = b\}$ separates $A$ and $B$ if $a^Tx \leq b$ for all $x \in A$ and $a^Tx \geq b$ for all $x \in B$
• The Strong Separation Theorem states that if $A$ and $B$ are disjoint nonempty convex sets and one of them is compact, then there exists a hyperplane that strictly separates them
  • A hyperplane $H$ strictly separates $A$ and $B$ if there exists $\epsilon > 0$ such that $a^Tx \leq b - \epsilon$ for all $x \in A$ and $a^Tx \geq b + \epsilon$ for all $x \in B$
• The Supporting Hyperplane Theorem states that at every boundary point of a convex set, there exists a supporting hyperplane
  • A hyperplane $H$ supports a convex set $C$ at $x$ if $x \in C \cap H$ and $C$ lies entirely in one of the closed half-spaces determined by $H$

Applications in Optimization

• Convex sets play a crucial role in optimization, particularly in convex optimization problems
• A convex optimization problem involves minimizing a convex function over a convex set
  • Convex optimization problems have the property that any local minimum is also a global minimum
• Linear programming problems, where the objective function and constraints are linear, involve optimizing over convex polyhedra
• Quadratic programming problems, with a quadratic objective function and linear constraints, also involve convex sets
• The feasible set of an optimization problem, which is the set of all points satisfying the constraints, is often required to be convex for efficient solution methods
• Duality in optimization, such as Lagrangian duality and Fenchel duality, heavily relies on the properties of convex sets and functions

Visualizing Convex Sets

• Visualizing convex sets can aid in understanding their properties and relationships
• In two dimensions, convex sets can be easily visualized as regions without any "dents" or "holes"
  • Examples include circles, ellipses, triangles, and polygons
• In three dimensions, convex sets can be visualized as solid objects without any "dents" or "cavities"
  • Examples include spheres, ellipsoids, tetrahedra, and polyhedra
• Higher-dimensional convex sets can be challenging to visualize directly, but their properties can be understood through lower-dimensional projections or cross-sections
• The convex hull of a set of points can be visualized as the smallest convex polygon (in 2D) or polyhedron (in 3D) containing all the points
• Separation theorems can be visualized by drawing hyperplanes that separate or support convex sets

Practice Problems and Exercises

• Prove that the intersection of any collection of convex sets is convex
• Show that the Minkowski sum of two convex sets is convex
• Determine whether the following sets are convex: a) $S_1 = \{(x, y) : x^2 + y^2 \leq 1\}$ b) $S_2 = \{(x, y) : x^2 + y^2 = 1\}$ c) $S_3 = \{(x, y) : |x| + |y| \leq 1\}$
• Find the convex hull of the following sets of points: a) $\{(0, 0), (1, 0), (0, 1)\}$ b) $\{(0, 0), (1, 1), (2, 0), (0, 2)\}$
• Prove Carathéodory's theorem for a set $S \subseteq \mathbb{R}^2$
• Find a hyperplane that separates the following pairs of convex sets: a) $A = \{(x, y) : x \leq 0\}$ and $B = \{(x, y) : x \geq 1\}$ b) $A = \{(x, y) : x^2 + y^2 \leq 1\}$ and $B = \{(x, y) : x \geq 2\}$
• Formulate a convex optimization problem to find the point in a convex set $C$ closest to a given point $p$