凸优化对偶：换个角度求最优

可视化演示

动态演示凸优化对偶的核心机制，通过开始/执行/监控/完成四种模式展示关键概念与交互流程。

1. 优化问题回顾：一杯奶茶的成本账

佳佳的奶茶店每天要出几百杯茶。她把每种原材料的用量记成一个向量 x：茶底多少克、牛奶多少毫升、糖浆多少泵。这些数字拼在一起，决定了这杯奶茶的材料成本 f₀(x)。但单图便宜可不行——总部的品控手册规定：糖含量不能超过 50 克（一条“上限”约束），净含量必须恰好 500 毫升（一条“等式”约束）。佳佳要做的，就是在一堆配方里找出“满足所有规矩且成本最低”的那一个。

这个场景被数学家抽象成了标准的约束优化问题：有决策变量 x，有想最小化的目标函数 f₀(x)，还有一群“必须满足”的条件。把“糖不超过 50 克”写成 f₁(x) = 糖含量 − 50 ≤ 0，把“净含量恰好 500 毫升”写成 h₁(x) = 净含量 − 500 = 0。所有满足条件的 x 构成可行域 D，就像贴着“品控合格证”的配方清单，而所有可行配方里最低的那个成本，记作最优值 p*。

$$\displaystyle \min_{x} \; f_0(x) \quad \text{s.t.} \quad f_i(x) \leq 0 \; (i=1,\ldots,m), \quad h_j(x) = 0 \; (j=1,\ldots,p)$$

1. 决策变量向量 x：这是我们可以拧动的所有旋钮，比如每款配料的用量，一个 n 维向量。

$$\displaystyle x \in \mathbb{R}^{n}$$

2. 目标函数 f₀(x)：想压到最低的指标，比如每杯奶茶的材料成本，单位是元。

$$\displaystyle f_0(x)$$

3. 不等式约束 fᵢ(x) ≤ 0：只许低于上限的质量标准，糖含量减去上限后必须为负或零。

$$\displaystyle f_i(x) \leq 0, \quad i = 1, \ldots, m$$

4. 等式约束 hⱼ(x) = 0：必须分毫不差的硬指标，比如净含量减 500 毫升必须正好为零。

$$\displaystyle h_j(x) = 0, \quad j = 1, \ldots, p$$

佳佳能做的，只是在自己的配方表里翻来覆去地比较。她并不知道：在这个问题上方，还有一个“上帝视角”在等着她——如果有人给这些规矩标上价格，故事会完全不一样。

2. 拉格朗日函数：给约束贴上价格标签

这天，总部质检顾问阿强走进佳佳的店里，掏出一份《品控违约价目表》：糖含量每超 1 克，罚款 λ₁ 元；热量每超 1 卡，罚款 λ₂ 元；净含量偏差每 1 毫升，罚款 ν₁ 元……阿强宣布：从今天起，佳佳不必死守标准，只要“成本 + 罚款”最低就行。佳佳眼前一亮——这等于把冷冰冰的禁令，变成了可以讨价还价的软约束。

这正是拉格朗日乘子法的精髓：把“必须满足 fᵢ(x) ≤ 0”的硬规矩，改写成“违规就按单价 λᵢ 交罚款”的软成本。罚款单价 λᵢ 有个重要规定：必须非负。道理很简单——如果糖超标还能倒拿奖励，那罚款单就变成了鼓励违规的奖金单，整个约束体系瞬间崩塌。至于等式约束的乘子 νⱼ，由于偏差可正可负，它就可以是任意实数。

$$\displaystyle 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)$$

1. 拉格朗日乘子 λᵢ：为第 i 条不等式质量标准定的“罚款单价”，必须非负，这是奖优罚劣的底线。

$$\displaystyle \lambda_i \geq 0, \quad i = 1, \ldots, m$$

2. 罚款项 Σλᵢfᵢ(x)：违规量乘以单价。标准被满足时 fᵢ(x) ≤ 0，这项是零或负贡献，所以 λ 非负才不至于奖励违规。

