凸函数

凸函数的四种判别

第一定义

f是凸函数，当且仅当其定义域为凸集，且

∀x, y ∈ S, ∀θ ∈ [0, 1], f(θx + (1 − θ)y) ≤ θf(x) + (1 − θ)f(y)

第二定义

domf 为凸,且 ∀x ∈ domf, ∀v, g(t) = f(x + tv) 为凸函数

几何意义是用一个超平面去截凸函数，截面一定也是凸函数

一阶条件

设f : Rⁿ → R可微，则f为凸函数等价于以下两点同时成立
- domf为凸集 - f(y) ≥ f(x) + ∇f^T(x)(y − x), ∀x, y ∈ domf

证明从略，复习点击此处

二阶条件

若f二阶可微，则f为凸函数等价于

∇²f(x) ≽ 0, ∀x ∈ domf

凸函数的扩展

f: Rⁿ → R为凸函数，dom f: C ⊆ Rⁿ

$\tilde{f} = \begin{cases} f( x) \:& x\in dom\:f\\ \infty \:& x\notin dom\:f& \end{cases}$, f̃: Rⁿ → R, dom f̃: R,即将 f 的定义域由 C 扩展到 R，此函数依然为凸函数

常见凸函数与凹函数

仿射函数

f(x) = Ax + b,显然∇²f(x) = 0,因此仿射函数非凸非凹

指数函数

f(x) = e^ax, x ∈ R, ∇²f(x) = a²e^ax ≥ 0，凸函数

幂函数

f(x) = x^a, x ∈ R₊₊ $$\nabla^2f(x)=a(a-1)x^{a-2}=\begin{cases}\ge0&a\ge1, a\le0&\text{凸}\\\\\le0&a\in[0,1]&\text{凹}\end{cases}$$

负熵

$f(x)=xlogx, x\in R_{++}, f''(x)=\frac{1}{x}>0$，凸函数

范数

函数P(x)要想能称为范数，等价于满足以下三个条件 - P(ax) = |a|P(x) - P(x + y) ≤ P(x) + P(y) - P(x) = 0 ⇔ x = 0 由第二条性质可以容易的证明范数是凸函数

极大值函数

f(x) = max {x₁, …, x_n}, x ∈ Rⁿ

证明: $$\begin{aligned}&\forall x,y\in R^n, \forall\theta\in[0,1]\\&f(\theta x+(1-\theta)y)=max\{\theta x_i+(1-\theta)y_i, i=1,\ldots,n\}\leq\theta\max\{x_i\}+(1-\theta)\max\{y_i\}\end{aligned}$$

log-aum-up函数

f(x) = log (e^x₁ + ⋯ + e^x_n), x ∈ Rⁿ是凸的 由于极大函数往往不可导，log-sum-up函数其实就是对极大函数的解析逼近， max {x₁, ⋯, x_n} ≤ f(x) ≤ max {x₁ + ⋯ + x_n} + log n

讨论该函数的海森矩阵 $$H_{ij}=\begin{cases}\frac{\partial^2f}{\partial x_i\partial x_j}=\frac{-e^{x_i}e^{x_j}}{(e^{x_1}+\cdots+e^{x_n})^2}&\quad i\neq j\\[2ex]\frac{\partial^2f}{\partial x_i\partial x_i}=\frac{-e^{x_i}e^{x_i}+e^{x_i}(e^{x_1}+\cdots+e^{x_n})}{(e^{x_1}+\cdots+e^{x_n})^2}&\quad i=j\end{cases}$$

$$\left.H=\frac{1}{(e^{x_1}+\cdots+e^{x_n})^2}\left\{\left[\begin{array}{ccc}e^{x_1}(e^{x_1}+\cdots+e^{x_n})&\cdots&0\\\vdots&\ddots&\vdots\\0&\cdots&e^{x_n}(e^{x_1}+\cdots+e^{x_n})\end{array}\right.\right]-\left[\begin{array}{c}e^{x_1}\\\vdots\\e^{x_n}\end{array}\right]\cdot\left[\begin{array}{ccc}e^{x_1}&\cdots&e^{x_n}\end{array}\right]\right\}$$

