凸优化学习（一）凸集与凸函数、凸优化问题

4.1 凸集 convex sets

仿射集（Affine Sets）：如果一个集合C∈Rn$C\in {\mathbb{R}}^n$ 是仿射的，则在C中两点的直线也在C中，若x1∈C,x2∈C,则x=θx1+(1−θ)x2 ∈C,θ∈R$x_1\in C,x_2\in C,则x=\theta x_1+(1-\theta )x_2\in C,\theta \in R$ ，例如Ax=b的解集就是一个仿射集。

凸集：如果集合C∈Rn$C\in {\mathbb{R}}^n$ 是凸集，如果C中两点间的线段也在C中，即x=θx1+(1−θ)x2 ∈C,θ∈[0,1]$x=\theta x_1+(1-\theta )x_2\in C,\theta \in [0,1]$ 。注意θ$\theta$ 取值范围的不同。

常见的凸集：

• 所有Rn${\mathbb{R}}^n$

• 所有Rn+${\mathbb{R}}_{+}^n$

• 超平面（Hyperplane）：C={x|aTx=b}$C=\{x|a^{T}x=b\}$ 既是仿射集又是凸集

• 半空间（Halfspace）C={x|aTx≥b}或C={x|aTx≤b}$C=\{x|a^{T}x\ge b\}或C=\{x|a^{T}x\le b\}$ 只是凸集

• 范数球：满足 ∥x∥p≤1,p≥1$\Vert x{\Vert }_p\le 1,p\ge 1$的集合称为范数球。（依据范数的三角不等式可证）

  但是∥x∥p=1,p≥1$\Vert x{\Vert }_p=1,p\ge 1$ 不是凸集。当0<p<1$0<p<1$ 时， ∥x∥p≤1$\Vert x{\Vert }_p\le 1$ 也不是凸集。

• 多面体（polyhedron）：有限个半空间和超平面的交集。（凸集的交集是凸集）

  P={x|Ax≤b,Cx=d},A∈Rm×n,b∈Rm,C∈Rp∗n,d∈Rp$P=\{x|Ax\le b,Cx=d\},A\in R^{m\times n},b\in R^m,C\in R^{p\ast n},d\in R^p$ , 由于A，C都是矩阵，因此对应了有限个半空间和超平面。

凸集的性质：

凸集的交集是凸集。

凸集的并集不一定是凸集。

4.2 凸函数

一个函数f:Rn→R$f:R^n\to R$ 被称为凸函数，如果：

1. f的定义域dom(f)$dom(f)$ 是凸集
2. 对于任何x,y∈dom(f),0≤θ≤1,有f(θx+(1−θ)y)≤θf(x)+(1−θ)f(y)$x,y\in dom(f),0\le \theta \le 1,有f(\theta x+(1-\theta )y)\le \theta f(x)+(1-\theta )f(y)$

几何解释：函数值小于连接函数值的线段的值。

凸函数的充要条件

一阶充要条件：f(x1)≥f(x)+∇Tf(x)(x1−x)$f(x_1)\ge f(x)+{\mathrm{\nabla }}^{T}f(x)(x_1-x)$ 对于所有x1,x$x_1,x$ 均成立。

二阶充要条件：如果函数f二阶可导，则凸函数的充要条件为：H(x)⪰0$H(x)⪰0$ 即Hessian矩阵半正定。（如果是正定的，则是严格凸函数。半负定，则是凹函数）

在实际使用中，使用二阶充要条件比较好用。

证明：凸函数的局部最优解就是全局最优解。

假定x∗$x^{\ast }$ 是局部最优解，则在x∗$x^{\ast }$ 的邻域内的点z有f(x∗)≤f(z)$f(x^{\ast })\le f(z)$ 。假设y点为可行域内的任意一点，则z=(1−t)x∗+t)y,t∈[0,1]$z=(1-t)x^{\ast }+t)y,t\in [0,1]$ ,通过调整t的值，可以使得z保持在x∗$x^{\ast }$ 的邻域内。根据凸函数定义：

f(x∗)≤f(z)=f(tx∗+(1−t)y)≤tf(x∗)+(1−t)f(y)$f(x^{\ast })\le f(z)=f(t{x}^{\ast }+(1-t)y)\le tf(x^{\ast })+(1-t)f(y)$

化简上面的不等式有：f(x∗)≤f(y)$f(x^{\ast })\le f(y)$

由于y为任意一点，因此x∗$x^{\ast }$ 也是全局最优解。

常见凸函数

• ax+b: 既是凸函数，也是凹函数
• x2$x^2$ 凸函数
• eαx$e^{\alpha x}$ 凸函数
• -log(x) 凸函数，x>0
• −xlogx，x≥0$-xlogx，x\ge 0$ 凸函数
• f(x)=aTx+b$f(x)=a^{T}x+b$ 凸函数、凹函数
• f(x)=xTPx+2qTx=r,当且仅当P⪰0时是凸函数$f(x)=x^{T}Px+2q^{T}x=r,当且仅当P⪰0时是凸函数$， 特别地f(x)=xTx$f(x)=x^{T}x$ 是凸函数（2范数是凸函数）

