对偶问题（二）

对偶问题与最优性条件

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

在上一节中，我们建立了原优化问题与对偶问题之间的联系，并引入了强对偶性的概念。强对偶性告诉我们，在某些条件下，原问题的最优值和对偶问题的最优值是相等的。然而，它并没有告诉我们如何找到这个最优值，或者如何判断一个解是否是最优的。本节将深入探讨这个问题，引入互补松弛条件和KKT最优性条件，它们是判断和寻找最优解的关键工具。通过学习这些条件，你将掌握在凸优化问题中，如何通过求解一组方程来找到最优解，并理解对偶理论在支持向量机等经典机器学习算法中的核心应用。

💡 核心导读

本节你将掌握：

1. 互补松弛条件：在强对偶性成立时，原问题与对偶问题最优解之间必须满足的乘积关系。
2. KKT最优性条件：包含可行性、互补松弛和梯度条件在内的完整最优解判定条件组。
3. 凸问题的特殊地位：理解为何KKT条件在凸优化问题中成为最优解的充要条件，从而为求解提供系统方法。
4. 对偶问题的求解路径：学习如何通过先求解对偶问题，再回代求解原问题最优解的两步法。
5. SVM中的应用实例：直观感受对偶理论与KKT条件在支持向量机算法中的关键作用。

1. 互补松弛条件的推导

我们考虑标准形式的优化问题： $$\begin{aligned} \text{minimize} \quad & f_0(x) \ \text{subject to} \quad & f_i(x) \leq 0, \quad i = 1, \ldots, m \ & h_j(x) = 0, \quad j = 1, \ldots, p \end{aligned}$$ 其拉格朗日函数为： $$L(x, \lambda, \nu) = f_0(x) + \sum_{i=1}^{m} \lambda_i f_i(x) + \sum_{j=1}^{p} \nu_j h_j(x)$$ 其中 $\lambda_i \geq 0$ 为不等式约束对应的拉格朗日乘子，$\nu_j$ 为等式约束对应的拉格朗日乘子。

假设强对偶性成立，即原问题最优值 $p^$p∗ 等于对偶问题最优值 $d^$。令 $x^$x∗ 是原问题的一个最优解，$(\lambda^$, \nu^*) 是对偶问题的一组最优解。

由强对偶性，我们有： $$f_0(x^$$) = p^ = d^* = g(\lambda^, \nu^) 其中 $g(\lambda, \nu) = \inf_{x} L(x, \lambda, \nu)$ 是对偶函数。

根据对偶函数的定义（下确界），对于任意 $x$，有 $g(\lambda^$, \nu^) \leq L(x, \lambda^, \nu^)。特别地，取 $x = x^$x=x∗，得到： $$f_0(x^$$) = g(\lambda^, \nu^) \leq L(x^, \lambda^, \nu^) 另一方面，由于 $x^$ 是原问题的可行解，满足 $f_i(x^$) \leq 0fi​(x∗)≤0 和 $h_j(x^$) = 0，且 $\lambda_i^* \geq 0$，因此： $$L(x^$$, \lambda^, \nu^) = f_0(x^) + \underbrace{\sum_{i=1}^{m} \lambda_i^* f_i(x^)}{\leq 0} + \underbrace{\sum{j=1}^{p} \nu_j^ h_j(x^)}_{=0} \leq f_0(x^) 综合以上两个不等式，我们得到： $$f_0(x^$$) \leq L(x^, \lambda^, \nu^) \leq f_0(x^*) 这意味着所有不等号都必须取等号。由此可以推导出两个关键结论：

1. 拉格朗日函数在 $x^*$ 处取极小值： $$g(\lambda^$$, \nu^) = L(x^, \lambda^, \nu^)g(λ∗,ν∗)=L(x∗,λ∗,ν∗) 这表明 $x^$ 是拉格朗日函数 $L(x, \lambda^$, \nu^)（在固定乘子下）的一个极小值点。

2. 互补松弛条件： 由于 $\sum_{i=1}^{m} \lambda_i^* f_i(x^$) = 0∑i=1m​λi∗​fi​(x∗)=0，且每一项 $\lambda_i^$f_i(x^) \leq 0（因为 $\lambda_i^$\geq 0, f_i(x^) \leq 0），要使得求和为零，必须每一项都为零： $$\boxed{\lambda_i^$$f_i(x^) = 0, \quad i = 1, \ldots, m} 这个条件称为互补松弛条件。它意味着对于每个不等式约束，要么约束是“紧”的（$f_i(x^$) = 0，即最优解落在约束边界上），要么对应的拉格朗日乘子为零（$\lambda_i^* = 0$，即该约束在最优解处不起作用）。