令z = [e^x₁, …, e^x_n]，则上式可以写为

$$H=\frac{1}{(1\cdot z)^{2}}\left((1^{T}\cdot z) diag\{z\}-z\cdot z^{T}\right)$$

欲证明log-sum-up为凸，只需利用二阶条件证明 Hessian 矩阵的半正定性 计算v^THv

$$\begin{aligned}&=(1^{T}\cdot z) v^{T}diag\{z\}v-v^{T}z\cdot z^{T}v\\&=(\sum_{i}z_{i})(\sum_{i}v_{i}^{2} z_{i})-(\sum_{i}v_{i} z_{i})^{2}\end{aligned}$$

$$\begin{aligned}&\text{令 }a_i=v_i\sqrt{z_i}, b_i=\sqrt{z_i}\\&=(b^Tb)(a^Ta)-(a^Tb)^2\geq0\quad[Cauchy-Schwarz\text{不等式,得证}]\end{aligned}$$

行列式的对数

凹函数 f(x) = logdet(x), domf = S₊₊ⁿ

我们常使用定义二来证明高维的凸函数情况

∀z ∈ S₊₊ⁿ, ∀t ∈ R, ∀v ∈ R^n × n, z + tv ∈ S₊₊ⁿ = domf

$$\begin{aligned} g(t)=f(z+tv)& =log det(z+tv) \\ &=log det\{z^{\frac12}(I+tz^{-\frac12}vz^{-\frac12})z^{\frac12}\} \\ &=log det\{z\}+log det(I+tz^{-\frac12}vz^{-\frac12}) \end{aligned}$$

对后半部分做对称分解，有logdet(QQ^T + tQΛQ^T) = logdet(I + tΛ)

$$=log det\{z\}+\sum^nlog(1+t\lambda_i)\quad[\lambda_i\text{是}tz^{-\frac12}vz^{-\frac12}\text{的第 i 个特征根}]$$

$$\begin{aligned}g'(t)=\sum_i\frac{\lambda_i}{1+t\lambda_i},\quad g''(x)=\sum_i\frac{-\lambda_i}{(1+t\lambda_i)^2}\leq0\end{aligned}$$

保凸映射

非负加权和

• 若f₁, …, f_m都是凸函数，则f = ∑_iw_if_i为凸，其中w_i ≥ 0, ∀i 加权和函数定义域dom f = ∩_idom f_i

• 求和推广到积分也成立g(x) = ∫w(y)f(x, y)dy, w(y) ≥ 0

仿射映射和凸映射的复合函数

若f(x)为凸函数 - g(x) = f(Ax + b)是凸函数 - $g(x)=A^T\begin{bmatrix}f_1(x)\\\vdots\\f_n(x)\end{bmatrix}+b$是凸的，其中A ∈ Rⁿ, b ∈ R.

凸函数的极大值函数

若 f₁, f₂为凸函数,则极大值函数f(x) = max_x{f₁(x), f₂(x)}也为凸函数,其定义域为domf = domf₁ ∩ domf₂。

$$\begin{aligned} f(\theta x+(1-\theta)y)=& \begin{aligned}\max\{f_{1}(\theta x+(1-\theta)y),f_{2}(\theta x+(1-\theta)y)\}\end{aligned} \\ &\leq\max\{\theta f_1(x)+(1-\theta)f_1(y),\theta f_2(x)+(1-\theta)f_2(y)\} \\ &\leq\max\{\theta f_1(x),\theta f_2(x)\}+(1-\theta)\max\{(1-\theta)f_1(y),(1-\theta)f_2(y)\} \\ &=\theta f(x)+(1-\theta)f(y) \end{aligned}$$

自然地，推广到无穷个凸函数的极大值函数依然成立，因为无穷个凸函数的比较总可以看为多次进行函数之间的两两比较。

即：如果对于任意的y ∈ A,函数f(x, y)都是关于x的凸函数，则函数g(x) = sup_{y ∈ 𝒜}f(x, y)关于x也是凸的
其中sup为逐点取最大操作，称为上确界。

