若干知识点补充（二）

共轭函数、凸集与凸函数

小象实战讲义 · 人工智能数学基础

在优化理论与机器学习中，我们经常需要处理复杂的函数和集合。为了更有效地分析和求解最优化问题，数学家们引入了一些结构良好的数学对象。本节将介绍三个核心概念：共轭函数、凸集与凸函数。理解它们不仅有助于我们洞察优化问题的几何本质，更是掌握后续对偶理论、凸优化等高级内容的关键基石。学完本节，你将能够定义并识别凸集与凸函数，理解共轭函数的构造与意义，并掌握证明函数凸性的基本方法。

💡 核心导读

本节将构建从基础定义到实际应用的知识地图：

1. 共轭函数：学习如何通过”取上确界”的操作，从一个（可能非凸的）函数构造出一个新的凸函数，理解其几何意义及其与后续拉格朗日对偶的联系。
2. 凸集：掌握凸集的严格数学定义与直观几何解释，学会判断一个集合是否为凸集，并了解其与仿射集、凸组合等概念的关系。
3. 凸函数：深入理解凸函数的定义式（Jensen不等式）及其两种几何解释（切线在下、弦在上）。这是判断函数凸性的根本依据。
4. 凸性判定：掌握两种最实用的凸函数判定方法：一是将其转化为一元函数进行验证；二是通过计算并判断其Hessian矩阵（黑塞矩阵）是否半正定。
5. 实例演练：以逻辑回归的损失函数为例，完整演示两种判定凸函数的方法，将理论应用于机器学习中的经典模型。

共轭函数

定义与几何解释

设函数 $f: \mathbb{R}^n \to \mathbb{R}$，我们定义其共轭函数 $f^$: \mathbb{R}^n \to \mathbb{R}f∗:Rn→R 为： $$f^$$(y) = \sup_{x \in \text{dom} f} \left( y^T x - f(x) \right) 其中，$\text{dom} f$ 是 $f$ 的定义域，$\sup$ 表示上确界。

理解要点：

1. 变量：表达式 $g(x, y) = y^T x - f(x)$ 是一个关于 $2n$ 维变量 $(x, y)$ 的函数。
2. 操作：对固定的 $y$，我们在 $x$ 的定义域内寻找使 $g(x, y)$ 最大的 $x$（即取上确界）。这个操作”消去”了变量 $x$，最终结果 $f^*(y)$ 仅是 $y$ 的函数。
3. 几何意义（一元情形）：当 $n=1$ 时，$y^T x$ 退化为 $yx$，即一条过原点、斜率为 $y$ 的直线。$f^$(y)f∗(y) 就是这条直线与函数 $f(x)$ 图像之间，在竖直方向上的最大差值。对于给定的斜率 $y$，$f^$(y) 等于直线 $y \cdot x$ 与曲线 $f(x)$ 之间的最大垂直距离。

重要性质

1. 凸性：无论原函数 $f$ 是否为凸函数，其共轭函数 $f^$f∗ 一定是凸函数。这是因为 $f^$(y) 是一系列关于 $y$ 的仿射函数 $y^T x - f(x)$（每个 $x$ 对应一个）的上确界，而仿射函数是凸函数，凸函数的上确界仍是凸函数。
2. 可微情形下的极值点：如果 $f$ 可微，那么使 $y^T x - f(x)$ 达到上确界的 $x$ 满足一阶最优性条件。对 $x$ 求导并令其为零： $$\frac{\partial}{\partial x} (y^T x - f(x)) = y - \nabla f(x) = 0$$ 即最优解 $x$ 满足 $y = \nabla f(x)$。这意味着，在可微的情况下，共轭函数在 $y$ 处的值，是由梯度等于 $y$ 的那些点 $x$ 所决定的。

示例：二次函数的共轭

考虑严格凸的二次函数 $f(x) = \frac{1}{2} x^T Q x$，其中 $Q \in \mathbb{R}^{n \times n}$ 是对称正定矩阵。求其共轭函数 $f^*(y)$。

求解过程： 根据定义，$f^*(y) = \sup_{x \in \mathbb{R}^n} \left( y^T x - \frac{1}{2} x^T Q x \right)$。

