[응용수학특강] 볼록 집합 (Convex Set)

Convex Set

Affine and Convex Sets

Definition of Affine and Convex Sets

Line: through $x_{1},x_{2}:$ all points

$$x=\theta x_{1}+(1-\theta)x_{2};(\theta \in \mathbb{R})$$

Affine set: contains the line through any two distinct points in the set

Example: solution set of linear eqautions ${ \textbf{x} | \textbf{Ax}=\textbf{b} }$

(Conversely, every affine set can be expressed as solution set of system of linear equations) subspace는 안되더라도 affine set은 될 수 있다.

Line segment: between $x_{1}$ and $x_{2}$: all points

$$x=\theta x_{1}+(1-\theta)x_{2};; (0\leq \theta \leq1)$$

Convex set: contains line segment between any two points in the set $C$

$$x_{1},x_{2} \in C, 0 \leq \theta \leq 1 \Rightarrow \theta x_{1}+(1- \theta)x_{2} \in C$$

Some Important Examples

Hyperplane: set of the form ${\textbf{x}|\textbf{a}^{T}\textbf{x}=b }(\textbf{a} \neq \textbf{0})$

Halfspace: set of the form ${\textbf{x} |\textbf{a}^{T}\textbf{x} \leq b }(\textbf{a} \neq \textbf{0})$

• $\textbf{a}$ is the normal vector
• hyperplanes are affine and convex, halfspaces are convex

Polyhedra: Solution set of finitely many linear inequalities and equalities

$$\textbf{Ax} \preceq \textbf{b},;\textbf{C}\textbf{x} = \textbf{d}$$

($\textbf{A} \in \mathbb{R}^{m \times n}$, $\textbf{C} \in \mathbb{R}^{p \times n}$, $\preceq$ is component-wise inequality)

Polyhedron is intersection of finite number of halfspaces and hyperplanes.

Euclidean ball with center $x_{c}$ and radius $r$:

$$B(\textbf{x}{c},r)={\textbf{x}| \Vert \textbf{x}-\textbf{x}{c} \Vert_{2} \leq r } = { \textbf{x}{c}+r\textbf{u}| \Vert\textbf{u} \Vert{2} \leq 1 }$$

Ellipsoid: set of the form

$$\begin{aligned} E(x_{c},\textbf{P})& = {\textbf{x}|(\textbf{x}-\textbf{x}{c})\textbf{P}^{-1}(\textbf{x}-\textbf{x}{c}) \leq 1 } \ & = { \textbf{x}{c}+\textbf{Au}| \Vert \textbf{u} \Vert{2} \leq 1 } \end{aligned}$$

with $\textbf{P} \in \mathbb{S}_{++}^{n}$ (i.e. $\textbf{P}$ is symmetric positive definite), $\textbf{A}$ is square and nonsingular.

Convex combination of $\textbf{x}{1}, \cdots, \textbf{x}{k}$: any point $\textbf{x}$ of the form

$$\textbf{x}= \theta_{1}\textbf{x}{1} + \cdots + \theta{k}\textbf{x}_{k}$$

with $\theta_{1}+\cdots+\theta_{k}=1, \theta_{i} \geq0$

Convex hull conv $S$: set of all convex combinations of points in $S$

Conic combination of $\textbf{x}{1}$ and $\textbf{x}{2}$: any point of the form

$$\textbf{x}=\theta_{1}\textbf{x}{1}+\theta{2}\textbf{x}_{2}$$

with $\theta_{1}, \theta_{2} \geq 0$

Convex cone: set that contains all conic combinations of points in the set

Positive Semidefinite Cone

Notation

• $\mathbb{S}^{n}$ is set of symmetrix $n \times n$ matrices
• $\mathbb{S}^{n}_{+} = { \textbf{X} \in \mathbb{S}^{n}|\textbf{X} \succeq 0 }$: positive semidefinite $n \times n$ matrices

