保凸运算

交集

交集运算是保凸的：如果 $S_1$ 和 $S_2$ 是凸集，那么 $S_1\cap S_2$ 也是凸集。这个性质可以推广到无穷个凸集的交。

仿射函数

函数 $f:{\mathbf{R}}^n\to {\mathbf{R}}^m$ 若满足 $f(x)=Ax+b$，其中 $A\in {\mathbf{R}}^{m\times n}$，$b\in {\mathbf{R}}^m$，则称 $f$ 是仿射函数。设 $S\subseteq {\mathbf{R}}^n$ 是凸的，那么 $S$ 在 $f$ 下的象

$$\begin{array}{r}f(S)=\{f(x)\mid x\in S\}\end{array}$$

也是凸的。从几何上看，凸集经过伸缩变换和平移变换后仍然是凸集。一个凸集向它的某几个坐标的投影也是凸的。

反过来，凸集在仿射函数下的原象也是凸的：若 $S\subseteq {\mathbf{R}}^m$ 凸，则 $f^{-1}(S)=\{x\mid f(x)\in S\}$ 也是凸的。这是因为若 $f(x_1),f(x_2)\in S$，则由 $S$ 的凸性，$f(\theta x_1+(1-\theta )x_2)=\theta f(x_1)+(1-\theta )f(x_2)\in S$。

双曲锥

$$\begin{array}{r}\{x\mid x^{\mathrm{\top }}Px⩽{\left(c^{\mathrm{\top }}x\right)}^2,c^{\mathrm{\top }}x⩾0\}\end{array}$$

其中 $P\in {\mathbf{S}}_{+}^n$，$c\in {\mathbf{R}}^n$。这是因为它是二阶锥

$$\begin{array}{r}\{(z,t)\mid z^{\mathrm{\top }}z⩽t^2,t⩾0\}\end{array}$$

在仿射函数 $f(x)=(P^{1/2}x,c^{\mathrm{\top }}x)$ 下的原象。

椭球

$$\begin{array}{r}\mathcal{E}=\{x\mid {(x-x_c)}^{\mathrm{\top }}{P}^{-1}(x-x_c)⩽1\}\end{array}$$

是单位 Euclid 球 $\{u\mid \parallel u{\parallel }_2⩽1\}$ 在仿射函数 $f(u)=P^{1/2}u+x_c$ 下的象，其中 $P\in {\mathbf{S}}_{++}^n$。

透视函数

定义 $P:{\mathbf{R}}^{n+1}\to {\mathbf{R}}^n$，$P(z,t)=z/t$ 为透视函数，其定义域为 $\mathrm{dom}P={\mathbf{R}}^n\times {\mathbf{R}}_{++}$。透视函数对向量进行伸缩，或称为规范化，使得最后一维分量为 1 并舍弃之。

INFO

小孔成像

我们可以用小孔成像的原理来解释透视函数。

在二维空间 ${\mathbf{R}}^2$ 中，小孔坐标 $(0,0)$。圆 $x^2+(y-2{)}^2=1$ 在直线 $y=-\sqrt{3}$ 上所成的像为线段 $y=-\sqrt{3},x\in [-1,1]$。如图所示：

TikZ 代码

\begin{tikzpicture}[line cap=round,line join=round,scale=1.0]
  % pinhole imaging: circle projects to a segment on y = -sqrt(3)
  \draw[fill=gray!20] (0,2) circle (1);
  \node at (-1.35,2.4) {$x^2+(y-2)^2=1$};
  \fill (0,0) circle (1.6pt) node[below left] {$0$};
  \draw[gray!60] (-2.6,-1.732) -- (2.6,-1.732);
  \node[gray!60] at (2.35,-1.42) {$y=-\sqrt{3}$};
  \draw[thick,blue] (-1,-1.732) -- (1,-1.732);
  \draw (-0.866,1.5) -- (1,-1.732);
  \draw (0.866,1.5) -- (-1,-1.732);
  \fill (-0.866,1.5) circle (1.2pt);
  \fill (0.866,1.5) circle (1.2pt);
  \fill (-1,-1.732) circle (1.4pt);
  \fill (1,-1.732) circle (1.4pt);
  \node at (-1.15,-1.42) {$-1$};
  \node at (1.2,-1.42) {$1$};
\end{tikzpicture}

:::

一个凸集在透视函数下的象和原象也是凸的，因此透视运算是保凸运算。

线性分式函数

线性分式函数有透视函数和仿射函数复合而成。设 $g:{\mathbf{R}}^n\to {\mathbf{R}}^{m+1}$ 是仿射的，即

$$\begin{array}{rl}g(x)& =\left[\begin{array}{c}A\\ c^{\mathrm{\top }}\end{array}\right]x+\left[\begin{array}{c}b\\ d\end{array}\right]\end{array}$$

其中 $A\in {\mathbf{R}}^{m\times n}$，$b\in {\mathbf{R}}^m$，$c\in {\mathbf{R}}^n$ 并且 $d\in \mathbf{R}$。则由 $f=P\circ g$ 给出的函数 $f:{\mathbf{R}}^n\to {\mathbf{R}}^m$

$$\begin{array}{rl}f(x)& ={\displaystyle \frac{Ax+b}{c^{\mathrm{\top }}x+d}},\mathrm{dom}f=\{x\mid c^{\mathrm{\top }}x+d>0\}\end{array}$$

称为线性分式函数（或投射函数）。如果 $c=0$，$d>0$，则 $f$ 是仿射函数。因此，仿射函数和线性函数被视为特殊的线性分式函数。线性分式函数也是保凸运算：凸集在线性分式函数下的象和原象都是凸的。