1. 对于固定的 $y$，括号内的函数关于 $x$ 是凹的二次函数（因为 $-Q$ 负定）。其最大值在梯度为零的点取得。
2. 计算梯度并令其为零： $$\nabla_x (y^T x - \frac{1}{2} x^T Q x) = y - Q x = 0$$ 解得 $x = Q^{-1} y$。
3. 将最优解 $x = Q^{-1} y$ 代回原表达式： $$\begin{aligned} f^$$(y) &= y^T (Q^{-1} y) - \frac{1}{2} (Q^{-1} y)^T Q (Q^{-1} y) \ &= y^T Q^{-1} y - \frac{1}{2} y^T Q^{-1} Q Q^{-1} y \ &= y^T Q^{-1} y - \frac{1}{2} y^T Q^{-1} y \ &= \frac{1}{2} y^T Q^{-1} y. \end{aligned}f∗(y)​=yT(Q−1y)−21​(Q−1y)TQ(Q−1y)=yTQ−1y−21​yTQ−1QQ−1y=yTQ−1y−21​yTQ−1y=21​yTQ−1y.​ 因此，严格凸二次函数 $f(x) = \frac{1}{2} x^T Q x$ 的共轭函数是另一个二次函数 $f^$(y) = \frac{1}{2} y^T Q^{-1} y。

import numpy as np

# 定义对称正定矩阵Q
np.random.seed(42)
A = np.random.randn(3, 3)
Q = A.T @ A + np.eye(3) * 0.1  # 确保正定

# 定义原函数 f(x) = 0.5 * x^T Q x
def f(x, Q):
    return 0.5 * x.T @ Q @ x

# 定义其共轭函数 f*(y) = 0.5 * y^T Q^{-1} y
def f_star(y, Q):
    Q_inv = np.linalg.inv(Q)
    return 0.5 * y.T @ Q_inv @ y

# 验证共轭关系：对于随机y，计算 sup_x (y^T x - f(x))
y = np.array([1.0, -0.5, 2.0])
# 根据理论，最优 x = Q^{-1} y
x_opt = np.linalg.solve(Q, y)  # 等价于 Q^{-1} y

# 计算 f*(y) 的理论值
theory_value = f_star(y, Q)

# 通过数值优化验证（使用梯度为零的条件，这里直接代入最优解）
numerical_value = y @ x_opt - f(x_opt, Q)

print(f"理论计算的共轭函数值 f*(y): {theory_value:.6f}")
print(f"代入最优x计算的 y^T x - f(x): {numerical_value:.6f}")
print(f"两者是否接近: {np.isclose(theory_value, numerical_value)}")

凸集

定义

集合 $S \subseteq \mathbb{R}^n$ 称为凸集，如果对于任意 $x, y \in S$ 和任意标量 $\alpha \in [0, 1]$，都有： $$\alpha x + (1-\alpha) y \in S.$$ 这个点 $\alpha x + (1-\alpha) y$ 称为 $x$ 和 $y$ 的凸组合。

几何解释

凸集的定义意味着：连接集合中任意两点的线段整个都包含在该集合之内。这是判断一个集合是否为凸集最直观的方法。

示例：

• 凸集：实心圆、实心球、整个空间 $\mathbb{R}^n$、超平面、半空间。
• 非凸集：空心圆（不含内部）、星形、有凹痕的多边形。因为总能在其中找到两点，使得它们之间的部分线段落在集合外部。

相关概念：仿射集、凸组合与仿射组合

1. 仿射集：如果集合 $S$ 满足：对于任意 $x, y \in S$ 和任意标量 $\alpha \in \mathbb{R}$，都有 $\alpha x + (1-\alpha) y \in S$，则 $S$ 称为仿射集。与凸集定义相比，它将 $\alpha$ 的取值范围从 $[0,1]$ 扩大到全体实数 $\mathbb{R}$，要求在更大的范围上成立，约束更严格。几何上，仿射集包含通过其中任意两点的整条直线。仿射集是凸集的特例（满足仿射集定义的集合一定是凸集，但凸集不一定是仿射集）。
2. 凸组合：点 $x_1, x_2, \dots, x_k$ 的一个凸组合是指形如 $\sum_{i=1}^k \alpha_i x_i$ 的点，其中系数 $\alpha_i \ge 0$ 且 $\sum_{i=1}^k \alpha_i = 1$。
3. 仿射组合：点 $x_1, x_2, \dots, x_k$ 的一个仿射组合是指形如 $\sum_{i=1}^k \alpha_i x_i$ 的点，其中系数 $\alpha_i \in \mathbb{R}$ 且 $\sum_{i=1}^k \alpha_i = 1$。仿射组合对系数没有非负要求。

