无约束优化

约束最优化：KKT条件与对偶问题

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

在机器学习的模型训练中，我们常常需要在满足特定条件（如模型参数范围、数据分布假设）下寻找最优解，这就是约束最优化问题。本节将介绍处理这类问题的两大核心理论工具：KKT条件与对偶问题。KKT条件为约束最优化问题提供了一阶必要条件，是理论分析和算法推导的基石；而对偶问题则为我们提供了从另一个角度求解原问题的思路，有时能显著简化计算。掌握这两者，你将能深入理解支持向量机（SVM）等经典算法的理论基础，并具备分析更复杂约束优化模型的能力。

💡 核心导读

• 约束优化标准形式：理解带等式与不等式约束的最小化问题的一般表述。
• KKT条件：掌握约束最优化问题的一阶必要条件，特别是互补松弛条件的深刻含义。
• 拉格朗日乘子的意义：从灵敏度分析角度，理解乘子如何量化约束条件对最优解的影响。
• 对偶问题：学习如何从原问题构造对偶问题，并理解其对偶性在简化求解中的应用。
• 线性规划对偶：通过线性规划这一经典案例，掌握对偶问题的推导过程。

约束最优化问题概述

在无约束优化中，我们直接最小化目标函数 $f(x)$。然而，实际问题中变量 $x$ 往往需要满足一系列条件，例如物理定律、资源限制或模型假设。这就引出了约束最优化问题。其标准形式如下：

$$\begin{aligned} \min_{x} \quad & f(x) \ \text{s.t.} \quad & c_i(x) = 0, \quad i \in \mathcal{E} \quad \text{(等式约束)} \ & c_i(x) \ge 0, \quad i \in \mathcal{I} \quad \text{(不等式约束)} \end{aligned}$$

其中：$f(x): \mathbb{R}^n \to \mathbb{R}$ 是目标函数；$c_i(x): \mathbb{R}^n \to \mathbb{R}$ 是约束函数；$\mathcal{E}$ 和 $\mathcal{I}$ 分别是等式约束和不等式约束的指标集；我们要求 $f(x)$ 和所有 $c_i(x)$ 是光滑的（至少一阶连续可导）。

几点说明：若原问题是 $\max f(x)$，等价于求解 $\min -f(x)$；标准形式约定不等式为”$\ge 0$”，遇到”$\le 0$”的约束两边乘以 $-1$ 即可转换；所有满足约束的点构成的集合称为可行域 $\Omega$，优化就是在 $\Omega$ 中寻找使 $f(x)$ 最小的点。与无约束优化相比，搜索空间从整个 $\mathbb{R}^n$ 缩小到了 $\Omega$，这给求解带来了额外的复杂性。

KKT条件：约束最优解的一阶必要条件

为了系统性地分析约束优化问题，我们首先引入两个关键概念。

激活集：在可行点 $x$ 处，所有等式约束以及那些取等号（即 $c_i(x)=0$）的不等式约束，被称为在 $x$ 处是激活的。这些约束的指标构成的集合称为激活集 $\mathcal{A}(x)$。激活的约束意味着该约束在 $x$ 点”紧贴”着可行域的边界。

LICQ条件：线性无关约束规范。假设 $x^$x∗ 是一个可行点，且其激活集为 $\mathcal{A}(x^$)。如果所有激活约束函数在 $x^$x∗ 处的梯度向量 ${\nabla c_i(x^$) \mid i \in \mathcal{A}(x^)} 是线性无关的，则称在 $x^$ 处 LICQ 条件成立。这保证了在最优解附近，没有”多余”的约束，所有激活的约束都是独立起作用的。

基于上述准备，我们定义约束优化问题的拉格朗日函数：

$$\mathcal{L}(x, \lambda) = f(x) - \sum_{i \in \mathcal{E} \cup \mathcal{I}} \lambda_i c_i(x)$$