$$\displaystyle \sum_{i=1}^{m} \lambda_i f_i(x)$$

3. 等式项 Σνⱼhⱼ(x)：等式约束的偏离可正可负，因此乘子 νⱼ 不受符号限制，可以是全体实数。

$$\displaystyle \sum_{j=1}^{p} \nu_j h_j(x)$$

阿强把价目表贴在墙上，然后说了一句关键的话：“佳佳，你按这个规矩重新算一遍最低总付出吧。”佳佳一算，问题简单多了——原来的硬约束全不见了，只剩一个无约束的极小化。这个“给定价目表后的最小总付出”，就是下一个小节的明星：对偶函数。

3. 对偶函数：给定价格后的最小总付出

佳佳发现，有了罚款单之后，她甚至可以不理会原始标准：只要某款配方的“成本 + 罚款”最低，它就胜出。比如糖超一点、罚款才两毛，但能省下三块钱的原料费，她会毫不犹豫地选择超糖。对每一份固定的价目表 (λ, ν)，佳佳都会选出一个最小总付出，这个值记为 g(λ, ν)，它就是对偶函数。

代数上，这就是拉格朗日函数对所有可能配方 x 取下确界（最大的下界，记作 inf）。注意：这个“下确界”是在全空间里找的，允许配方闯入原来被禁止的可行域之外——因为在软罚款模式下，那里只是“贵了一点”而已。奇妙的是，即使原问题不是凸的，g 也永远是一个凹函数：对固定的 x，拉格朗日是关于 (λ, ν) 的线性函数，而一族线性函数的逐点下确界必然是凹的。

$$\displaystyle g(\lambda, \nu) = \inf_{x} \left[ f_0(x) + \sum_{i=1}^{m} \lambda_i f_i(x) + \sum_{j=1}^{p} \nu_j h_j(x) \right]$$

1. 下确界 inf：在所有配方 x 中寻找“成本 + 罚款”的最小值，允许进入原问题的不可行区域。

$$\displaystyle \inf_{x}$$

2. 凹函数性质：对每个固定的 x，L 是 (λ, ν) 的线性函数；线性函数族逐点取 inf 后必为凹函数。

$$\displaystyle g(\lambda, \nu) = \inf_{x} L(x, \lambda, \nu)$$

3. 对偶可行域：使 g(λ, ν) 大于负无穷的 (λ, ν) 集合，才是有意义的价目表。

$$\displaystyle \mathrm{dom} \; g = \{ (\lambda, \nu) \mid g(\lambda, \nu) > -\infty \}$$

阿强看着佳佳报出的一个个数字，心里打起了算盘：既然给定罚款单能“逼”出一个保证成本，那我为什么不把罚款单价调高，让这个保证值尽量大呢？只要保证值够高，就相当于用价格杠杆倒逼所有门店把品质做上去——这正是对偶问题的雏形。

4. 对偶问题：稽查员的反向博弈

阿强开始玩他的反向博弈：他不是在配方案，而是在定罚款单价。他的目标很明确——选一份价目表 (λ, ν)，让佳佳无论怎么闪转腾挪，报出的“最小总付出”都尽可能高。用数学语言说，阿强在求解一个极大化问题：在 λ ≥ 0 的约束下，最大化对偶函数 g(λ, ν)。这个极大化问题就是对偶问题，它的最优值记作 d*。

这个对偶问题有个让人拍案叫绝的性质：它永远是一个凸优化问题！无论原问题多么“野蛮”（非凸、不可导），对偶函数 g 始终是凹的，凹函数求最大化就是凸问题。这意味着对偶问题没有“局部最优陷阱”——阿强总能找到全局最优的价目表。这就像佳佳的配方世界再乱，阿强手里那本价目表的算术世界始终是井井有条的。

$$\displaystyle \max_{\lambda \succeq 0, \; \nu} \; g(\lambda, \nu)$$