凸集的一个重要性质是：凸集包含其中任意有限个点的所有凸组合。

凸函数

定义

设 $S \subseteq \mathbb{R}^n$ 是一个凸集，函数 $f: S \to \mathbb{R}$。如果对于任意 $x, y \in S$ 和任意 $\alpha \in [0, 1]$，都有： $$f(\alpha x + (1-\alpha) y) \le \alpha f(x) + (1-\alpha) f(y),$$ 则称 $f$ 是 $S$ 上的一个凸函数。如果不等式对于 $x \neq y$ 和 $\alpha \in (0,1)$ 严格成立（即 $<$），则称 $f$ 是严格凸函数。

这个不等式称为 Jensen 不等式，是凸函数最本质的定义。

几何解释

1. 弦在上方：对于定义域内任意两点 $(x, f(x))$ 和 $(y, f(y))$，连接这两点的弦（线段）始终位于函数图像的上方（或之上）。
2. 切线在下方（可微函数）：如果 $f$ 是可微的凸函数，那么函数图像在其定义域内任意一点处的切线（或切平面）都在该点处位于图像的下方（或之上）。

凹函数：如果将定义中的不等式符号反向（$\ge$），则称 $f$ 为凹函数。显然，$f$ 是凸函数当且仅当 $-f$ 是凹函数。

凸函数的判定定理（等价定义）

对于二次连续可微（$C^2$）的函数 $f: \mathbb{R}^n \to \mathbb{R}$，以下命题等价，它们提供了判定凸函数的有力工具：

1. $f$ 是凸函数。
2. 对任意 $x, y \in \mathbb{R}^n$，一元函数 $\phi(t) = f(x + t(y-x))$ 在 $t \in [0,1]$ 上是凸的。
3. （一阶条件）对任意 $x, y \in \mathbb{R}^n$，有 $f(y) \ge f(x) + \nabla f(x)^T (y-x)$。
4. （梯度单调性）对任意 $x, y \in \mathbb{R}^n$，有 $(\nabla f(y) - \nabla f(x))^T (y-x) \ge 0$。
5. （二阶条件）对任意 $x \in \mathbb{R}^n$，Hessian 矩阵 $\nabla^2 f(x)$ 是半正定的，即对任意 $v \in \mathbb{R}^n$，有 $v^T \nabla^2 f(x) v \ge 0$。

最常用的判定方法：

• 方法一（定理第2条）：将多元函数的凸性判定，转化为验证一个相关的一元函数 $\phi(t)$ 的凸性。这通常通过计算 $\phi”(t) \ge 0$ 来实现。
• 方法二（定理第5条）：计算函数的 Hessian 矩阵，并验证其在整个定义域内是半正定的。这是多元函数凸性判定的直接方法。

凸函数的运算性质

以下性质可以帮助我们构造新的凸函数：

1. 非负加权和：若 $f_1, f_2, \dots, f_m$ 是凸函数，$\omega_1, \omega_2, \dots, \omega_m \ge 0$，则 $\sum_{i=1}^m \omega_i f_i$ 也是凸函数。
2. 仿射变换：若 $f$ 是凸函数，则 $g(x) = f(Ax + b)$ 也是凸函数（在适当的定义域上）。
3. 逐点最大值：若 $f_1, f_2$ 是凸函数，则 $f(x) = \max{f_1(x), f_2(x)}$ 也是凸函数。

实例：逻辑回归损失函数的凸性证明

逻辑回归模型中，常需要最小化负对数似然函数（即损失函数）。对于二分类问题，该函数形式为： $$J(\omega, b) = -\sum_{i=1}^N \left[ y_i \log \sigma(\omega^T x_i + b) + (1-y_i) \log (1 - \sigma(\omega^T x_i + b)) \right],$$ 其中 $\sigma(z) = 1/(1+e^{-z})$ 是 sigmoid 函数，$y_i \in {0,1}$ 是标签，$x_i \in \mathbb{R}^{p-1}$ 是特征向量。

