01 凸优化 Convex Optimization

凸集

对于点集$C$，如果$\forall x,y \in C$满足以$x,y$为端点的线段都落在$C$内，就称$C$为凸集。以$x,y$为端点的线段写成方程的形式是$u=x+\theta(y-x)$，$\theta \in [0,1]$。因此“线段落在$C$内”这一条件可以写作“$\theta x+(1-\theta)y \in C$，$\theta \in (0,1)$”。通常把$1-\theta$记作$\bar{\theta}$，把$\theta x+\bar{\theta}y$称为$x,y$的凸组合。于是验证凸集只要验证两两点的凸组合都落在凸集内。

一般地，$n$个点的凸组合定义为$\theta_1x_1+\cdots+\theta_nx_n$，其中$\theta_i \geq 0$，$\sum\limits_{i=1}^{n}\theta_i=1$。如果$x_1,\cdots,x_n$都在凸集$C$内，那么它们的凸组合也在$C$内（对$n$归纳，证明很容易）。

常见的凸集有：空集，$\R^n$，超平面， 多面体，1-范数球，半正定矩阵集合等。证明它们是凸集只需验证它们两两的凸组合落在集合内。

保凸运算

凸集的交集依然是凸集：$C=\bigcap\limits_{i \in I}C_i$，因为显然交集内任意两点的凸组合依然在凸集中，可见“交”是保凸运算。

对于向量$x$，$x \to Ax$的变换称为线性变换，$x \to Ax+b$的变换称为仿射变换。仿射变换是保凸运算。设仿射映射$Ax+b$为$f(x)$，凸集$C$的像$f(C)$依然是凸集。反过来，如果某个仿射变换的像是凸集，其原像也是凸集：$C'$是凸集$\Rightarrow f^{-1}(C')$是凸集。

凸包

对于点集$S$，定义$S$的凸包$\text{conv}(S)$为包含$S$的最小凸集（最小指任何$\text{conv}(S)$的真子集都不是包含$S$的凸集，或任何包含$S$的凸集都包含$\text{conv}(S)$）。下面证明，$\text{conv}(S)$恰好是$S$中所有任取$m$个点做凸组合得到的所有点集合，即$\text{conv}(S)=\{\sum\limits_{i=1}^{m}\theta_ix_i \mid x_i \in S, \theta_i \geq 0,\sum\limits_{i=1}^{m}\theta_i=1\}$。“包含$S$”与“凸集”是显然的，而任何一个满足“包含$S$的凸集”的集合$C$一定包含上式的右式，因此$S$就是最小的。

我们定义过线性独立是指若干向量的线性组合为0向量时所有的系数都为0。下面定义仿射独立的概念，$n+1$个点仿射独立当且仅当从中选取一个点并让剩余点与它做差后的$n$个向量线性独立。对于给定的$m+1$个仿射独立的点$x_0,\cdots,x_m$，称它们构成的凸包$\text{conv}\{x_0,\cdots,x_m\}$为这$m+1$个点的单纯形。

凸集上的投影

定义点$x$到点集$C$的距离为$C$中的点到$x$距离的下确界，即$\text{dist}(C,x)=\inf\limits_{z\in C}\|x-z\|$。下面我们证明，如果$C$是凸集并且是闭集，那么存在一个唯一的$\hat{x}$使得$\|x-\hat{x}\|=\text{dist}(C,x)$。这个$\hat{x}$就称为$x$在$C$上的投影，记为$P_C(x)$。

先证存在性。任取$C$中某个$y$，取$S=C \cap \bar{B}(x,\|x-y\|)$，其中$\bar{B}$是以第一个参数为球心，第二个参数为半径的闭球。由于$C \setminus S$中的点到$x$的距离都要大过$\|x-y\|$，因此不可能小于$\text{dist}(C,x)$，于是我们只需证明$S$中存在$\|x-y\|$关于$y$的最小值存在。因为这个最小值一旦存在就意味着它是$C$上的最小值，因此也就等于$\text{dist}(C,x)$。而闭集与闭集的交集依然是闭集，而闭球是有界集，因此$S$是有界闭集（紧集）。$\|x-y\|$关于$y$显然是连续函数。紧集上的连续函数存在最小值。证毕。

再证唯一性。假如有两个点处取到最小值，那么这两个点与$x$形成等腰三角形。因为$C$是凸集， 等腰三角形的底边都落在集合内。连接底边的中点与$x$，得到的线段必然小于腰。与最小值矛盾。（代数证明用向量的极化恒等式）

凸集上的投影有下面的性质：