互补松弛条件是连接原问题最优解与对偶问题最优解的重要桥梁，也是KKT条件的重要组成部分。

2. KKT最优性条件

现在，我们假设目标函数 $f_0$ 和约束函数 $f_i$, $h_j$ 都是可微的。结合上一节的推导，我们可以得到最优解必须满足的一系列条件。

2.1 KKT条件的组成

对于任意优化问题（不一定是凸的），如果强对偶性成立，且函数可微，那么任何一对原问题最优解 $x^$x∗ 和对偶问题最优解 $(\lambda^$, \nu^*) 都必须满足以下KKT条件：

1. 原始可行性： $$\begin{aligned} f_i(x^$$) &\leq 0, \quad i = 1, \ldots, m \ h_j(x^) &= 0, \quad j = 1, \ldots, p \end{aligned}

2. 对偶可行性： $$\lambda_i^* \geq 0, \quad i = 1, \ldots, m$$

3. 互补松弛条件： $$\lambda_i^* f_i(x^*) = 0, \quad i = 1, \ldots, m$$

4. 梯度条件（平稳性）： 由于 $x^$x∗ 是 $L(x, \lambda^$, \nu^) 的一个极小值点，在可微的假设下，该点处的梯度必须为零： $$\nabla f_0(x^$$) + \sum_{i=1}^{m} \lambda_i^* \nabla f_i(x^) + \sum_{j=1}^{p} \nu_j^ \nabla h_j(x^*) = 0

这四组条件合称为 Karush-Kuhn-Tucker (KKT) 条件。

2.2 凸问题中KKT条件的特殊地位

KKT条件的重要性在凸优化问题中尤为突出。回忆一下，一个优化问题是凸的，如果 $f_0$ 和所有 $f_i$ 是凸函数，且所有 $h_j$ 是仿射函数。

对于凸优化问题，KKT条件的作用发生了质的变化：

• 对于一般（非凸）问题：KKT条件只是最优解的必要条件。满足KKT条件的点（称为KKT点）不一定是最优解。
• 对于凸问题：如果存在一组 $(\lambda^$, \nu^) 使得 $x^*$ 满足KKT条件，并且斯莱特条件（或其它保证强对偶性成立的约束品性）成立，那么KKT条件就成为最优解的充分必要条件。即：

  $x^$x∗ 是原凸问题的最优解 当且仅当 存在 $(\lambda^$, \nu^*) 使得KKT条件成立。

这个结论极其强大。它意味着对于许多凸优化问题，我们可以通过求解KKT条件对应的方程组来找到最优解。KKT条件将优化问题转化为一个（可能非线性的）方程组求解问题，这为算法设计提供了理论基础。

2.3 求解思路总结

综合强对偶性和KKT条件，我们得到了求解约束优化问题的两种主要思路：

思路一：直接求解KKT条件（适用于凸问题）

1. 验证问题是凸优化问题，且满足斯莱特条件（保证强对偶性）。
2. 写出完整的KKT条件（四个部分）。
3. 求解这组方程和不等式，得到候选解 $(x^$, \lambda^, \nu^*)。
4. 由于在凸问题下KKT条件是充要的，求得的 $x^*$ 即为原问题最优解。

思路二：通过对偶问题求解（更通用）

1. 构造原问题的拉格朗日函数和对偶函数。
2. 求解对偶问题，得到对偶最优解 $(\lambda^$, \nu^) 和对偶最优值 $d^*$。
3. 如果强对偶性成立（$p^* = d^$p∗=d∗），那么原问题最优解 $x^$ 必然是拉格朗日函数 $L(x, \lambda^$, \nu^) 的极小值点。
4. 通过求解 $\min_x L(x, \lambda^$, \nu^) 来恢复原问题最优解 $x^*$。如果这个极小值点唯一，那么它就是原问题的唯一最优解。

import numpy as np
import sympy as sp

# 示例：利用KKT条件求解一个简单的凸优化问题
# 问题：minimize f(x) = (x - 4)^2, subject to x <= 1
# 这是一个凸问题（目标函数为凸二次函数，约束为线性）

# 定义符号变量
x = sp.symbols('x', real=True)
lam = sp.symbols('lam', real=True, nonnegative=True) # 拉格朗日乘子需非负

