一、非负加权求和

凸函数的集合本身是一个凸锥：凸函数的非负加权求和仍然是凸函数，即函数：

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

可拓展至无限项的求和以及积分的情形。例如，如果固定任意$y \in \mathcal{A}$，函数$f(x, y)$关于$x$是凸函数，且对任意$y \in \mathcal{A}$，有$w(y) \geq 0$，则函数$g$

$$g(x) = \int_\mathcal{A} w(y)f(x, y) dy$$

关于$x$是凸函数。

还可以验证非负伸缩以及求和运算是保凸运算，例如：

如果$w \geq 0$且$f$是凸函数，我们有：

$$\mathbb{epi}(wf) = \begin{bmatrix} I & 0 \\ 0 & w\end{bmatrix} \mathbb{epi}f$$

因为凸集通过线性变换得到的像仍然是凸集，所以$\mathbb{epi}(wf)$是凸集。

二、复合仿射映射

假设函数$f :\mathbb{R}^n \rightarrow \mathbb{R}$，$A \in \mathbb{R}^{n\times m}$，以及$b \in \mathbb{R}^n$，定义$g:\mathbb{R}^m \rightarrow \mathbb{R}$为

其中$\textbf{dom}g = \{x |Ax+b \in \textbf{dom}f \}$。若函数$f$是凸函数，则函数$g$是凸函数；若函数$f$是凹函数，则函数$g$是凹函数。

三、逐点最大和逐点上确界

1. 逐点最大值

如果函数$f_1$和$f_2$均为凸函数，则二者的逐点最大函数$f$

其定义域为$\textbf{dom} f = \textbf{dom} f_1 \cap \textbf{dom} f_2$，仍然是凸函数。

证明：

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

因此函数$f$是凸函数。

拓展：如果函数$f_1, \cdots, f_m$为凸函数，则它们的逐点最大函数

仍然是凸函数。

1. 分片线性函数。函数

   $$f(x) = \max\{a_1^Tx + b_1, \cdots, a_L^Tx + b_L \}$$

   定义了一个分片线性（实际上是仿射）函数，因为它是一些列仿射函数的逐点最大值，所以它是凸函数。

   反之：任意具有$L$个或者更少区域的分片线性凸函数都可以表述成上述形式。

2. 最大$r$个分量之和

   对于任意$x \in \mathbb{R}^n$，用$x_{[i]}$表示$x$中第$i$大的分量，即将$x$的分量按照非升序进行排列得到下式

   $$x_{[1]} \geq x_{[2]} \geq \cdots \geq x_{[n]}.$$

   则对$x$的最大$r$个分量进行求和所得到的函数

   $$f(x) = \sum_{i=1}^r x_{[i]}.$$

   是凸函数。事实上，此函数可以表述为

   $$f(x)=\sum_{i=1}^r x_{[i]} = \max\{x_{i_1} + \cdots +x_{i_r} | 1 \leq i_1 < i_2 < \cdots <i_r \leq n \},$$

   即从$x$的分量中选取$r$个不同分量进行求和的所有可能组合的最大值。因为函数$f$是$\frac{n!}{(r!(n-r)!)}$个线性函数的逐点最大，所以是凸函数。

   作为一个扩展，可以证明当$w_1 \geq w_2 \geq \cdots \geq w_r \geq 0$时，函数$\sum_{i=0}^r w_i x_{[i]}$是凸函数。

2. 逐点上确界

逐点最大的性质可以拓展至无限个凸函数的逐点上确界。如果对于任意$y \in \mathcal{A}$，函数$f(x,y)$关于$x$都是凸的，则函数$g$

关于$x$亦是凸的。此时，函数$g$的定义域为

类似地，一系列凹函数的逐点下确界仍然是凹函数。

从上境图的角度解释：一系列函数的逐点上确值函数对应着这些函数上境图的交集。

对于函数$f, g$以及式（11）定义的$\mathcal{A}$，我们有

$$\mathbb{epi} g = \cap_{y \in \mathcal{A}} \textbf{epi} f(\cdot, y).$$

因此，函数$g$的凸性可由一些凸集的交集仍然是凸集得到。

注：此处的$y$可理解为函数$f(x,y)$的索引，从而表示有无限个凸函数。

3. 最小化

如果函数$f(x,y)$是凸函数，集合$C$是非空凸集，定义函数

若存在某个$x$使得$g(x) > -\infty$，则函数$g$关于$x$是凸函数。

任取$x_1, x_2 \in \textbf{dom} g$，我们利用 Jensen 不等式来证明上述结论。令$\epsilon >0$，则存在$y_1, y_2 \in C$，使$f(x_i, y_i) \leq g(x_i) + \epsilon (i = 1, 2)$.设$\theta \in [0, 1]$，我们有：

$$\begin{aligned} g(\theta x_1 +(1- \theta) x_2) &= \textbf{inf}_{y \in C} f(\theta x_1 + (1 - \theta) x_2, y)\\ &\leq f(\theta x_1 + (1 - \theta)x_2, \theta y_1 + (1 - \theta)y_2)\\ &\leq \theta f(x_1, y_1) + (1 - \theta)f(x_2, y_2)\\ &\leq \theta g(x_1) + (1 - \theta)g(x_2) + \epsilon \end{aligned}$$

因为上述对任意的$\epsilon > 0$均成立，所以下式成立：

$$g(\theta x_1 + (1 - \theta) x_2) \leq \theta g(x_1) +(1-\theta)g(x_2).$$

4. 复合

给定函数$h:\mathbb{R}^k \rightarrow \mathbb{R}$以及$g :\mathbb{R}^n \rightarrow \mathbb{R}^k$，定义复合函数$f = h \circ g:\mathbb{R}^n \rightarrow \mathbb{R}$为

我们考虑当函数$f$保凸或者保凹时，函数$h$和$g$必须满足的条件。

标量复合

因为对于符合函数$f : h \circ g$的二阶导数为

简单的复合结论：

• 如果$g$是凸函数，则$\textbf{exp} g(x)$是凸函数
• 如果$g$是凹函数且大于零，则$\log g(x)$是凹函数
• 如果$g$是凹函数且大于零，则$\frac{1}{g(x)}$是凸函数
• 如果$g$是凸函数且不小于零，$p \geq 1$，则$g(x)^p$是凸函数

矢量复合

设$f(x) = h(g(x)) = h(g_1(x), \cdots, g_k(x))$,其中$h:\mathbb{R}^k \rightarrow \mathbb{R}$, $g_i : \mathbb{R}^n \rightarrow \mathbb{R}$。

假设$f$二次可微，对函数$f$进行二次微分有：

5. 透视函数

给定函数$f:\mathbb{R}^n \rightarrow \mathbb{R}$，则$f$的透视函数$g: \mathbb{R}^n \times \mathbb{R} \rightarrow \mathbb{R}$定义为

其定义域为

透视函数是保凸运算：如果函数$f$是凸函数，则其投射函数$g$也是凸函数。类似地，若$f$是凹函数，则$g$亦是凹函数。

证明：

$$\begin{aligned} (x, s, t) \in \textbf{epi}g &\Leftrightarrow tf(x/t) \leq s\\ &\Leftrightarrow f(x/t) \leq s/t\\ &\Leftrightarrow (x/t, s/t) \in \textbf{epi} f. \end{aligned}$$