其中 $\lambda_i$ 称为拉格朗日乘子。注意，对于不等式约束，我们采用了”减号”的形式，这与我们”$\ge 0$”的标准形式相匹配。有些文献采用”$c_i(x) \le 0$”的标准形式，此时拉格朗日函数为 $f(x) + \sum \lambda_i c_i(x)$，本质等价。

现在，我们可以陈述著名的 Karush-Kuhn-Tucker (KKT) 条件。

定理 (KKT条件)：设 $x^$x∗ 是约束优化问题的一个局部最优解，且 $f$ 和所有 $c_i$ 在 $x^$ 处连续可微。如果在 $x^$x∗ 处 LICQ 条件成立，则存在唯一的拉格朗日乘子向量 $\lambda^$，使得以下条件成立：

1. 平稳性： $$\nabla_x \mathcal{L}(x^$$, \lambda^) = \nabla f(x^) - \sum_{i \in \mathcal{E} \cup \mathcal{I}} \lambda_i^ \nabla c_i(x^*) = 0
2. 原始可行性： $$c_i(x^$$) = 0, \quad \forall i \in \mathcal{E}; \qquad c_i(x^) \ge 0, \quad \forall i \in \mathcal{I}
3. 对偶可行性： $$\lambda_i^* \ge 0, \quad \forall i \in \mathcal{I}$$
4. 互补松弛性： $$\lambda_i^* c_i(x^*) = 0, \quad \forall i \in \mathcal{I}$$

互补松弛性是 KKT 条件的精髓。它表明，对于每个不等式约束，要么其乘子 $\lambda_i^* = 0$（该约束不激活，对最优解无直接影响），要么约束取等号 $c_i(x^*) = 0$（该约束激活，在边界上）。换言之，激活的约束其乘子可能非零，非激活的约束其乘子必为零。

实例验证与几何解释

考虑一个简单问题： $$\begin{aligned} \min_{x_1, x_2} \quad & f(x) = (x_1 - 2)^2 + (x_2 - 1)^2 \ \text{s.t.} \quad & c_1(x) = x_1 \ge 0 \ & c_2(x) = x_2 \ge 0 \ & c_3(x) = 1 - x_1 - x_2 \ge 0 \ & c_4(x) = 1 - x_1 + x_2 \ge 0 \end{aligned}$$ 可行域是以 $(0,0)$、$(1,0)$、$(0,1)$ 为顶点的三角形（约束 $c_4$ 只在顶点 $(1,0)$ 处取等）。目标函数度量的是到点 $(2,1)$ 的距离平方，而 $(2,1)$ 本身不可行（不满足 $c_3$）。$(2,1)$ 到斜边 $x_1+x_2=1$ 的投影恰好落在顶点 $(1,0)$ 上，距离平方为 $2$，小于其余顶点的 $4$ 和 $5$。因此最优解为 $x^* = (1, 0)$。

在该点：

• 约束 $c_2$（$x_2=0$）、$c_3$（$1-x_1-x_2=0$）、$c_4$（$1-x_1+x_2=0$）取等号，为激活约束；$c_1$（$x_1=1>0$）未取等，为非激活约束。
• 激活集为 $\mathcal{A}(x^$) = {2, 3, 4}A(x∗)={2,3,4}。根据互补松弛性，$\lambda_1^$= 0。

代入平稳性条件 $\nabla f(x^$) = \sum_i \lambda_i^ \nabla c_i(x^*)。计算各梯度：

• $\nabla f(1,0) = (2(x_1-2),, 2(x_2-1))\big|_{(1,0)} = (-2, -2)^T$
• $\nabla c_1 = (1,0)^T$，$\nabla c_2 = (0,1)^T$，$\nabla c_3 = (-1,-1)^T$，$\nabla c_4 = (-1,1)^T$

由互补松弛性 $\lambda_1^* = 0$，代入两个分量方程：

• 第 1 分量：$-2 = -\lambda_3^* - \lambda_4^*$
• 第 2 分量：$-2 = \lambda_2^* - \lambda_3^* + \lambda_4^*$

