保凸运算

3.2 保凸运算

3.2.1 非负加权求和

条件：

1. 如果函数$f$是凸函数
2. $\alpha \geq 0$

则：函数$\alpha f$也为凸函数。

如果函数$f_1$和$f_2$都是凸函数，则它们的和$f_1 + f_2$也是凸函数。

将非负伸缩以及求和运算结合起来，可以看出，凸函数的集合本身是一个凸锥：凸函数的非负加权求和仍然是凸函数，即

$$f = w_1f_1 + \cdots + w_mf_m,$$

是凸函数。

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

这个性质可以扩展至无限项的求和及积分的情况。例如，如果固定任意$y \in A$，函数$f(x, y)$关于$x$是凸函数，且对任意$y \in A$，有$w(y) > 0$，则函数

$$g(x) = \int_A w(y)f(x, y)\,dy$$

关于$x$是凸函数（条件：此积分存在）。

我们可以很容易地直接验证非负伸缩和求和运算是保凸运算，或者可以根据相关的上镜图得到此结论。例如，如果$w \geq 0$且$f$是凸函数，我们有

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

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

---

3.2.2 复合仿射映射

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

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

其中$\text{dom}\, g = \{x \mid Ax + b \in \text{dom}\, f\}$。

若函数$f$是凸函数，则函数$g$是凸函数；

若函数$f$是凹函数，那么函数$g$是凹函数。

---

3.2.3 凸点最大和凸点上确界

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

$$f(x) = \max\{f_1(x), f_2(x)\},$$

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

这个性质可以很容易验证：

任取$0 \leq \theta \leq 1$以及$x, y \in \text{dom}\, f$，有

$$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)\}$$ $$= \theta f(x) + (1-\theta)f(y).$$

从而说明了函数$f$的凸性。

同样可以很容易证明，如果函数$f_1, \cdots, f_m$为凸函数，则它们的凸点最大函数

$$f(x) = \max\{f_1(x), \cdots, f_m(x)\}$$

仍然是凸函数。

---

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

$$g(x) = \sup_{y \in A} f(x, y), \tag{3.7}$$

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

$$\text{dom}\, g = \{x \mid \forall y \in A, \sup_{y \in A} f(x, y) < \infty \}.$$

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

从上镜图的角度理解，一系列函数的凸点上确界函数对应着这些函数上镜图的交集。对于函数$f$, $g$以及式$(3.7)$定义的$A$，我们有

$$\text{epi}\, g = \bigcap_{y \in A} \text{epi}\, f(\cdot, y).$$

因此，函数$g$的凸性可由一系列凸集合的交集仍然是凸集得出。

---

表示成一族仿射函数的逐点上确界

上述例子描述了一个建立函数上确界的好方法：将其表示为一族仿射函数的逐点上确界。

反过来也能成立：几乎所有的凸函数都可以表示为一族仿射函数的逐点上确界。例如，如果函数$f: \mathbb{R}^n \to \mathbb{R}$是凸函数，其定义域为$\text{dom} \, f = \mathbb{R}^n$，我们有

$$f(x) = \sup\{g(x) \mid g \text{仿射}, g(z) \leq f(z) \, \forall z \}.$$

换言之，函数$f$是它所有的仿射下估计的逐点上确界。下面我们将证明这个结论。

---

设函数$f$是凸函数，定义域为$\text{dom} \, f = \mathbb{R}^n$，显然下面的不等式成立：

$$f(x) = \sup\{g(x) \mid g \text{仿射}, g(z) \leq f(z) \, \forall z \}.$$

因为函数$f$是函数$g$的任意仿射下估计，我们有$g(x) \leq f(x)$。为了建立等式，我们说明，对于任意$x \in \mathbb{R}^n$，存在仿射函数$g$是函数$f$的仿射下估计，并且满足$g(x) = f(x)$。

---

3.2.4 部分最小化

• 函数 $g(x) = \inf_{y \in C} f(x, y)$ 被称为 $f$ 关于 $y$ 的部分最小化。
• 如果 $f(x, y)$ 在 $(x, y)$ 上是凸的，且 $C$ 是凸集，则部分最小化 $g(x)$ 是凸的。

示例