1. 极大化操作：定价官在满足非负条件的价目表里，挑选保证值最大的那一份。

$$\displaystyle \max_{\lambda \succeq 0, \nu}$$

2. 非负约束 λ ⪰ 0：所有不等式约束的罚款单价不得为负，保证不会奖励违规。

$$\displaystyle \lambda_i \geq 0, \quad i=1,\ldots,m$$

3. 对偶最优值 d*：对偶问题能达到的最大目标值，也是阿强能给出的最高保证成本。

$$\displaystyle d^{*} = \max_{\lambda \succeq 0, \nu} g(\lambda, \nu)$$

现在，账本有两本了：佳佳的原问题算出了 p*，阿强的对偶问题算出了 d*。两人坐在一起对账——这个对账结果，就是优化理论里最优雅的定理之一：弱对偶与强对偶。

5. 弱对偶与强对偶：两份账何时对得上

对账开始了。阿强得意地说：“我这份价目表能保证每个店至少付出 d*。”佳佳不服：“我精打细算的真实最低成本是 p*。”谁说得对？答案是：阿强的保证值永远不可能超过佳佳的真实成本，即 d* ≤ p*。这就是弱对偶定理。证明只用一个观察：任何一个满足原始标准的可行配方，都不会触发任何罚款（因为 fᵢ(x) ≤ 0 且 λᵢ ≥ 0），所以它的“成本 + 罚款”不超过它的真实成本；取遍所有可行配方和对偶可行点，自然得到 d* ≤ p*。

弱对偶的威力在于：它不需要任何凸性假设，对一切优化问题成立。哪怕原问题难到爆炸，只要随手找一份对偶可行解，就能立刻得到一个下界——这是很多算法用来判断“离最优还有多远”的尺子。但 d* 和 p* 之间的差值（对偶间隙）能否归零，就要看强对偶的脸色了。对凸问题，只要满足 Slater 条件——存在一个让所有不等式约束都严格留有余量的可行点，比如佳佳手里有一款“糖含量明显低于上限”的配方——就一定有 d* = p*，两本账严丝合缝。

$$\displaystyle d^{*} \leq p^{*}$$

1. 对偶最优值 d*：定价官能榨出的最高保证成本。

$$\displaystyle d^{*} = \max_{\lambda \succeq 0, \nu} g(\lambda, \nu)$$

2. 原问题最优值 p*：佳佳满足全部标准时的最低真实成本。

$$\displaystyle p^{*} = \min_{x \in \mathcal{D}} f_0(x)$$

3. 不等号 ≤ 的含义：可行配方不触发罚款，所以对任意可行 x 有 g(λ,ν) ≤ f₀(x)，取极值后即弱对偶。

$$\displaystyle g(\lambda, \nu) \leq f_0(x), \quad \forall x \in \mathcal{D}$$

$$\displaystyle \exists x \in \mathcal{D} : \quad f_i(x) < 0 \;(i=1,\ldots,m), \quad h_j(x) = 0$$

1. 严格可行点：至少有一款配方把每条不等式标准都留出严格余量，这是 Slater 条件的核心。

$$\displaystyle \exists x, \quad f_i(x) < 0, \quad i=1,\ldots,m$$

2. 凸性与强对偶：目标与约束均为凸函数且 Slater 成立时，对偶间隙为零。

$$\displaystyle d^{*} = p^{*}$$

当两本账完全对齐时，佳佳和阿强之间就形成了一份“合作协议”。这份协议的具体条款，就是大名鼎鼎的 KKT 条件。

6. KKT条件：合作协议生效的四个条款

强对偶成立时，佳佳和阿强不再是讨价还价的对手，而是达成了默契。这份默契可以拆成四条同时成立的条款：平稳性——佳佳的配方 x* 处，任何微调都无法再压低“成本 + 罚款”，梯度必须相互抵消；原始可行性——x* 毕竟还是要满足原始标准的；对偶可行性——罚款单价必须非负；互补松弛——最精彩的一条：如果某条标准在最优处根本没有卡到边界（比如糖含量远低于上限），那它的罚款单价必须为零，因为没人会为一条“从不越界”的规矩付钱。