结合全部乘子非负的要求，解得唯一解 $\lambda^* = (0, 0, 2, 0)$。验证：$-2 = -2 - 0$ 与 $-2 = 0 - 2 + 0$ 均成立，且 $\lambda_3^* = 2 \ge 0$，互补松弛性也满足（$\lambda_3^* c_3(x^*) = 2 \times 0 = 0$）。这验证了 KKT 条件。

值得注意的是，$(1,0)$ 处有 3 个激活约束，而问题只有 2 个变量，3 个梯度向量在 $\mathbb{R}^2$ 中必然线性相关，故 LICQ 在该点不成立。但此例中满足全部 KKT 条件的非负乘子依然存在且唯一—LICQ 是乘子存在且唯一的充分条件，并非必要条件。

下面的 Python 代码演示了如何利用符号计算验证最优解 $x^* = (1,0)$ 及其乘子 $\lambda^* = (0,0,2,0)$ 满足全部 KKT 条件。

import sympy as sp

# 定义符号变量
x1, x2, lam1, lam2, lam3, lam4 = sp.symbols('x1 x2 lam1 lam2 lam3 lam4', real=True)

# 目标函数与约束函数（标准形式 c_i(x) >= 0）
f = (x1 - 2)**2 + (x2 - 1)**2
c1 = x1          # x1 >= 0
c2 = x2          # x2 >= 0
c3 = 1 - x1 - x2 # 1 - x1 - x2 >= 0
c4 = 1 - x1 + x2 # 1 - x1 + x2 >= 0

# 构建拉格朗日函数 L = f - sum(lambda_i * c_i)
L = f - (lam1*c1 + lam2*c2 + lam3*c3 + lam4*c4)

# 已知最优解 x* = (1, 0)，乘子 λ* = (0, 0, 2, 0)
x_star = [1, 0]
lam_star = [0, 0, 2, 0]
subs_dict = {x1: x_star[0], x2: x_star[1],
             lam1: lam_star[0], lam2: lam_star[1],
             lam3: lam_star[2], lam4: lam_star[3]}

# 1. 验证平稳性条件: ∇_x L(x*, λ*) = 0
grad_x1 = sp.diff(L, x1).subs(subs_dict)
grad_x2 = sp.diff(L, x2).subs(subs_dict)
print("平稳性条件验证:")
print(f"∂L/∂x1 at (x*, λ*) = {grad_x1}")
print(f"∂L/∂x2 at (x*, λ*) = {grad_x2}")

# 2. 验证原始可行性
print("\n原始可行性验证:")
for i, c in enumerate([c1, c2, c3, c4], start=1):
    val = c.subs({x1: x_star[0], x2: x_star[1]})
    print(f"c{i}(x*) = {val} >= 0 : {val >= 0}")

# 3. 验证对偶可行性 (λ_i >= 0)
print("\n对偶可行性验证:")
for i, lam_val in enumerate(lam_star, start=1):
    print(f"λ_{i}* = {lam_val} >= 0 : {lam_val >= 0}")

# 4. 验证互补松弛性 (λ_i * c_i(x*) = 0)
print("\n互补松弛性验证:")
for i, (lam_val, c) in enumerate(zip(lam_star, [c1, c2, c3, c4]), start=1):
    val = c.subs({x1: x_star[0], x2: x_star[1]})
    product = lam_val * val
    print(f"λ_{i}* * c_{i}(x*) = {lam_val} * {val} = {product} == 0 : {sp.simplify(product) == 0}")

拉格朗日乘子的意义：灵敏度分析

拉格朗日乘子 $\lambda_i^$λi∗​ 不仅仅是引入的辅助变量，它具有深刻的物理和经济学意义：**它衡量了对应约束”收紧”或”放松”时，最优目标值 $f(x^$) 的变化灵敏度**。

考虑一个扰动问题：将第 $i$ 个不等式约束从 $c_i(x) \ge 0$ 改为 $c_i(x) \ge \delta$。$\delta > 0$ 意味着约束收紧（可行域变小），$\delta < 0$ 意味着约束放松（可行域变大）。设新问题的最优值为 $f^*(\delta)$。可以证明，在一定的正则性条件下，最优值关于扰动的一阶变化率为：

