凸集合(Convex set)

線段 (Line segment)

• Line segment between $x_1$ and $x_2$

  • $x = \theta x_1 + (1-\theta) x_2$ with $0 \leq \theta \leq 1$.

  • 線段有限制長度, 必須在$x_1$與$x_2$之間，所以$0 \leq \theta \leq 1$。

• Convex set $C$ contains line segment between any two points in the set.
  • $\forall x_1, x_2 \in C$, $0 \leq \theta \leq 1$ $\Rightarrow$ $\theta x_1 + (1-\theta) x_2 \in C$.

仿射集合(Affine set)

• Line through $x_1, x_2$.

  • $x = \theta x_1 + (1-\theta) x_2, \ \forall \theta \in \mathbb{R}$.

  • 直線沒有限制長度，所以$\theta$可為任意實數。

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

  • E.g. solution set of linear equation $\lbrace x \vert Ax = b \rbrace$.
  • 反過來說，Affine set可寫做線性方程式的解答集合。

凸組合與凸包(Convex combination and convex hull)

• convex combination of $x_1, x_2, \cdots, x_N$

  • $x = \theta_1 x_1 + \theta_2 x_2 + \cdots + \theta_N x_N$ with
  • $\theta_1 + \theta_2 + \cdots + \theta_N = 1$, $\forall \theta_n \geq 0$.

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

凸錐組合與凸錐(conic combination and convex cone)

• conic combination of $x_1$ and $x_2$.
  • $x = \theta_1 x_1 + \theta_2 x_2$ with $\theta_1 \geq 0$ and $\theta_2 \geq 0$.

• convex cone: set that contains all conic combinations of points in the set.

超平面與半空間(hyperplanes and halfspaces)

• Hyperplane
  • $\lbrace \mathbf{x} \vert \mathbf{a}^T \mathbf{x}=\mathbf{b},\ \mathbf{a} \neq 0 \rbrace$.

• Halfspace
  • $\lbrace \mathbf{x} \vert \mathbf{a}^T \mathbf{x} \leq \mathbf{b}, \mathbf{a} \neq \mathbf{0} \rbrace$.

• $a$ is the normal vector.

球與橢圓(Ball and ellipsoids)

• (Euclidean) ball with center $x_c$ and radius $r > 0$:

  • $\begin{array}{rcl} B(x_c, r) & = & \lbrace x \vert \begin{Vmatrix} x - x_c \end{Vmatrix}_2 \leq r \rbrace \\ & = & \lbrace x_c + ru \vert \begin{Vmatrix} u \end{Vmatrix} \leq 1 \rbrace \end{array}$

• Ellipsoid: set of the form

  • $\lbrace x \vert (x-x_c) P^{-1} (x-x_c) \leq 1 \rbrace = \lbrace x_c + Au \vert \begin{Vmatrix} u \end{Vmatrix} \leq 1 \rbrace$.
  • $P \in S_{++}^n$ ($P$ is symmetric positive definite).
  • $A$ square and nonsingular.

範數球與錐(norm ball and cone)

• for a general norm: $\begin{Vmatrix} \cdot \end{Vmatrix}$.

• norm ball with center $x_c$ and radius $r > 0$

  • $\lbrace x \vert \begin{Vmatrix} x - x_c \end{Vmatrix} \leq r \rbrace$.

• norm cone

  • $\lbrace (x,t) \vert \begin{Vmatrix} x \end{Vmatrix} \leq t \rbrace$.

• Euclidean norm cone常稱為second-order cone.

多面體(Polyhedra)

• Solution set of finitely many linear inequalities and equalities.
  • $A x \preceq b$, and $Cx = d$.
  • $A \in \mathbb{R}^{m \times n}$, $C \in \mathbb{R}^{p \times n}$
  • 常見於線性規劃的限制式。

正半定錐(Positive semidefinite cone)

• $\mathbf{S}^n$ is set of symmetric $n \times n$ matrices.
• $\mathbf{S}_{+}^n = \lbrace \mathbf{X} \in \mathbf{S}^n \vert 0 \preceq \mathbf{X} \rbrace$ : positive semidefinite $n \times n$ matrices.
  • $\mathbf{S}_{+}^n$ is a convex cone.
• $\mathbf{S}_{++}^n = \lbrace \mathbf{X} \in \mathbf{S}^n \vert 0 \prec \mathbf{X} \rbrace$ : positive definite $n \times n$ matrices.

保留凸性的運算

交集(Intersection)

• 任意數量個的凸集合之交集仍為凸集合。

仿射函數(Affine function)

• Suppose $f: \mathbf{R}^n \rightarrow \mathbf{R}^m$ is affine function.

  • E.g. $f(x) = Ax +b$ with $A \in \mathbb{R}^{m \times n}$, $b \in \mathbb{R}^m$.

  • 旋轉 (rotation)、縮放(scaling)、投影(projection)都是仿射運算。

• The image of a convex set under $f$ is convex.

  • $S \subseteq \mathbb{R}^n$ is convex $\Rightarrow$ $f(S) = \lbrace f(x) \vert x \in S \rbrace$ is convex.

• The pre-image $f^{-1}(C)$ of a convex set under $f$ is convex.

  • $C \subseteq \mathbb{R}^m$ is convex $\Rightarrow$ $f^{-1}(C) = \lbrace x \in \mathbb{R}^n \vert f(x) \in C \rbrace$ is convex.

透視函數(Perspective function)

• $f: \mathbb{R}^{n+1} \rightarrow \mathbb{R}^{n}$.

  • $f(x,t) = \frac{x}{t}$.
  • $dom f = \lbrace (x,t) \vert t > 0 \rbrace$.

• Images and pre-images of convex sets under perspective function are still convex.

線性分數函數(Linear-fractional function)

• $f: \mathbb{R}^n \rightarrow \mathbb{R}^m$.
  • $f = \frac{Ax + b}{c^T x + d}$.
  • $dom f = \lbrace x \vert c^T x + d > 0 \rbrace$.

• Images and pre-images of convex sets under linear-fractional functions are still convex.

• E.g. $f(x) = \frac{x}{x_1 + x_2 +1}$.

• 原始Data envelopment analysis(DEA)的目標函數為線性分數函數，分母為輸入加權值，分子為輸出加權值，而目標函數是要找出給定特徵下，何種輸入、輸出權重可使效率最大化。