如果$C$是凸集并且是闭集，那么$\hat{x}=P_C(x)$当且仅当$\forall z \in C$都有$\lang x-\hat{x},z-\hat{x}\rang \leq 0$。这在直观上是容易想象的，它指出由投影点指向$x$与凸集上另外一点的两条向量的夹角不可能是锐角，这恰好体现了“凸性”。（证明时为了方便我们可以引入参数$t$来描述线段这一性质）。

这个性质的一个推论是，对于两个点$x,y$，它们一定满足$\|P_C(x)-P_C(y)\| \leq \|x-y\|$。这称为凸集上投影的非扩张性，投影点间的距离相比于两点原来的距离不会变得更长。从几何上看，这四个点形成的类似四边形的形状的两个底角都不是锐角，因此底边的长度会更短。

我们还可以这样描述凸性：任取闭的凸集$C$外的一点$x_0$，我们都可以找到一个过$x_0$的超平面，使得$C$严格落在该超平面的一侧。这个性质用数学语言描述为，存在单位向量$w$使得$\sup\limits_{x \in C}\lang x,w\rang < \lang x_0,w\rang$，其中$w$就是超平面的法向量。容易发现，这要把$w$取在$P_C(x_0)$到$x_0$的方向上就好了。

现在考虑$x_0$落在边界上的情况。凸集具有这样的性质，任取它的一个边界点$x_0$，都存在一个过$x_0$的超平面使得凸集落在它的一侧（注意，这里我们没有要求$C$是闭集）。用数学语言描述，$\forall x_0 \in \part C$，$\exists P=\{x \mid \lang w,x\rang=\lang w,x_0\rang\}$，使得$\forall x\in C,\lang w,x\rang \leq \lang w,x_0\rang$。这样的超平面称为支撑超平面。注意支撑超平面不一定是唯一的（例如，三角形是凸集，在它的一个角上就存在不只一条直线把它“支撑”起来）。为了证明这一点，我们先假设$C$是闭集。这样我们就可以用刚才的结论了。我们取一系列点逼近$x_0$，于是有一列满足不等式的$w_i$。由于$w_i$是单位向量，它的每一维都是有界的，于是我们可以找到一个$w$的收敛子列，这样我们就最终收敛到了一个$w$，并容易证明这就是我们要找的超平面。对于$C$不是闭集的情况，我们可以取它的闭包。唯一的问题是，闭包的边界点和原集合的边界点并不能等价。而事实上我们可以证明对于凸集，闭包的边界点就是原集合的边界点，证明略。

现在假设我们有两个不交的凸集$C_1,C_2$。下面我们要证明存在这样的超平面，使得$C_1,C_2$分别落在超平面的两侧。这样的超平面称为分离超平面。用数学描述，只要证明存在$w$使得$\forall x_1\in C_1,x_2\in C_2,\lang w,x_1\rang \leq\lang w,x_2\rang$恒成立。也即$\lang w,x_1-x_2\rang \leq 0$。把所有的$x_1-x_2$看作一个新的集合，容易发现这也是一个凸集。那么由于注意到0向量不落在集合内，我们通过刚才的结论就已经找到了我们要的超平面了。

凸函数

凸函数是对于任意两个自变量$x,y$都满足Jensen不等式成立的函数，即$\forall x,y$，$\forall \theta \in (0,1)$都有$f(\theta x+\bar{\theta}y) \leq \theta f(x)+\bar{\theta}f(y)$，即自变量的凸组合对应的函数值始终不大于相应自变量对应的函数值做同样的凸组合。当然为了满足$\theta x+\bar{\theta}y$始终在定义域内，我们要求凸函数的定义域$\text{dom }f$必须也要是凸集。直观上，函数的图形一定是“凸”的。把Jensen不等式中的小于等于改作小于，称为“严格凸函数”。改作大于等于，称为“凹函数”。

一个多元函数是凸函数，当且仅当取任意定义域中的直线，在该直线上函数是一元情形下的凸函数。

可微函数$f$是凸函数当且仅当$\forall x,y\in S,f(y) \geq f(x)+\nabla f(x)^\top(y-x)$，这称为凸函数判定的一阶条件。这意味着从某个点$x$处看，整个函数都落在该点的切平面上方。将梯度的那一项理解为方向导数，这就回到了一元的情况：切线斜率始终小于割线斜率。

二阶可微函数$f$是凸函数当且仅当$\forall x \in S,\nabla^2 f(x)$始终是半正定的，这称为凸函数判定的二阶条件。$\nabla^2 f$称为Hesse矩阵。