2. Convex set

Affine set

• Line : all points through $x_1, x_2$

$$x = \theta x_1 + (1 - \theta) x_2$$

where $\theta\in \R$

This idea can be generalized to more than two points.

$$\theta_1x_1 + \theta_2 x_2 + \cdots + \theta_kx_k$$

where $\theta_1 + \cdots + \theta_k = 1$

We refer to a point can be expressed as the following form as an affine combination of the points $x_1 , \dots x_k$

• affine set : contains every affine combination of its points

If $C$ is an affine set and $x_0\in C$, then the set

$$V = C - x_0 := \{x - x_0 | x\in C\}$$

is a subspace, $i.e.$, closed under vector addition and scalar multiplication.

• Proof

  Let $v_1, v_2\in V, \alpha, \beta \in \R$. Then $v_1 + x_0, v_2 + x_0 \in C$

  Moreover,

  $$\begin{align}\alpha v_1 + \beta v_2 + x_0 &= \alpha v_1 + \beta v_2 + (\alpha + (1 - \alpha))x_0 \\ &= \alpha(v_1 + x_0) + \beta(v_2 + x_0)\end{align} \\ \Rightarrow \alpha v_1 + \beta v_2 + x_0 \in C$$

  That means $\alpha v_1 + \beta v_2 \in V$

  Therefore $V$ is closed under vector addition and scalar multiplication.

Thus, the affine set $C$ can be expressed as

$$C = V + x_0 := \{v + x_0 | v\in V\}$$

The set of all affine combinations of points in some set $C\subset \R^n$ is called the affine hull of $C$, and denoted $\text{aff }C$

$$\text{aff } C = \{\theta_1x_1 + \cdots + \theta_kx_k|x_1, \dots, x_k\in C, \theta_1 + \dots + \theta_k = 1\}$$

💡

The affine hull is the smallest affine set that contains $C$

Affine dimension and relative interior

We define the dimension of an affine set $C$ as the dimension of the subspace $V$. But it is not always consistent with other definitions of dimension.

Let’s think about the unit circle in $\R^2$. Its affine dimension is two. By most definitions of dimension, however, the unit circle in $\R^2$ has dimension one.

We define the relative interior of the set $C$, denoted $\text{relint } C$, as its interior relative to $\text{aff }C$

$$\text{relint } C = \{x\in C | \exist r, B_r(x) \cap \text{aff }C\subset C\}$$

💡

Topologically, we only consider a open set relative to $C$

Convex set

• line segment : all points between $x_1$ and $x_2$

  $$x = \theta x_1 + (1 - \theta) x_2$$

  where $0\le \theta \le 1$

• convex set : contains line segment between any two points in the set

  $$\forall x_1, x_2\in C, \theta x_1 + (1-\theta)x_2 \in C$$

  where $0 \le \theta\le 1$

  

💡

Note that affine set is not a convex set

List of convex set

1. convex hull

2. convex cone/ norm cone

3. half-space

4. euclidean ball / norm ball

5. ellipsoid

6. polyhedra

7. simplex

Convex combination and convex hull

• convex combination : any point $x$ of the form

  $$x = \theta_1x_1 + \cdots + \theta_k x_k$$

  where $\theta_1 + \cdots + \theta_k = 1 , \theta_i \ge 0$

  💡

  Generalization of the convex set

• convex hull : set of all convex combinations

  

  The convex hull of a set $C$, denoted $\text{conv} C$, is the set of all convex combinations of points in $C$

  $$\text{conv } C = \{\theta_1x_1 + \cdots + \theta_k x_k|x_i \in C, \;\theta_i \ge 0,\; i = 1, \dots, k, \,\theta_1 + \cdots + \theta_k = 1\}$$

  💡

  The convex hull $\text{conv }C$ is always convex. Moreover, it is the smallest convex set that contains $C$

Convex cone

A set $C$ is called a cone if for every $x\in C$ and $\theta \ge 0$, we have $\theta x\in C$.

A set $C$ is a convex cone if it is convex and cone, which means that

$$\forall x_1, x_2\in C \text{ and }\theta_1, \theta_2\ge 0, \theta_1 x_1 + \theta_2 x_2 \in C$$

💡

This condition is stronger than the condition of convexity. Therefore, convex cone is trivially a convex set.

A point of the form

$$\theta_1x_1 + \cdots + \theta_k x_k$$

where $\theta_1, \dots, \theta_k \ge 0$

is called a conic combination of $x_1, \dots, x_k$.

Hyperplane

A hyperplane is a set of the form

$$\{x | a^Tx = b\}$$

where $a\in \R^n, a\ne 0, b\in \R$

Let

$$a^\perp = \{v | a^Tv = 0\}$$

Then,

$$\{x | a^Tx = b\} = x_0 + a^\perp$$

where $x_0 \in \{x | a^Tx = b\}$

Halfspace

A hyperplane divides $\R^n$ into two halfspaces. A (closed) halfspace is a set of the form

$$\{x|a^Tx\le b\}$$

