关于机器学习中对偶问题解的可行性与有效性的技术疑问

阿华AIGC实验室

2026-4-20

嘿，这个问题问到了对偶理论的核心痛点上，咱们一步步拆解来搞清楚：

首先，先明确对偶函数的「下界属性」本质

你提到的不等式 $f(x) \ge L(x, u, v)$ 确实只有当 $x$ 是原问题可行点（即满足 $Ax=b$ 且 $Gx \le h$）时才成立——因为此时 $u^{T(Ax-b)=0$，$v}T(Gx-h) \le 0$（又因为 $v \ge 0$），所以 $L(x,u,v) = f(x) + 0 + \text{非正数} \le f(x)$。

但对偶函数 $g(u,v) = \min_x L(x,u,v)$ 的定义是对所有x求极小值，不管x是否可行。这里有个关键：如果某个 $(u,v)$ 对应的极小值点 $x=t(u,v)$ 不可行，那 $g(u,v)$ 的值会变得非常小甚至趋向 $-\infty$——举个例子，假设 $Ax \neq b$，我们可以让 $u$ 的方向和 $(Ax-b)$ 相反，那 $u^T(Ax-b)$ 会趋向负无穷，拉低整个 $L(x,u,v)$ 的值，最终 $g(u,v)=-\infty$。

而我们的对偶问题是 $\max_{u,v \ge 0} g(u,v)$，显然这种取到 $-\infty$ 的 $(u,v)$ 会被自动排除——我们要找的是能让下界尽可能大的 $(u,v)$，所以只有那些让 $g(u,v)$ 取有限值的 $(u,v)$ 才会被考虑。

强对偶性成立时，最优对偶解对应的x必然可行

在机器学习的常见场景（比如SVM、线性回归带约束的情况），原问题都是凸优化问题，且满足Slater条件（即存在至少一个严格可行点，满足 $Ax=b$ 且 $Gx < h$），这时候会触发强对偶性：原问题的最优值 $p^$ 等于对偶问题的最优值 $d^$，即 $p^* = d^* = \max_{u,v \ge 0} g(u,v)$。

当强对偶性成立时，对偶问题的最优解 $(u^*,v)$ 对应的 $x^*=t(u,v^)$ 必然是原问题的可行点，这可以通过KKT条件来证明：
强对偶性成立时，原问题最优解 $x^$ 和对偶最优解 $(u^*,v*)$ 必须满足KKT条件，其中就包括：

原始可行性：$Ax^*=b$，$Gx* \le h$
互补松弛：$v^{*T}(Gx*-h)=0$
梯度条件：$\nabla_x L(x^*,u,v^)=0$

而你的 $x^*=t(u,v^)$ 正是满足梯度条件的点，结合强对偶性，它必然同时满足原始可行性——否则会出现矛盾：如果 $x^$ 不可行，那原问题的最优值 $p^ \le f(x^)$，但 $d^*=g(u,v^*)=L(x,u^*,v)=f(x^) + u^{*T}(Ax-b) + v^{*T}(Gx-h)$，因为 $x^$ 不可行，要么 $Ax^* \neq b$ 要么 $Gx^* > h$，结合 $v^* \ge 0$，这个式子会小于 $f(x^)$，但 $d^*=p$，就会推出 $p^* < f(x^)$，但原问题存在可行点 $x^\text{feasible}$ 满足 $f(x^{\text{feasible})=p} \le f(x^)$，而 $x^\text{feasible}$ 应该也是 $L(x,u^*,v)$ 的极小值点（因为 $L(x^{\text{feasible},u},v^) \le f(x^{\text{feasible})=p}=d^*=g(u,v^)=\min_x L(x,u^*,v)$），这就和 $x^$ 是凸问题下梯度为0的全局极小点矛盾，所以 $x^$ 必须可行。

非凸问题的情况：不可行x也没关系

如果原问题是非凸的，强对偶性通常不成立，此时对偶最优值 $d^* < p^$，对应的 $x^*=t(u,v^)$ 可能不可行。但这时候我们使用对偶问题的目的只是得到原问题最优值的一个下界，而不是用 $x^$ 作为原问题的解——所以即使 $x^*$ 不可行，也不影响对偶问题作为下界的有效性，只是它没法帮我们找到原问题的最优解而已。