凸优化
凸函数
保凸运算

保凸运算

非负加权求和

如果函数 f1,⋯ ,fmf_1, \cdots, f_m 都是凸函数，ω1,⋯ ,ωm∈R+\omega_1, \cdots, \omega_m \in \mathbf{R}_+，那么

f=ω1f1+⋯+ωmfm f = \omega_1 f_1 + \cdots + \omega_m f_m

是凸函数。

类似地，凹函数的非负加权求和仍然是凹函数。当然，严格凸函数的非零加权求和也是严格凸函数。

这个性质可以扩展至无限项求和以及积分的情形。例如，如果固定任意 y∈Ay \in \mathcal{A}，有 ω(y)⩾0\omega(y) \geqslant 0，则函数

g(x)=∫Aω(y)f(x,y)dy g(x) = \int _\mathcal{A} \omega(y) f(x,y) \mathrm{d} y

是关于 xx 的凸函数。

复合仿射映射

假设函数 f:Rn→Rf: \mathbf{R}^n \rightarrow \mathbf{R}，A∈Rn×mA \in \mathbf{R}^{n \times m}，以及 b∈Rnb \in \mathbf{R}^n，定义函数 g:Rm→Rg: \mathbf{R}^m \rightarrow \mathbf{R} 为

g(x)=f(Ax+b) g(x) = f(Ax + b)

其中 dom⁡g={x∣Ax+b∈dom⁡f}\operatorname{dom} g = \{ x \mid Ax + b \in \operatorname{dom} f \}。若函数 ff 是凸函数，则函数 gg 也是凸函数。

逐点最大和逐点上确界

如果函数 f1f_1 和 f2f_2 均为凸函数，则它们的逐点最大函数

f(x)=max⁡{f1(x),f2(x)} f(x) = \max \{ f_1(x), f_2(x) \}

和逐点上确界函数

g(x)=sup⁡{f1(x),f2(x)} g(x) = \sup \{ f_1(x), f_2(x) \}

都是凸函数，并且可以推广至 mm 个凸函数的情形。同理，mm 个凹函数的逐点最小和逐点下确界函数也都是凹函数。

复合

给定函数 h:Rk→Rh: \mathbf{R}^k \rightarrow \mathbf{R} 以及 g:Rn→Rkg: \mathbf{R}^n \rightarrow \mathbf{R}^k，定义复合函数 f=h∘g:Rn→Rf = h \circ g : \mathbf{R}^n \rightarrow \mathbf{R} 为

f(x)=h(g(x)) f(x) = h(g(x))

判断其凸性还需要 hh 和 gg 满足一定的条件。

标量复合

现在我们考虑 k=1k=1 这个简单的情形。如果我们仅考虑 n=1n=1 的情况，其实就是我们高中所学习的复合函数。为了判断 ff 的凸性，我们需要求其二阶导数：

f′′(x)=h′′(g(x))g′(x)2+h′(g(x))g′′(x) f^{\prime \prime}(x)=h^{\prime \prime}(g(x)) g^{\prime}(x)^{2}+h^{\prime}(g(x)) g^{\prime \prime}(x)

根据非负加权求和的保凸性质，我们可以得出如下结论：

hh 的凸性 hh 的单调性 gg 的凸性 ff 的凸性
凸函数 单调递增 凸函数 凸函数
凸函数 单调递减 凹函数 凸函数
凹函数 单调递增 凹函数 凹函数
凹函数 单调递减 凸函数 凹函数

只有上表当中的四种情况可以判断函数 ff 的凸性，而还有另外四种情况不能够判断函数 ff 的凸性。

现在考虑更一般的情况，即 n>1n>1，那么相似的复合规则仍然成立：

hh 的凸性 h~\tilde {h} 的单调性 gg 的凸性 ff 的凸性
凸函数 单调递增 凸函数 凸函数
凸函数 单调递减 凹函数 凸函数
凹函数 单调递增 凹函数 凹函数
凹函数 单调递减 凸函数 凹函数

其中，h~\tilde {h} 表示函数 hh 的扩展值延伸。

我们可以通过我们在高中时学习的一些初等函数来更好地理解复合定理中函数 hh 需要满足的条件。

  • 函数 h(x)=log⁡xh(x) = \log{x}，定义域为 R++\mathbf{R}_{++}，为凹函数且 h~\tilde {h} 单调递增。
  • 函数 h(x)=xh(x) = \sqrt{x}，定义域为 R+\mathbf{R}_{+}，为凹函数且 h~\tilde {h} 单调递增。
  • 函数 h(x)=x3/2h(x) = x^{3/2}，定义域为 R+\mathbf{R}_{+}，为凸函数，但是不满足 h~\tilde {h} 单调递增的条件。例如 h~(−1)=∞\tilde {h}(-1) = \infty，但 h~(1)=1\tilde {h}(1) = 1。如果我们定义当 x<0x<0 时，h(x)=0h(x) = 0，使得 dom⁡h=R\operatorname{dom} h = \mathbf{R}，那么 hh 是凸函数且满足 h~\tilde {h} 单调递增的条件。

有如下简单的复合结论成立：

  • 如果 gg 是凸函数，那么 exp⁡g(x)\exp g(x) 是凸函数。
  • 如果 gg 是凹函数且恒正，则 log⁡g(x)\log g(x) 是凹函数。
  • 如果 gg 是凹函数且恒正，则 1/g(x)1/g(x) 是凸函数。
  • 如果 gg 是凸函数且非负，p⩾1p \geqslant 1，则 (g(x))p(g(x))^p 是凸函数。
  • 如果 gg 是凸函数，则 −log⁡(−g(x))-\log (-g(x)) 在 {x∣g(x)<0}\{ x \mid g(x) < 0 \} 上是凸函数。

矢量复合

下面考虑 k⩾1k \geqslant 1 的情况，虽然情况更复杂一些，但也可以得到类似标量的结论。同样地，我们求出 ff 的二阶导数：

f′′(x)=g′(x)⊤∇2h(g(x))g′(x)+∇h(g(x))⊤g′′(x) f^{\prime \prime}(x)=g^{\prime}(x)^{\top} \nabla^{2} h(g(x)) g^{\prime}(x)+\nabla h(g(x))^{\top} g^{\prime \prime}(x)

根据标量复合的结论，我们得到矢量复合的类似性质如下：

hh 的凸性 hh 的每维分量的单调性 gg 的凸性 ff 的凸性
凸函数 单调递增 凸函数 凸函数
凸函数 单调递减 凹函数 凸函数
凹函数 单调递增 凹函数 凹函数

最小化

我们已经得到，任意个凸函数的逐点最大或者上确界仍然是凸函数。事实上，一些特殊形式的最小化同样可以得到凸函数。如果函数 f(x,y)f(x, y) 是凸函数，集合 CC 是非空凸集，那么函数

g(x)=inf⁡y∈Cf(x,y) g(x) = \inf _{y \in C} f(x, y)

是凸函数只需要满足 g(x)g(x) 可以取得有限值即可。函数 gg 的定义域是 dom⁡f\operatorname{dom} f 在 xx 方向上的投影，即

dom⁡g={x∣∃y∈C,s.t.⁡(x,y)∈dom⁡f} \operatorname{dom} g = \{ x \mid \exists y \in C, \operatorname{s.t.} (x, y) \in \operatorname{dom} f \}

透视函数

我们已经知道透视运算是保凸运算。那么显然，如果函数 ff 是凸函数，则其透视函数 g(x,t)=tf(x/t)g(x, t) = tf(x/t) 也是凸函数。

重要凸函数共轭函数