where $a\ne 0$

💡

Trivially, half-spaces are convex, but not affine.

Euclidean balls and ellipsoids

A Euclidean ball in $\R^n$ has the form

$$B_r(x_c) = \{x | \|x- x_c\|_2 \le r\}$$

where $r > 0$

💡

In mathematical perspective, we normally erase the boundary to make it an open set.

We can expressed above term differently

$$B_r(x_c) = \{x_c + ru |\; \|u\|_2 \le 1\}$$

A Euclidean ball is a convex set

• Proof

  Let $x_1, x_2 \in B_r(x_c), \theta \ge 0$

  $$\begin{aligned}\|\theta x_1 + (1 - \theta)x_2 - x_c\| &= \|\theta(x_1 - x_c) + (1 - \theta)(x_2 - x_c) \| \\ &\le \|\theta(x_1 - x_c)\| + \|(1 - \theta)(x_2 - x_c)\| \\ & \le \theta + (1- \theta) = 1\end{aligned}$$

  So, $\theta x_1 + (1 - \theta)x_2 \in B_r(x_c)$.

  Therefore, a euclidean ball is convex set.

A ellipsoid in $\R^n$ has the form

$$\mathcal E = \{x | (x- x_c)^TP^{-1}(x - x_c) \le 1\}$$

where $P = P^T \succ 0$ (i.e. $P$ is symmetric and positive definite)

💡

In mathematical perspective, it is a quadratic form and its matrix is positive definite.

We can expressed above term differently

$$\{x_c + Au |\; \|u \|_2 \le 1\}$$

where $A$ is square and nonsingular.

Norm balls and norm cones

A norm ball is the generalization of a Euclidean ball

$$\{x | \; \|x- x_c\| \le r\}$$

A norm cone associated with the norm $\|\cdot \|$ is the set

$$C = \{(x, t) | \; \|x\|\le t \} \subset \R^{n + 1}$$

💡

Note that norm cone is a convex cone. However, we can’t always certain that convex cone is a norm cone (i.e. $\R^2$)

As we proved in Euclidean ball case, a norm ball is also a convex set. Moreover, a norm cone is a convex set

• Proof

  Let $(x_1, t_1) , (x_2, t_2) \in C, \theta \ge 0$, $i.e.$

  $$\|x_1\| \le t_1, \|x_2 \| \le t_2$$

  We want to show that

  $$\theta(x_1, t_1) + (1 - \theta)(x_2, t_2 ) \in C$$

  It is equivalent to check whether

  $$\begin{aligned}\|\theta x_1 + (1 - \theta)x_2\| &\le \|\theta x_1\| + \|(1 - \theta)x_2\| \\ &\le \theta t_1 + (1- \theta) t_2\end{aligned}$$

  Then, $\theta x_1 + (1 - \theta) x_2 \in C$

  Therefore, $C$ is a convex set.

Polyhedra

A polyhedron is defined as the solution set of a finite number of linear equalities and inequalities

$$\mathcal P = \{x | a_j^Tx \le b_j, \; j = 1, \dots, m, \; c_j^Tx = d_j, \; j = 1, \dots, p\}$$

It will be convenient to use the compact notation

$$\mathcal P = \{x | Ax \preceq b, Cx = d\}$$

where the symbol $\preceq$ denotes vector inequality or component-wise inequality in $\R^n$.

A polyhedron is thus the intersection of a finite number of half-space and hyperplanes.

A polyhedron is a convex set

• Proof

  Since half space and hyperplane are convex set, it is enough to show that intersection of convexs set is also a convex set.

  Let $A, B$ is a convex set and $x_1, x_2 \in A\cap B, \theta \ge 0$

  Since $x_1, x_2 \in A$

  $$\theta x_1 + (1 - \theta)x_2 \in A$$

  For the similar reason,

  $$\theta x_1 + (1 - \theta)x_2 \in B$$

  So, $\theta x_1 + (1 - \theta)x_2 \in A\cap B$

  Therefore, the intersection of a convex sets is also a convex set.

  By using this conclusion, we can easily show that a polyhedron is a convex set.

Simplex

Suppose the $k + 1$ points $v_0, \dots, v_k\in \R^n$ are affinely independent, which means $v_1 - v_0, \cdots, v_k - v_0$ are linearly independent

💡

In mathematical perspective, we can view $v_i - v_0 \in T_{v_0}R^n, \forall i$. That means each tangent vectors are linearly independent.

The simplex determined by them is given by

$$\begin{aligned}C &= \text{conv} \{v_0, \dots ,v_k\} \\ &= \{\theta_0v_0 + \cdots + \theta_kv_k|\theta\succeq0, 1^T\theta = 1\}\end{aligned}$$

The affine dimension of this simplex is $k$, so it is sometimes referred to as a k-dimensional simplex in $\R^n$

The four simplexes that can be fully represented in 3D space.

The simplex is so-named because it represents the simplest possible polytope in any given dimension. For example,

• a 0-dimensional simplex is a point

