强对偶定理Strong Duality Theorem在凸优化里是一个很奇妙的存在。学机器学习的人每天在跟它对偶问题打交道SVM的拉格朗日对偶、线性回归的核技巧、各种带约束的估计问题算法能收敛、解能求出来背后几乎都有这个定理在撑腰。但当真去读证明时很多教材要么一句话带过“由凸集分离定理可得”要么直接说超出范围留一句“Slater条件保证强对偶成立”就翻过去了。我当年第一次完整推这个证明时卡了整整一个周末。后来发现卡住的地方不是分离定理本身而是对这个定理“怎么用”缺少直觉。把证明完整走一遍之后很多原来靠背的结论——对偶变量为什么非负、为什么要有Slater条件、互补松弛是不是额外假设——全都串起来了。这篇就按我自己的推导路径把强对偶定理的证明拆开揉碎讲清楚每个关键步骤都说明动机和依据。适合已经学过凸函数和Lagrange对偶基本概念、但想真正弄懂“为什么强对偶成立”的读者。1. 从Lagrange对偶说起——先搞明白我们到底在证什么1.1 原始问题与Lagrange函数先固定记号。考虑一个标准的凸优化问题$$ \min_{x} f(x) \quad \text{s.t.} \quad g_i(x) \le 0,\quad i1,\dots,m $$其中 $f, g_1,\dots,g_m$ 都是凸函数。这里我故意不写等式约束原因后面会讲等式约束并不会改变证明的思想只会多一组符号。写出Lagrange函数$$ L(x,\lambda)f(x)\sum_{i1}^{m}\lambda_i g_i(x),\qquad \lambda \succeq 0。 $$很多初学者第一次看到这个函数会困惑为什么要无端把约束乘个系数加在目标函数后面一个比较直觉的解释是$L(x,\lambda)$是$f(x)$在“约束被惩罚”意义下的一个替代目标。当某个$x$违反了$g_i(x)0$时只要$\lambda_i0$这个违反会给$L$带来一个正惩罚当约束满足时惩罚项是负的相当于给了一个“奖励”。我们后面会看到这个带惩罚的下界恰好是证明强对偶的关键工具。1.2 对偶函数、弱对偶与真正要证的那个“等号”定义对偶函数$$ d(\lambda)\inf_{x} L(x,\lambda)。 $$也就是说固定一组惩罚权重$\lambda$把$x$整个空间上扫一遍找到$L$的最小值。这个$d(\lambda)$有一个非常重要的性质对任意可行点$x$即满足$g_i(x)\le0$和任意$\lambda\succeq0$都有$$ L(x,\lambda)f(x)\sum_{i1}^m\lambda_i g_i(x)\le f(x) $$因为第二项是非正的。两边对可行$x$取下确界再对$\lambda$取上确界就得到弱对偶不等式$$ d^\star\sup_{\lambda\succeq0}d(\lambda)\le p^\star $$其中$p^\star$是原问题最优值。这个不等式不需要任何凸性假设它只是“可行点上的函数值不小于对偶函数值”的直接推论。弱对偶告诉我们$d^\star$永远不会超过$p^\star$这是一个保险的下界。而强对偶定理要证的就是在凸性加约束品性的条件下这个不等式变成等式$$ d^\starp^\star。 $$换句话说通过解对偶问题得到的最优值恰好就等于原始问题的最优值。这就是“强对偶”里“强”的含义。1.3 为什么非要有“凸”这个前提如果$f$或$g_i$不是凸函数强对偶大概率是不成立的。原因可以这么感受弱对偶只给了$d^\star \le p^\star$两者之间的差叫对偶间隙。非凸问题里这个间隙经常严格为正因为对偶问题本质上是在做一个“凸化”处理它看到的是函数的某种下包络而不是原始问题的真实复杂度。凸性保证了$L$关于$x$的最小化行为和原始问题的最优值之间有足够强的几何联系——具体来说就是可以构造一个凸集把原问题和对偶问题同时“放”进去然后用分离超平面把两者连接起来。这也是整个证明的骨架。2. 分离超平面定理强对偶证明的真正引擎2.1 从几何直觉到代数形式分离超平面定理的内容很直观如果两个凸集不相交或者一个点在凸集外面那么存在一个超平面把它们隔开。用代数语言说对于凸集$C$和点$y \notin \operatorname{int} C$存在非零向量$u$和常数$c$使得对所有$x \in C$都有$u^\top x \ge c$并且$u^\top y \le c$。为什么强对偶的证明要借助这个定理因为对偶问题本质上就是在找某个超平面的截距。你想想$d^\star$是一个上确界$p^\star$是一个下确界两者之间的缝隙在几何上恰好就是能不能用一个超平面把某个关键点从某个凸集里“撑”出去。如果撑得出去对偶间隙就是零如果撑不出去对偶间隙就卡在那里。这个思路听起来有点抽象但具体展开后会发现整个证明就是把这个几何过程一步一步代数化。2.2 为什么分离超平面法向量能“变成”对偶变量这是整个证明里最震撼的一步分离超平面的法向量归一化之后就是一组最优对偶变量$\lambda^\star$。所以强对偶定理的证明其实带有构造性——它不只是告诉你“存在一个$\lambda$”而是通过分离超平面真的把这个$\lambda$找出来了。从几何上看原问题的最优值$p^\star$对应一个点$(p^\star,0)$而所有可行解的“函数值-约束值”组合形成另一个凸集$A$。如果$(p^\star,0)$在$A$的边界上分离超平面就会从这个点“切”过去。这个超平面的法向量分成两部分第一部分对应目标函数的权重第二部分对应约束的权重。约束权重那一部分归一化后就是$\lambda^\star$。这也是为什么强对偶和KKT条件经常一起出现——KKT条件里的那个拉格朗日乘子在几何上就是这个支撑超平面的法向量。2.3 需要哪种分离形式内部点和闭集的区别很多教材写到这里时用“由分离定理可得”一句话带过但这里有版本差异。常用的分离定理有两种形式一种是点不在凸集内部存在一个非平凡支撑超平面过该点另一种是点不在凸集闭包内存在超平面严格分离。我们证明中需要的是前者点$(p^\star,0)$落在凸集$A$的闭包里但不在$A$的内部。这时分离超平面可能不是“严格”分开的而是在点处与$A$相切。这种“切触型”分离也叫支撑超平面定理。对初学者来说这里最容易犯的错是选错了分离定理版本试图证明“存在$(p^\star-\varepsilon,0)$在$A$外面”结果发现根本证不出来。正确做法是先从$A$的内部入手证明$(p^\star,0)$不可能是内点再用支撑超平面定理。3. 强对偶定理的完整证明过程3.1 构造关键集合A及其凸性证明的起点是构造一个集合把所有“可能的目标值和约束值组合”都装进去$$ A{(p,w)\in\mathbb{R}^{m1}:\ \exists x,\ p\ge f(x),\ w_i\ge g_i(x),\ i1,\dots,m}。 $$换句话说$A$由所有“被某个$x$生成、并且在其上方”的点$(p,w)$组成。这里有个关键细节为什么取$p\ge f(x)$、$w_i\ge g_i(x)$而不是直接取点$(f(x),g(x))$因为直接取$(f(x),g(x))$得到的集合不一定是凸的。凸函数$f$本身的图像不是凸集但它的上境图epigraph${(p,x):p\ge f(x)}$一定是凸集。这个“向上取整”的操作就是把非凸的图像补成凸集好让分离超平面定理有地方用。验证$A$的凸性也很简单。取$(p_1,w_1),(p_2,w_2)\in A$对应$x_1,x_2$。对任意$\theta\in[0,1]$令$x_\theta\theta x_1(1-\theta)x_2$。由$f$的凸性$$ f(x_\theta)\le \theta f(x_1)(1-\theta)f(x_2)\le \theta p_1(1-\theta)p_2 $$对$g_i$同理。所以凸组合$(\theta p_1(1-\theta)p_2,\ \theta w_1(1-\theta)w_2)$也能被$x_\theta$生成落在$A$里。3.2 最优值点为什么落在A的边界上设$p^\star$是原问题的最优值我们要关注的点是$(p^\star,0)$。先证明它不在$A$的内部。用反证法。如果$(p^\star,0)$是$A$的内点那么存在足够小的$\varepsilon0$使得$(p^\star-\varepsilon,-\varepsilon,\dots,-\varepsilon)$也属于$A$。根据$A$的定义这意味着存在某个$x$同时满足$$ f(x)p^\star,\qquad g_i(x)0,\quad i1,\dots,m。 $$但这就是一个严格可行解且函数值小于$p^\star$直接和$p^\star$的最优性矛盾。所以$(p^\star,0)$不可能在$A$内部。另一方面$(p^\star,0)$一定在$A$的闭包里。因为如果原问题有可行解序列$x_k$使得$f(x_k)\to p^\star$那么$(f(x_k),g(x_k))$就落在$A$里并逼近$(p^\star,0)$。于是我们有了一个非常干净的局面$A$是凸集$(p^\star,0)$在$A$的边界上。这就是支撑超平面定理的适用场景。3.3 分离超平面给出的三个关键信息由支撑超平面定理存在非零法向量$(\mu_0,\mu)\in\mathbb{R}^{m1}$使得对所有$(p,w)\in A$$$ \mu_0 p\sum_{i1}^m \mu_i w_i \ge \mu_0 p^\star。 $$这里法向量方向我选的是“指向$A$内部”的一侧。如果你在别的书上看到符号相反不要慌把法向量整体乘个$-1$就换过来了。这个不等式里其实藏着三个关键信息需要一步步挖出来第一$\mu_0\ge0$且每个$\mu_i\ge0$。因为$A$是向上封闭的如果$\mu_00$固定$w$让$p\to\infty$左边会趋近$-\infty$而不等式左边必须始终$\ge\mu_0p^\star$矛盾同理如果某个$\mu_i0$让$w_i\to\infty$也会破坏不等式。所以法向量每个分量都非负。注意法向量非零因此这些分量不全为0。第二这个不等式对所有的$x$都成立。因为对任意$p\ge f(x)$、$w_i\ge g_i(x)$上面的不等式都成立特别地取$pf(x)$、$w_ig_i(x)$立刻得到$$ \mu_0 f(x)\sum_{i1}^m \mu_i g_i(x)\ge \mu_0 p^\star,\quad \forall x。 $$第三$\mu_0$必须严格大于0这一步是整个证明的关键节点需要单独的论证。3.4 法向量非负性与μ00的证明先处理一个很容易被跳过的问题为什么$\mu_0$不能等于0如果$\mu_00$前面的不等式就退化为$$ \sum_{i1}^m \mu_i g_i(x)\ge0,\qquad \forall x。 $$这看起来不矛盾——有些问题里确实存在这样的非零$\mu\succeq0$。但别忘了我们还有Slater条件。Slater条件说的是存在一个点$\hat{x}$使得$$ g_i(\hat{x})0,\quad i1,\dots,m。 $$既然$\mu_i\ge0$且不全为零那么$$ \sum_{i1}^m \mu_i g_i(\hat{x})0 $$这和上式矛盾。所以$\mu_0\neq0$结合非负性就是$\mu_00$。这一步就是Slater条件在证明中真正发挥作用的地方。它确保分离超平面的法向量里“目标方向的分量”不为零这样我们才能把法向量归一化成对偶变量。如果$\mu_00$得到的只是一个关于约束方向的恒等式根本推不出任何关于目标函数的有用信息。既然$\mu_00$就放心地归一化。令$$ \lambda_i\frac{\mu_i}{\mu_0}\ge0 $$于是前面的不等式变成$$ f(x)\sum_{i1}^m \lambda_i g_i(x)\ge p^\star,\qquad \forall x。 $$这组$\lambda_i$就是我们构造出的对偶可行解。3.5 从分离不等式到强对偶等式到这一步剩下的推导几乎是水到渠成。上面的不等式对所有$x$都成立那么对$x$取下确界右边是$p^\star$左边正是对偶函数$d(\lambda)$$$ d(\lambda)\inf_x\left[f(x)\sum_{i1}^m \lambda_i g_i(x)\right]\ge p^\star。 $$一个具体的对偶可行解已经让对偶函数值不小于$p^\star$了那么对偶问题的最优值$d^\star\sup_{\lambda\succeq0}d(\lambda)$当然也至少是$p^\star$$$ d^\star\ge p^\star。 $$再加上弱对偶不等式$d^\star\le p^\star$两条一夹得到$$ d^\starp^\star。 $$强对偶定理证完。回看整个证明可以总结成一句话把原问题和对偶问题同时装进一个凸集$A$用支撑超平面在最优值点处切开切出来的法向量就是最优对偶变量。凸性是$A$能成为凸集的理由Slater条件是法向量目标分量不为零的理由弱对偶负责给出另一个方向的不等式。4. Slater条件与约束品性条件在证明中到底卡在哪一步4.1 Slater条件的几何含义Slater条件存在$\hat{x}$使得对所有不等式约束$g_i(\hat{x})0$严格成立。如果有等式约束通常还要加一条存在严格满足不等式约束的点且等式约束线性无关。为什么叫“条件”而不是“定义”因为它其实是在说一件几何上的事可行域的“内部”不是空的。严格可行点的存在意味着可行域在约束边界内有厚度不会被约束面压扁成一个低维流形。这一厚度恰好保证了前面证明中分离超平面法向量的$\mu_0$分量非零。几何图像可以这样想如果可行域像一张只有边界没有内部的薄片那么用一个超平面去支撑它的时候支撑方向可以完全“贴”在约束方向上法向量根本没有目标方向的分量。这正好对应$\mu_00$证明就卡住了。4.2 缺少Slater条件时证明会怎样失效用一个最简单的例子来说明。考虑$$ \min x,\qquad \text{s.t.}\quad x^2\le0。 $$约束只有$x0$这个点$p^\star0$。构造集合$A$分离法向量可以取$(\mu_0,\mu_1)(0,1)$因为对所有$(p,w)\in A$确实有$w\ge x^2\ge0$所以$$ 0\cdot p1\cdot w\ge0 $$成立。法向量非负且非零但$\mu_00$证明在这里断掉——没法归一化也就构造不出对偶变量。注意这个例子强对偶其实还是成立的。计算对偶函数$$ d(\lambda)\inf_x(x\lambda x^2) $$当$\lambda0$时最小值在$x-1/(2\lambda)$处取得$d(\lambda)-1/(4\lambda)$当$\lambda\to\infty$时趋向0。所以$d^\star0p^\star$。但对偶最优解取不到是一个开区间上的上确界而非最大值。这说明了一件事Slater条件是证明强对偶的充分条件而不是必要条件。缺少它证明中的某个关键步骤会失效但定理本身有时仍然成立只是需要更精细的工具。4.3 约束品性失效仍然强对偶成立的反例前面那个例子会给人一个错觉反正强对偶最后还是成立的Slater条件是不是多余不是。构造一个凸问题同样只有一个可行点但强对偶真的会失效$$ \min e^{-x},\qquad \text{s.t.}\quad x^2\le0。 $$可行域还是只有$x0$所以$p^\stare^01$。但对偶函数$$ d(\lambda)\inf_x(e^{-x}\lambda x^2)。 $$当$\lambda0$时$\inf_x e^{-x}0$当$\lambda0$时$d(\lambda)$也始终小于1。所以$d^\star1p^\star$出现真正的对偶间隙。问题出在哪目标函数$e^{-x}$在$x\to\infty$时趋近0而约束$x^2\le0$把可行点硬按在$x0$上。对偶问题看不到这个“约束把点钉死”的事实它以为可以让$x$跑向无穷远处来压低$L$的值。这就是没有Slater条件时对偶间隙能真实出现的原因。在实际工程里遇到带复杂约束的优化问题我的建议是先尝试验证Slater条件。如果有严格可行点对偶间隙为0这件事就板上钉钉可以放心解对偶问题如果验证不了至少要知道对偶解可能和原问题有偏差不能盲目信任。5. 学习这个证明时常被卡住的点和我的几点体会5.1 四个经典卡壳点卡壳点一为什么$A$要向上取。这个问题我在前面强调过但值得再啰嗦一次。$f$是凸函数不代表集合${(f(x),g(x)):x\in\mathbb{R}^n}$是凸集只有取“上方”才能把凸性转化为集合的凸性。直观类比一座山的山脊线不是凸的但山的水平截面以上的整个空间是凸的。很多初学者栽在这里因为默认“凸函数的图像是凸集”其实凸函数的图像graph不是凸集上境图才是。卡壳点二支撑超平面定理的版本。分离定理有“严格分离”和“支撑分离”两种形态强对偶证明用的是后者。区分方法很简单看关键点是否在凸集的闭包内。在闭包内且在边界上就用支撑版本完全在闭包外才用严格分离版本。用错版本会导致构造不出来。卡壳点三符号方向。分离不等式写成$\ge$还是$\le$取决于法向量方向选在哪一侧。我建议每次推导时都固定一个习惯法向量指向凸集内部那一侧这样分离不等式就是$\mu^\top x\ge\mu^\top y$。方向反了就把法向量整体取负号不影响证明。卡壳点四为什么对偶变量必须非负。本质原因是原始约束是$g_i(x)\le0$Lagrange函数第二项$\lambda_i g_i(x)$只有对非负$\lambda_i$才是$f(x)$的一个下界修正。如果约束写成$g_i(x)\ge0$乘子符号就要反过来。我在推KKT条件时经常看到有人把符号搞混根源就是没想明白这一点。5.2 证明思路对KKT条件与算法设计的延伸强对偶证明完成后KKT条件的推导变得非常自然。设原问题和对偶问题分别有最优解$x^\star$和$\lambda^\star$强对偶成立意味着$$ f(x^\star)d(\lambda^\star)\le f(x^\star)\sum_{i1}^m\lambda_i^\star g_i(x^\star)\le f(x^\star)。 $$链式不等式两端相等所以中间都是等号。由最后一个等号$\sum_i\lambda_i^\star g_i(x^\star)0$每一项$\lambda_i^\star\ge0$、$g_i(x^\star)\le0$所以只能逐项为零这就是互补松弛条件。换句话说互补松弛不是额外假设而是强对偶下乘子和约束之间自动满足的关系。这个理解对算法实践有直接帮助。解SVM对偶问题时支持向量对应的$\lambda_i0$那些样本的约束恰好取等号正是互补松弛的几何体现。反过来如果数值解里配对关系对不上说明求解过程有问题或者问题本身不满足约束品性。5.3 一点学习建议最后分享一个我自己的笨办法。学这个证明时我建议花半小时把$m1$的情况画出来$A$是一个平面区域边界由参数曲线${(f(x),g(x))}$的上方包络构成$(p^\star,0)$是最低可行为处。看看支撑超平面是怎么在这个点切过$A$的法向量的斜率就是$\lambda^\star$。把这张图画出来强对偶就不再是个抽象定理而是一个看得见摸得着的几何事实。在这个图形里$p^\star$就是$A$与竖轴$w0$相交的最低高度支撑超平面保证了这个高度能通过对偶方向“看见”。Slater条件保证支撑超平面不是竖直的。一旦想明白这一层以后再遇到各种对偶相关的算法和理论你都会比那些只背结论的人多一个判断工具。强对偶定理的价值不只是保证“能解对偶问题”它更提供了看待优化问题的一种视角任何优化问题背后都有一对凸集它们的距离就是最优解而在这中间站着的永远是超平面。