Convex Sets

Convex and Affine Set

Line in Euclidean Space

A line through two points $x_1,x_2$ is defined as $x=\theta x_1+(1-\theta )x_2,(\theta \in \mathbb{R})$ A line segment between two points $x_1,x_2$ is defined as $x=\theta x_1+(1-\theta )x_2,(\theta \in [0,1])$

Affine Set

An affine set contains the line through any two distinct points in the set:$x_1,x_2\in affine\; setS⟹\forall \theta \in \mathbb{R}.\theta x_1+(1-\theta )x_2\in S.$

e.g. An entire 2D plane.

Theorem

Every affine set can be expressed as the solution set of a system of linear equations.

Convex Set

Let $X$ be a vector space. A subset $C$ of $X$ is convex if whenever $x,y\in C$ and $0\le \theta \le 1$, we have �$\theta x+(1-\theta )y\in C$. That is it contains the line segment between any two distinct points in the set:$x_1,x_2\in \text{convex set }C⟹\forall \theta \in [0,1],\theta x_1+(1-\theta )x_2\in C$

e.g.

Convex Combination

A convex combination of $x_1,\dots ,x_k$ is any point of the form:$x={\theta }_1{x}_1+{\theta }_2{x}_2+...+{\theta }_k{x}_k$with ${\theta }_1+{\theta }_2+\dots +{\theta }_k=1$ and ${\theta }_i\ge 0$.

Convex Hull

The convex hull of a set of points $S$, denoted $\mathrm{conv}(S)$, is the set of all convex combinations of the points in $S$.

Proposition

The convex hull is the smallest convex set to contain all the points in the set $S$.

Cones

Convex Cone

Conic Combination

A conic combination of points $x_1$ and $x_2$ is any point of the form: $x={\theta }_1{x}_1+{\theta }_2{x}_2$ with ${\theta }_1\ge 0$ and ${\theta }_2\ge 0$.

Cone

A cone is a set $S$ containing all non-negative multiples of its points: $x\in S,\theta \ge 0⟹\theta x\in S$

Convex Cone

A convex cone is a set containing all conic combinations of its points.

Proper Cone

A convex cone $K\subseteq {\mathbb{R}}^n$ is a proper cone if

• $K$ is closed (contains its boundary)
• $K$ is solid (has nonempty interior)
• $K$ is pointed (contains no line i.e. $x,-x\in K⟹x=0$)

e.g.

• Nonnegative orthant ${\mathbb{R}}_{+}^q$ is a proper cone.
• Positive semidefinite matrices ${\mathbb{S}}_{+}^n$ is a proper cone.
• Second-order cone $K=\left\{y\in {\mathbb{R}}^{n+1}\mid \sqrt{y_1^2+\cdots +y_n^2}\le y_{n+1}\right\}$ is proper.

Dual Cone

The dual cone of a cone $K$ is$K^{\ast }=\{y\mid y^{\top }x\ge 0\text{ for all }x\in K\}$

Positive Semidefinite Cone

Real Symmetric Matrices

We have the following notation for real symmetric matrices:

• ${\mathbb{S}}^n$ is the set of symmetric $n\times n$ matrices
• ${\mathbb{S}}_{+}^n\subset {\mathbb{S}}^n$: positive semidefinite $n\times n$ matrices: $X\in {\mathbb{S}}_{+}^n⟺z^{\top }Xz\ge 0\text{ for all }z$
• ${\mathbb{S}}_{++}^n\subset {\mathbb{S}}^n$: positive definite $n\times n$ matrices

Proposition

Prop $X\in {\mathbb{S}}_{+}^n$ iff all eigenvalues are real and nonnegative.

Proposition

Prop ${\mathbb{S}}_{+}^n$ is a convex cone.

Hyperplanes, Halfspaces and Polyhedron

Hyperplane

A hyperplane is a set of the form $\{x\mid a^{\top }x=b\}$ with $a\ne 0$. And we call $a$ the normal vector.

Halfspace

Halfspace is a set of the form $\{x\mid a^{\top }x\le b\}$ with $a\ne 0$.

Prop Convexity of Hyperplane and Halfspace Hyperplanes are affine and convex, while halfspaces are convex.

Polyhedron

A polyhedron is the intersection of a finite number of halfspaces and hyperplanes.

Proposition

A polyhedron is the solution set of finitely many linear inequalities and equalities: $Ax⪯b,Cx=d$ where $A\in {\mathbb{R}}^{m\times n}$, $C\in {\mathbb{R}}^{p\times n}$, $⪯$ is component-wise inequality.

Polytope