$$\frac{df^$$(\delta)}{d\delta} \bigg|_{\delta=0} \approx \lambda_i^

解释：

• 如果 $\lambda_i^* > 0$，收紧该约束（$\delta > 0$）会使最优值上升约 $\lambda_i^* \delta$；反过来，放松该约束（$\delta < 0$）会使最优值下降约 $\lambda_i^* |\delta|$。$\lambda_i^*$ 越大，意味着该约束在原最优解处”绑得越紧”，扰动它对最优值的影响越大。
• 如果 $\lambda_i^* = 0$，说明该约束在原最优解处是非激活的，微小的扰动不会改变最优值。
• 对于等式约束，乘子 $\lambda_i^*$ 可正可负，其绝对值大小同样反映了该约束对最优值的”限制力”强度。

因此，拉格朗日乘子提供了关于问题结构的重要信息：哪些约束是关键的（大乘子），哪些是松弛的（零乘子）。这在资源分配、经济学边际分析等领域有直接应用。

对偶问题：另一个视角的优化

对于原约束优化问题（称为原始问题），我们可以构造一个与之紧密关联的对偶问题。对偶理论在最优化中极为重要，它提供了原问题最优值的下界，有时还能提供更易求解的途径。

考虑一个只有不等式约束的简化原始问题 $(P)$：

$$\begin{aligned} (P): \quad \min_{x} \quad & f(x) \ \text{s.t.} \quad & c(x) \ge 0 \end{aligned}$$

其中 $c(x) = [c_1(x), \dots, c_m(x)]^T \in \mathbb{R}^m$。其拉格朗日函数为 $\mathcal{L}(x, \lambda) = f(x) - \lambda^T c(x)$， $\lambda \ge 0$。

对偶函数 $q(\lambda)$ 定义为拉格朗日函数关于原始变量 $x$ 的下确界：

$$q(\lambda) = \inf_{x} \mathcal{L}(x, \lambda) = \inf_{x} \left[ f(x) - \lambda^T c(x) \right]$$

注意，$q(\lambda)$ 是 $\lambda$ 的函数，它可能取 $-\infty$。我们定义对偶函数的有效定义域为那些使得 $q(\lambda) > -\infty$ 的 $\lambda$ 的集合。对偶问题 $(D)$ 则是最大化这个对偶函数：

$$(D): \quad \max_{\lambda \ge 0} q(\lambda)$$

对偶问题的性质：

1. 弱对偶性：对于任意可行 $x$（满足 $c(x) \ge 0$）和任意 $\lambda \ge 0$，有 $q(\lambda) \le f(x)$。进而，对偶问题的最优值 $d^$d∗ 不超过原始问题的最优值 $p^$，即 $d^* \le p^*$。
2. 强对偶性：在某些条件下（如 Slater 条件：存在严格可行点 $c(x) > 0$，且问题是凸的），有 $d^* = p^$d∗=p∗，且对偶问题的最优解 $\lambda^$ 就是原始问题最优解处的 KKT 乘子。
3. 求解意义：即使原问题非凸，对偶函数 $q(\lambda)$ 总是关于 $\lambda$ 的凹函数（因为是一族仿射函数的下确界），最大化凹函数相对容易。有时，对偶问题的形式比原问题简单得多（例如维度降低、约束简化）。

对偶问题求解示例

考虑问题： $$\begin{aligned} \min_{x_1, x_2} \quad & \frac{1}{2}(x_1^2 + x_2^2) \ \text{s.t.} \quad & x_1 \ge 1 \end{aligned}$$

