EE364A Lecture 3 and Lecture 4

课程主页:https://see.stanford.edu/Course/EE364A

这次回顾凸优化第三,第四讲,这部分介绍了凸函数的概念。

Lecture 3 and Lecture 4 Convex functions

定义

$f : \mathbf{R}^{n} \rightarrow \mathbf{R}$是凸函数,如果$\operatorname{dom} f$是凸集,并且

对任意$x, y \in \operatorname{dom} f, 0 \leq \theta \leq 1$都成立,图示如下

  • $f$是凹的,如果$-f$是凸的

  • $f$是严格凸的,如果$\operatorname{dom} f$是凸的,并且

    对任意$x, y \in \operatorname{dom} f, x \neq y, 0<\theta<1$

$\mathbf R$上的例子

凸函数:

  • 仿射:$a x+b$,其中$a,b$为$\mathbf R$上任意实数
  • 指数函数:$e^{a x}$,其中$a$为$\mathbf R$上任意实数
  • 幂函数:定义在$\mathbf{R}_{++}$上的$x^{\alpha}$,其中$\alpha \ge 1$或$\alpha \le 0$
  • 绝对值函数的幂:$|x|^{p}, p \ge 1 $
  • 负熵:定义在$\mathbf{R}_{++}$的$x \log x$

凹函数:

  • 仿射:$a x+b$,其中$a,b$为$\mathbf R$上任意实数
  • 幂函数:定义在$\mathbf{R}_{++}$上的$x^{\alpha}$,$0\le \alpha \le 1$
  • 对数函数:定义在$\mathbf{R}_{++}$的$ \log x$

$\mathbf{R}^{n}$和$\mathbf{R}^{m \times n}$上的例子

仿射函数既是凸的又是凹的;所有的范数都是凸的。

$\mathbf{R}^{n}$上的例子

  • 仿射函数:$f(x)=a^{T} x+b$
  • 范数:$|x|_{p}=\left(\sum_{i=1}^{n}\left|x_{i}\right|^{p}\right)^{1 / p} , p \geq 1$,$|x|_{\infty}=\max _{k}\left|x_{k}\right|$

$\mathbf{R}^{m \times n}$上的例子($m\times n$)

  • 仿射函数

  • 谱范数(最大奇异值)

将凸函数限制为直线

$f : \mathbf{R}^{n} \rightarrow \mathbf{R}$是凸(凹)函数当且仅当函数$g : \mathbf{R} \rightarrow \mathbf{R}$,

对任意$x \in \operatorname{dom} f,v \in \mathbf{R}^{n}$,关于$t$是凸(凹)函数。

例子:$f : \mathrm{S}^{n} \rightarrow \mathrm{R}$,其中

应用上述定理得到

其中$\lambda_i $是$X^{-1 / 2} V X^{-1 / 2}$的特征值。

因为$g$关于$t$是凹函数;因此$f$是凹函数。

拓展值延伸

$f$的拓展值延伸$\tilde f$为

拓展值延伸可以简化记号;例如,凸函数的条件可以简化为

意味着

  • $\operatorname{dom} f$是凸集

  • 对$x, y\in \operatorname{dom} f$,

一阶条件

假设$f$可微,$\operatorname{dom} f$是开集,梯度

对任意$x \in \operatorname{dom} f$都存在。

凸函数的一阶判别条件为:

$f$的一阶近似是全局的下界估计。

二阶条件

$f$二阶可微,$\operatorname{dom} f$是开集,$\nabla^{2} f(x) \in \mathbf{S}^{n}$对每个$x \in \operatorname{dom} f$都存在,其中

凸函数的二阶判别条件为:

  • $f$为凸函数当且仅当

  • 如果对所有$x \in \operatorname{dom} f$,$\nabla^{2} f(x) \succ 0$,那么$f$严格凸

例子

二次函数:$f(x)=(1 / 2) x^{T} P x+q^{T} x+r$,其中$P \in \mathbf{S}^{n}$

如果$P \succeq 0$,那么该函数为凸函数。

最小二乘目标函数:$f(x)=|A x-b|_{2}^{2}$