互补松弛用一句话概括就是“便宜的规矩没人定价，卡脖子的规矩才有价格”。它把约束分成了两类：紧贴边界的活跃约束（fᵢ(x*) = 0），以及松松垮垮的非活跃约束（fᵢ(x*) < 0，必有 λᵢ* = 0）。这条性质在机器学习里孕育出了“支持向量”这个概念——我们很快就会看到。

$$\displaystyle \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$$

1. 平稳性：在 x* 处，目标函数与所有约束的梯度加权和恰为零，任何方向微调都无法改进。

$$\displaystyle \nabla L(x^{*}, \lambda^{*}, \nu^{*}) = 0$$

2. 梯度抵消：f₀ 的梯度被乘子加权的约束梯度精确抵消。

$$\displaystyle \sum_{i=1}^{m} \lambda_i^{*} \nabla f_i(x^{*}) + \sum_{j=1}^{p} \nu_j^{*} \nabla h_j(x^{*}) = -\nabla f_0(x^{*})$$

$$\displaystyle \lambda_i^{*} \cdot f_i(x^{*}) = 0, \quad i = 1, \ldots, m$$

1. 互补松弛等式：罚款单价与违规量的乘积必为零，二者至少有一个取零。

$$\displaystyle \lambda_i^{*} \cdot f_i(x^{*}) = 0$$

2. 两种互斥情形：约束卡在边界时 fᵢ(x*) = 0；约束宽松时则单价 λᵢ* = 0。

$$\displaystyle f_i(x^{*}) = 0 \quad \text{或} \quad \lambda_i^{*} = 0$$

在凸问题 + Slater 条件下，KKT 条件是充要的：只要找到一组 (x*, λ, ν) 满足这四条，就一定是原问题和对偶问题的最优解。这给了工程上一个绝妙的解题套路——把优化问题变成解方程组。下面就用这个套路，去推 SVM。

7. 对偶与SVM：奶茶店学过的东西如何分类

场景切换：佳佳的店开始进货，供应商送来一批批原料。每种原料有两个指标（甜度、纯度），质检员阿强需要画一条分界线，把“合格”和“不合格”两类原料分开。为了安全，他不想只画一条分界线，而是想画一条“隔离带”——在两类原料之间留出尽可能宽的空白地带。这条隔离带的半宽，叫做间隔；间隔越大，未来新原料被误判的风险越小。

SVM（支持向量机）就是把“最大间隔”写成优化问题：找权重 w 和偏置 b，使分类函数 wx + b 的符号与标签一致，同时最小化 ½‖w‖²（它等价于最大化间隔 2/‖w‖）。每个样本的约束是 yᵢ(wᵀxᵢ + b) ≥ 1，即每个点都要在正确一侧并留出一单位余量。这样一个带约束的凸问题，正好可以被我们前面学过的拉格朗日对偶机制接管。

$$\displaystyle \min_{w, b} \; \frac{1}{2} \| w \|^{2} \quad \text{s.t.} \quad y_i (w^{T} x_i + b) \geq 1, \quad i = 1, \ldots, n$$

1. 目标 ½‖w‖²：最小化权重范数的平方，等价于最大化分类间隔，是 SVM 的“安全缓冲带”。

$$\displaystyle \frac{1}{2} \| w \|^{2}$$

2. 间隔约束：每个样本必须落在正确一侧，且到分界面的函数距离至少为 1。

$$\displaystyle y_i (w^{T} x_i + b) \geq 1$$

把约束改写成标准形式 1 − yᵢ(wᵀxᵢ + b) ≤ 0 后，构造拉格朗日并令其对 w、b 的梯度为零（平稳性），会得到两个漂亮的结论：w = Σαᵢyᵢxᵢ，以及 Σαᵢyᵢ = 0。把它们代回拉格朗日，w 和 b 就消失了，只剩下关于 α 的对偶问题——目标函数里所有的 x 都以内积 xᵢᵀxⱼ 的形式出现，这就是核技巧的入口。

