Covex optitimization 第二周,凸函数。xjtu 的课程老师更侧重凸函数作为函数一般的性质,例如连续性、可微的一些证明,讲了更多利用上镜图研究凸函数的一些知识;

Boyd 课程涵盖更多凸函数的保凸运算和凸函数性质的例子。本文结合两部分摘选一部分记录。

Convex Function

1. Definition

$f:\mathbb{R^n} \rightarrow \mathbb {R}$ 是凸函数,且 $dom\ f $ 是凸集,如果 $$ f (\theta x + (1-\theta)y) \leq \theta f(x) + (1-\theta)f(y),\ \forall x,y \in \boldsymbol {dom} f $$ 则称 $f$ 是其定义域上的凸函数。如果 $\leq$ 为 $\lt$ 成为严格凸;

另一个等价条件: $$ g(t) = f(x + tv),\ {t|x+tv \in dom\ f}$$ $g (t)$ 为凸函数;这个等价条件可以用来将高维函数低维处理来证明凸性;

2. 一阶条件 FOC

如果函数一节可微,凸函数的一阶条件为: $$\forall x,y \in dom\ f, \ f(y) \ge f(x) + \nabla^Tf(y-x) $$

3. 二阶条件 SOC

如果函数二阶在定义域内处处二阶可微分,则凸函数的二阶条件为: $$\forall x \in dom\ f, \nabla^2f(x) \ge0 $$ 也就当是处处的 Hessian 矩阵半正定(一阶导数不减);

上镜图与凸函数的连续性

$$ epi(f) = {(x,w)|x\in C, w\in R, f(x) \le w } $$

实值函数扩展前后的上镜图不变,$dom (f)$ 是 $epi (f)$ 在 $\mathbb {R^n}$ 的投影;

实值函数为凸函数 $\iff$ 上镜图为凸集

上镜图为闭集的函数称之为闭函数

在跳跃点处取值较小的函数值的函数称之为下半连续的

则下面三个条件的是等价的:

  • 任意水平集合是闭的;
  • 函数下半连续
  • 函数上镜图是闭集

4. Examples

$e^{ax},\ \forall a \in R, x\in R$ 为凸;

$x^a,\ x \in \mathbb{R_{++}},\ a\ge 1\ or\ a\le 0$ 为凸

$|x|^p,\ p\ge1$ 为凸

$xlogx,\ x\in \mathbb{R_{++}}$ 为凸

所有的 Norm (范数)都是凸函数(除了 0 范数,因为 0 范数不是范数)

Log-Sum-Exp: $log\sum{e^{x_i}}$ 他是 max 函数的一个解析近似;

几何平均数: $f (x) = (\prod_{i=1}^N\ xi)^{1/N}$, 是 凹函数 , $domf = \mathbb {R{++}^n}$

对数绝对值函数: $f (x) = log\ det(X)$, $domf = \mathbb{S_{++}^n} $ (可以用第二个等价条件切换到一维证明)

Jessen 不等式, 如果函数是凸的,则在期望上有如下结论: $$ f (E (x))\le E(f(x)) $$

保持凸性的函数运算

非负加权

有限: $$ f = w_1f_1 + w_2f_2 + ... + w_nfn $$ 无限: $$ g (x) =\int{y\in A} f(x, y)w(y)dy $$

仿射组合

$$ g(x) = f(Ax +b)\ dom\ g = {x | Ax+b \in dom\ f } $$

Pointwise 最大

$$ f(x) = max{f_1(x), f_2(x), ..., f_n(x)} \ dom\ f = dom\ f_1 \cap ...dom\ f_n $$

无限维: $$ g (x) =\sup_{y\in A} f (x, y) $$ 例如: $$ max\ {a_1^Tx +b_1, ...., a_n^Tx+b_n }$$ 是多个仿射组合的取最大,保持凸性;

函数组合

我们定义 函数组合 $$ f = h (g (x)),\ dom\ f = {x\in dom\ g|g(x) \in dom\ h }$$ 若考虑组合都是标量函数的情况下,假设二阶可微,求出二阶条件: $$ f^{''} (x) = h^{''}(g (x)) g^{'}(x)^2 + h^{'}(x) g^{''}(x) $$ 可以得出如下的一些保凸条件:

  • $\tilde {h}$ 为凸且不减, $g$ 为凸
  • $\tilde {h}$ 为凸且不增,$g$ 为凹

Minimization

如果 $f (x,y)$ 是凸函数,则 $$ g (x) =\inf_{y\in C} f (x, y) $$ 是凸函数;

透视函数

$$ g(x, t) = tf(\frac{x}{t}) $$

若 $f$ 为凸,则透视函数 $g$ 为凸;

例子:

$f (x) = -logx$ 为凸, 则 $g (x, t) = tlog\frac {t}{x}$ 为凸,这个函数可以用来证明KL 散度总是凸函数

共轭函数

无论函数 $f$ 是否是凸函数,他的共轭函数 $$ f^*(y) = \sup_{x\in dom\ f} (x^Ty - f (x)) $$ 都为凸函数;

共轭函数可以从图像上看出是一系列线性函数取最大;Boyd 讲课时举了一个经济学中的现实意义;如果 $x$ 是生产品数量,$y$ 是市场价格,$f (x)$ 是成本函数,则成本函数的共轭就是每种市场条件下生产得到的最大利润值;

例子:

$f (x) = x^TQx$ 的共轭是 $f^*(y) = y^TQ^{-1}y$

拟凸函数与拟凹函数

Definition

从两个方面来定义:

  1. 所有的低水平集为凸集,则函数为拟凸,凸函数一定是拟凸函数;

  2. 满足下列:

$$ f(\theta x + (1-\theta)y) \le max\ {f(x),f (y)} $$

可见拟凸函数要求的凸组合的函数值只需要小于两端中较大值即可;

FOC

函数拟凸时,他有下列的一个逻辑关系: $$ f (y)\le f(x) \Longrightarrow \ \nabla^Tf(x)(y-x) \le 0 $$

SOC

函数拟凸且二阶可微时,存在如下的逻辑关系: $$ y^T\nabla f(x) = 0 \Longrightarrow y^T \nabla^2f(x)y \ge 0 $$ 即拟凸函数不需要处处二阶矩阵半正定;

对数凹

几乎所有的分布函数都是对数凹的;

Reference

哦,天呐。为什么这星期字数变少了?莫非是沉迷炉石自走棋不能自拔? 啊,其实是这样的。凸函数这章节其实有很多有意思的案例证明。有很多与其他知识联系的函数的凸性证明,但是这些证明都在 Boyd 的原作中能找到;唯一需要记录的是 xjtu 课堂上关于凸函数连续性的一些证明,但是我没有泛函的基础,很多还没看太明白,等我研究好了再回来补充。