显然该函数为凸函数。

二次-线性分式函数:$f(x, y)=x^{2} / y$

对$y>0$是凸函数。

指数和的对数:$f(x)=\log \sum_{k=1}^{n} \exp x_{k}$是凸函数

下面证明上述矩阵半正定,即对于所有$v$,$v^{T} \nabla^{2} f(x) v \geq 0$:

其中不等号利用了柯西不等式。

几何平均:定义在$\mathbf{R}_{++}^{n}$上的$f(x)=\left(\prod_{k=1}^{n} x_{k}\right)^{1 / n}$是凹函数

上镜图和下水平集

$f : \mathbf{R}^{n} \rightarrow \mathbf{R}$的$\alpha - $下水平集定义为

凸函数的下水平集为凸集(反之不成立)

$f : \mathbf{R}^{n} \rightarrow \mathbf{R}$的上镜图定义为

$f$是凸函数当且仅当$\operatorname{epi} f$是凸集

Jensen不等式

基本不等式:如果$f$是凸集,那么对于$0\le \theta \le1$,

推广:如果$f$是凸集,那么对任意随机变量$z$

基本不等式是推广的特殊情形:

保凸运算

非负加权和以及复合仿射函数

非负相乘:若果$f$是凸函数,$\alpha \ge 0$,那么$\alpha f $是凸函数

:如果$f_1,f_2$是凸函数,那么$f_1 +f_2$是凸函数(推广到无限和以及积分)

仿射函数复合:如果$f$是凸函数,那么$f(Ax+b)$是凸函数

例子:

  • 对数函数和仿射函数复合

  • 仿射函数的范数

逐点最大值

如果$f_{1}, \ldots, f_{m}$是凸函数,那么$f(x)=\max \left\{f_{1}(x), \ldots, f_{m}(x)\right\}$是凸函数

例子:

  • $f(x)=\max _{i=1, \ldots, m}\left(a_{i}^{T} x+b_{i}\right)$是凸函数

  • $x \in \mathbf{R}^{n}$的$r$个最大分量:

    证明:

逐点上确界

如果对每个$y \in \mathcal{A}$,$f(x,y)$关于$x$是凸函数,那么

是凸函数。

例子:

  • $S_{C}(x)=\sup _{y \in C} y^{T} x$是凸函数

  • $f(x)=\sup _{y \in C}|x-y|$

  • 对称矩阵的最大值$X \in \mathbf{S}^{n}$

标量函数复合

考虑$g : \mathbf{R}^{n} \rightarrow \mathbf{R}$以及$h : \mathbf{R} \rightarrow \mathbf{R}$的复合:

$f$是凸函数,如果

  • $g$是凸函数,$h$是凸函数,$\tilde h$非减
  • $g$是凹函数,$h$是凸函数,$\tilde h$非增

证明:考虑$n=1$的情形,

例子:

  • 如果$g$是凸函数,那么$\exp g(x)$是凸函数
  • 如果$g$是正凹函数,那么$1/ g(x)$是凸函数
向量复合

考虑$g : \mathbf{R}^{n} \rightarrow \mathbf{R}^k$以及$h : \mathbf{R}^k \rightarrow \mathbf{R}$的复合:

$f$是凸函数,如果

  • $g_i$是凸函数,$h$是凸函数,$\tilde h$关于每个分量非减
  • $g_i $是凹函数,$h$是凸函数,$\tilde h $关于每个分量非增

证明:考虑$n=1$的情形,

例子:

  • $\sum_{i=1}^{m} \log g_{i}(x)$是凹函数,如果$g_i$是正凹函数
  • $\log \sum_{i=1}^{m} \exp g_{i}(x)$是凸函数,如果$g_i$是凸函数
最小化

$f(x,y)$关于$(x,y)$是凸函数,并且$C$是凸集,那么

是凸函数。

例子

  • $f(x, y)=x^{T} A x+2 x^{T} B y+y^{T} C y$,其中

    关于$y$最小化得到

  • 如果$S$是凸集,那么

    是凸集

透视函数