$$\displaystyle \max_{\alpha} \; \sum_{i=1}^{n} \alpha_i - \frac{1}{2} \sum_{i=1}^{n} \sum_{j=1}^{n} \alpha_i \alpha_j y_i y_j x_i^{T} x_j \quad \text{s.t.} \quad \alpha_i \geq 0, \;\; \sum_{i=1}^{n} \alpha_i y_i = 0$$

1. 非负约束 αᵢ ≥ 0：每个样本对应一个对偶变量，它本质是“该样本罚款单价”的化身。

$$\displaystyle \alpha_i \geq 0$$

2. 内积 xᵢᵀxⱼ：对偶目标只依赖样本成对的内积，这是把线性 SVM 升级成核 SVM 的钥匙。

$$\displaystyle x_i^{T} x_j$$

3. 等式约束 Σαᵢyᵢ = 0：来自对偏置 b 取平稳性，是拉格朗日求导后自然浮现的条件。

$$\displaystyle \sum_{i=1}^{n} \alpha_i y_i = 0$$

互补松弛在这里大放异彩：αᵢ > 0 的样本，恰好是那些约束卡在边界（yᵢ(wᵀxᵢ+b) = 1）上的点——它们被称为支持向量。大多数样本的 αᵢ 都是零，模型天然稀疏。对偶的视角，让 SVM 从一个笨重的约束优化，变成了一个轻盈的“只跟少数边界点打交道”的内积游戏。

8. 对偶应用：从账本到算法工具箱

佳佳和阿强渐渐发现，这套“换视角”的功夫不只是奶茶店和 SVM 的专利。对偶理论像一个通用工具箱，凡是遇到“约束太多、问题太难、数据太散”的场合，都能掏出相应的家伙。

第一件工具是下界与停机判据：弱对偶保证任何对偶可行点都给出原最优值的下界，分支定界、全局优化算法用它判断“当前解离最优还有多远，能不能提前收工”；第二件工具是灵敏度分析：对偶最优值 λ 就是约束的“影子价格”，预算增加一块钱能让目标改善多少，答案就在 λ 里；第三件工具是分布式优化：当全局问题被一条耦合约束拴住时，固定 λ 后每个子问题都可以独立求解，再把各自的梯度汇聚起来更新 λ——这正是联邦学习等场景的数学底座。

举个分布式优化的标准例子：总目标是 K 个模块的成本之和，唯一把它们绑在一起的是共享资源上限 b。对这条耦合约束引入乘子 λ 后，每个模块只需独立求解自己的“本地成本 + λ 分摊的资源费”，完全不需要看到别人的数据。

$$\displaystyle \min_{x} \; \sum_{k=1}^{K} f_k(x_k) \quad \text{s.t.} \quad \sum_{k=1}^{K} A_k x_k \leq b$$

1. 可分目标：总目标拆成 K 个互不相关的子块，每个子块只管自己的局部变量。

$$\displaystyle \sum_{k=1}^{K} f_k(x_k)$$

2. 耦合约束：唯一把子块绑在一起的是共享资源上限 b，对应“总预算不能超”。

$$\displaystyle \sum_{k=1}^{K} A_k x_k \leq b$$

3. 对偶分解：给定 λ 后，每个子问题独立求解，再通过更新 λ 协调全局。

$$\displaystyle \min_{x_k} \; f_k(x_k) + \lambda^{T} A_k x_k$$

佳佳最后总结道：“原来我一直在配方表里打转，而阿强站在价格表的高度看同一个问题。”对偶理论最好的礼物，就是教会我们：当一个视角算不下去时，换一个视角，有时不仅更简单，还能给出原来看不见的边界与价格。

AI 应用场景

Python 演示