1. 对于 $f(x, y) = x^T A x + 2x^T B y + y^T C y$，其中

   $$\begin{bmatrix} A & B \\ B^T & C \end{bmatrix} \succeq 0, \quad C > 0,$$

   对 $y$ 进行最小化得到：

   $$g(x) = \inf_y f(x, y) = x^T (A - BC^{-1}B^T)x.$$

   $g(x)$ 是凸的，因此 Schur 补 $A - BC^{-1}B^T \succeq 0$。

2. 到集合的距离：$\text{dist}(x, S) = \inf_{y \in S} \|x - y\|$ 在 $S$ 是凸集时是凸的。

---

3.2.5 复合

• 函数$g: \mathbb{R}^n \to \mathbb{R}$和$h: \mathbb{R} \to \mathbb{R}$的复合函数定义为$f(x) = h(g(x))$（记作$f = h \circ g$）。

• 复合函数$f$是凸函数，当且仅当满足以下条件：

  • $g$是凸函数，$h$是凸函数，并且$\tilde{h}$是非减函数；
  • 或者$g$是凹函数，$h$是凸函数，并且$\tilde{h}$是非增函数。

  （对于扩展值的函数$\tilde{h}$，需要满足单调性）

证明（对于$n = 1$且$g, h$可导）

$$f''(x) = h''(g(x))g'(x)^2 + h'(g(x))g''(x)$$

示例

1. 如果$g$是凸函数，则$f(x) = \exp(g(x))$是凸函数。
2. 如果$g$是凹函数且正值，则$f(x) = 1/g(x)$是凸函数。

一般复合规则

• 给定$g: \mathbb{R}^n \to \mathbb{R}^k$和$h: \mathbb{R}^k \to \mathbb{R}$，复合函数$f(x) = h(g(x)) = h(g_1(x), g_2(x), \ldots, g_k(x))$。
• 如果$h$是凸函数，并且对于每个$i$，以下条件之一成立，则$f$是凸函数：
  • $g_i$是凸函数，且$\tilde{h}$在其第$i$个变量上是非减的；
  • $g_i$是凹函数，且$\tilde{h}$在其第$i$个变量上是非增的；
  • $g_i$是仿射函数。

E.g.

• 函数$\log \sum_{i=1}^m \exp g_i(x)$是凸函数，如果$g_i$是凸函数。
• 函数$f(x) = \frac{p(x)^2}{q(x)}$是凸函数，如果：
  • $p(x)$是非负且凸的；
  • $q(x)$是正值且凹的。

复合规则包含的其他性质，例如：

• $\alpha f$是凸函数，如果$f$是凸函数且$\alpha \geq 0$；
• 凸函数（或凹函数）的和是凸函数（或凹函数）；
• 凸函数的最大值是凸函数；
• 凹函数的最小值是凹函数。

构造性凸性

1. 从给定的函数$f$表达式开始。
2. 为表达式构建解析树：
   • 叶子节点为变量或常量；
   • 非叶节点为子表达式的函数。
3. 使用复合规则为子表达式标注凸性（凸、凹、仿射或无）。
4. 如果根节点被标记为凸（凹），则函数$f$是凸（凹）的。
5. 扩展：为每个表达式标记符号，并结合符号相关的单调性规则。

---

• 这种方法足以证明$f$是凸（凹）的，但不必要。
• 这种验证凸性（凹性）的方法可以轻松自动化。

约束凸规划（Disciplined Convex Programming, DCP）

在约束凸规划（DCP）中，用户通过构造性凸性分析来构建凸函数和凹函数，表达式具有以下特点：

• 表达式由以下部分组成：
  • 变量，
  • 常量，
  • 来自库的原子函数。
• 原子函数具有已知的凸性、单调性和符号属性。
• 所有子表达式均符合一般复合规则。
• 一个有效的DCP函数满足以下条件：
  • 通过构造即为凸函数；
  • 语法上是凸的（可以“局部”验证）。

凸性依赖于原子函数的属性，而非其具体含义：

• 例如，可以替换$\sqrt{f}$与$f^{1/4}$，或$\exp$与$(\cdot)_+$，因为它们的属性相同。

3.2.6透视变换（Perspective）

• 函数$f: \mathbb{R}^n \to \mathbb{R}$的透视变换定义为函数$g: \mathbb{R}^n \times \mathbb{R} \to \mathbb{R}$：

  $$g(x, t) = t f(x / t),$$

  其定义域为：

  $$\text{dom} \, g = \{(x, t) \mid x / t \in \text{dom} \, f, \, t > 0\}.$$