A polytope is a bounded polyhedron, i.e. a polyhedron with a finite number of extreme points. Equivalently, it is the convex hull of a finite number of points.

Balls and Norm

Euclidean Balls and Ellipsoids

Def Euclidean Ball A (Euclidean) ball with centre $x_c$ and radius $r$ is a set of the form:

$$B(x_c,r)=\{x\mid \Vert x-x_c{\Vert }_2\le r\}=\{x_c+ru\mid \Vert u{\Vert }_2\le 1\}$$

Def Ellipsoid An ellipsoid is a set of the form:

$$\{x\mid (x-x_c{)}^{\mathrm{T}}{P}^{-1}(x-x_c)\le 1\}$$

where $P\in {\mathbb{S}}_{++}^n$ (i.e. $P$ is symmetric positive definite) Alternatively, we can represent an ellipsoid as $\{x_c+Au\mid \Vert u{\Vert }_2\le 1\}$ with A square and nonsingular.

Norm Balls and Norm Cones

Def Norm Cone A norm ball with centre $x_c$ and radius $r$ is the set $\{x\mid \Vert x-x_c\Vert \le r\}$. A norm cone is the set $\{(x,t)\mid \Vert x\Vert \le t\}$. The Euclidean norm cone is also called the second-order cone.

Prop Norm balls and norm cones are convex.

Summary of Common Convex Sets

Operations that Preserve Convexity

Proposition

The intersection of arbitrarily many convex sets is convex.

Def Affine Function A function $f:{\mathbb{R}}^n\to {\mathbb{R}}^m$ is affine if $f(x)=Ax+b$ with $A\in {\mathbb{R}}^{m\times n}$, $b\in {\mathbb{R}}^m$.

Prop The image of a convex set under affine function $f$ is convex: $S\subseteq {\mathbb{R}}^n\text{ convex }⟹f(S)=\{f(x)\mid x\in S\}\text{ convex}.$

Proposition

The inverse image $f^{-1}(C)$ of a convex set under affine function $f$ is convex:$C\subseteq {\mathbb{R}}^m\text{ convex }⟹f^{-1}(C)=\{f^{-1}(x)|x\in C\}\text{ convex}.$

Perspective Function

A perspective function $P:{\mathbb{R}}^{n+1}\to {\mathbb{R}}^n$ is defined as: $P(x,t)=x/t,\text{dom}(P)=\{(x,t)\mid t>0\}$

Prop Images and inverse images of convex sets under perspective are convex.

Def Linear-Fractional Function A linear-fractional function is defined as:$f(x)=\frac{Ax+b}{c^{\mathrm{T}}x+d},\text{dom}(f)=\{x\mid c^{\mathrm{T}}x+d>0\}$

Prop Images and inverse images of convex sets under linear-fractional functions are convex.

Generalized Inequalities

Generalized Inequality

A generalized inequality relation defined by a proper cone $K$ satisfies $x{⪯}_{K}y⟺y-x\in K,x{\prec }_{K}y⟺y-x\in \text{interior}(K)$where $\text{interior}(K)$ denotes the interior of $K$.

Prop ${⪯}_K$ is a partial order, but not in general a linear order.

Prop $x{⪯}_{K}y,u{⪯}_{K}v⟹x+u{⪯}_{K}y+v$.

Minimum

$x\in S$ is the minimum element of $S$ with respect to ${⪯}_K$ if $y\in S⟹x{⪯}_{K}y$

Minimal

$x\in S$ is a minimal element of $S$ with respect to ${⪯}_K$ if (for any) $y\in S,y{⪯}_{K}x⟹y=x$

e.g. Here $K={\mathbb{R}}_{+}^2$. $x_1$ is the minimum element of $S_1$; $x_2$ is a minimal element of $S_2$

Proposition

Minimum if exists, must be unique; however, several minimals may be found for $S$ given an generalized inequality ${⪯}_K$ induced by a proper cone $K$.

Separating Hyperplane Theorem

If $C$ and $D$ are nonempty disjoint convex sets, there exists $a\ne 0$ and $b$ such that$a^{\top }x\le b\text{ for }x\in C,a^{\top }x\ge b\text{ for }x\in D$That is the hyperplane $\{x\mid a^{\top }x=b\}$ separates $C$ and $D$.

Supporting Hyperplane Theorem

A supporting hyperplane to set $C$ at boundary point $x_0$ is$\{x\mid a^{\mathrm{T}}x=a^{\mathrm{T}}{x}_0\}$where $a\ne 0$ and $a^{\mathrm{T}}x\le a^{\mathrm{T}}{x}_0$ for all $x\in C$. And if $C$ is convex, then there exists a supporting hyperplane at every boundary point of $C$.