凸函数1（斯坦福凸优化笔记5）

1 基本性质和例子

1.1 凸函数

函数f:Rn→R是凸的，如果dom f是凸集，且对于任意x,y∈dom f和任意0≤θ≤1,有：
f(θx+(1−θ)y)≤θf(x)+(1−θ)f(y)，
则称为函数是凸的。
称函数f是严格凸的，如果上式中不等式x≠y以及0<θ<1严格成立。
如果函数−f是凸的，则函数f是凸的。
1.2 扩展值延伸

通常我们可以定义凸函数在定义域外的值为∞，从而将这个凸函数延伸至全空间Rn。
如果f是凸函数，我们定义凸函数的扩展值延伸f˜：Rn→R∪{∞}如下：

延伸函数是定义在全空间Rn上的，值域是R∪{∞}。
我们还可以从延伸函数f~的定义中找出原函数的定义域，即dom f={x∣f~(x)<∞}。
这样定义后，我们在描述不等式时就不需要限定定义域了。
比如对于上面的不等式，对于延伸函数，可以描述为：
对于任意x和y，以及0<θ<1，有：
f~(θx+(1−θ)y)≤θf~(x)+(1−θ)f~(y)
不引起歧义的情况下，以后将假设所有凸函数都被隐含的延伸了，不引起歧义的情况下，f~将被简写为f。
1.3 一阶条件：

假设f可微（即其梯度▽f在开集dom f内处处存在），则f是凸函数的充要条件：
1 dom f是凸集
2 ∀x,y∈domf⇒f(y)≥f(x)+▽f(x)T(y−x)
一阶条件是充要条件。
对于严格凸函数的一阶条件，我们有：
1 dom f是凸集
2 ∀x,y∈domf,x≠y⇒f(y)≥f(x)+▽f(x)T(y−x)
▽算子的解释：
对于

（图片来自斯坦福Boyd Convex Optimization）
如果函数f是凸的且可微，那么对于任意x,y∈domf，有f(x)+▽f(x)T(y−x)≤f(y)
1.4 二阶条件：

假设函数f二阶可微，函数f是凸函数的充要条件是：其Hessian矩阵是半正定阵。即▽2f(x)⪰0
黑塞矩阵定义：
严格凸的条件可以部分由二阶条件刻画。
如果对于任意x∈domf，有▽2f(x)≻0，则函数f严格凸。反过来不一定成立，例如，函数f:R→R,f(x)=x4，它是严格凸的，但是不满足上述条件。
例：二次函数
对于函数f(x)=(1/2)xTPx+qTx+r，▽2f(x)=P，所以f是凸的⇔P⪰0
对于二次函数，严格凸比较好表达，可以推出：f是凸的⇔P≻0
无论应用一阶条件还是二阶条件，都必须提前验证定义域是凸的：
对于函数f=1x因为定义域不是凸的，直接可以判断函数不是凸的。
关于矩阵的求导运算，请参阅矩阵理论课程。这里给出简要的一点介绍。
1.5 矩阵求导

1） 矩阵对标量求导
相当于矩阵中每个元素对标量求导：

2） 标量对矩阵求导
注意与上面不同，这次括号内是求偏导，对m×n矩阵求导后还是m×n矩阵

3） 函数矩阵Y对矩阵X求导
矩阵Y对每一个X的元素求导，构成一个超级矩阵。


其中：

重要结论：假设x⃗ 是一个向量：

4） 向量积对列向量x⃗ 求导运算法则
注意与标量有点不同，假设u⃗ ,v⃗ 都是列向量，

5）重要结论

1.6 一些常见的例子

范数。Rn上的任意函数都是凸函数。
最大值函数是凸的，因为最大值函数可以看成是无穷维的范数。
范数是凸函数的证明可以直接用凸函数的定义加上三角不等式得出（简单的说，就是三角形两边之和大于第三边）。
二次线性分式函数f(x,y)=x2/y(y>0)是凸的：

指数和的对数：f(x)=log(ex1+⋯+exn)是凸函数。
仿射函数既是凸函数，也是凹函数。
对于广义矩阵的乘法(仿射)，对于X∈Rm×n,f(X)=tr(ATX)+b,也既是凸函数也是凹函数。
几何平均f(x)=(∏i=1nxi)1n是一个凹函数。
1.7 凸函数的仿射定理
对于函数f:Rn→R是凸函数当且仅当对:
g:R→R,g(t)=f(X+tV)domg={t∣X+tV∈domf} 是凸的。（对于所有X∈domf,V∈Rn）
我们用这个定理证明下以下结论： f(X)=log detX是凸的。
g(t)=log det(Z+tV)，Z,V∈Sn,Z≻0
   =log det(Z1/2(I+tZ−1/2VZ−1/2)Z1/2)
对于方阵，行列式的乘积等于乘积的行列式。
矩阵的行列式还等于矩阵特征值的乘积。所以：
   =∑i=1nlog(1+tλi)+log detZ
其中λ1,⋯λn是矩阵Z−1/2VZ−1/2的特征值。
g′(t)=∑i=1nλi1+tλi
g′′(t)=−∑i=1nλ2i(1+tλi)2≤0
所以，原函数是凸的。
1.8 下水平集和上镜图

函数的下水平集定义为：
Cα={x∈domf∣f(x)≤α}
下水平集是自变量的一个范围。一个凸函数的下水平集仍然是凸集，反之不成立。
函数的上镜图定义为：
epif={(x,t)∣x∈domf,f(x)≤t}
上镜图是函数上方的一个范围。一个函数是凸函数，当且仅当其上镜图是凸集。
下图展示了上镜图的图片。

（图片来自斯坦福Boyd Convex Optimization）
(未完，待续)