# 定义函数
f0 = (x - 4)**2          # 目标函数
g = x - 1                # 约束改写为 g(x)=x-1 <= 0（即x <= 1）

# 构造拉格朗日函数
L = f0 + lam * g

# KKT条件：
# 1. 原始可行性: g(x) <= 0 -> x - 1 <= 0
# 2. 对偶可行性: lam >= 0 (已通过符号定义保证)
# 3. 互补松弛: lam * g(x) = 0 -> lam * (x - 1) = 0
# 4. 梯度为零: dL/dx = 0

# 求解梯度条件
dL_dx = sp.diff(L, x)
print("梯度条件: dL/dx =", dL_dx, "= 0")

# 联立求解互补松弛条件和梯度条件
# 互补松弛条件意味着两种情况：lam = 0 或 x = 1
print("\n情况1: λ = 0")
sol_case1 = sp.solve([sp.Eq(dL_dx, 0), sp.Eq(lam, 0)], [x, lam], dict=True)
print("解:", sol_case1)
if sol_case1:
    x_val, lam_val = sol_case1[0][x], sol_case1[0][lam]
    print(f"  x = {x_val}, λ = {lam_val}, 检查原始可行性 g(x)={g.subs(x, x_val)} <= 0: {g.subs(x, x_val) <= 0}")

print("\n情况2: x = 1")
sol_case2 = sp.solve([sp.Eq(dL_dx, 0), sp.Eq(x, 1)], [x, lam], dict=True)
print("解:", sol_case2)
if sol_case2:
    x_val, lam_val = sol_case2[0][x], sol_case2[0][lam]
    print(f"  x = {x_val}, λ = {lam_val}, 检查对偶可行性 λ>=0: {lam_val >= 0}")

# 综合判断
print("\n结论分析：")
print("情况1的解 x=4, λ=0 满足所有KKT条件（g(4)=3>0，不满足原始可行性x<=1），因此不是可行解。")
print("情况2的解 x=1, λ=6 满足所有KKT条件：")
print("  原始可行性: g(1)=0 <= 0 ✓")
print("  对偶可行性: λ=6 >= 0 ✓")
print("  互补松弛: λ*g(1)=6*0=0 ✓")
print("  梯度为零: 2*(1-4)+6=0 ✓")
print("因此，原问题的最优解为 x* = 1，对应的拉格朗日乘子 λ* = 6。")
print("此时约束是‘紧’的（起作用），目标函数值 f0(1) = 9。")

3. 对偶理论在支持向量机中的应用

对偶理论和KKT条件在机器学习中有着广泛而深刻的应用，其中最经典的例子之一是支持向量机。

支持向量机（SVM）的基本型（硬间隔）可以表述为以下凸二次规划问题： $$\begin{aligned} \min_{\mathbf{w}, b} \quad & \frac{1}{2} |\mathbf{w}|^2 \ \text{s.t.} \quad & y_i (\mathbf{w}^\top \mathbf{x}_i + b) \geq 1, \quad i=1,\ldots,n \end{aligned}$$ 其中 $y_i \in {-1, +1}$ 是样本标签。

直接求解原问题的困难在于，约束数量等于样本数 $n$，当 $n$ 很大或特征维度很高时，求解效率可能较低。

通过对偶问题求解则可以带来诸多好处：

1. 更易求解：原问题的对偶问题也是一个凸二次规划，但约束条件更简单（主要是对拉格朗日乘子 $\alpha_i$ 的非负约束和一個线性等式约束）。
2. 核函数引入：在对偶形式中，样本特征总是以内积 $\mathbf{x}_i^\top \mathbf{x}_j$ 的形式出现。这允许我们使用核函数 $K(\mathbf{x}_i, \mathbf{x}_j)$ 替代内积，从而将线性SVM隐式地映射到高维特征空间，实现非线性分类，而无需显式计算高维映射。这是SVM的核心技巧。
3. 解的解释性：根据KKT条件中的互补松弛条件： $$\alpha_i [y_i(\mathbf{w}^\top \mathbf{x}_i + b) - 1] = 0$$ 这意味着，对于大多数样本，其对应的 $\alpha_i = 0$；只有那些满足 $y_i(\mathbf{w}^\top \mathbf{x}_i + b) = 1$ 的样本（即位于间隔边界上的样本），对应的 $\alpha_i > 0$。这些样本被称为支持向量，它们决定了最终的最优分类超平面。模型具有稀疏性。

