凸集

仿射 affine

仿射集 Affine Sets

$X_1\not=X_2 \in \R^n,\theta\in \R$

直线

$y=\theta X_1+(1-\theta)X_2$

线段

$y=\theta X_1 +(1-\theta)X_2$

限定 $\theta \in [0,1]$。

仿射集：连接集合内任意两点的直线也在集合内。

Fancy定义：设 $X_1,\cdots,X_k\in C$，$\theta_1,\cdots,\theta_k\in \R$，$\theta_1+\cdots+\theta_k=1$，放射组合：

$\theta_1X_1+\cdots+\theta_kX_k\in C$

定义等价？

$(\theta_1+\theta_2)(\frac{\theta_2}{\theta_1+\theta_2} X_1+\frac{\theta_2}{\theta_1+\theta_2}X_2)+(1-\theta_1-\theta_2) X_3$

若要满足 $\alpha X_1 +\beta X_2 \in C$，则需要过原点，或者观察到：

$V=C-X_0=\{X-X_0|X\in C\}$

这样 $\theta(X_1-X_0)+(1-\theta)(X_2-X_0)=\theta X_1+(1-\theta) X_2 -X_0 \in V$。

线性方程的解集是仿射集。

仿射包

$\operatorname{aff} C=\{\theta_1 X_1+\cdots+\theta_kX_k | \forall X_k\in C,\sum \theta=1\}$

凸性 convex

凸集

$\forall X_1,X_2 \in C,\forall \theta ,\theta\in [0,1]$

$\theta X_1+(1-\theta) X_2 \in C$

凸组合

$\sum \theta X,\sum \theta=1,\theta \in [0,1]$

凸包

$\operatorname{conv} C=\{\theta_1 X_1+\cdots+\theta_kX_k | \forall X_k\in C,\sum \theta=1,\theta \in [0,1]\}$

锥 Cone

凸锥 Convex Cone

C 是锥 $\Leftrightarrow$ $\forall X\in C,\theta \ge 0$，有 $\theta X\in C$。

C 是凸锥 $\Leftrightarrow$ $\forall X_1,X_2\in C,\theta_1,\theta_2 \ge 0$，有 $\theta_1 X_1+\theta_2X_2\in C$。

凸锥组合

$\sum \theta X,\theta \ge 0$

凸锥包

常见的凸集

超平面

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

分成两部分：

$\alpha^T x \ge b,\alpha^T x \le b$

半空间。

超平面和半空间都是凸集。

球和椭球

$B(X_c,r)=\{x| ||x-x_c||_2=r\}$

是凸集

$\varepsilon(X_C,P)=\{x|(X-X_C)^TP^{-1}(X-X_C)\le 1\} P\in S_{++}^n,X_C\in\R^n$

奇异值对应半轴长的平方。

多面体

$P=\{x|a_j^Tx \le b_j,c_j^Tx=d_j\}$

有界多面体。

单纯形 Simplex

$\R ^n$ 空间中选择 $V_0,\cdots,V_k$ 共 $k+1$ 个点。

$V_1-V_0,\cdots,V_k-V_0$

线性无关，则过点相关的单纯形为：

$C=\operatorname{conv} \{V_0,\cdots,V_k\}$

$\{x|x\le 0\}$

取点 $0,-\infin$，则构成了单纯形

无法构造 $V_0,V_1,V_2,V_3$ 单纯形。

一个单纯形一定是一个多面体。

在 $n$ 维空间构造 $C_{n+1}^n=n+1$ 个超平面。

对称矩阵集合/对称半正定矩阵集合

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

$S_{+}^n =\{X\in \R^{n\times n} | X=X^T,X \succeq0\}$

$S_{++}^n =\{X\in \R^{n\times n} | X=X^T,X \succ0\}$

证明 $S_{+}^n$ 是凸锥。可以说明 $\theta A$ 是半正定矩阵，$\theta_1 A+\theta_2 B$ 是半正定。

但是 $S_{++}^n$ 不是凸锥，因为当 $\theta=0$ 就不是正定。

保凸操作

任意多个凸集的交集是凸集

若 $S_1,S_2$ 为凸，则 $S_1 \cap S_2$ 为凸。

若 $S_a$ 为凸集 $\forall a\in A$，则 $\cap_{a\in A} S_a$ 为凸集。

仿射函数是保凸函数

$f:\R ^n \to \R^m$ 是放射的，$f(x)=Ax+b$。

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

若 $S\in\R^n$ 为凸，$f:\R^n \to\R^m$ 放射，则

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

也是凸集。

几何意义是拉伸和旋转。

缩放和移位是保持凸性的。

两个凸集的和是凸的

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

$S_1 \times S_2 = \{(x,y)|x\in S_1,y\in S_2\}$

