../

2026-09-01 Convex Optimization

$\newcommand{\R}{\mathbb{R}}$ $\newcommand{\hp}{\quad\quad\square}$

Convex sets

A set $C \subseteq \R^n$ is a convex set if $\forall x, y\in C,$ $$\theta y + (1 - \theta) x \in C, \theta \in [0, 1]$$

Another way to express it is : $$x + \theta (y - x) \in C, \forall x, y \in C, \theta \in [0, 1]$$

  • For any two points in the set, every point on the line segment between them is also in the set

Affine Sets

A set $C \subseteq \R^n$ is an affine set if $\forall x, y\in C$ $$\theta y + (1-\theta) x\in C, \theta \in \R$$

  • This corresponds to a hyperplane
  • For any two points in the set, every point on the line between them is also in the set
  • If a set is affine, it is also convex
  • The opposite is not true.

Affine combination

An affine combination of a set of points $x_1, x_2, \ldots, x_n$ is defined as $$\sum_{i=1}^n\theta_i x_i$$ given that the coefficients sum up to one $\theta_i \in \R, \sum_{i=1}^n \theta_i = 1$

Theorem 1: Affine combination of a set of $k$ points is an affine set

Let us prove this using induction

Base case: $k=2$

Claim: $\theta_1 x_1 + \theta_2 x_2, \theta_i \in \R, \theta_1 + \theta_2 = 1$ is a convex set

$\theta_2 = 1 - \theta_1$

$x_3 = \theta_1 x_2 + (1 - \theta_1) x_2$

Which is the form required to be in the affine set. $\hp$

Induction step:

Let us assume for some $k-1$ that the points of the form $\theta_1 x_1 + \theta_2 x_2 + \ldots + \theta_{k-1} x_{k-1}$ form an affine set given $\theta_i \in \R, \sum_i^{k-1} \theta = 1$

We want to prove that the set of points formed be $\theta_1 x_1 + \theta_2 x_2 + \ldots + \theta_{k-1} x_{k-1} + \theta_k x_k$ also form an affine set given $\theta_i \in \R, \sum_{i}^k \theta = 1$

I want to reiterate that the $\theta$s are not the same. Given any $k$ (or $k-1$) real numbers summing up to one, the resultant point will be in the affine set.

We know that $\sum_i^{k}\theta_i = 1$

$\theta_1 + \ldots + \theta_k = 1$

$\theta_1 + \ldots + \theta_{k-1} = 1 - \theta_k$

$\frac{\theta_1}{1 - \theta_k} + \ldots + \frac{\theta_{k-1}}{1 - \theta_k} = 1$

We now have $k-1$ real numbers summing up to one. Ergo

$\tilde{x} = \left(\frac{\theta_1}{1 - \theta_k} x_1 + \ldots + \frac{\theta_{k-1}}{1 - \theta_k} x_{k-1}\right) \in C$ which is affine.

We now use the two point rule on $x_k$ and $\tilde{x}$

$\tilde{x}(1-\theta_k) + x\theta_k = \theta_1 x_1 + \ldots + \theta_k x_k\hp$

Convex combination

A convex combination of a set of points $x_1 \ldots x_n$ is $$\theta_1 x_1 + \ldots + \theta_k x_k$$ given $\theta\in[0, 1], \sum_i^{k} \theta_i = 1$