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

1 基本性质和例子

1.1 凸函数

函数f:R^n \rightarrow R是凸的，如果\mathbf{dom }\ f是凸集，且对于任意x,y \in \mathbf{dom }\ f和任意0 \leq \theta \leq 1,有：
f(\theta x+(1-\theta)y) \leq \theta f(x)+(1-\theta)f(y)，
则称为函数是凸的。
称函数f是严格凸的，如果上式中不等式x \neq y 以及0<\theta<1严格成立。
如果函数-f是凸的，则函数是凸的。
1.2 扩展值延伸

通常我们可以定义凸函数在定义域外的值为\infty，从而将这个凸函数延伸至全空间R^n。
如果是凸函数，我们定义凸函数的扩展值延伸\widetilde{f}：R^n \rightarrow R\cup \{\infty\} 如下：

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

假设可微（即其梯度 \triangledown f在开集 \mathbf{dom}\ f 内处处存在），则 是凸函数的充要条件：
1 \mathbf{dom}\ f是凸集
2 \forall x,y \in \mathbf{dom} f\Rightarrow f(y) \geq f(x)+\triangledown f(x)^T(y-x)
一阶条件是充要条件。
对于严格凸函数的一阶条件，我们有：
1 是凸集
2 \forall x,y \in \mathbf{dom} f,x \neq y\Rightarrow f(y) \geq f(x)+\triangledown f(x)^T(y-x)
\triangledown算子的解释：
对于

（图片来自斯坦福Boyd Convex Optimization）
如果函数 是凸的且可微，那么对于任意x,y \in \mathbf{dom} f，有 f(x)+\triangledown f(x)^T (y-x) \leq f(y)
1.4 二阶条件：

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

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

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

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


其中：

重要结论：假设\vec{x}是一个向量：

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

5）重要结论

1.6 一些常见的例子

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

指数和的对数： f(x)=log(e^{x_1}+\cdots+e^{x_n})是凸函数。
仿射函数既是凸函数，也是凹函数。
对于广义矩阵的乘法(仿射)，对于 X \in R^{m \times n},f(X)=tr(A^TX)+b,也既是凸函数也是凹函数。
几何平均 f(x)=(\prod\limits_{i=1}^{n}x_i)^{\frac{1}{n}}是一个凹函数。
1.7 凸函数的仿射定理
对于函数 是凸函数当且仅当对:
g: R\rightarrow R , \quad g(t)=f(X+tV) \mathbf{dom}g=\{t\mid X+tV \in \mathbf{dom} f\} 是凸的。（对于所有 X \in \mathbf{dom} f,V \in R^n）
我们用这个定理证明下以下结论： f(X)=log \ detX 是凸的。
g(t)=log \ det (Z+tV) ，Z,V \in S^n,Z \succ 0
\quad \ \ \ =log \ det (Z^{1/2}(I+tZ^{-1/2}VZ^{-1/2})Z^{1/2})
对于方阵，行列式的乘积等于乘积的行列式。
矩阵的行列式还等于矩阵特征值的乘积。所以：
\quad \ \ \ =\sum\limits_{i=1}^{n}log(1+t \lambda _i)+log \ det Z
其中 \lambda _1,\cdots \lambda _n是矩阵 Z^{-1/2}VZ^{-1/2}的特征值。
g'(t)=\sum\limits_{i=1}^{n}\frac{\lambda _i}{1+t \lambda _i}
g''(t)=-\sum\limits_{i=1}^{n}\frac{\lambda _i ^2}{(1+t \lambda _i)^2} \leq 0
所以，原函数是凸的。
1.8 下水平集和上镜图

函数的下水平集定义为：
C _ \alpha = \{x \in \mathbf{dom} f \mid f(x) \leq \alpha \}
下水平集是自变量的一个范围。一个凸函数的下水平集仍然是凸集，反之不成立。
函数的上镜图定义为：
\mathbf{epi} f=\{(x,t) \mid x \in \mathbf{dom} f,f(x) \leq t\}
上镜图是函数上方的一个范围。一个函数是凸函数，当且仅当其上镜图是凸集。
下图展示了上镜图的图片。

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