Q：求实对称矩阵的最大特征值，f(x) = λ_max(x), domf = S^m A： $$\begin{aligned}&Xy=\lambda y\Rightarrow y^TXy=\lambda y^Ty=\lambda\|y\|_2^2\Rightarrow\lambda=\frac{y^TXy}{\|y\|_2^2}\\&\text{令 }\|y\|_2^2=1\text{,则 }\lambda=y^TXy\\&f(x)=\lambda_{max}(x)=\sup\{y^TXy\mid\|y\|_2^2=1\}\\&\text{注意到 }y^TXy\text{ 是关于 x 的线性组合(将 }y^2\text{ 看作系数),同时 }\sup\text{保凸,所以该函数为凸函数}\end{aligned}$$

推导出：逐点上确界也是保凸映射1

复合函数

f = h(g(x)) 当函数都为一元函数时，f^′′ = h^′′g^′2 + h^′g^′′,分析这个式子与0的大小，可得 - 若h为不降的凸函数，g为凸函数，则f为凸函数 - 若h为不增的凸函数，g为凹函数，则f为凸函数 - 若h为不降的凹函数，g为凹函数，则f为凹函数 - 若h为不增的凹函数，g为凸函数，则f为凹函数

多元函数时，情况类似，需要对函数f的定义域做出扩展，例如 - 若g为凸，则exp {g(x)}为凸，因为满足上述1式 · - 若g为凹，则log {g(x}为凹，因为满足上述3式 - 若g为凹，g(x) > 0,则1/g(x)为凸，因为满足上述2式 - 若g为凸，g(x) ≥ 0,p ≥ 1,则g(x)^p为凸，因为满足上述1式

函数的透视

$$\begin{aligned}f: R^{n}&\to R, g: R^{n}\times R_{++}\to R\\&g(x,t)=tf(\frac{x}{t})\quad dom g=\{(x,t)\mid t\in R_{++},\frac{x}{t}\in dom f\}\end{aligned}$$

函数的透视有一个很重要的性质，若f为凸函数，则g也为凸函数，且对(x,t)是联合凸的，若f 为凹函数，则g对(x,t) 联合凹

由此导出的一些常用函数的凸性：
加权负对数是凸的 $$u,v\in R_{++}^n,g(u,v)=\sum_{i=1}^nu_i\log\frac{u_i}{v_i}$$ KL-Divergence是凸的（凸+线性=凸） $$D_{KL}(u,v)\triangleq\sum_{i=1}^{n}u_{i}log\frac{u_{i} }{v_{i} }-u_{i}+v_{i}$$

函数的共轭

函数f : Rⁿ → R的共轭f^* : Rⁿ → R表示为 f^*(y) = sup_{x ∈ domf}{y^Tx − f(x)}

性质 - 无论f是否凸，f^*(y)总是凸的(相当于无数条线取max，因此恒为凸) - f(x)如果可微，则f^*(y)对应的x就是f^′(x) = y的点([f^*(y)]_x^′ = y − f^′(x) = 0)

对于函数而言常常说共轭，对于问题而言常常说对偶

举几个求函数共轭的例子

求f(x) = ax + b , dom f = R的共轭函数 $$f^*(y)=\sup\limits_{x\in dom}\left(yx-(ax+b)\right)=\sup\limits_{x\in dom}\left((y-a)x+b\right)=\begin{cases}-b&\quad y=a\\[2ex]+\infty&\quad y\neq a\end{cases}$$

求f(x) = −logx, domf = R₊₊的共轭函数

$$\begin{aligned}\text{利用 }[f^*(x)]_x'&=y+\frac1x=0\text{,将 }x=-\frac1y\text{ 回代有 }-1-log(-y)\\f^*(y)&=\sup_{x>0} (yx+logx)=\begin{cases}-1-log(-y)&\quad y<0\\\\+\infty&\quad y\ge0\end{cases}\end{aligned}$$

求二次函数$f(x)=\frac{1}{2}x^{T}Q x, Q\in S_{++}^{n}, dom f=R^{n}$的共轭函数

$$f^*(y)=\sup (y^Tx-\frac{1}{2}x^TQx), [f^*(y)]_x^{\prime}=y-Qx=0$$ 回带消去x，$y^Tx-\frac{1}{2}x^TQx$化为 $$\begin{aligned}y^TQ^{-1}y-\frac{1}{2}y^TQ^{-1}Q^TQ^{-1}y=\frac{1}{2}y^TQ^{-1}y\end{aligned}$$

对于数而言，共轭的共轭为其自身，而这对函数并不成立，因为函数的共轭一定是凸函数，凹函数 的共轭的共轭一定不为自身 只有在f 为凸函数，并且为闭函数时，f的共轭的共轭才为自身

拟凸函数

α-sublevel-set (下水平集):任意函数 f : Rⁿ → R的 α-sublevel-set 为： C_α = {x ∈ domf|f(x) ≤ α}.

定义一

对于任意的α,其α-sublevel set均为凸集的函数为拟凸函数，又叫做单模态函数。

定义二

∀x, y ∈ domf, θ ∈ [0, 1], max {f(x), f(y)} ≥ f(θx + (1 − θ)y)

例子：向量的长度，向量x ∈ Rⁿ，即

$$f(x)=\left\{\begin{array}{ll}\max\{i,x_i\neq0\},&x\neq0\\0,&x=0\end{array}\right.$$

S_α = {f(x) ≤ α} ⇒ ∀i = ⌊i⌋ + 1…n, x_i = 0

相当于取子空间，S_α代表的是一些轴上取零，其余轴上的值任意，为凸集，因此f(x)为拟凸函数

例子：线性分数函数 $\begin{aligned}f(x)=\frac{a^Tx+b}{c^Tx+d}, dom f=\{x\mid c^Tx+d>0\}\end{aligned}$

$$S_{\alpha}=\{x\mid c^{T}x+d>0, \frac{a^{T}x+b}{c^{T}x+d}<\alpha\}=\{x\mid c^{T}x+d>0, ax+b\leq\alpha(c^{T}x+d)\}$$

该集合表示一个多面体，为凸集，因此f(x)为拟凸函数

优化性质分析

一般来说凸函数能用的算法拟凸函数也能用，拟凸函数是相对比较好做的非凸优化问题，不过与凸优化问题不同的是，他往往很难找到多项式时间内可以求解的算法

凸松弛

例，向量的零范数x ∈ ℝⁿ,f(x) = ∥x∥₀

一维情况，函数图像如下，不是凸函数，是拟凸函数

二维情况，函数图像如下，下水平集不是凸集，不是拟凸函数

1725031417805.png

通常求解稀疏约束问题时，可将零范数放缩、松弛为1范数

1725031464851.png

有的人会使用性质更好的函数去近似一范数

1725031517660.png

一阶条件

f 拟凸 ⇔ domf 凸,且若f(y) ≤ f(x),则 ∇^Tf(x)(y − x) ≤ 0.

以上公式文字表述为：拟凸函数只有一个极小值点。

拟凸函数梯度为0的点不一定是极小值点

二阶条件

domf 为凸,且 y^T∇f(x) ≥ 0 ⇒ y^T∇²f(x)y ≥ 0

• log 凸：f(x) > 0,若log f为凸函数，则f为log凸函数
  
• log 凹：f(x) > 0,若log f为凹函数，则f为log凹函数
  
• 若f为log凸，则f为凸。(提示：用复合函数凹凸性可判断)
• 若f为凹，则log f为log凹

参考文献/blog

• https://www.bilibili.com/video/BV19M411T7S7?p=20&vd_source=84b977d2834d5eca6c0ca78bd619156f，中科大/凌青《凸优化》，chapter9-20
• 知乎专栏，https://www.zhihu.com/column/c_1492543238217478144
• 知乎专栏，https://zhuanlan.zhihu.com/c_1280779583399882752
• 《ConvexOptimizationnotes》，https://github.com/ZxyGed/ConvexOptimization，Convex_Function pdf笔记