共轭函数
1 基础知识
定义1（共轭函数）
设 \(f: \mathbb{E} \to [-\infty, \infty]\) 是一个扩展实值函数。函数 \(f^{*}: \mathbb{E}^{*} \to [-\infty, \infty]\) 定义为：
\[f^{*}(y) = \max_{x \in \mathbb{E}} \{ \langle y, x \rangle - f(x) \}, \quad y \in \mathbb{E}^{*}
\]
称为 \(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) \geq \langle y, \hat{x} \rangle - f(\hat{x})
\]
因此 \(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(z) \geq f(x) + \langle g, z - x \rangle
\]
因此：
\[f^{*}(g) = \max_{z \in \mathbb{E}} \{ \langle g, z \rangle - f(z) \} \leq \langle g, x \rangle - f(x) < \infty
\]
从而得出 \(f^{*}\) 是适当函数。
定理3（Fenchel不等式）
设 \(f: \mathbb{E} \to (-\infty, \infty]\) 是一个扩展实值适当函数，则对任意 \(x \in \mathbb{E}\) 和 \(y \in \mathbb{E}^{*}\)，有：
\[f(x) + f^{*}(y) \geq \langle y, x \rangle
\]
证明：根据共轭函数的定义，对任意 \(x \in \mathbb{E}\) 和 \(y \in \mathbb{E}^{*}\)，有：
\[f^{*}(y) \geq \langle y, x \rangle - f(x)
\]
由于 \(f\) 是适当的，\(f(x)\) 和 \(f^{*}(y)\) 都大于 \(-\infty\)。在不等式两边加上 \(f(x)\) 即可得到所需结果。
2 双共轭
共轭运算可以进行两次，得到双共轭运算。具体来说，对于函数 \(f: \mathbb{E} \to [-\infty, \infty]\)，我们定义（回想本书中 \(\mathbb{E}\) 和 \(\mathbb{E}^{**}\) 被视为相同）：
\[f^{**}(x) = \max_{y \in \mathbb{E}^{*}} \{ \langle x, y \rangle - f^{*}(y) \}, \quad x \in \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}^{*}\)，有：
\[f^{*}(y) \geq \langle y, x \rangle - f(x)
\]
即：
\[f(x) \geq \langle y, x \rangle - f^{*}(y)
\]
因此：
\[f(x) \geq \max_{y \in \mathbb{E}^{*}} \{ \langle y, x \rangle - f^{*}(y) \} = f^{**}(x)
\]
定理4
设 \(f: \mathbb{E} \to (-\infty, \infty]\) 是一个适当闭凸函数，则 \(f^{**} = f\)。
3 共轭计算规则
定理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}^{*}\)，有：
\[g^{*}(y_{1}, y_{2}, \cdots, y_{p}) = \sum_{i=1}^{p} f_{i}^{*}(y_{i})
\]
证明：对任意 \((y_{1}, y_{2}, \cdots, y_{p}) \in \mathbb{E}_{1}^{*} \times \mathbb{E}_{2}^{*} \times \cdots \times \mathbb{E}_{p}^{*}\)，有：
\[\begin{aligned}
g^{*}(y_{1}, y_{2}, \cdots, y_{p})
&= \max_{x_{1}, x_{2}, \cdots, x_{p}} \left\{ \langle (y_{1}, y_{2}, \cdots, y_{p}), (x_{1}, x_{2}, \cdots, x_{p}) \rangle - g(x_{1}, x_{2}, \cdots, x_{p}) \right\} \\
&= \max_{x_{1}, x_{2}, \cdots, x_{p}} \left\{ \sum_{i=1}^{p} \langle y_{i}, x_{i} \rangle - \sum_{i=1}^{p} f_{i}(x_{i}) \right\} \\
&= \sum_{i=1}^{p} \max_{x_{i}} \left\{ \langle y_{i}, x_{i} \rangle - f_{i}(x_{i}) \right\} \\
&= \sum_{i=1}^{p} f_{i}^{*}(y_{i})
\end{aligned}
\]
定理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\) 的共轭为：
\[g^{*}(y) = f^{*}\left( (A^{T})^{-1}(y - b) \right) + \langle a, y \rangle - c - \langle a, b \rangle, \quad y \in \mathbb{V}^{*}
\]
证明：变量替换 \(z = A(x - a)\)，即 \(x = A^{-1}(z) + a\)，对任意 \(y \in \mathbb{V}^{*}\)，有：
\[\begin{aligned}
g^{*}(y)
&= \max_{x} \{ \langle y, x \rangle - g(x) \} \\
&= \max_{x} \{ \langle y, x \rangle - f(A(x - a)) - \langle b, x \rangle - c \} \\
&= \max_{z} \left\{ \langle y, A^{-1}(z) + a \rangle - f(z) - \langle b, A^{-1}(z) + a \rangle - c \right\} \\
&= \max_{z} \left\{ \langle y - b, A^{-1}(z) \rangle - f(z) + \langle a, y \rangle - \langle a, b \rangle - c \right\} \\
&= \max_{z} \left\{ \langle (A^{-1})^{T}(y - b), z \rangle - f(z) + \langle a, y \rangle - \langle a, b \rangle - c \right\} \\
&= f^{*}\left( (A^{T})^{-1}(y - b) \right) + \langle a, y \rangle - c - \langle a, b \rangle
\end{aligned}
\]
其中最后一个等式利用了 \((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)\) 的共轭为：
\[g^{*}(y) = \alpha f^{*}\left( \frac{y}{\alpha} \right), \quad y \in \mathbb{E}^{*}
\]
(b) 函数 \(h(x) = \alpha f\left( \frac{x}{\alpha} \right)\) 的共轭为：
\[h^{*}(y) = \alpha f^{*}(y), \quad y \in \mathbb{E}^{*}
\]
证明：
(a) 对任意 \(y \in \mathbb{E}^{*}\)，有：
\[\begin{aligned}
g^{*}(y)
&= \max_{x} \{ \langle y, x \rangle - g(x) \} \\
&= \max_{x} \{ \langle y, x \rangle - \alpha f(x) \} \\
&= \alpha \max_{x} \left\{ \langle \frac{y}{\alpha}, x \rangle - f(x) \right\} \\
&= \alpha f^{*}\left( \frac{y}{\alpha} \right)
\end{aligned}
\]
(b) 证明如下：
\[\begin{aligned}
h^{*}(y)
&= \max_{x} \{ \langle y, x \rangle - h(x) \} \\
&= \max_{x} \left\{ \langle y, x \rangle - \alpha f\left( \frac{x}{\alpha} \right) \right\} \\
&= \alpha \max_{x} \left\{ \langle y, \frac{x}{\alpha} \rangle - f\left( \frac{x}{\alpha} \right) \right\} \\
&= \alpha \max_{z} \{ \langle y, z \rangle - f(z) \} \quad (\text{令 } z = \frac{x}{\alpha}) \\
&= \alpha f^{*}(y)
\end{aligned}
\]
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\) 是适当凸函数，所以：
\[\begin{aligned}
& \langle x, y \rangle = f(x) + f^{*}(y) \\
\Leftrightarrow & f^{*}(y) = \langle x, y \rangle - f(x) = \max_{u \in \mathbb{E}} \{ \langle u, y \rangle - f(u) \} \\
\Leftrightarrow & 0 \in y - \partial f(x) \\
\Leftrightarrow & y \in \partial f(x)
\end{aligned}
\]
若 \(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}^{*}\)，有：
\[\partial f(x) = \underset{\tilde{y} \in \mathbb{E}^{*}}{\arg\max} \left\{ \langle x, \tilde{y} \rangle - f^{*}(\tilde{y}) \right\}
\]
和
\[\partial f^{*}(y) = \underset{\tilde{x} \in \mathbb{E}}{\arg\max} \{ \langle y, \tilde{x} \rangle - f(\tilde{x}) \}
\]
特别地，对任意适当闭凸函数 \(f\)，有：
\[\partial f(0) = \underset{y \in \mathbb{E}^{*}}{\arg\min} f^{*}(y)
\]
和
\[\partial f^{*}(0) = \underset{x \in \mathbb{E}}{\arg\min} f(x)
\]
定理9（Lipschitz连续性与共轭定义域的有界性）
设 \(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]\)