Convex | Sahithyan's Notes

For all definitions in this note, whenever a set is mentioned, it is assumed to be a set of points in $\mathbb{R}^n$ .

Convex Combination

A point $x = \sum_{i=1}^{k} \lambda_i x_i$ is a convex combination of $x_1, \dots, x_k$ if $\lambda_i \ge 0$ for every $i$ and $\sum_{i=1}^{k} \lambda_i = 1$ .

Convex Set

A set is convex iff it contains every convex combination of its points.

A set $S$ is convex iff for every pair of points $x, y \in S$ , the line segment joining them lies entirely in $S$ .

\lambda x + (1 - \lambda) y \in S \quad \text{for all } \lambda \in [0, 1]

The intersection of convex sets is convex. The union of convex sets is not necessarily convex.

For example: a half-space.

Verifying Convexity

To prove $S$ is convex:

Take arbitrary $x, y \in S$ and arbitrary $\lambda \in [0, 1]$ .
Form $z = \lambda x + (1 - \lambda) y$ .
Check $z$ satisfies every defining condition of $S$ , using only $x \in S$ , $y \in S$ , and $\lambda \in [0, 1]$ .
If it always holds, $S$ is convex.

To prove $S$ is not convex: give one explicit counterexample, i.e. points $x, y \in S$ and a value $\lambda \in [0, 1]$ with $\lambda x + (1 - \lambda) y \notin S$ .

Shortcuts for the “is convex” case:

$S = \{x \mid a^T x \le b\}$ or $\{x \mid a^T x = b\}$ (half-space, hyperplane): convex.
A finite intersection of convex sets is also convex.
Image or preimage of a convex set under an affine map: convex.
$S = \{x \mid f(x) \le c\}$ with $f$ convex: convex.

Set of Convex Combinations

For a convex set $S$ , the set of all convex combinations of points of $S$ (say $H$ ) is also convex.

H = \left\{ \sum \lambda_i x_i \mid \lambda_i \ge 0, \sum \lambda_i = 1, x_i \in S\right\}

Extreme Point

A point in a convex set that cannot be written as a convex combination of 2 other distinct points in the set. A bounded convex polyhedron has finitely many extreme points.

For example: the corners of a polygon, or every point on the boundary of a disk.

Equivalently, $x$ is an extreme point iff no non-zero direction $d$ lets both $x + \epsilon d$ and $x - \epsilon d$ stay in the set for small $\epsilon > 0$ . Otherwise $x$ is the midpoint of two distinct points of the set.

Convex Polygon

A polygon that is a convex set. All segments joining any 2 of its points stays inside it.

Geometrically, a convex polygon is a polygon where every interior angle is $\le 180°$ .

For a finite point set, the convex hull is a convex polygon whose vertices are a subset of the given points.

Convex Polyhedron

The intersection of finitely many half-spaces. Always a convex set, since the intersection of convex sets is convex.

Polytope

A bounded convex polyhedron. Every point in it is a convex combination of its extreme points, so a polytope is exactly the convex hull of its extreme points.

This relies on boundedness, not on being a polyhedron specifically. See Minkowski’s Theorem.

Convex Hull

The smallest convex set containing all the points of a set.

Equivalently, the set of all convex combinations of the points.

Minkowski’s Theorem

Any compact (closed and bounded) convex set in $\mathbb{R}^n$ equals the convex hull of its extreme points.

For example: polytopes.

Every point in the set is a convex combination of its extreme points.

Simplex

The convex hull of $n+1$ affinely independent points in $\mathbb{R}^n$ . Points $x_0, \dots, x_n$ are affinely independent if the vectors $x_1 - x_0, \dots, x_n - x_0$ are linearly independent, i.e. none of the points lies in the affine subspace spanned by the others.

For example:

Dimension ( $n$ )	Simplex
0	Point
1	Line
2	Triangle
3	Tetrahedron

A simplex is the simplest possible polytope with non-zero volume in its dimension. It has the fewest vertices needed to enclose an $n$ -dimensional region.

Relationship with Linear Programs

The feasible region of a linear program is a polytope.

Vertex Property

If the LP has an optimal solution, at least one extreme point attains it. This is why the optimal solution can always be found at a vertex, as used in the graphical method and the simplex algorithm.

Proof hint

Let $v_1, \dots, v_k$ be the vertices of the feasible region, and let $v^*$ be the one with the largest objective value: $z(v^*) = \max_i z(v_i)$ .

Any feasible point $x$ is a convex combination of the vertices: $x = \sum_i \lambda_i v_i$ , with $\lambda_i \ge 0$ and $\sum_i \lambda_i = 1$ .
$z$ is linear, so it distributes over the combination: $z(x) = \sum_i \lambda_i z(v_i)$ .
Replace every $z(v_i)$ with the upper bound $z(v^*)$ : $z(x) \le \sum_i \lambda_i z(v^*) = z(v^*) \sum_i \lambda_i = z(v^*)$ , using $\sum_i \lambda_i = 1$ .

So $z(x) \le z(v^*)$ for every feasible $x$ : no point, interior or on an edge, can beat the best vertex. Hence $v^*$ is optimal.

Simplex Algorithm

Walks vertex to vertex along the edges of the feasible polytope, improving the objective at each step, until no adjacent vertex is better. It does not construct geometric simplices during iteration.

The name is historical. In Dantzig’s original formulation the constraints $\sum_i x_i = 1$ , $x_i \ge 0$ appear, whose feasible set is a standard simplex. A basic feasible solution is a vertex of it.

Per iteration (a pivot): at a vertex, $n$ constraint hyperplanes meet, and the vertex together with its $n$ neighbouring vertices forms a local $n$ -simplex. A pivot swaps one basic variable for one non-basic variable, which replaces one vertex of that local simplex with a better one.