• a 1-dimensional simplex is a line segment

• a 2-dimensional simplex is a triangle

• a 3-dimensional simplex is a tetrahedron

Specifically, a k-simplex is a k-dimensional polytope that is the convex hull of its k + 1 vertices.

Simplex

In geometry, a simplex is a generalization of the notion of a triangle or tetrahedron to arbitrary dimensions. The simplex is so-named because it represents the simplest possible polytope in any given dimension. For example,a 0-dimensional simplex is a point, a 1-dimensional simplex is a line segment, a 2-dimensional simplex is a triangle, a 3-dimensional simplex is a tetrahedron, and a 4-dimensional simplex is a 5-cell.

https://en.wikipedia.org/wiki/Simplex

To describe the simplex as a polyhedron, we proceed as follows.

By definition, $x\in C$ iff $x = \theta_0 v_0 + \cdots + \theta_k v_k$ for some $\theta \succeq 0$ with $1^T\theta = 1$. Define $y = (\theta_1, \dots, \theta_k)$ and

$$B = \begin{bmatrix}v_1 - v_0 & \cdots & v_k - v_0\end{bmatrix} \in \R^{n \times k}$$

we can say that $x\in C$ iff

$$x = v_0 + By$$

💡

It is just a matrix representation of $x$

Since the columns in $B$ are linearly independent, the rank of $B$ is $k$. Therefore, there exists a nonsingular matrix $A = \begin{bmatrix}A_1 \\ A_2\end{bmatrix} \in \R^{n\times n}$ such that

$$AB = \begin{bmatrix}A_1\\A_2\end{bmatrix}B = \begin{bmatrix}I \\0 \end{bmatrix}$$

💡

In mathematical perspective, we can view $A$ as a transition matrix that we use in Gauss elimination process.

Therefore,

$$Ax = Av_0 + ABy \\ \Rightarrow A_1x = A_1 v_0 + y, \; A_2x = A_2v_0$$

From this we can see that $x\in C$ if and only if

$$A_2 x = A_2v_0 \\ y = A_1x - A_1v+0 \\ y\succeq 0 \\ 1^Ty \le 1$$

In other words, we have $x\in C$ iff

$$A_2x = A_2v_0, \; A_1x \succeq A_1v_0, \; 1^TA_1x \le 1 + 1^TA_1v_0$$

which is a set of linear equalities and inequalities in $x$. Therefore, we can express a simplex as a polyhedron.

💡

Re-check the definition of simplex, it is a function with respect to $\theta$ not $x$. By using above reformulation, we can expressed the simplex as a function of $x$.

Positive semidefinite cone

We use the notation $S^n$ to denote the set of symmetric $n\times n$ matrices

$$S^n = \{X \in \R^{n\times n} |\; X = X^T\}$$

Note that $S^n$ is a convex set.

• Proof

  Let $X, Y \in S^n, \theta\ge 0$

  $\theta X + (1 - \theta)Y$ is also symmetric.

  So, $\theta X + (1 - \theta)Y\in S^n$

  Therefore, $S^n$ is a convex set.

We use the notation $S_+^n$ to denote the set of symmetric positive semi-definite matrices

$$S_+^n = \{X\in S^n | \;X\succeq0\}$$

In mathematics, these are equivalent

$$X\in S_+^n \Leftrightarrow z^TXz \ge 0, \forall z$$

Note that $S_+^n$ is a convex cone.

• Proof

  Let $X, Y \in S_+^n$, $\alpha, \beta \ge 0$

  For given z,

  $$z^T(\alpha X + \beta Y )z \Leftrightarrow \langle z, (\alpha X + \beta Y)z\rangle$$

  By using the properties of inner-product,

  $$\begin{aligned}\langle z, (\alpha X + \beta Y)z\rangle &= \langle z, \alpha Xz + \beta Yz\rangle \\ &= \langle z, \alpha Xz\rangle + \langle z, \beta Yz\rangle \\ &= \alpha\langle z, Xz\rangle + \beta \langle z, Yz\rangle \\ &\ge 0\end{aligned}$$

  That means $\alpha X + \beta Y \in S_+^n$

  Therefore, $S_+^n$ is a convex cone.

The notation $S_{++}^n$ to denote the set of symmetric positive definite matrices

$$S_{++}^n = \{X \in S^n|\; X \succ 0\}$$

Boundary of positive semidefinite cone

Operations that preserve convexity

List of preserving convexity

1. Intersection

2. Affine functions
   1. scaling and translation
   2. projection
   3. sum of two sets
   4. partial sum

3. Cartesian product

4. Perspective function

5. Linear fractional function

Intersection

Convexity is preserved under intersection: if $S_1$ and $S_2$ are convex, then $S_1\cap S_2$ is convex.

• Proof

  Let $A, B$ is a convex set and $x_1, x_2 \in A\cap B, \theta \ge 0$

  Since $x_1, x_2 \in A$

  $$\theta x_1 + (1 - \theta)x_2 \in A$$

  For the similar reason,

  $$\theta x_1 + (1 - \theta)x_2 \in B$$

  So, $\theta x_1 + (1 - \theta)x_2 \in A\cap B$

  Therefore, the intersection of a convex sets is also a convex set.