• 如果$f$是凸函数，则$g$是凸函数。

示例

1. 若$f(x) = x^T x$是凸函数，则$g(x, t) = x^T x / t$在$t > 0$时是凸函数。
2. 若$f(x) = -\log x$是凸函数，则相对熵函数$g(x, t) = t \log t - t \log x$在$\mathbb{R}_+^2$上是凸函数。

---

3.2.7共轭函数（Conjugate Function）

• 函数$f$的共轭函数定义为：

  $$f^*(y) = \sup_{x \in \text{dom} \, f} \big( y^T x - f(x) \big).$$

• 共轭函数$f^*$是凸的，即使原函数$f$不是凸函数。

图示说明

函数 $f: \mathbb{R} \to \mathbb{R}$ 以及某一 $y \in \mathbb{R}$ 的共轭函数 $f^*(y)$ 是线性函数 $y x$ 和 $f(x)$ 之间的最大差值，如图中的虚线所示。

如果 $f$ 可微，则在满足 $f'(x) = y$ 的点 $x$ 处，差值达到最大。

---

考虑 $\mathbb{R}$ 上一些凸函数的共轭函数

1. 仿射函数
   函数 $f(x) = ax + b$。作为 $y x$ 的函数，当且仅当 $y = a$（即为常数）时，$y x - ax - b$ 有界。因此，共轭函数 $f^*$ 的定义域为单点集 $\{a\}$，且 $f^*(a) = -b$。

2. 负对数函数
   函数 $f(x) = -\log x$，定义域为 $\text{dom} \, f = \mathbb{R}_{++}$。

   • 当 $y \geq 0$ 时，函数 $y x + \log x$ 无上界；
   • 当 $y < 0$ 时，在 $x = -1 / y$ 处函数达到最大值。
     因此，定义域为 $\text{dom} \, f^* = \{y \mid y < 0\} = -\mathbb{R}_{++}$，共轭函数为 $f^*(y) = -\log(-y) - 1$。

3. 指数函数
   函数 $f(x) = e^x$。

   • 当 $y < 0$ 时，函数 $y x - e^x$ 无上界；
   • 当 $y > 0$ 时，函数在 $x = \log y$ 处达到最大值。
     因此，$f^*(y) = y \log y - y$。当 $y = 0$ 时，$f^*(y) = \sup -e^x = 0$（规定 $0 \log 0 = 0$）。综合可得，$\text{dom} \, f^* = \mathbb{R}_+$。

4. 负幂函数
   函数 $f(x) = x \log x$，定义域 $\text{dom} \, f = \mathbb{R}_+$（与上述类似，$f(0) = 0$）。
   对于所有 $y$，函数 $y x - x \log x$ 在 $\mathbb{R}_+$ 上有上界。因此，$\text{dom} \, f^* = \mathbb{R}_+$，在 $x = e^{y-1}$ 处函数达到最大值，$f^*(y) = e^{y-1}$。

5. 反函数
   函数 $f(x) = 1 / x$，定义域为 $\mathbb{R}_{++}$。

   • 当 $y > 0$ 时，函数 $y x - 1 / x$ 无上界；
   • 当 $y < 0$ 时，在 $x = (-y)^{-1/2}$ 处达到上确界。
     因此，$f^*(y) = -2(-y)^{1/2}$，且 $\text{dom} \, f^* = -\mathbb{R}_+$。

---

共轭函数性质

Fenchel 不等式

从共轭函数的定义可以得到，对于任意$x$和$y$，如下不等式成立：

$$f(x) + f^*(y) \geq x^T y,$$

上述不等式即为 Fenchel 不等式（当$f$可微时称为 Young 不等式）。
以函数 $f(x) = \frac{1}{2}x^T Q x$ 为例，其中 $Q \in \mathbb{S}_{++}^n$，我们可以得到如下不等式：

$$x^T y \leq \frac{1}{2}x^T Q x + \frac{1}{2}y^T Q^{-1} y.$$

共轭的共轭

上面的例子以及“共轭”的名称都隐含了凸函数的共轭函数的共轭函数是原函数。
也即：如果函数$f$是凸函数且$f$是闭的（即 $\text{epi} \, f$ 是闭集，见§A.3.3），则 $f^{**} = f$。