1. 拉格朗日函数：$\mathcal{L}(x, \lambda) = \frac{1}{2}(x_1^2 + x_2^2) - \lambda (x_1 - 1)$， $\lambda \ge 0$。
2. 对偶函数：$q(\lambda) = \inf_{x_1, x_2} \mathcal{L}(x, \lambda)$。对 $x_1, x_2$ 求偏导并令为零： $\frac{\partial \mathcal{L}}{\partial x_1} = x_1 - \lambda = 0 \Rightarrow x_1 = \lambda$ $\frac{\partial \mathcal{L}}{\partial x_2} = x_2 = 0 \Rightarrow x_2 = 0$ 代入得 $q(\lambda) = \frac{1}{2}\lambda^2 - \lambda(\lambda - 1) = \lambda - \frac{1}{2}\lambda^2$。
3. 对偶问题：$\max_{\lambda \ge 0} \quad \lambda - \frac{1}{2}\lambda^2$。 这是一个关于 $\lambda$ 的凹二次函数，求导得 $1 - \lambda = 0 \Rightarrow \lambda^* = 1$。最大值为 $q(1) = 1 - 0.5 = 0.5$。
4. 恢复原始解：将 $\lambda^* = 1$ 代回 $x_1 = \lambda, x_2 = 0$，得到原始最优解 $x^* = (1, 0)$。原始最优值 $f(x^*) = 0.5$，与对偶最优值相等，强对偶成立。

线性规划的对偶

线性规划是约束优化中最重要的特例之一，其对偶形式非常规整且应用广泛。考虑标准形式的线性规划原始问题 $(P)$：

$$\begin{aligned} (P): \quad \min_{x} \quad & c^T x \ \text{s.t.} \quad & A x \ge b \ & x \ge 0 \end{aligned}$$

其中 $c \in \mathbb{R}^n$, $A \in \mathbb{R}^{m \times n}$, $b \in \mathbb{R}^m$。其拉格朗日函数为（将 $x \ge 0$ 也纳入拉格朗日函数，记其乘子为 $\mu \ge 0$）：

$$\mathcal{L}(x, \lambda, \mu) = c^T x - \lambda^T (A x - b) - \mu^T x = (c^T - \lambda^T A - \mu^T)x + \lambda^T b$$

对偶函数 $q(\lambda, \mu) = \inf_x \mathcal{L}(x, \lambda, \mu)$。由于 $x \ge 0$ 已经由乘子 $\mu$ 处理，这里的 $\inf$ 在整个 $\mathbb{R}^n$ 上取。线性函数在 $\mathbb{R}^n$ 上的下确界只有两种情况：系数全为零时等于常数项 $\lambda^T b$，否则为 $-\infty$。因此，要使 $q(\lambda, \mu) > -\infty$，必须要求

$$c - A^T \lambda - \mu = 0$$

且此时 $q(\lambda, \mu) = \lambda^T b$。再利用 $\mu \ge 0$ 消去 $\mu$：$\mu = c - A^T \lambda \ge 0$ 等价于 $A^T \lambda \le c$。

因此，线性规划的对偶问题 $(D)$ 为：

$$\begin{aligned} (D): \quad \max_{\lambda} \quad & b^T \lambda \ \text{s.t.} \quad & A^T \lambda \le c \ & \lambda \ge 0 \end{aligned}$$

这是一个形式非常对称的对偶问题：原始是”$\min c^T x$, s.t. $Ax \ge b, x\ge0$”，对偶是”$\max b^T \lambda$, s.t. $A^T \lambda \le c, \lambda\ge0$”。变量和约束的角色发生了互换。

📝 动手练一练