This property extends to the intersection of an infinite number of sets. If $S_\alpha$ is convex for every $\alpha \in \mathcal A$, then $\cap_{\alpha \in \mathcal A} S_\alpha$ is convex.

💡

We still can argue above even though the number of given sets is uncountable.

Affine functions

A function $f : R^n \to R^m$ is affine if it is a sum of a linear function and a constant, i.e. if it has the form

$$f(x) = Ax +b$$

where $A \in \R^{m \times n}, b \in \R^m$

Suppose $S\sub \R^n$ is convex and $f : R^n \to R^m$ is an affine function. Then the image of $S$ under $f$,

$$f(S) = \{f(x) | \; x\in S\}$$

is convex.

💡

The graph of an affine function is an affine set

• Proof

  Let $y_1, y_2\in f(S)$, $\theta \ge 0$. Then there exists $x_1, x_2$ such that

  $$f(x_1) = y_1, \quad f(x_2) = y_2$$

  $$\begin{aligned}\theta y_1 + (1 - \theta)y_2 &= \theta f(x_1) + (1 - \theta) f(x_2) \\ &= f(\theta x_1 + (1-\theta)x_2)\end{aligned}$$

  Since $S$ is a convex set, $\theta x_1 + (1 - \theta) x_2 \in S$. So, $\theta y_1 + (1 - \theta) y_2 \in f(S)$.

  Therefore, $f(S)$ is a convex set.

Similarly, if $f: \R^k \to \R^n$ is an affine function, the inverse image of $S$ under $f,$

$$f^{-1}(S) = \{x |\; f(x) \in S\}$$

is convex.

• Proof

  Let $x_1, x_2\in f^{-1}(S), \theta \ge 0$. Then there exists $y_1, y_2 \in S$ such that

  $$f(x_1) = y_1, \quad f(x_2) = y_2$$

  $$\begin{aligned}f(\theta x_1 + (1 - \theta)x_2) &= \theta f(x_1) + (1-\theta) f(x_2) \\ &\in S\end{aligned}$$

  So, $\theta x_1 + ( 1- \theta) x_2\in f^{-1}(S)$.

  Therefore, $f^{-1}(S)$ is a convex set.

Example : scaling and translation

If $S \subset \R^n$ is convex, $\alpha \in \R$ and $a\in \R^n$, then the sets $\alpha S, S + a$ are convex, where

$$\alpha S = \{\alpha x |\; x\in S\}, \quad S + a = \{x + a | \; x\in S\}$$

• Proof

  If $\alpha = 0$, $\alpha S$ and $S + a$ are trivially convex sets. Therefore, without loss of generality, we may assume $\alpha > 0$.

  Let $x, y\in \alpha S, \theta\ge 0$. Then, $x/\alpha , y/\alpha \in S$

  Since $S$ is a convex set,

  $$\theta x/\alpha + (1 - \theta)y/\alpha\in S$$

  So, $\alpha(\theta x/\alpha + (1 - \theta)y/\alpha) = \theta x + (1-\theta)y\in \alpha S$.

  Therefore, $\alpha S$ is a convex set.

  Similarly, $x, y\in S + a, \theta\ge 0$. Then $x - a, y-a \in S$

  Since $S$ is a convex set

  $$\theta(x -a ) + (1 - \theta)(y - a)\in S$$

  So, $\theta(x -a ) + (1 - \theta)(y - a) + a = \theta x + (1 - \theta)y \in S + a$

  Therefore, $S + a$ is a convex set.

Example : projection

The projection of a convex set onto some of its coordinates is convex. If $S \sub \R^m \times \R^n$ is convex, then

$$T = \{x_1\in \R^m |\;(x_1, x_2)\in S\text{ for some }x_2\in \R^n\}$$

is convex.

• Proof

  Let $x_1, x_2 \in T, \theta \ge 0$. Then there exists $y_1, y_2\in \R^n$ such that

  $$(x_1, y_1) \in S \quad (x_2, y_2) \in S$$

  Since, $S$ is a convex set

  $$\theta(x_1, y_1) + (1-\theta)(x_2, y_2) = (\theta x_1 + (1 - \theta)x_2, \theta y_1 + (1 - \theta)y_2)$$

  So, $\theta x_1 + (1 - \theta)x_2\in T$.

  Therefore, $T$ is a convex set.

Example : sum of two sets

The sum of two sets is defined as

$$S_1 + S_2 = \{x + y|\; x\in S_1, y\in S_2\}$$

If $S_1$ and $S_2$ are convex, then $S_1 + S_2$ is convex.