为简化记号，令 $W = [\omega^T, b]^T \in \mathbb{R}^p$，$\tilde{x}_i = [x_i^T, 1]^T \in \mathbb{R}^p$，则 $\omega^T x_i + b = W^T \tilde{x}_i$。损失函数简化为： $$J(W) = \sum_{i=1}^N \left[ \log(1 + e^{W^T \tilde{x}_i}) - y_i W^T \tilde{x}_i \right].$$ 下面证明 $J(W)$ 是关于 $W$ 的凸函数。

证明方法一：转化为一元函数 任取 $W_1, W_2 \in \mathbb{R}^p$，定义一元函数： $$\phi(t) = J(W_1 + t(W_2 - W_1)), \quad t \in [0,1].$$ 只需证明 $\phi(t)$ 在 $[0,1]$ 上是凸函数，即 $\phi”(t) \ge 0$。 经过计算（过程略），可得： $$\phi”(t) = \sum_{i=1}^N \frac{( (W_2 - W_1)^T \tilde{x}_i )^2 e^{W(t)^T \tilde{x}_i}}{(1 + e^{W(t)^T \tilde{x}_i})^2},$$ 其中 $W(t) = W_1 + t(W_2 - W_1)$。由于平方项和非负指数项，上式求和中的每一项都 $\ge 0$，因此 $\phi”(t) \ge 0$。故 $\phi(t)$ 凸，从而 $J(W)$ 凸。

证明方法二：验证 Hessian 矩阵半正定 计算 $J(W)$ 的梯度与 Hessian 矩阵。 梯度： $$\nabla J(W) = \sum_{i=1}^N (\sigma(W^T \tilde{x}_i) - y_i) \tilde{x}$$i.∇J(W)=i=1∑N​(σ(WTxi​)−yi​)xi​. Hessian 矩阵： $$\nabla^2 J(W) = \sum$${i=1}^N \sigma(W^T \tilde{x}_i) (1 - \sigma(W^T \tilde{x}_i)) \tilde{x}_i \tilde{x}i^T. 对于任意向量 $v \in \mathbb{R}^p$，有： $$v^T \nabla^2 J(W) v = \sum$${i=1}^N \underbrace{\sigma(W^T \tilde{x}_i) (1 - \sigma(W^T \tilde{x}i))}{>0} \underbrace{(\tilde{x}i^T v)^2}{\ge 0} \ge 0. 因此，$\nabla^2 J(W)$ 是半正定矩阵，根据判定定理，$J(W)$ 是凸函数。

import numpy as np

# 数值验证逻辑回归损失函数的Hessian矩阵半正定性（以2维特征为例）
# 直接按上文推导的公式 ∇²J(W) = Σ σ(W^T x_i)(1-σ(W^T x_i)) x_i x_i^T 累加计算
p = 2  # W的维度，对应 omega (1维) + b
N = 3  # 样本数

np.random.seed(123)
X_tilde = np.random.randn(N, p)  # 每行是一个样本的 \tilde{x}_i^T

def sigma(z):
    return 1 / (1 + np.exp(-z))

def hessian(W):
    """按公式 ∇²J(W) = Σ σ(W^T x_i)(1-σ(W^T x_i)) x_i x_i^T 累加计算"""
    H = np.zeros((p, p))
    for i in range(N):
        xi = X_tilde[i, :]
        s = sigma(W @ xi)
        H += s * (1 - s) * np.outer(xi, xi)
    return H

# 随机取一个 W 值，计算 Hessian 矩阵并检查特征值
W_val = np.array([0.5, -0.2])
H_num = hessian(W_val)
print("在 W =", W_val, "处，Hessian矩阵为:")
print(H_num)

eigenvalues = np.linalg.eigvals(H_num)
print(f"\nHessian矩阵的特征值: {eigenvalues}")
print(f"所有特征值是否均 >= 0? {np.all(eigenvalues >= -1e-10)}")  # 考虑数值误差

# 再随机取若干向量 v，验证二次型 v^T H v >= 0（与上文推导一致：它是若干非负项的和）
for k in range(3):
    v = np.random.randn(p)
    print(f"随机向量 v{k} 的二次型 v^T H v = {v @ H_num @ v:.6f}")

📝 动手练一练

1. 凸集判断：判断下列 $\mathbb{R}^2$ 中的集合是否为凸集，并简述理由。 a) $S_1 = { (x, y) \mid x^2 + y^2 \le 4 }$ b) $S_2 = { (x, y) \mid xy \ge 1, x>0, y>0 }$ c) $S_3 = { (x, y) \mid y \ge |x| }$