$f : \mathbf{R}^{n} \rightarrow \mathbf{R}$的透视函数为$g : \mathbf{R}^{n} \times \mathbf{R} \rightarrow \mathbf{R}$,其中

如果$f$是凸函数,那么$g$是凸函数。

例子:

  • $f(x)=x^T x$是凸函数,所以$g(x, t)=x^{T} x / t,t>0$是凸函数

  • 负对数函数$f(x)=-\log x$是凸函数;因此相对熵$g(x, t)=t \log t-t \log x$是$\mathbf{R}_{++}^{2}$上凸函数

  • $f$是凸函数,那么

    是凸函数,其中定义域为

共轭函数

$f$的共轭为

关于共轭有如下性质

  • $f^*$是凸函数

例子:

  • 负对数函数$f(x)=-\log x$

  • 严格二次凸函数$f(x)=(1 / 2) x^{T} Q x,Q \in \mathbf{S}_{++}^{n} $

拟凸函数

$f : \mathbf{R}^{n} \rightarrow \mathbf{R}$是拟凸函数,如果$\operatorname{dom} f$是凸集,并且下水平集对任意$\alpha $是凸集

  • $f$是拟凹,如果$-f$是拟凸
  • $f$是拟线性,如果$f$是拟凸并且拟凹
例子
  • $\sqrt{|x|}$是$\mathbf R $上拟凸函数

  • $\operatorname{ceil}(x)=\inf \{z \in \mathbf{Z} | z \geq x\}$是拟线性

  • $\log x$是$\mathbf{R}_{++}$上拟线性

  • $f\left(x_{1}, x_{2}\right)=x_{1} x_{2}$是$\mathbf{R}_{++}^{2}$上拟凹函数

  • 线性分式函数

    是拟线性

  • 距离比

    是拟凸函数

拟凸函数的性质

调整的Jenson不等式:对于拟凸函数$f$

一阶条件:可微$f$关于凸定义域是拟凸函数当且仅当

注意,拟凸函数的和不一定是拟凸函数

对数凸以及对数凹函数

$f$是对数凹函数,如果$\log f$是凹函数:

$f$是对数凸函数,如果$\log f$是对数凸

  • $\mathbf{R}_{++}$上的$x^{a}$是对数凸函数,如果$a\le 0$;是对数凹函数,如果$\alpha \ge 0$

  • 正态分布是对数凹函数

  • 正态分布的累计分布函数是对数凹函数

对数凹函数的性质
  • 定义域为凸集的二阶可微的$f$为对数凹函数当且仅当对任意$x \in \operatorname{dom} f$,

  • 对数凹函数的乘积是对数凹函数

  • 对数凹函数的和不总是对数凹函数

  • 积分:如果$f : \mathbf{R}^{n} \times \mathbf{R}^{m} \rightarrow \mathbf{R}$是对数凹函数,那么

    是对数凹函数

积分性质的结果

  • 如果$f,g$是对数凹函数,那么

    是对数凹函数

  • $C \subseteq \mathrm{R}^{n}$是凸集,$y$是pdf为对数凹函数的随机变量,那么

    是对数凹函数

    证明:定义

    其中$p$为$y$的pdf

关于广义不等式的凸性

$f : \mathbf{R}^{n} \rightarrow \mathbf{R}^{m}$是$K$凸,如果$\operatorname{dom} f$是凸集,并且

对任意$x, y \in \operatorname{dom} f, 0 \leq \theta \leq 1$都成立,图示如下

例子:

证明:固定$z \in \mathbf{R}^{m}$,$z^{T} X^{2} z=|X z|_{2}^{2}$关于$X$是凸集,即

对于$X, Y \in \mathbf{S}^{m}, 0 \leq \theta \leq 1$成立。

因此

本文标题:EE364A Lecture 3 and Lecture 4

文章作者:Doraemonzzz

发布时间:2019年07月22日 - 09:55:00

最后更新:2019年08月22日 - 00:28:46

原始链接:http://doraemonzzz.com/2019/07/22/EE364A Lecture 3 and Lecture 4/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。