• Proof

  Let $z_1, z_2\in S_1 + S_2, \theta \ge 0$. Then there exists $x_1, x_2\in S_1, y_1, y_2\in S_2$ such that

  $$z_1 = (x_1, y_1) \quad z_2 = (x_2, y_2)$$

  $$\begin{aligned}\theta z_1 + (1 - \theta)z_2 &= \theta(x_1, y_1) + (1-\theta) (x_2, y_2) \\ &= (\theta x_1, \theta y_1) + ((1-\theta)x_2, (1-\theta)y_2) \\ &= (\theta x_1 + (1 -\theta) x_2, \theta y_1 + (1 -\theta) y_2)\end{aligned}$$

  Since $\theta x_1 + (1 -\theta) x_2 \in S_1, \theta y_1 + (1 -\theta) y_2 \in S_2$, $\theta z_1 + (1-\theta)z_2\in S_1 + S_2$.

  Therefore, $S_1 + S_2$ is a convex set.

Example : partial sum

The partial sum of $S_1, S_2\in \R^n\times \R^m$, defined as

$$S = \{(x, y_1+y_2) | \; (x, y_1)\in S_1, (x, y_2)\in S_2\}$$

where $x\in \R^n, y_i\in\R^m$

• Proof

  Let $z_1, z_2 \in S, \theta \ge 0$. Then there exists $x_1, x_2 \in \R^n, y_{11}, y_{12}, y_{21}, y_{22}\in \R^m$ such that

  $$z_1 = (x_1, y_{11} + y_{12}) \quad z_2 = (x_2, y_{21} + y_{22})$$

  $$\begin{aligned}\theta z_1 + (1 - \theta)z_2 &= \theta(x_1, y_{11} + y_{12}) + (1 -\theta) (x_2, y_{21} + y_{22}) \\ &= (\theta x_1 + (1-\theta) x_2, \theta(y_{11} + y_{12}) + (1-\theta)(y_{21} + y_{22}))\end{aligned}$$

  Since $\theta x_1 + (1- \theta) x_2 \in S_1, \theta(y_{11} + y_{12}), (1-\theta)(y_{21} + y_{22}) \in S_2 , \theta z_1 + (1- \theta) z_2\in S$.

  Therefore, $S$ is a convex set.

Cartesian product

The Cartesian product of two convex sets

$$S_1 \times S_2 =\{(x_1, x_2) |\; x_1\in S_1, x_2\in S_2\}$$

is a convex set.

• Proof

  Let $z_1, z_2\in S_1 \times S_2, \theta \ge 0$. Then there exists $x_1, x_2\in S_1, y_1, y_2\in S_2$ such that

  $$z_1 = (x_1, y_1) \quad z_2 = (x_2, y_2)$$

  $$\begin{aligned}\theta z_1 + (1 - \theta)z_2 &= \theta(x_1, y_1) + (1-\theta)(x_2, y_2) \\ &= (\theta x_1 + (1 -\theta) x_2, \theta y_1 + (1 -\theta) y_2) \end{aligned}$$

  Since $\theta x_1 + (1-\theta) x_2 \in S_1, \; \theta y_1 + (1-\theta) y_2 \in S_2$, $\theta z_1 + (1 - \theta)z_2 \in S_1 \times S_2$.

  Therefore, $S_1\times S_2$ is a convex set.

Perspective function

Define the perspective function $P : \R^{n + 1}\to \R^n$, with domain $\text{dom }P = \R^n \times \R_{++}$, as

$$P(z, t) = z/t$$

where $\R_{++}$ denotes the set of positive numbers. The perspective function scales or normalizes vectors so the last component is one, and then drops the last component.

💡

Since we eliminate the case when $t = 0$, we don’t have to worry about that.

If $C\sub \text{dom }P$ is convex, then its image

$$P(C) = \{P(x) |\; x\in C\}$$

is convex.

• Proof

  Let $x, y\in P(C), \theta \ge 0$. Then there exists $z_1, z_2 \in \R^n, t_1, t_2\in \R$ such that

  $$x = P(z_1, t_1) = z_1/t_1 \quad y = P(z_2, t_2)=z_2/t_2 \\ \begin{aligned}\theta x + (1 - \theta)y &= \theta P(z_1, t_1) + (1 - \theta)P(z_2, t_2) \end{aligned}$$

  We want to find $\mu$ such that

  $$P(\mu(z_1, t_1) + (1- \mu)(z_2, t_2)) = \theta P(z_1, t_1) + (1 - \theta)P(z_2, t_2) \\ \Rightarrow \mu z_1 + (1 - \mu)z_2 / \mu t_1 + (1 - \mu)t_2 = \theta z_1 / t_1 + (1 - \theta)z_2/t_2 \\ \Rightarrow \mu = \frac{\theta t_1}{\theta t_1 + (1-\theta)t_2}$$

  Since $\mu\ge 0$ and $C$ is a convex set,

  $$\begin{aligned}\mu(z_1, t_1) + (1 - \mu)(z_2, t_2)\in C &\Rightarrow P(\mu(z_1, t_1) + (1 - \mu)(z_2, t_2)) \in P(C) \\ &\Rightarrow \theta P(z_1, t_1) + (1- \theta) P(z_2, t_2)\in P(C) \\ & \Rightarrow \theta x + (1 - \theta)y \in P(C)\end{aligned}$$

  Therefore, $P(C)$ is a convex set.

  

  We can interpret the relation between $\mu$ and $\theta$ like this. Since two triangulars are similar,

  $$\mu : (1-\mu) = \theta t_1 : (1-\theta)t_2$$

  By using this, we can easily derive

  $$\mu = \frac{\theta t_1}{\theta t_1 + (1-\theta)t_2}$$

