最优化|凸函数

Posted by Derek on January 23, 2021

1. 凸函数的定义


定义 1.1(凸函数,Convex function)    设$C$是非空凸集,$f$是定义在$C$上的函数. 如果对于任意的$\mathbf{x}, \mathbf{y} \in C, \alpha \in (0, 1),$ 均有$$f(\alpha\mathbf{x}+(1-\alpha)\mathbf{y}) \leq \alpha f(\mathbf{x})+(1-\alpha)f(\mathbf{y})$$则称$f$为$C$上的凸函数. 若上述不等式严格小于,则称$f$为$C$上的严格凸函数. 若$-f$是凸函数,则$f$是凹函数.

2. 常见的凸函数


常见的凸函数有:

    1. 线性函数:$$f(\mathbf{x})=\mathbf{a}^T\mathbf{x}+\mathbf{b}$$     2. 二次函数:$$f(\mathbf{x})=\mathbf{x}^TQ\mathbf{x}+\mathbf{a}^T\mathbf{x}+\mathbf{b}$$其中$Q$为半正定矩阵($Q \in S_n^+$).

    3. 最小二乘函数:$$f(\mathbf{x})=\|A\mathbf{x}-\mathbf{b}\|^2_2$$     4. $p$范数:$$f(\mathbf{x})=\left(\sum_{i=1}^n|x_i|^p\right)^{1/p}, p \geq 1$$

3. 凸函数的性质


性质 3.1    凸函数一定是连续函数.

性质 3.2    $f(\mathbf{x})$为凸函数$\Leftrightarrow$对于任意的$\mathbf{x}, \mathbf{y} \in \mathbb{R}^n,$ 一元函数$\varphi(\alpha)=f(\mathbf{x}+\alpha\mathbf{y})$是凸函数.

性质 3.3    $f(\mathbf{x})$是$C$上的凸函数的充要条件是$$f(\mathbf{y}) \geq f(\mathbf{x})+\nabla f(\mathbf{x})^T(\mathbf{y}-\mathbf{x}), \forall\mathbf{x}, \mathbf{y} \in C$$

证明    ($\Leftarrow$)记$\mathbf{z}=\lambda\mathbf{x}+(1-\lambda)\mathbf{y}, \lambda \in (0, 1).$ 我们有$$f(\mathbf{x}) \geq f(\mathbf{z})+\nabla f(\mathbf{z})^T(\mathbf{x}-\mathbf{z})$$及$$f(\mathbf{y}) \geq f(\mathbf{z})+\nabla f(\mathbf{z})^T(\mathbf{y}-\mathbf{z})$$那么$$\lambda f(\mathbf{x})+(1-\lambda)f(\mathbf{y}) \geq f(\mathbf{z})+\nabla f(\mathbf{z})^T(\lambda\mathbf{x}-\lambda\mathbf{z}+(1-\lambda)\mathbf{y}-(1-\lambda)\mathbf{z})=f(\lambda\mathbf{x}+(1-\lambda)\mathbf{y})$$因此$f(\mathbf{x})$是凸函数.

($\Rightarrow$)因为$f(\mathbf{x})$是凸函数,所以$$f(\lambda\mathbf{y}+(1-\lambda)\mathbf{x}) \leq \lambda f(\mathbf{y})+(1-\lambda)f(\mathbf{x}), \lambda \in (0, 1)$$ 因此整理后可以得到$$f(\mathbf{x})+\frac{f(\mathbf{x}+\lambda(\mathbf{y}-\mathbf{x}))- f(\mathbf{x})}{\lambda} \leq f(\mathbf{y})$$根据泰勒展开公式$$f(\mathbf{x}+\lambda(\mathbf{y}-\mathbf{x}))=f(\mathbf{x})+\lambda\nabla f(\mathbf{x})^T(\mathbf{y}-\mathbf{x})+o(\lambda\|\mathbf{y}-\mathbf{x}\|)$$因此$$\frac{f(\mathbf{x}+\lambda(\mathbf{y}-\mathbf{x}))-f(\mathbf{x})}{\lambda}=\nabla f(\mathbf{x})^T(\mathbf{y}-\mathbf{x})+\frac{o(\lambda\|\mathbf{y}-\mathbf{x}\|)}{\lambda}$$所以$$f(\mathbf{x})+\nabla f(\mathbf{x})^T(\mathbf{y}-\mathbf{x})+\frac{o(\lambda\|\mathbf{y}-\mathbf{x}\|)}{\lambda} \leq f(\mathbf{y})$$因此$$f(\mathbf{x})+\nabla f(\mathbf{x})^T(\mathbf{y}-\mathbf{x}) \leq f(\mathbf{y})$$ 性质 3.4    设$C \subset \mathbb{R}^n$是非空开凸集,$f(\mathbf{x})$在$C$上二阶连续可微,则$f(\mathbf{x})$是$C$上的凸函数$\Leftrightarrow$$f(\mathbf{x})$的Hessian矩阵$\nabla^2f(\mathbf{x}) \succeq 0, \forall \mathbf{x} \in C.$

