共軛函數

1 基礎知識

定義1（共軛函數）

設 \(f: \mathbb{E} \to [-\infty, \infty]\) 是一個擴展實值函數。函數 \(f^{*}: \mathbb{E}^{*} \to [-\infty, \infty]\) 定義為：

稱為 \(f\) 的共軛函數。

定理1（共軛函數的凸性與閉性）

設 \(f: \mathbb{E} \to (-\infty, \infty]\) 是一個擴展實值函數，則共軛函數 \(f^{*}\) 是閉且凸的。

證明：注意到 \(f^{*}\) 是仿射函數的逐點最大值，而仿射函數是凸且閉的，因此 \(f^{*}\) 是閉且凸的。

定理2（共軛函數的適當性）

設 \(f: \mathbb{E} \to (-\infty, \infty]\) 是一個適當凸函數，則 \(f^{*}\) 是適當的。

證明：由于 \(f\) 是適當的，存在 \(\hat{x} \in \mathbb{E}\) 使得 \(f(\hat{x}) < \infty\)。根據共軛函數的定義，對任意 \(y \in \mathbb{E}^{*}\)，有：

因此 \(f^{*}(y) > -\infty\)。要證明 \(f^{*}\) 的適當性，還需證明存在 \(g \in \mathbb{E}^{*}\) 使得 \(f^{*}(g) < \infty\)。存在 \(x \in \text{dom}(f)\) 使得 \(\partial f(x) \neq \emptyset\)，取 \(g \in \partial f(x)\)。根據次梯度的定義，對任意 \(z \in \mathbb{E}\)，有：

因此：

從而得出 \(f^{*}\) 是適當函數。

定理3（Fenchel不等式）

設 \(f: \mathbb{E} \to (-\infty, \infty]\) 是一個擴展實值適當函數，則對任意 \(x \in \mathbb{E}\) 和 \(y \in \mathbb{E}^{*}\)，有：

證明：根據共軛函數的定義，對任意 \(x \in \mathbb{E}\) 和 \(y \in \mathbb{E}^{*}\)，有：

由于 \(f\) 是適當的，\(f(x)\) 和 \(f^{*}(y)\) 都大于 \(-\infty\)。在不等式兩邊加上 \(f(x)\) 即可得到所需結果。

2 雙共軛

共軛運算可以進行兩次，得到雙共軛運算。具體來說，對于函數 \(f: \mathbb{E} \to [-\infty, \infty]\)，我們定義（回想本書中 \(\mathbb{E}\) 和 \(\mathbb{E}^{**}\) 被視為相同）：

引理1（\(f^{**} \leq f\)）

設 \(f: \mathbb{E} \to [-\infty, \infty]\) 是一個擴展實值函數，則對任意 \(x \in \mathbb{E}\)，有 \(f(x) \geq f^{**}(x)\)。

證明：根據共軛函數的定義，對任意 \(x \in \mathbb{E}\) 和 \(y \in \mathbb{E}^{*}\)，有：

即：

因此：

定理4

設 \(f: \mathbb{E} \to (-\infty, \infty]\) 是一個適當閉凸函數，則 \(f^{**} = f\)。

3 共軛計算規(guī)則

定理5（可分函數的共軛）

設 \(g: \mathbb{E}_{1} \times \mathbb{E}_{2} \times \cdots \times \mathbb{E}_{p} \to (-\infty, \infty]\) 由 \(g(x_{1}, x_{2}, \cdots, x_{p}) = \sum_{i=1}^{p} f_{i}(x_{i})\) 給出，其中對任意 \(i = 1, 2, \cdots, p\)，\(f_{i}: \mathbb{E}_{i} \to (-\infty, \infty]\) 是適當函數。則對任意 \(y_{i} \in \mathbb{E}_{i}^{*}\)，有：

證明：對任意 \((y_{1}, y_{2}, \cdots, y_{p}) \in \mathbb{E}_{1}^{*} \times \mathbb{E}_{2}^{*} \times \cdots \times \mathbb{E}_{p}^{*}\)，有：

定理6（\(f(A(x-a)) + \langle b, x \rangle + c\) 的共軛）

設 \(f: \mathbb{E} \to (-\infty, \infty]\) 是一個擴展實值函數，\(A: \mathbb{V} \to \mathbb{E}\) 是可逆線性變換，\(a \in \mathbb{V}\)，\(b \in \mathbb{V}^{*}\)，\(c \in \mathbb{R}\)。則函數 \(g(x) = f(A(x-a)) + \langle b, x \rangle + c\) 的共軛為：

證明：變量替換 \(z = A(x - a)\)，即 \(x = A^{-1}(z) + a\)，對任意 \(y \in \mathbb{V}^{*}\)，有：

其中最后一個等式利用了 \((A^{-1})^{T} = (A^{T})^{-1}\)。

定理7（\(\alpha f(\cdot)\) 和 \(\alpha f(\cdot / \alpha)\) 的共軛）

設 \(f: \mathbb{E} \to (-\infty, \infty]\) 是一個擴展實值函數，\(\alpha \in \mathbb{R}_{++}\)。
(a) 函數 \(g(x) = \alpha f(x)\) 的共軛為：

(b) 函數 \(h(x) = \alpha f\left( \frac{x}{\alpha} \right)\) 的共軛為：

證明：
(a) 對任意 \(y \in \mathbb{E}^{*}\)，有：

(b) 證明如下：

4 共軛函數的次梯度

定理8（共軛次梯度定理）

設 \(f: \mathbb{E} \to (-\infty, \infty]\) 是適當凸函數。對任意 \(x \in \mathbb{E}\)，\(y \in \mathbb{E}^{*}\)，以下兩個命題等價：
(i) \(\langle x, y \rangle = f(x) + f^{*}(y)\)
(ii) \(y \in \partial f(x)\)

此外，若 \(f\) 是閉的，則(i)和(ii)等價于：
(iii) \(x \in \partial f^{*}(y)\)

證明：因為 \(f\) 是適當凸函數，所以：

若 \(f\) 是閉的，由定理4知 \(f^{**} = f\)，這特別意味著(i)等價于 \(\langle x, y \rangle = g(y) + g^{*}(x)\)，其中 \(g = f^{*}\)。根據已建立的(i)和(ii)之間的等價性（應用于 \(g\)），得出(i)等價于 \(x \in \partial g(y) = \partial f^{*}(y)\)。

推論1（共軛次梯度定理-第二形式）

設 \(f: \mathbb{E} \to (-\infty, \infty]\) 是適當閉凸函數，則對任意 \(x \in \mathbb{E}\)，\(y \in \mathbb{E}^{*}\)，有：

和

特別地，對任意適當閉凸函數 \(f\)，有：

和

定理9（Lipschitz連續(xù)性與共軛定義域的有界性）

設 \(f: \mathbb{E} \to \mathbb{R}\) 是凸函數。對給定常數 \(L > 0\)，以下三個命題等價：
(i) 對任意 \(x, y \in \mathbb{E}\)，\(|f(x) - f(y)| \leq L \| x - y \|\)
(ii) 對任意 \(x \in \mathbb{E}\)，\(g \in \partial f(x)\)，\(\| g \|_{*} \leq L\)
(iii) \(\text{dom}(f^{*}) \subseteq B_{\| \cdot \|_{*}}[0, L]\)