We can also show that the line segments are mapped to line segments under the perspective function. The result can be interpreted as a concept of a pin-hole camera.

The inverse image of a convex set under the perspective function is also convex.

If $C\sub \R^n$ is convex, then

$$P^{-1}(C) = \{(x, t) \in \R^{n + 1}|\; x/t\in C, t> 0\}$$

is convex.

• Proof

  Let $(x_1, t_1), (x_2, t_2) \in P^{-1}(C), \theta\ge 0$.

  We want to show that $\theta(x_1, t_1) + (1-\theta)(x_2, t_2)\in P^{-1}(C)$, i.e.

  $$(\theta x_1 + (1-\theta)x_2, \theta t_1 + (1 - \theta)t_2)\in P^{-1}(C) \\ \Leftrightarrow \frac{\theta x_1 + (1-\theta)x_2}{\theta t_1 + (1 - \theta)t_2} \in C$$

  We want to find $\mu \ge 0$ such that

  $$\mu(x_1/t_1) + (1 - \mu)(x_2/t_2) = \frac{\theta x_1 + (1-\theta)x_2}{\theta t_1 + (1 - \theta)t_2}$$

  Take

  $$\mu = \frac{\theta t_1}{\theta t_1 + (1-\theta)t_2}$$

  Since $x_1/t_1, x_2/t_2\in C$ and $C$ is a convex set,

  $$\mu(x_1/t_1) + (1 - \mu)(x_2/t_2)\in C \\ \Leftrightarrow \theta(x_1, t_1) + (1-\theta)(x_2, t_2)\in P^{-1}(C)$$

  Therefore, $P^{-1}(C)$ is a convex set.

Linear-fractional functions

A linear-fractional function is formed by composing the perspective function with an affine function. Suppose $g: \R^n \to \R^{m + 1}$ is affine, i.e.

$$g(x) = \begin{bmatrix}A \\ c^T\end{bmatrix} x + \begin{bmatrix}b \\ d\end{bmatrix}$$

where $A\in \R^{m \times n}, b\in \R^m, c\in \R^n$, and $d\in \R$. The function $f : \R^n\to \R^m$ given by $f = P\circ g$ such that

$$f(X) = \frac{Ax + b}{ c^Tx + d}$$

where $\text{dom f} = \{x|\; c^Tx + d > 0\}$

is called a linear-functional (or projective) function. If $c = 0$ and $d > 0$, the domain of $f$ is $\R^n$, and $f$ is an affine function.

💡

Images and inverse images of convex sets under linear-fractional functions is a convex set.

Example

$$f(x) = \frac{1}{x_1 + x_2 + 1}x$$

Generalized inequalities

Proper cones and generalized inequalities

A cone $K\sub \R^n$ is called a proper cone if it satisfies the following

1. $K$ is convex

2. $K$ is closed

3. $K$ is solid (it has nonempty interior)

4. $K$ is pointed, which means that it contains no line (or equivalently, $x\in K, -x\in K \Rightarrow x = 0$)

Examples

1. nonnegative orthant $K = \R_+^n = \{x\in \R^n|\; x_i \ge 0, i = 1, \dots, n\}$

2. positive semidefinite cone $K = S_+^n$

3. nonnegative polynomials on $[0, 1]$

   $$K = \{x \in \R^n|\; x_1 + x_2 t+ x_3 t^2 + \cdots + x_n t^{n - 1}\ge 0 \text{ for } t\in [0, 1]\}$$

A proper cone $K$ can be used to define generalized inequality, which is a partial ordering on $\R^n$ that has may of the properties of the standard ordering on $\R$ defined by

$$x \preceq_K y \Leftrightarrow y - x \in K \\ x \prec_K y \Leftrightarrow y - x \in \text{int }K$$

Actually, we have to check whether the above definition satisfy the following conditions

For all $a, b, c \in \R^n$,

Partial orders

1. Reflexivity : $a\le a$ (every element is related to itself)

2. Antisymmetry : if $a\le b$ and $b \le a$ then $a = b$ (no two distinct elements precede each other)

3. Transitivity : if $a\le b$ and $b \le c$ then $a \le c$

Strict partial orders

1. Ir-reflexivity : not $a < a$ (no element is related to itself)

2. Asymmetry : if $a < b$ then not $b < a$

3. Transitivity : if $a\le b$ and $b \le c$ then $a \le c$

Examples