import numpy as npfrom scipy.optimize import minimize  # ============ 第一部分：拉格朗日对偶的完整闭环 ============# 原问题：min x^2, s.t. x >= 1（标准形式 f1(x) = 1 - x <= 0）# 解析解：x* = 1，p* = 1 def dual_obj(lam):    # 对偶函数 g(lam) = min_x [x^2 + lam*(1-x)] = lam - lam^2/4    # minimize 默认求极小，所以取负号    return -(lam - lam * lam / 4.0)  res = minimize(dual_obj, 0.0, bounds=[(0.0, None)])lam_star = res.x[0]d_star = -res.funp_star = 1.0print("原问题最优 p* =", p_star, "，解 x* =", round(lam_star / 2, 6))print("对偶最优 d* =", round(d_star, 6), "，lambda* =", round(lam_star, 6))print("对偶间隙 p* - d* =", round(p_star - d_star, 6))  # ============ 第二部分：SVM 对偶求解与支持向量 ============# 六个二维样本：前三个正类，后三个负类X = np.array([[2.0, 2.0], [2.0, 3.0], [3.0, 2.0],              [6.0, 6.0], [7.0, 6.0], [6.0, 7.0]])y = np.array([1.0, 1.0, 1.0, -1.0, -1.0, -1.0])n = len(y) # 对偶问题矩阵：Q[i,j] = y_i * y_j * x_i^T x_jQ = np.array([[y[i] * y[j] * X[i].dot(X[j]) for j in range(n)] for i in range(n)])  def svm_dual(alpha):    # 对偶目标：max sum(alpha) - 0.5 * alpha^T Q alpha    return 0.5 * alpha.dot(Q.dot(alpha)) - alpha.sum()  cons = [{"type": "eq", "fun": lambda a: a.dot(y)}]  # 等式约束 sum(alpha_i * y_i) = 0bnds = [(0.0, None)] * n  # 不等式约束 alpha_i >= 0res = minimize(svm_dual, np.zeros(n), method="SLSQP", bounds=bnds, constraints=cons)alpha = np.clip(res.x, 0.0, None)alpha[np.abs(alpha) < 1e-6] = 0.0 sv = np.where(alpha > 0.0)[0]  # 互补松弛：非零 alpha 对应的即支持向量w = (alpha * y).dot(X)         # 平稳性：w = sum(alpha_i * y_i * x_i)b = np.mean(y[sv] - X[sv].dot(w)) print("\nSVM 对偶变量 alpha =", np.round(alpha, 4))print("支持向量索引 =", sv)print("w =", np.round(w, 4), "，b =", round(b, 4))pred = np.sign(X.dot(w) + b)print("训练集分类准确率 = %.0f%%" % (np.mean(pred == y) * 100))

1. def dual_obj(lam):定义对偶目标函数 g(λ)，输入是罚款单价 λ，输出是对偶函数值。
2. return -(lam - lam * lam / 4.0)g(λ) = λ − λ²/4 的解析式，取负号转成 scipy 默认的极小化形式。
3. res = minimize(dual_obj, 0.0, bounds=[(0.0, None)])求解对偶问题，bounds 实现 λ ≥ 0 的对偶可行域。
4. lam_star = res.x[0]取出最优罚款单价 λ，数值上应收敛到 2，此时 x = 1。
5. Q = np.array([[y[i] * y[j] * X[i].dot(X[j]) for j in range(n)] for i in range(n)])组装对偶 QP 的 Q 矩阵，里面全是样本内积。
6. def svm_dual(alpha):SVM 对偶目标函数，等价于最大化 Σα − ½αᵀQα。
7. cons = [{"type": "eq", "fun": lambda a: a.dot(y)}]等式约束 Σαᵢyᵢ = 0，来自对 b 求平稳性。
8. sv = np.where(alpha > 0.0)[0]互补松弛条件告诉我们：只有边界样本的 α 非零，余者皆零。
9. w = (alpha * y).dot(X)由平稳性条件 w = Σαᵢyᵢxᵢ 从对偶解恢复出原始空间的权重向量。

常见误区

面试题