$$\textbf{X} \in \mathbb{S}^{n}_{+} \Leftrightarrow z^{T}\textbf{X}z \geq 0 ; \forall z$$

• $\mathbb{S}_{+}^{n}$ is convex cone
• $\mathbb{S}_{++}^{n}= {\textbf{X} \in \mathbb{S}^{n} | \textbf{X} \succ 0 }$: positive definite $n \times n$ matrices

Operations that Preserve Convexity

How to establish the convexity of a given set $C$

• Apply the definition (can be cumbersome)

$$x_{1},x_{2} \in C, 0 \leq \theta \leq 1 \Rightarrow \theta x_{1}+(1-\theta)x_{2} \in C$$

• Show that $C$ is obtained from simple convex set(hyperplanes, halfspaces, norm balls, $\cdots$) by operations that preserve convexity
• intersection
• affine functions
• perspective function
• linear-fractional functions

Intersection

If $S_{1},\cdots,S_{k}$ are convex, then $S_{1} \cap \cdots \cap S_{k}$ is convex.

Ex

• Polyhedron is the intersection of halfspaces and hyperplanes

Affine Function

Suppose $f: \mathbb{R}^{n} \rightarrow \mathbb{R}^{m}$ is affine ($f(x)=\textbf{A}\textbf{x}+\textbf{b}$ with $\textbf{A} \in \mathbb{R}^{m \times n}, \textbf{b} \in \mathbb{R}^{m}$)

• the image of convex set under $f$ is convex
• the inverse image $f^{-1}(C)$ a convex set under $f$ is convex

Ex

• scaling, translation, projection
• solution set of linear matrix inequality ${\textbf{x} | x_{1}\textbf{A}{1}+\cdots+x{m}\textbf{A}_{m} \preceq \textbf{B} }$

Perspective and Linear-fractional Function

Perspective function $P: \mathbb{R}^{n+1} \rightarrow \mathbb{R}^{n}$

$$P(\textbf{x},t)=\frac{\textbf{x}}{t},;; domP={(\textbf{x},t)|t> 0}$$

images and inverse images of convex sets under perspective are convex

Linear-fractional function $f:\mathbb{R}^{n}\rightarrow\mathbb{R}^{m}$

$$f(\textbf{x})=\frac{\textbf{A}\textbf{x}+\textbf{b}}{\textbf{c}^{T}\textbf{x}+d},;; domf={\textbf{x}|\textbf{c}^{T}\textbf{x}+d >0 }$$

Generalized Inequalities

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

• $K$ is closed (contains its boundary)
• $K$ is solid (has non-empty interior)
• $K$ is pointed (contains no line)

Ex

• non-negative orthant
• positive semidefinite cone
• non-negative polynomials on $[0,1]$

Generalized inequality defined by a proper cone $K$:

$$y \succeq_{K} x \Leftrightarrow y-x \succeq0 ;; or ;; y-x \in K$$

Ex

• Component-wise inequality ($K=\mathbb{R}^{n}_{+}$)
• Matrix inequality ($K=\mathbb{S}^{n}_{+}$)

Separating Hyperplane Theorem

If $C, D$ are non-empty disjoint convex sets, there exist $\textbf{a} \neq \textbf{0}$ and b, such that

$$\textbf{a}^{T}\textbf{x} \leq b ; for ; x \in C, ; \textbf{a}^{T}\textbf{x} \geq b ; for ; x \in D$$

• the hyperplane separates $C$ and $D$

Supporting Hyperplane Theorem

Supporting hyperplane to set $C$ at boundary point $x_{0}$:

$${\textbf{x}|\textbf{a}^{T}\textbf{x}=\textbf{a}^{T}\textbf{x}_{0} }$$

where $\textbf{a} \neq \textbf{0}$ and $\textbf{a}^{T}\textbf{x} \leq \textbf{a}^{T}\textbf{x}_{0}$ for all $\textbf{x} \in C$

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