1. component-wise inequality ($K = \R_+^n)$

   $$x\preceq_{\R_+^n}y \Leftrightarrow x_i \le y_i, i = 1, \dots, n$$

2. matrix inequality ($K = S_{+}^n$)

   $$X\preceq_{S_+^n}Y \Leftrightarrow Y - X \text{ positive semi-definite}$$

💡

these two types are so common that we normally drop the subscript in $\preceq_K$

💡

These are not total ordering (i.e. there are some elements that are not comparable by using this order relation)

Properties

many properties of $\preceq_K$ are similar to $\le$ on $\R$

1. $\preceq_K$ is preserved under addition

   $$x\preceq_K y, u\preceq_K v \Rightarrow x+u \preceq_K y+ v$$

   • Proof

     $y - x\in K$ and $v - u\in K$. Since $K$ is a proper cone,

     $$(y - x) + (v - u)\in K \\ \Rightarrow y + v - (x + u) \in K \text{ (associative in }\R^n) \\ \Rightarrow x + u\preceq_Ky + v$$

2. $\preceq_K$ is preserved under non-negative scaling

   $$x\preceq_K y, \alpha \ge 0 \Rightarrow \alpha x \preceq_K \alpha y$$

   • Proof

     $y - x \in K$. Since $\alpha > 0$ $\alpha > 0$$K$ is a proper cone,

     $$\alpha(y - x) \in K \\ \Rightarrow \alpha y - \alpha x \in K \\ \Rightarrow \alpha x \preceq_K \alpha y$$

3. $\preceq_K$ is preserved under limits

   If $x_i\preceq_K y_i$ for $i = 1, 2, \dots$ and $x_i \to x$ and $y_i \to y$ as $i \to \infty$, then $x\preceq_K y$

   • Proof

     $y_i - x_i \in K, \forall i$ and $y_i - x_i \to y - x$ as $i \to \infty$

     Since $K$ is closed (it contains all of its limit points),

     $$y- x\in K$$

     Therefore, $x\preceq_Ky$

Minimum and minimal elements

A point $x\in S$ is the minimum element of $S$ with respect to $\preceq_K$ if

$$\forall y\in S, x\preceq_K y$$

If a set has a minimum element, then it is unique.

• Proof

  Let $x$ and $y$ are minimum element of $S$. Then,

  $$\forall z\in S, z\preceq_K x \\ \forall z\in S, z \preceq_K y$$

  Therefore,

  $$y \preceq_K x \text{ and } x\preceq_Ky$$

  By anti-symmetry,

  $$x = y$$

  Therefore, it is unique.

A point $x\in S$ is the minimal element of $S$, if

$$\nexists y\in S, y \preceq_K x \text{ and } x\ne y$$

💡

If a set $X$ has a minimum element, then all elements in $X$ are comparable with respect to $\preceq_K$.

Example

When $K = \R_+^2$,

$x_1$ is the minimum element of $S_1$

$x_2$ is a minimal element of $S_2$ since the yellow regions are not comparable to $x_2$.

Separating hyperplane

If $C$ and $D$ are disjoint convex sets, then there exists $a\ne 0, b$ such that

$$\forall x\in C, a^Tx \le b \\ \forall x\in D, a^Tx \ge b$$

the hyperplane $\{x |\; a^Tx = b\}$ separates $C$ and $D$

strict separation requires additional assumptions (e.g. $C$ is closed, $D$ is a singleton)

Supporting hyperplane theorem

supporting hyperplane to set $C$ at boundary point $x_0$:

$$\{x |\; a^Tx = a^T x_0\}$$

where $a\ne 0, \forall x\in C, a^Tx \le a^Tx_0$

supporting hyperplane theorem : if $C$ is convex, then there exists a supporting hyperplane at every boundary point of $C$

💡

Note that the normal vector $a$ directs to the opposite side of the $C$

Dual cones and generalized inequalities

Let $K$ be a cone. The set

$$K^* = \{y | \; y^Tx \ge 0,\forall x\in K\}$$

is called the dual cone of $K$. As the name suggests, $K^*$ is a cone, and is always convex, even when the original cone $K$ is not.

• Proof

  Let $y_1, y_2\in K^*, \theta \ge 0$.

  Therefore, $y_1^T x\ge 0$ and $y_2^Tx \ge 0$ for all $x\in K$

  We want to show that $\theta y_1 + (1 - \theta)y_2\in K^*$ i.e.

  $$(\theta y_1 + (1 - \theta) y_2)^Tx \ge 0, \forall x\in K \\ \Leftrightarrow \theta y_1^Tx + (1-\theta)y_2^Tx \ge 0, \forall x\in K$$

  Since $y_1^T x\ge 0$ and $y_2^Tx \ge 0$ for all $x\in K$,

  $$\theta y_1^Tx + (1 - \theta)y_2^Tx \ge 0$$

  So, $\theta y_1 + (1 - \theta)y_2\in K^*$

  Therefore, $K^*$ is a convex set.

  💡

  There is no requirement of convexity of $K$

