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

4.1 凸集 convex sets

仿射集（Affine Sets）：如果一个集合C∈RnC∈Rn 是仿射的，则在C中两点的直线也在C中，若x1∈C,x2∈C,则x=θx1+(1−θ)x2 ∈C
,θ∈Rx1∈C,x2∈C,则x=θx1+(1−θ)x2 ∈C,θ∈R ，例如Ax=b的解集就是一个仿射集。

凸集：如果集合C∈RnC∈Rn 是凸集，如果C中两点间的线段也在C中，即x=θx1+(1−θ)x2 ∈C,θ∈[0,1]x=θx1+(1−θ)x2 ∈C,θ∈
[0,1] 。注意θθ 取值范围的不同。

常见的凸集：

*
所有RnRn

*
所有Rn+R+n

*
超平面（Hyperplane）：C={x|aTx=b}C={x|aTx=b} 既是仿射集又是凸集

*
半空间（Halfspace）C={x|aTx≥b}或C={x|aTx≤b}C={x|aTx≥b}或C={x|aTx≤b} 只是凸集

*
范数球：满足 ∥x∥p≤1,p≥1‖x‖p≤1,p≥1的集合称为范数球。（依据范数的三角不等式可证）

但是∥x∥p=1,p≥1‖x‖p=1,p≥1 不是凸集。当0<p<10<p<1 时， ∥x∥p≤1‖x‖p≤1 也不是凸集。

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

P={x|Ax≤b,Cx=d},A∈Rm×n,b∈Rm,C∈Rp∗n,d∈RpP={x|Ax≤b,Cx=d},A∈Rm×n,b∈Rm,C∈Rp∗n,d∈Rp
, 由于A，C都是矩阵，因此对应了有限个半空间和超平面。

凸集的性质：

凸集的交集是凸集。

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

4.2 凸函数

一个函数f:Rn→Rf:Rn→R 被称为凸函数，如果：

* f的定义域dom(f)dom(f) 是凸集
* 对于任何x,y∈dom(f),0≤θ≤1,有f(θx+(1−θ)y)≤θf(x)+(1−θ)f(y)x,y∈dom(f),0≤θ≤1,有f(θx+(1−
θ)y)≤θf(x)+(1−θ)f(y)

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

凸函数的充要条件

一阶充要条件：f(x1)≥f(x)+∇Tf(x)(x1−x)f(x1)≥f(x)+∇Tf(x)(x1−x) 对于所有x1,xx1,x 均成立。

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

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

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

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

f(x∗)≤f(z)=f(tx∗+(1−t)y)≤tf(x∗)+(1−t)f(y)f(x∗)≤f(z)=f(tx∗+(1−t)y)≤tf(x∗)+(1−t)f
(y)

化简上面的不等式有：f(x∗)≤f(y)f(x∗)≤f(y)

由于y为任意一点，因此x∗x∗ 也是全局最优解。

常见凸函数

* ax+b: 既是凸函数，也是凹函数
* x2x2 凸函数
* eαxeαx 凸函数
* -log(x) 凸函数，x>0
* −xlogx，x≥0−xlogx，x≥0 凸函数
* f(x)=aTx+bf(x)=aTx+b 凸函数、凹函数
* f(x)=xTPx+2qTx=r,当且仅当P⪰0时是凸函数f(x)=xTPx+2qTx=r,当且仅当P⪰0时是凸函数，特别地f(x)=xTxf(x)=
xTx 是凸函数（2范数是凸函数）
凸函数的性质

*
f(x)是凸函数，则f(Ax+b)也是凸函数。例如∥y−Ax∥2‖y−Ax‖2

*
如果g(x)，h(x)是凸函数，h函数是非递减函数，则f(x)=h(g(x))f(x)=h(g(x)) 是凸函数。例如：g(x)=∥y−Ax∥2,h(x)=x
2在x≥0上非递减g(x)=‖y−Ax‖2,h(x)=x2在x≥0上非递减, 则f(x)=∥y−Ax∥22f(x)=‖y−Ax‖22 是凸函数。

*
f1,...,fmf1,...,fm 是凸函数，w1,...,wm≥0w1,...,wm≥0 ，则∑mi=1wifi∑i=1mwifi 是凸函数，例如：

f(x)=∥y−Ax∥22+λ∥x∥22f(x)=‖y−Ax‖22+λ‖x‖22 是凸函数。（L2正则化项）

*
逐点最大：f1,...,fmf1,...,fm 是凸函数，则f(x)=max{f1(x),...,fm(x)}f(x)=max{f1(x),...,fm(x)
} 是凸函数。例如，f(x,y)f(x,y) 对于每个y∈Ay∈A 都是凸函数，则supy∈Af(x,y)supy∈Af(x,y)
是凸函数（f(x,y)的上确界，可以类比最大值）。

凸函数和凸集的关系

αα 水平集或下水平集

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

如果f为凸函数，则对每个αα ，SαSα都是凸集。反之则不成立。

4.3 凸优化问题

对于一般优化问题：

minimizesubjecttof0(x)fi(x)≤0fori=1,2,...,mhi(x)=0fori=1,2,...,pminimizef0(x)su
bjecttofi(x)≤0fori=1,2,...,mhi(x)=0fori=1,2,...,p
如果f0(x)f0(x) 是凸函数，且可行域是凸集，则上述优化问题是凸优化问题。因此，凸优化问题是在凸集上极小化一个凸的目标函数。

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

* 不等式约束函数必须是凸的。（若fi(x)fi(x) 是凸函数，则不等式约束为下水平集，是凸集。）
* 等式约束函数必须是仿射的。
凸优化问题的最优值写为：p∗=min{f0(x):fi(x)≤0,hi(x)=0}p∗=min{f0(x):fi(x)≤0,hi(x)=0} ，可能的取值为：

* p∗=+∞p∗=+∞ 不可行（可行域为空集）
* p∗=−∞p∗=−∞ 称为unbounded below (存在可行点使得f0(x)→∞f0(x)→∞ )
* f0(x∗)=p∗f0(x∗)=p∗
凸优化问题的重要结论

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

局部最优点x指：存在R>0R>0 ，对于所有可行点z，且有∥x−z∥2≤R‖x−z‖2≤R ，满足f0(x)≤f0(z)f0(x)≤f0(z)

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

反证法证明：

x∗x∗ 是凸优化问题的局部最优点，假设存在一点x′x′ 使得f0(x∗)>f0(x′)f0(x∗)>f0(x′) ，则由于f0f0 是凸函数：

f0(tx∗+(1−t)x′)≤tf(x∗)+(1−t)f(x′)f0(tx∗+(1−t)x′)≤tf(x∗)+(1−t)f(x′)

当(1-t)很小时，∥x−(tx∗+(1−t)x′)∥2≤R‖x−(tx∗+(1−t)x′)‖2≤R ，则f0(x∗)≤f0(tx∗+(1−t)x′)f0(x
∗)≤f0(tx∗+(1−t)x′)

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

典型凸优化问题

实例

形式转换成凸优化问题

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

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

CVX软件包

热门工具换一换