1. KKT条件验证：考虑优化问题 $$\min_{x \in \mathbb{R}} f(x) = x^2 \quad \text{s.t.} \quad x \ge 1.$$ a) 写出其拉格朗日函数。 b) 求解该问题的最优解 $x^$x∗ 和对应的拉格朗日乘子 $\lambda^$。 c) 验证解 $(x^$, \lambda^) 满足 KKT 条件。 d) 若将约束改为 $x \ge 1 + \delta$（$\delta$ 很小），利用 $\lambda^$λ∗ 估计最优值 $f^$ 的变化。

   参考答案： a) $\mathcal{L}(x, \lambda) = x^2 - \lambda (x - 1)$, $\lambda \ge 0$. b) 直观上，无约束最优解为 $x=0$，但不满足约束。约束最优解应在边界 $x=1$ 上取得。验证：若 $x^$=1x∗=1，则 $\nabla f = 2x^$= 2，$\nabla c = 1$。由平稳性 $2 - \lambda^* = 0$，得 $\lambda^* = 2 \ge 0$。互补松弛 $\lambda^$(x^-1)=0 成立。故 $x^$=1, \lambda^=2. c) 平稳性：$2$1 - 21=0；原始可行：$1 \ge 1$；对偶可行：$2 \ge 0$；互补松弛：$2*(1-1)=0$。全部满足。 d) 原最优值 $f^* = 1$。新约束 $x \ge 1+\delta$（收紧约束），最优解 $x_{new}^* = 1+\delta$，新最优值 $f_{new}^* = (1+\delta)^2 \approx 1 + 2\delta$。变化量 $\Delta f^* \approx 2\delta$。根据灵敏度分析，变化率约为 $\delta$ 的系数恰好是 $\lambda^* = 2$（因为 $f_{new}^* - f^* \approx \lambda^* \delta$）。乘子 $\lambda^*$ 反映了约束右端项每增加1单位（收紧）时，最优目标值的增量，即约束变化对最优值影响的灵敏度。

2. 构造对偶问题：对于只有不等式约束的凸优化问题 $$\min_{x} \frac{1}{2} |x|^2 \quad \text{s.t.} \quad a_i^T x \ge b_i, ; i=1,\dots,m,$$ 其中 $x \in \mathbb{R}^n$, $a_i \in \mathbb{R}^n$, $b_i \in \mathbb{R}$。试写出其对偶问题。

   参考答案： 拉格朗日函数：$\mathcal{L}(x, \lambda) = \frac{1}{2} x^T x - \sum_{i=1}^m \lambda_i (a_i^T x - b_i)$, $\lambda \ge 0$. 对偶函数 $q(\lambda) = \inf_x \mathcal{L}(x, \lambda)$。对 $x$ 求梯度：$\nabla_x \mathcal{L} = x - \sum_i \lambda_i a_i = 0 \Rightarrow x = \sum_i \lambda_i a_i = A \lambda$，其中 $A$ 是以 $a_i$ 为列的矩阵。 代入得 $q(\lambda) = \frac{1}{2} (A\lambda)^T (A\lambda) - \lambda^T (A^T (A\lambda) - b) = -\frac{1}{2} \lambda^T (A^T A) \lambda + \lambda^T b$. 对偶问题：$\max_{\lambda \ge 0} ; -\frac{1}{2} \lambda^T (A^T A) \lambda + \lambda^T b$，这是一个关于 $\lambda$ 的凹二次规划。

本章小结

本节深入探讨了约束最优化中的两个核心概念：KKT条件与对偶问题。

• KKT条件是约束局部最优解必须满足的一阶必要条件，包含平稳性、原始可行性、对偶可行性和互补松弛性四个部分。互补松弛性揭示了最优解处约束的激活状态与乘子取值的紧密关系。
• 拉格朗日乘子具有明确的灵敏度意义，量化了约束条件变化对最优目标值的影响程度。
• 对偶问题通过拉格朗日函数构造，提供了求解原问题的另一个视角。在凸优化且满足约束规范时，强对偶性成立，对偶问题的最优解能恢复原始最优解。线性规划的对偶形式具有优美的对称性。

行动清单：

1. 推导练习：任选一个简单的带不等式约束的优化问题（如本节练习题），手动推导其 KKT 条件并求解。
2. 代码验证：使用 Python 的 sympy 或 cvxopt 库，验证一个线性规划问题的原始解与对偶解，并比较它们的目标值。
3. 建立联系：回顾机器学习中 SVM 的基本型，尝试写出其拉格朗日函数，并思考其对偶问题在支持向量机算法中的作用（为下一节学习做准备）。

— 小象教研组