凸函数的性质

• f(x)是凸函数，则f(Ax+b)也是凸函数。例如∥y−Ax∥2$\Vert y-Ax{\Vert }_2$

• 如果g(x)，h(x)是凸函数，h函数是非递减函数，则f(x)=h(g(x))$f(x)=h(g(x))$ 是凸函数。例如：g(x)=∥y−Ax∥2,h(x)=x2在x≥0上非递减$g(x)=\Vert y-Ax{\Vert }_2,h(x)=x^2在x\ge 0上非递减$, 则f(x)=∥y−Ax∥22$f(x)=\Vert y-Ax{\Vert }_2^2$ 是凸函数。

• f1,...,fm$f_1,...,f_m$ 是凸函数，w1,...,wm≥0$w_1,...,w_m\ge 0$ ，则∑mi=1wifi$\sum _{i=1}^m{w}_i{f}_i$ 是凸函数，例如：

  f(x)=∥y−Ax∥22+λ∥x∥22$f(x)=\Vert y-Ax{\Vert }_2^2+\lambda \Vert x{\Vert }_2^2$ 是凸函数。（L2正则化项）

• 逐点最大：f1,...,fm$f_1,...,f_m$ 是凸函数，则f(x)=max{f1(x),...,fm(x)}$f(x)=max\{f_1(x),...,f_m(x)\}$ 是凸函数。例如，f(x,y)$f(x,y)$ 对于每个y∈A$y\in A$ 都是凸函数，则supy∈Af(x,y)$su{p}_{y\in A}f(x,y)$ 是凸函数（f(x,y)的上确界，可以类比最大值）。

凸函数和凸集的关系

α$\alpha$ 水平集或下水平集

一元函数f的α$\alpha$ 水平集为：Sα={x|f(x)≤α}$S_{\alpha }=\{x|f(x)\le \alpha \}$

如果f为凸函数，则 对每个α$\alpha$ ，Sα$S_{\alpha }$都是凸集。反之则不成立。

4.3 凸优化问题

对于一般优化问题：

如果f0(x)$f_0(x)$ 是凸函数，且可行域是凸集，则上述优化问题是凸优化问题。因此，凸优化问题是在凸集上极小化一个凸的目标函数。

凸优化问题要求（可行域是凸集）：

• 不等式约束函数必须是凸的。（若fi(x)$f_i(x)$ 是凸函数，则不等式约束为下水平集，是凸集。）
• 等式约束函数必须是仿射的。

凸优化问题的最优值写为：p∗=min{f0(x):fi(x)≤0,hi(x)=0}$p^{\ast }=min\{f_0(x):f_i(x)\le 0,h_i(x)=0\}$ ，可能的取值为：

• p∗=+∞$p^{\ast }=+\mathrm{\infty }$ 不可行（可行域为空集）
• p∗=−∞$p^{\ast }=-\mathrm{\infty }$ 称为unbounded below (存在可行点使得f0(x)→∞$f_0(x)\to \mathrm{\infty }$ )
• f0(x∗)=p∗$f_0(x^{\ast })=p^{\ast }$

凸优化问题的重要结论

凸优化问题局部最优就是全局最优

局部最优点x指：存在R>0$R>0$ ，对于所有可行点z，且有∥x−z∥2≤R$\Vert x-z{\Vert }_2\le R$ ，满足f0(x)≤f0(z)$f_0(x)\le f_0(z)$

全局最优点x指，对于所有可行点，满足f0(x)≤f0(z)$f_0(x)\le f_0(z)$

反证法证明：

x∗$x^{\ast }$ 是凸优化问题的局部最优点，假设存在一点x′$x^{\prime }$ 使得f0(x∗)>f0(x′)$f_0(x^{\ast })>f_0(x^{\prime })$ ，则由于f0$f_0$ 是凸函数：

f0(tx∗+(1−t)x′)≤tf(x∗)+(1−t)f(x′)$f_0(t{x}^{\ast }+(1-t)x^{\prime })\le tf(x^{\ast })+(1-t)f(x^{\prime })$

当(1-t)很小时，∥x−(tx∗+(1−t)x′)∥2≤R$\Vert x-(t{x}^{\ast }+(1-t)x^{\prime }){\Vert }_2\le R$ ，则f0(x∗)≤f0(tx∗+(1−t)x′)$f_0(x^{\ast })\le f_0(t{x}^{\ast }+(1-t)x^{\prime })$

可以得到f0(x∗)≤f0(x′)$f_0(x^{\ast })\le f_0(x^{\prime })$ ，这与假设条件相违背，因此，不存在一点x′$x^{\prime }$ 使得f0(x∗)>f0(x′)$f_0(x^{\ast })>f_0(x^{\prime })$，即 x∗$x^{\ast }$ 是全局最优点。

典型凸优化问题

实例

形式转换成凸优化问题

将本质是凸优化问题的问题，从形式上转换为凸优化问题。

对于以下问题，通过定义矩阵和向量的方式，转换为标准的凸优化问题，便于利用软件包进行求解。

CVX软件包