因此，在实际的SVM算法实现中，几乎总是求解其对偶问题。这完美地诠释了对偶理论如何将一个看似复杂的原始优化问题，转化为一个更易处理、且能揭示问题深刻结构（支持向量、核方法）的对偶问题。

📝 动手练一练

1. KKT条件验证：考虑优化问题 $\min_{x} f(x) = x^2$，约束条件为 $x \geq 2$。

   • a) 写出该问题的拉格朗日函数。
   • b) 写出完整的KKT条件。
   • c) 求解KKT条件，找出候选最优解 $x^$x∗ 和对应的拉格朗日乘子 $\lambda^$。
   • d) 该问题是凸问题吗？求得的解是否是最优解？计算最优目标函数值。

2. 互补松弛条件的理解：对于问题 $\min_{x, y} x^2 + y^2$，约束为 $x + y \geq 2$ 和 $x \geq 0$。

   • a) 直观判断最优解应在哪里取得？（提示：考虑目标函数的等高线和约束区域）
   • b) 在最优解处，两个不等式约束的拉格朗日乘子，哪个可能为0？哪个对应的约束是“紧”的（取等号）？试用互补松弛条件解释。

参考答案：

1. KKT条件验证：

   • a) 将约束写为 $g(x)=2-x \leq 0$，拉格朗日函数为 $L(x, \lambda) = x^2 + \lambda(2-x)$。
   • b) KKT条件：
     1. 原始可行性：$2 - x \leq 0$ (即 $x \geq 2$)
     2. 对偶可行性：$\lambda \geq 0$
     3. 互补松弛：$\lambda(2-x)=0$
     4. 梯度为零：$2x - \lambda = 0$
   • c) 求解：若 $\lambda=0$，由梯度条件得 $x=0$，不满足 $x\geq2$。若 $2-x=0$ 即 $x=2$，代入梯度条件得 $\lambda=4 \geq 0$，满足所有条件。故候选解为 $x^$=2, \lambda^=4。
   • d) 是凸问题（目标函数凸，约束线性）。KKT条件是充要条件，因此 $x^*=2$ 是最优解，最优值为 $f(2)=4$。

2. 互补松弛条件的理解：

   • a) 目标函数是圆心在原点的圆，值越小半径越小。约束 $x+y\geq2$ 是一条直线，$x\geq0$ 是右半平面。最优解应在满足约束的前提下，尽可能靠近原点。直观上，最优解应在直线 $x+y=2$ 上，且 $x>0$（因为如果 $x=0$，则需 $y=2$，距离原点更远）。
   • b) 在最优解 $(1,1)$ 处（可通过求解KKT条件得到），约束 $x+y\geq2$ 是“紧”的（取等号），其乘子 $\lambda_1 > 0$。约束 $x\geq0$ 不是“紧”的（$x=1>0$），根据互补松弛条件，其乘子 $\lambda_2$ 必须为0。这符合直观：第一个约束“推动”解到达边界，是起作用的约束；第二个约束在最优解处是松弛的，不起作用。

本章小结

本节我们深入了对偶理论的核心，从强对偶性前进到实际求解最优解的工具。

要点回顾：

• 互补松弛条件 $\lambda_i^* f_i(x^*) = 0$ 是强对偶性成立时的必然结果，它清晰地刻画了最优解处约束的“活跃”状态。
• KKT最优性条件 整合了原始/对偶可行性、互补松弛和梯度为零条件，为最优解提供了完整的刻画。
• 凸问题的关键性：对于凸优化问题，在斯莱特条件等约束品性成立时，KKT条件从必要条件升级为充要条件，这使我们能通过求解KKT方程组来找到最优解。
• 对偶求解路径：另一种强大的方法是先求解对偶问题，再利用最优乘子恢复原问题解。这在SVM等算法中被广泛使用，并能引出核技巧等创新。

行动清单：

1. 推导练习：任选一个简单的带不等式约束的凸优化问题（如本节代码示例），手动完整推导其KKT条件并求解，验证与代码结果一致。
2. 概念对比：制作一个表格，对比“强对偶性”、“斯莱特条件”、“KKT条件”在“一般问题”和“凸问题”下的关系与作用。
3. 拓展阅读：查找线性支持向量机（硬间隔）的原问题和对偶问题形式，尝试写出其KKT条件，并理解“支持向量”是如何从互补松弛条件中自然产生的。

— 小象教研组