可微函数

可微函数$f$的共轭函数亦称为函数$f$的 Legendre 变换。
为区分一般情况和可微情况下定义的共轭，通常将共轭有时称为 Fenchel 共轭。

设函数$f$是凸且可微，其定义域为 $\text{dom} \, f = \mathbb{R}^n$，使 $y^T x - f(x)$ 取最大的$x^*$ 满足 $y = \nabla f(x^*)$。反之，若$x^*$ 满足 $y = \nabla f(x^*)$，则在 $x^*$ 处达到最大值。因此，

$$f^*(y) = x^T \nabla f(x) - f(x).$$

所以，给定任意$y$，我们可以求解梯度方程 $y = \nabla f(x)$，从而得到 $y$ 的共轭函数 $f^*(y)$。

换一个角度理解。若选定 $z \in \mathbb{R}^n$，令 $y = \nabla f(z)$，则：

$$f^*(y) = z^T \nabla f(z) - f(z).$$

---

伸缩变换和复合仿射变换

1. 伸缩变换
   若 $a > 0$ 以及 $b \in \mathbb{R}$，则 $g(x) = a f(x) + b$ 的共轭函数为：

   $$g^*(y) = a f^*(y / a) - b.$$

2. 复合仿射变换
   若 $A \in \mathbb{R}^{n \times n}$ 非奇异，$b \in \mathbb{R}^n$，则函数 $g(x) = f(Ax + b)$ 的共轭函数为：

   $$g^*(y) = f^*(A^{-T}y) - b^T A^{-T}y,$$

   其定义域为：

   $$\text{dom} \, g^* = A^T \text{dom} \, f^*.$$

---

独立函数的和

若函数 $f(u, v) = f_1(u) + f_2(v)$，其中 $f_1$ 和 $f_2$ 是凸函数，且共轭函数分别为 $f_1^*$ 和 $f_2^*$，则：

$$f^*(w, z) = f_1^*(w) + f_2^*(z).$$

换言之，独立凸函数的和的共轭函数是各个凸函数的共轭函数的和。
（“独立”是指每个函数具有不同的变量。）

3.3准凸函数（Quasiconvex Functions）

• 函数 $f: \mathbb{R}^n \to \mathbb{R}$ 是准凸的，当且仅当 $\text{dom} \, f$ 是凸集，且所有的下水平集：

  $$S_\alpha = \{x \in \text{dom} \, f \mid f(x) \leq \alpha\}$$

  对所有 $\alpha$ 都是凸集。

---

特性

1. 如果 $f$ 是准凹函数，则 $-f$ 是准凸函数。
2. 如果 $f$ 同时是准凸和准凹函数，则 $f$ 是准线性的（quasilinear）。

---

图示

• 图中展示了下水平集 $S_\alpha$ 和 $S_\beta$ 分别对应的 $\alpha$ 和 $\beta$ 水平线。
• 水平集的凸性直接说明了函数 $f$ 的准凸性质。

E.G.

1. $\sqrt{|x|}$ 是准凸函数，定义域为 $\mathbb{R}$。
2. $\text{ceil}(x) = \inf \{z \in \mathbb{Z} \mid z \geq x\}$ 是准线性函数。
3. $\log x$ 是准线性函数，定义域为 $\mathbb{R}_{++}$。
4. 函数 $f(x_1, x_2) = x_1 x_2$ 是准凹函数，定义域为 $\mathbb{R}_{++}^2$。

5. 线性分式函数：

   $$f(x) = \frac{a^T x + b}{c^T x + d},$$

   定义域为：

   $$\text{dom} \, f = \{x \mid c^T x + d > 0\},$$

   是准线性函数。

准凸函数的性质

1. 修改后的Jensen不等式
   对于准凸函数$f$，有：

   $$0 \leq \theta \leq 1 \implies f(\theta x + (1-\theta) y) \leq \max\{f(x), f(y)\}.$$

2. 一阶条件（First-order condition）
   如果$f$是可微函数且定义域是凸集，则$f$是准凸的，当且仅当：

   $$f(y) \leq f(x) \implies \nabla f(x)^T (y - x) \leq 0.$$

   这一条件的几何解释：当$y$在$x$的等值面的一侧时，梯度方向与$(y-x)$方向相反。

3. 准凸函数和的性质
   准凸函数的和不一定是准凸的。