Geometrically, $y\in K^*$ if and only if $-y$ is the normal of a hyperplane that supports $K$ at the origin.

Examples

1. $K = \R_+^n, K^* = \R_+^n$

2. Dual of a norm cone. Let $\|\cdot\|$ be a norm on $\R^n$. The dual of the associated cone $K = \{(x, t)\in \R^{n + 1}|\; \|x\|\le t\}$ is the cone defined by the dual norm

   $$K^* = \{(u, v)\in \R^{n + 1}|\; \|u\|_* \le v\}$$

   where the dual norm is given by $\|u\|_* = \sup \{u^Tx |\; \|x\|\le 1\}$

   • Proof

     We want to show that

     $$\forall x\in K, x^Tu + tv \ge 0 \Leftrightarrow \|u\|_*\le v \\ \Rightarrow \|x\|\le t \Rightarrow x^Tu + tv \ge 0 \Leftrightarrow \|u\|_* \le v$$

     TBC

   Note that

   $$\sup\{u^Tx |\; \|x\|_2\le 1\} = \|u\|_2 \\ \sup\{u^Tx |\; \|x\|_1\le 1\} = \|u\|_\infty \\ \\ \sup\{u^Tx |\; \|x\|_\infty\le 1\} = \|u\|_1$$

Properties

1. $K^*$ is closed and convex

2. $K_1\sub K_2 \Rightarrow K_2^* \sub K_1^*$

3. If $K$ has non-empty interior, then $K^*$ is pointed

4. If the closure of $K$ is pointed then $K^*$ has non-empty interior.

5. $K^{**}$ is the closure of the convex hull of $K$ (Hence if $K$ is convex and closed, $K^{**} = K$)

💡

These properties show that if $K$ is a proper cone, then so is its dual $K^*$, and moreover, that $K^{**} = K$

Dual generalized inequalities

Suppose that the convex cone $K$ is proper, it induces a generalized inequality $\preceq_K$. Then its dual cone $K^*$ is also proper, and therefore, induces a generalized inequality.

$$y\succeq_{K^*}0 \Leftrightarrow y^Tx\ge 0, \forall x\succeq_K 0$$

Example : positive semi-definite cone

On the set of symmetric $n\times n$ matrices $S^n$, we use the standard inner proudct $\text{tr}(XY) = \sum_{i, j}X_{ij}Y_{ij}$. The positive semi-definite cone $S_{+}^n$ is self-dual. i.e. for $X, Y\in S^n$

$$\text{tr}(XY)\ge 0, \forall X\succeq 0 \Leftrightarrow Y\succeq 0$$

• Proof

  Suppose $Y\notin S_{+}^n$. Then there exists $y\in \R^n$ with

  $$q^TYq = \text{tr}(qq^TY) < 0$$

  Since $X= qq^T$ is a positive semi-definite matrix, $Y\notin (S_{+}^n)^*$

  Now suppose $X, Y\in S_+^n$. We can express $X$ as a linear combination of rank-one matrix by using eigenvalue decomposition.

  $$X = \sum_{i = 1}^n \lambda_i q_iq_i^T$$

  Then,

  $$\begin{aligned}\text{tr}(YX) &= \text{tr}(Y\sum_{i = 1}^n \lambda_iq_iq_i^T) \\ &= \sum_{i = 1}^n\lambda_iq_i^TYq_i \\ & \ge 0\end{aligned}$$

  Therefore, $Y \in (S_+^n)^*$

Minimum and minimal elements via dual inequalities

We can use dual generalized inequalities to characterize minimum and minimal elements of a set $S\sub \R^n$ with respect to the generalized inequality induced by a proper cone $K$

Minimum element w.r.t $\preceq_K$

$x$ is a minimum element of $S$ if and only if for all $\lambda\succ_{K^{*}}0$, $x$ is the unique minimizer of $\lambda^Tz$ over $z\in S$. Geometrically, this means that for any $\lambda \succ_{K^*}0$, the hyperplane

$$\{z|\lambda^T(z - x) = 0\}$$

is a strict supporting hyperplane to $S$ at $x$. Equivalently, this means that the hyperplane intersects $S$ only at the point $x$

💡

We can think the level surface which has a normal vector as a $\lambda$

Minimal element w.r.t $\preceq_K$

If $x$ minimizes $\lambda^Tz$ over $S$ for some $\lambda \succ_{K^*}0$, then $x$ is minimal

💡

We only consider the specific $\lambda\in K^*$. It basically related to the supporting hyperplane.

If $x$ is a minimal element of a convex set $S$, then there exists a nonzero $\lambda\succeq_{K^*}0$ such that $x$ minimizes $\lambda^Tz$ over $S$.

💡

Justification of finding the supporting hyperplane for all point in the convex set.

If $S$ is not a convex, we can’t guarantee that there exists such $\lambda$

In this case, $x$ is a minimal point of $S$ with respect to $\R_{+}^2$. However, there doesn’t exist $\lambda$ for which $x$ minimizes $\lambda^Tz$ over $z\in S$