2.1 Definitions and properties of convex sets

Convex sets are fundamental in optimization, forming the basis for many algorithms. They're shapes without dents or holes, where any two points can be connected by a line entirely within the set. This concept is crucial for understanding feasible regions in optimization problems.

Convex combinations, interior points, and extreme points are key ideas within convex sets. These concepts help define the structure of convex sets and play a vital role in finding optimal solutions in various optimization scenarios.

Convex Sets and Combinations

Fundamental Concepts of Convex Sets

• Convex set encompasses all points on line segments connecting any two points within the set
  • Visualized as a shape without any indentations or concavities
  • Includes circles, ellipses, and rectangles
• Convex combination forms new points from weighted sum of existing points in set
  • Weights must sum to 1 and be non-negative
  • Expressed mathematically as $x = \sum_{i=1}^n \lambda_i x_i$ where $\sum_{i=1}^n \lambda_i = 1$ and $\lambda_i \geq 0$
• Interior point resides within set, surrounded by other points in all directions
  • Can move slightly in any direction while remaining in set
  • Mathematically defined using open balls: $\exists \epsilon > 0$ such that $B(x, \epsilon) \subseteq S$

Boundary and Extreme Points

• Boundary point lies on edge of set, not surrounded by other points in all directions
  • Can be approached arbitrarily closely by points both inside and outside set
  • Formally defined: $\forall \epsilon > 0, B(x, \epsilon) \cap S \neq \emptyset$ and $B(x, \epsilon) \cap S^c \neq \emptyset$
• Extreme point cannot be expressed as convex combination of other points in set
  • Represents "corners" or vertices of convex set
  • Crucial in optimization problems, often optimal solutions found at extreme points
  • Mathematically: $x$ is extreme if $x = \lambda y + (1-\lambda)z$ with $0 < \lambda < 1$ implies $x = y = z$

Hyperplanes and Half-spaces

Hyperplanes: Definition and Properties

• Hyperplane divides space into two half-spaces
  • Generalizes concept of line in 2D and plane in 3D to higher dimensions
  • Defined by linear equation $a^Tx = b$ where $a \neq 0$ is normal vector
• Hyperplane properties include flatness and extension to infinity
  • Dimensionality one less than ambient space (2D line in 3D space)
  • Separates space into two distinct regions

Half-spaces and Separation Theorem

• Half-space represents all points on one side of hyperplane, including hyperplane itself
  • Closed half-space defined by $a^Tx \leq b$ or $a^Tx \geq b$
  • Open half-space defined by $a^Tx < b$ or $a^Tx > b$
• Separating hyperplane theorem proves existence of hyperplane separating disjoint convex sets
  • Crucial in support vector machines and other machine learning algorithms
  • States: For disjoint convex sets $A$ and $B$, $\exists a \neq 0, b$ such that $a^Tx \leq b$ for all $x \in A$ and $a^Tx \geq b$ for all $x \in B$

Polyhedra and Simplices

Polyhedra: Characteristics and Representations

• Polyhedron defined as intersection of finite number of half-spaces
  • Includes familiar shapes (cubes, pyramids, prisms)
  • Can be bounded or unbounded
• Polyhedron representations include:
  • Half-space representation (H-representation): $\{x | Ax \leq b\}$
  • Vertex representation (V-representation): $\{x | x = \sum_{i=1}^k \lambda_i v_i, \sum_{i=1}^k \lambda_i = 1, \lambda_i \geq 0\}$
• Polyhedra play crucial role in linear programming and optimization

Simplices: Special Polyhedra

• Simplex represents simplest possible polyhedron in given dimension
  • 0-simplex (point), 1-simplex (line segment), 2-simplex (triangle), 3-simplex (tetrahedron)
• Simplex properties include:
  • Having $n+1$ vertices in $n$-dimensional space
  • Every face of simplex also simplex
  • Convex hull of $n+1$ affinely independent points
• Simplices used in triangulation methods and simplicial approximation in topology