本文为原创文章,未经本人允许,禁止转载。转载请注明出处。
1.优化与凸优化简介
1.1.优化问题基本形式
优化问题的一般形式:
\[最小化:f_0(x)\] \[条件:f_i(x) \leqslant b_i , i=1,...,m\]其中$f_0(x)$为目标函数,条件里的不等式是限制条件。优化问题举例:极大似然估计、最小二乘法。
1.2.凸优化问题基本形式
凸优化问题的一般形式:
\[最小化:f_0(x)\] \[条件:f_i(x) \leqslant b_i , i=1,...,m\]其中$f_0(x)$为目标函数,条件里的不等式是限制条件。
- 凸优化问题的条件:$f_0,f_1,…,f_m$都是凸函数。
- 凸优化问题的特点:局部最优等价于全局最优。
- 凸优化问题的求解:几乎总有现成的工具来求解。
1.3.凸优化的应用
- 凸优化问题逼近非凸优化问题,寻找非凸问题的初始点。
- 利用对偶问题的凸性给原问题提供下界估计。
- 凸优化问题可以给非凸问题带来一些启发。
针对应用1,假设代价函数的图像如下所示:
存在很多局部最优点。我们可以将其近似为一个凸函数,然后求其极值点作为优化问题的初始点(例如梯度下降法或牛顿法的起始点):
2.凸集合与凸函数基本概念
👉凸集合定义:如果一个集合$\Omega$中任何两个点之间的线段上任何一个点还属于$\Omega$,那么$\Omega$就是一个凸集合。即:
\[\lambda x_1+(1-\lambda) x_2 \in \Omega,\forall x_1,x_2 \in \Omega,\lambda \in (0,1)\]例如下图中,第一行的第一个集合和最后一行的集合都不是凸集合,其余均为凸集合:
👉凸函数定义:如果一个函数$f$定义域$\Omega$是凸集,而且对于任何两点,以及两点之间线段上任意一个点都有:
\[f(\lambda x_1+(1-\lambda)x_2) \leqslant \lambda f(x_1)+(1-\lambda) f(x_2),\forall x_1,x_2 \in \Omega,\lambda \in (0,1)\]👉函数的上境图:假设$f$是一个定义在$\Omega$上的函数,区域$\{(x,y):y \geqslant f(x) ,\forall x \in \Omega \}$就是$f$的上境图。即上境图就是函数图像上方的部分区域。
❗️凸集合与凸函数的关系:一个函数是凸函数当且仅当$f$的上境图是凸集合。
👉凸组合:对于任何$n$个点$\{ x_i \}^n_{i=1}$,以及权重系数$\{ w_i \}^n_{i=1}$。若权重系数非负$w_i \geqslant 0$而且$\sum^n_{i=1} w_i=1$,则线性组合
\[S=\sum^n_{i=1} w_i x_i\]为一个凸组合。从几何意义来说,凸组合就是这$n$个点所围成的图形中的任意一点。例如,下图中有$x_1,x_2,x_3$三个点,这三个点所围成的蓝色三角形中的任意一点$P$是这三个点的一种凸组合,而点$Q$不是:
👉集合的凸包:$n$个点$\{ x_i \}^n_{i=1}$的全部凸组合就构成$\{ x_i \}^n_{i=1}$的凸包。
👉集合的凸包的性质:若$\bar {C}$是$C$的凸包,那么,
- $C \subset \bar {C}$
- $C$的支撑平面也是$\bar {C}$的支撑平面,反之亦然
支撑超平面:设集合$C$,$x_0$为$C$边界上的点。若存在$a \neq 0$,满足对任意$x \in C$,都有$a^T x \leqslant a^T x_0$成立,则称超平面$\{ x \mid a^T x = a^T x_0 \}$为集合$C$在点$x_0$处的支撑超平面。
凸集边界上任意一点,均存在支撑超平面。反之,若一个闭的非中空(内部点不为空)集合,在边界上的任意一点存在支撑超平面,则该集合为凸集。
👉函数的凸闭包:如果$C$是函数$f$的上境图,$\bar {C}$是$C$的凸包,那么以$\bar {C}$为上境图的函数称为$f$的凸闭包。
上图中,$g(x)$为$f(x)$的凸闭包。
👉函数的凸闭包的性质:若$g$是$f$的凸闭包,那么,
- $g \leqslant f$
- $\inf g = \inf f$
3.凸集合与凸函数的对应性质
3.1.凸组合
👉凸集合性质:假设$\Omega$是一个凸集合,那么$\Omega$任何子集的凸包仍包含于$\Omega$。
👉凸函数性质:琴生不等式。
琴生不等式的应用举例:
应用一,证明算数平均大于等于几何平均,即对于正数$a_1,…,a_n$,
\[\frac{\sum^n_{i=1} a_i}{n} \geqslant (\prod ^n _{i=1} a_i)^{\frac{1}{n}}\]证明如下,以凸函数$-\ln (x)$为例:
\[-\ln (\frac{1}{n} (a_1+...+a_n) ) \leqslant \frac{1}{n} \sum^n_{i=1} -\ln (a_i)\] \[\ln (\frac{1}{n} (a_1+...+a_n) ) \geqslant \frac{1}{n} \sum^n_{i=1} \ln (a_i)\] \[exp(\ln (\frac{1}{n} (a_1+...+a_n) )) \geqslant exp(\frac{1}{n} \sum^n_{i=1} \ln (a_i))\] \[\frac{1}{n} (a_1+...+a_n) \geqslant (a_1 ... a_n) ^{\frac{1}{n}}\]应用二,证明柯西不等式:
\[(\sum^n_{i=1} a^2_i)(\sum^n_{i=1} b^2_i) \geqslant (\sum^n_{i=1} a_i b_i)^2\]证明如下,以函数$f(x)=x^2$为例,假设有:
\[w_i=\frac{b_i^2}{\sum^n_{i=1} (b_i^2)};x_i=\frac{a_i}{b_i}\]根据琴生不等式有:
\[f(\sum_{i=1}^n w_i x_i) \leqslant \sum_{i=1}^n w_i f(x_i)\] \[(\sum_{i=1}^n \frac{b_i a_i}{\sum^n_{i=1} (b_i^2)})^2 \leqslant \sum_{i=1}^n \frac{ a_i^2}{\sum^n_{i=1} (b_i^2)}\] \[(\frac{\sum_{i=1}^n( b_i a_i)}{\sum^n_{i=1} (b_i^2)})^2 \leqslant \frac{ \sum_{i=1}^n(a_i^2)}{\sum^n_{i=1} (b_i^2)}\] \[(\sum_{i=1}^n( b_i a_i))^2 \leqslant \frac{ \sum_{i=1}^n(a_i^2)}{\sum^n_{i=1} (b_i^2)} \cdot (\sum^n_{i=1} (b_i^2))^2\] \[(\sum_{i=1}^n( b_i a_i))^2 \leqslant \sum_{i=1}^n(a_i^2) \cdot \sum^n_{i=1} (b_i^2)\]3.2.集合相交
👉凸集合性质:任意多个凸集合的交集仍是凸集合。
👉凸函数性质:
- 任意多个凸函数的逐点上确界仍是凸函数。
- 固定一个凸函数的若干个变量,所得的函数仍然是凸函数。
- 凸函数的子水平集都是凸集合。
逐点上确界:
\[f(x)=\sup \{ f_1(x) ,..., f_n(x) \}\]逐点最大值:
\[f(x)=\max \{ f_1(x) ,..., f_n(x) \}\]
性质1示意图:
性质2,例如有如下凸函数$z$,固定变量$x$(即$x$为某一定值),剩余的函数$z=y^2$依旧是凸函数:
水平集(level set):集合
\[\{ (x_1,...,x_n) \mid f(x_1,...,x_n) = c \}\]被称为水平集,其中,$c$为常数。
子水平集(sublevel set):集合
\[\{ (x_1,...,x_n) \mid f(x_1,...,x_n) \leqslant c \}\]被称为子水平集,其中,$c$为常数。
3.3.线性组合
👉凸集合性质:假设$T:V\to W$是一个线性映射,则
- 若$\Omega _V$是$V$中的凸集合,则$\Omega _W=T(\Omega _V)$是$W$中的凸集合。
- 若$\Omega _W$是$W$中的凸集合,则$\Omega _V=T^{-1}(\Omega _W)$是$V$中的凸集合。
👉凸函数性质:
- 凸函数的非负线性组合仍是凸函数,$f_1,…,f_k$是凸函数,而且$w_i \geqslant 0$,则$\sum^k_{i=1} w_i f_i$也是凸函数。
- 若$f:\mathbb R ^n \to \mathbb R$是凸函数,$A \in \mathbb R ^{n\times m},b\in \mathbb R ^n$,那么复合函数$g(x)=f(Ax+b)$还是凸函数。
3.4.微分
👉凸集合性质:
- 若凸集合$\Omega$的边界$C$是一个可微曲线,则$C$在任何一点上的切线(平面)都是这个凸集合的支撑线(平面)。
- 若凸集合$\Omega$的边界$C$是一个二阶可微曲线,则$C$在任何一点上的曲率向量都指向$\Omega$内部。
平面曲线的曲率:圆上每一点处的弯曲程度都相同,半径越小弯曲得越厉害,所以可以用半径的倒数来定量描述圆的弯曲程度,即曲率。直线可以看作半径无限大的圆,所以直线的曲率为0。对于任意形状的曲线,每一点处的弯曲程度一般是不同的。对曲线$C$上任一点$P$,在其附近再找$C$上的两个点$P_1,P_2$,这三点总能确定一个圆(三点共线时确定一条直线,但可以把直线看作半径无限大的广义的圆)。当$P_1,P_2$无限接近点$P$时,相应的圆也有一个极限,这个极限圆就是在点$P$处最接近曲线$C$的圆,称为密切圆。密切圆的曲率就是曲线$C$在点$P$处的曲率。
👉凸函数性质:
- 若一个凸函数一阶可微,那么凸函数的一阶近似不大于函数本身:
- 若一个凸函数二阶可微,那么这个函数的二阶导数(Henssen矩阵)非负(半正定)。
3.5.光学投影
👉凸集合性质:
- 若$\Omega$是凸集合,那么$\Omega$在任何一个平面上的投影仍是凸集合(平行光源投影)。
- 若$\Omega \subset \mathbb R^n$是凸集合,那么$\Omega _{\hat n}=\{ (x_1 /x_n ,…,x_{n-1} / x_n,1) : (x_1,…,x_n) \in \Omega 且 x_n \neq 0 \}$也是凸集合(点光源投影)。
- 若$\Omega \subset \mathbb R ^n$是一个凸集合,那么锥体$tx :x \in \Omega,t\in \mathbb R_+$也是个凸集合(点光源)。
关于性质2,以下图为例,凸集合经过原点小孔成像到$x_n=1$的超平面,得到的投影仍然是一个凸集合,但是维度相比之前减少了一维:
性质3示意图见下,得到的锥体也是凸集合:
👉凸函数性质:
- 若$f(x,y)$是凸函数,那么$g(x)= \inf _{(x,y)\in \Omega} f(x,y)$,也是凸函数(对应凸集合性质1)。
- 若$f: \mathbb R ^n \to \mathbb R$是凸函数,那么$g(x,t)=tf(x/t):\mathbb R^{n+1} \to \mathbb R$也是个凸函数(对应凸集合性质3)。
4.凸集分离定理
若$C,D$分别为$\mathbb R^n$中的两个不交的非空凸集合,即$C \cap D = \varnothing$,则一定存在向量$a\in \mathbb R ^n$以及实数$b\in \mathbb R$使得任何$x_C \in C,x_D \in D$有$a^T x_C \leqslant b$以及$a^T x_D \geqslant b$。
定理中不等式的几何意义在于$C,D$分别位于超平面$a^T x=b$的两边。
凸集分离定理是凸集理论的最基本的定理,它是指在很弱的条件下,两个不相交的凸集总可用超平面分离。