笛卡尔积。

$S_1$ 与 $S_2$ 是凸集可以推出 $S_1 \times S_2$ 是凸集，然后根据仿射函数保凸，则 $S_1+S_2$ 是凸集。

类似的证明：$r(A)+r(B)\ge r(A|B)\ge r(A+B)$。

线性不等式的解集是凸的

根据一个线性不等式的解集是一个超平面，是凸的，取交集之后还是凸的证明。

如图，线性不等式的解集由红色区域表示。

线性规划解的几何特征：

• 有解：惟一解或多个解(整条边、面、甚至整个可行集)
• 无界：没有有限最优解
• 不可行：没有可行解，题目所给条件矛盾

极点 extreme point

几何上：极点即不能位于连接该集合中其它两点的开线段上的点

定义：称凸集中的点 $x$ 是 $C$ 的极点，如果存在 $C$ 中的点 $y,z$ 和某 $\theta \in (0,1)$，有：

$x=\theta y +(1-\theta) z$

则必有 $y=z$。

令 $C=\{x\in \R^n : Ax=b,x\ge0\}$，则 $x$ 是 $C$ 的极点当且仅当 $x$ 是系统 $Ax=b,x\ge0$ 的基本可行解。

若线性规划有解，则必有一个极点是最优解。

如果最优解都不是极点则能找到 $y \not=z$，使得 $x=\theta y+(1-\theta)z$，但是这样 $y,z$ 中必有一个更优。

线性矩阵不等式 LMI

$A(X)=X_1A_1+\cdots+X_nA_n \preceq B$

$B,A_i,X_i \in S^m$

$\{X|A(X)\preceq B\}$

为凸集。

定义仿射变换 $f(x)=B-A(X)$ 一系列对称矩阵 $X_1,\cdots,X_n$ 到 一个矩阵。

而 $S_{+}^n$ 为凸。则仿射变换后也为凸。

透视函数 Perspective Function

$P:\R^{n+1}\to\R^{n}$

$\operatorname {dom} P=\R^n \times \R_{++}$

最后一个元素是正数

$P(z,t)=\frac{z}{t}$

透视函数是保凸函数

Suppose that $x=\left(\tilde{x}, x_{n+1}\right), y=\left(\tilde{y}, y_{n+1}\right) \in \mathbf{R}^{n+1}$ with $x_{n+1}>0$, $y_{n+1}>0$. Then for $0 \leq \theta \leq 1$, 考虑凸组合 $\theta x+(1-\theta)y$

$P(\theta x+(1-\theta) y)=\frac{\theta \tilde{x}+(1-\theta) \tilde{y}}{\theta x_{n+1}+(1-\theta) y_{n+1}}=\mu P(x)+(1-\mu) P(y),$

where

$\mu=\frac{\theta x_{n+1}}{\theta x_{n+1}+(1-\theta) y_{n+1}} \in[0,1] .$

$P(x)=\frac{\tilde x}{x_{n+1}},Q(x)=\frac{\tilde y}{y_{n+1}}$

This correspondence between $\theta$ and $\mu$ is monotonic: as $\theta$ varies between 0 and 1 (which sweeps out the line segment $[x, y]$ ), $\mu$ varies between 0 and 1 (which sweeps out the line segment $[P(x), P(y)])$. This shows that $P([x, y])=[P(x), P(y)]$.

逆函数 $P^{-1}(C)=\left\{(x, t) \in \mathbf{R}^{n+1} \mid x / t \in C, t>0\right\}$ 也是保凸函数，映射为一个凸锥。

我们这里讲的逆函数将值域中的每个点映射到可以生成这个点的所有定义域中的点。

线性分数函数 Linear-fractional functions

$g(x)=\left[\begin{array}{l} A \\ c^T \end{array}\right] x+\left[\begin{array}{l} b \\ d \end{array}\right] \quad \begin{array}{lll} A \in R^{m \times n} & b \in R^m \\ c \in R^n & d \in R \end{array}$

两个随机变量的联合概率

Example 2.13 Conditional probabilities. Suppose $u$ and $v$ are random variables that take on values in $\{1, \ldots, n\}$ and $\{1, \ldots, m\}$, respectively, and let $p_{i j}$ denote $\operatorname{prob}(u=i, v=j)$. Then the conditional probability $f_{i j}=\operatorname{prob}(u=i \mid v=j)$ is given by

$f_{i j}=\frac{p_{i j}}{\sum_{k=1}^n p_{k j}} .$

Thus $f$ is obtained by a linear-fractional mapping from $p$.
It follows that if $C$ is a convex set of joint probabilities for $(u, v)$, then the associated set of conditional probabilities of $u$ given $v$ is also convex.