2. 凸函数判定：利用凸函数的判定定理（二阶条件），判断函数 $f(x, y) = e^{x} + 2x^2 + y^2 + 3xy$ 是否为凸函数。

参考答案：

1. a) 是凸集。$S_1$ 是以原点为圆心、半径为2的闭圆盘。连接圆盘内任意两点的线段必然完全落在圆盘内。 b) 是凸集。任取 $(x_1, y_1), (x_2, y_2) \in S_2$（即 $x_i > 0, y_i > 0, x_i y_i \ge 1$）及 $\alpha \in [0,1]$。凸组合的两个坐标显然均为正，其乘积满足： $$\begin{aligned} &(\alpha x_1 + (1-\alpha)x_2)(\alpha y_1 + (1-\alpha)y_2) \ &= \alpha^2 x_1 y_1 + \alpha(1-\alpha)(x_1 y_2 + x_2 y_1) + (1-\alpha)^2 x_2 y_2 \ &\ge \alpha^2 x_1 y_1 + 2\alpha(1-\alpha)\sqrt{x_1 x_2 y_1 y_2} + (1-\alpha)^2 x_2 y_2 \quad \text{(AM-GM 不等式)}\ &= \left(\alpha\sqrt{x_1 y_1} + (1-\alpha)\sqrt{x_2 y_2}\right)^2 \ge \left(\alpha + (1-\alpha)\right)^2 = 1. \end{aligned}$$ 故凸组合仍在 $S_2$ 中。注意：$xy$ 本身不是凸函数（其 Hessian 矩阵 $\begin{bmatrix}0 & 1 \ 1 & 0\end{bmatrix}$ 不定），因此不能套用”凸函数的上水平集是凸集”来论证，需要直接按定义验证。 c) 是凸集。$S_3$ 可以写成 ${ (x,y) \mid y \ge x, y \ge -x }$，即两个半空间的交集。半空间是凸集，凸集的交集仍是凸集。

2. 计算 $f(x,y)$ 的 Hessian 矩阵。 $$\nabla f = \begin{bmatrix} e^{x} + 4x + 3y \ 2y + 3x \end{bmatrix}, \quad \nabla^2 f = \begin{bmatrix} e^{x} + 4 & 3 \ 3 & 2 \end{bmatrix}.$$ 判断 $\nabla^2 f$ 是否半正定。利用顺序主子式：

   • 一阶主子式：$a_{11} = e^{x}+4 > 0$。
   • 行列式：$\det(\nabla^2 f) = 2(e^{x}+4) - 9 = 2e^{x} - 1$。 当 $2e^{x} - 1 \ge 0$，即 $x \ge \ln(1/2) \approx -0.693$ 时，$\det(\nabla^2 f) \ge 0$，矩阵半正定。但当 $x < \ln(1/2)$ 时，$\det(\nabla^2 f) < 0$，矩阵不定。 因此，函数 $f(x,y)$ 在整个 $\mathbb{R}^2$ 上不是凸函数，因为其 Hessian 矩阵在 $x$ 足够小时不是半正定的。

本章小结

本节系统介绍了优化理论中的三个基础而重要的概念：

• 共轭函数：通过取上确界从原函数构造出的新函数，具有天然的凸性，是联系原问题与对偶问题的桥梁。
• 凸集：包含其中任意两点连线的集合，具有良好的几何性质，是定义凸函数的舞台。
• 凸函数：满足 Jensen 不等式的函数，其图像具有”弦在上方”或”切线在下方”的几何特征。凸函数的局部极小值即全局最小值，这一性质使得凸优化问题在理论上和计算上都非常友好。

行动清单

1. 可视化理解：在纸上或使用绘图工具，画出几个凸集和非凸集的例子，画出凸函数（如 $x^2$）和凹函数（如 $-x^2$）的图像，直观感受其几何特征。
2. 判定练习：从你熟悉的函数（如线性函数、二次函数、指数函数、对数函数）中挑选几个，尝试使用二阶条件（计算 Hessian 矩阵）判断其凸性。
3. 代码验证：运行讲义中的 Python 代码示例，理解共轭函数的计算过程以及如何使用符号计算或数值计算来验证函数的凸性，并尝试修改参数或函数形式进行探索。

— 小象教研组