KNOWECON WIKI

ARTICLE

互补松弛

互补松弛 (Complementary Slackness) 互补松弛 (Complementary Slackness) 是凸优化和数学规划理论中的一个核心条件，构成卡罗需-库恩-塔克条件 (KKT条件) 的重要组成部分。该条件描述了最优点处约束条件与拉格朗日乘子之间的互斥关系：若某个不等式约束是松驰的（严格不等式成立），则其乘子必须为零；若乘子大于零，则

浏览 0 更新 2026-01-08

互补松弛 (Complementary Slackness)

互补松弛 (Complementary Slackness) 是凸优化和数学规划理论中的一个核心条件，构成卡罗需-库恩-塔克条件 (KKT条件) 的重要组成部分。该条件描述了最优点处约束条件与拉格朗日乘子之间的互斥关系：若某个不等式约束是松驰的（严格不等式成立），则其乘子必须为零；若乘子大于零，则对应约束必须是紧的（等式成立）。

数学表述

考虑标准约束优化问题：

<div>

min⁡xf(x)s.t.gi(x)≤0,i=1,…,mhj(x)=0,j=1,…,n\begin{aligned} \min_{x} \quad & f(x) \\ \text{s.t.} \quad & g_i(x) \le 0, \quad i=1,\ldots,m \\ & h_j(x) = 0, \quad j=1,\ldots,n \end{aligned}

</div>

其拉格朗日函数为 L(x,μ,λ)=f(x)+∑μigi(x)+∑λjhj(x) L(x, \mu, \lambda) = f(x) + \sum \mu_i g_i(x) + \sum \lambda_j h_j(x) ，其中 μi≥0 \mu_i \ge 0 。互补松弛条件为：

<div>

μi⋅gi(x∗)=0,i=1,…,m\mu_i \cdot g_i(x^*) = 0, \quad i = 1, \ldots, m

</div>

这意味：若 gi(x∗)<0 g_i(x^*) < 0 （松驰约束），则 μi=0 \mu_i = 0 ；若 μi>0 \mu_i > 0 ，则 gi(x∗)=0 g_i(x^*) = 0 （紧约束）。两者不能同时非零。

经济直觉：影子价格

互补松弛在经济学中有直观解释。拉格朗日乘子 μi \mu_i 是影子价格，表示约束资源每放宽一单位时目标函数最优值的改善量。

考虑企业在资源约束下最大化利润：

  • 若资源有剩余（gi(x∗)<0 g_i(x^*) < 0 ），该资源不稀缺，其影子价格应为零（μi=0 \mu_i = 0 ），增加该资源不会带来额外利润。
  • 若影子价格为正（μi>0 \mu_i > 0 ），说明资源稀缺，企业必定将其全部用完（gi(x∗)=0 g_i(x^*) = 0 ）。若资源仍有剩余，企业可扩大生产增加利润，说明尚未达到最优。

这揭示了资源稀缺性与其经济价值之间的深刻联系：只有稀缺资源才具有正价格。

线性规划中的互补松弛

在线性规划中，互补松弛具有对称形式。考虑对偶问题：

<div>

(P)  max⁡x  cTxs.t.  Ax≤b,  x≥0(D)  min⁡y  bTys.t.  ATy≥c,  y≥0\begin{aligned} \text{(P)} \; \max_x \; c^T x &\quad \text{s.t.} \; Ax \le b, \; x \ge 0 \\ \text{(D)} \; \min_y \; b^T y &\quad \text{s.t.} \; A^T y \ge c, \; y \ge 0 \end{aligned}

</div>

互补松弛条件为：

<div>

yi(bi−Aix)=0,xj(AjTy−cj)=0y_i (b_i - A_i x) = 0, \quad x_j (A_j^T y - c_j) = 0

</div>

若原始约束松驰（资源有剩余），则对偶变量 yi=0 y_i = 0 ；若 yi>0 y_i > 0 ，则原始约束紧。若原始变量 xj>0 x_j > 0 （活动被采用），则对偶约束紧（AjTy=cj A_j^T y = c_j ，零利润条件）；若对偶约束松驰（成本超收益），则 xj=0 x_j = 0 。

KKT条件中的角色

互补松弛是KKT条件的四个组成部分之一，其他为稳定性条件、原始可行性和对偶可行性。当满足约束规范（如斯莱特条件）时，KKT条件是凸优化问题最优解的充要条件。互补松弛在其中扮演连接原始域与对偶域的关键桥梁作用。

数值算法中的应用

互补松弛在优化算法设计中至关重要：

  • 内点法：逐步逼近互补松弛条件，沿可行域内部路径搜索最优解。
  • 积极集法：维护紧约束集合，每步迭代后根据互补松弛调整该集合。
  • 半光滑牛顿法：将互补松弛转化为半光滑方程组求解。

互补松弛将约束优化问题转化为代数方程与不等式，为理论分析和数值计算提供统一框架，是保证求解质量和算法收敛性的核心条件。