证明    ($\Leftarrow$)任取$\mathbf{x}, \mathbf{y} \in C.$ 根据泰勒展开公式$$f(\mathbf{y})=f(\mathbf{x})+\nabla f(\mathbf{x})^T(\mathbf{y}-\mathbf{x})+\frac{1}{2}(\mathbf{y}-\mathbf{x})^T\nabla^2f(\xi)(\mathbf{y}-\mathbf{x})$$其中$\xi=\mathbf{x}+\lambda(\mathbf{y}-\mathbf{x}), \lambda \in (0, 1).$ 易证$\xi \in C,$ 因此$\nabla^2f(\xi) \succeq 0.$ 所以$$f(\mathbf{y}) \geq f(\mathbf{x})+\nabla f(\mathbf{x})^T(\mathbf{y}-\mathbf{x}), \forall \mathbf{x}, \mathbf{y} \in C$$ 因此$f(\mathbf{x})$是$C$上的凸函数.

($\Rightarrow$)任取$\mathbf{x} \in C.$ 选择一个足够小的$\alpha \in \mathbb{R},$ 我们有$$f(\mathbf{x}+\alpha\mathbf{d})=f(\mathbf{x})+\alpha\nabla f(\mathbf{x})^T\mathbf{d}+\frac{\alpha^2}{2}\mathbf{d}^T\nabla^2f(\mathbf{x})\mathbf{d}+o(\alpha^2\|\mathbf{d}\|^2)$$由于$f(\mathbf{x}+\alpha\mathbf{d}) \geq f(\mathbf{x})+\alpha\nabla f(\mathbf{x})^T\mathbf{d},$ 因此$$\frac{1}{2}\mathbf{d}^T\nabla^2f(\mathbf{x})\mathbf{d}+\frac{o(\alpha^2\|\mathbf{d}\|^2)}{\alpha^2} \geq 0$$令$\alpha \to 0,$ 则$$\mathbf{d}^T\nabla^2f(\mathbf{x})\mathbf{d}^T\geq0$$ 也即$\nabla^2f(\mathbf{x})$是半正定矩阵.

性质 3.5    若$f(\mathbf{x})$是凸函数,则透视函数(Perspective function)$g(\mathbf{x}, t)=tf(\mathbf{x}/t), t>0$为凸函数.

性质 3.6    若$f_1(\mathbf{x}), \cdots, f_m(\mathbf{x})$是凸函数,则其非负组合$g(\mathbf{x})=w_1f_1(\mathbf{x})+\cdots+w_mf_m(\mathbf{x}), w_i \geq 0$为凸函数.

性质 3.7    若$f_1(\mathbf{x}), \cdots, f_m(\mathbf{x})$是凸函数,则$g(\mathbf{x})=\max\lbrace f_1(\mathbf{x}), \cdots, f_m(\mathbf{x})\rbrace$为凸函数.

接下来我们探讨一下凸集和凸函数之间的关系.

性质 3.8    设函数$f(\mathbf{x})$的水平集为$$L_a=\lbrace \mathbf{x}|f(\mathbf{x}) \leq a, \mathbf{x} \in C \rbrace$$若$f(\mathbf{x})$是凸函数,则其水平集均为凸集,但反之并不成立.

最后,我们补充一个关于上境图的定义,并探讨与凸函数的关系.

定义 3.9(上境图,Epigraph)    函数$f(\mathbf{x})$的上境图定义为$$\text{epi}(f)=\left\lbrace\begin{pmatrix}\mathbf{x} \\ y\end{pmatrix}\bigg|f(\mathbf{x}) \leq y, \mathbf{x} \in C\right\rbrace$$ 性质 3.10    $f(\mathbf{x})$是凸函数$\Leftrightarrow\text{epi}(f)$为凸集.