高等数学 / 系统课时

不等式约束与KKT条件

不等式约束与KKT条件

不等式约束既可能在最优点处真正限制解,也可能完全不起作用。KKT 条件通过原始可行性、对偶可行性、驻点条件和互补松弛,统一判断哪些约束处于激活状态以及候选解是否合理。

学习目标

  • 区分激活约束与非激活约束
  • 写出最小化问题的 KKT 四类条件
  • 用互补松弛验证简单不等式约束解

标准形式与拉格朗日函数

考虑最小化问题:

min⁡xf(x),s.t. gi(x)≤0,hj(x)=0\min_x f(x),\qquad \text{s.t. } g_i(x)\le 0,\quad h_j(x)=0

对不等式约束引入乘子 λi\lambda_i,对等式约束引入乘子 νj\nu_j:

L(x,λ,ν)=f(x)+∑iλigi(x)+∑jνjhj(x)\mathcal{L}(x,\lambda,\nu) =f(x)+\sum_i \lambda_i g_i(x)+\sum_j \nu_j h_j(x)

在这一符号约定下,不等式乘子必须满足 λi≥0\lambda_i\ge 0。若采用 gi(x)≥0g_i(x)\ge0 且仍在拉格朗日函数里加 λigi(x)\lambda_i g_i(x),则需 λi≤0\lambda_i\le0。也可以改为减去非负乘子乘约束。

KKT 条件的四个部分

KKT 点 (x∗,λ∗,ν∗)(x^*,\lambda^*,\nu^*) 满足以下四类条件。

  1. 原始可行性:gi(x∗)≤0g_i(x^*)\le 0,且 hj(x∗)=0h_j(x^*)=0。
  2. 对偶可行性:λi∗≥0\lambda_i^*\ge 0。
  3. 驻点条件:
∇f(x∗)+∑iλi∗∇gi(x∗)+∑jνj∗∇hj(x∗)=0\nabla f(x^*)+\sum_i \lambda_i^*\nabla g_i(x^*)+\sum_j \nu_j^*\nabla h_j(x^*)=0
  1. 互补松弛:
λi∗gi(x∗)=0\lambda_i^*g_i(x^*)=0

互补松弛表示每个不等式约束只能处于两种典型状态:约束未激活时 gi(x∗)<0g_i(x^*)<0,对应乘子必须为零;约束激活时 gi(x∗)=0g_i(x^*)=0,乘子可以为正,也可以为零。例如最小化 (x−1)2(x-1)^2 且 x≤1x\le1,最优点 x=1x=1 位于边界,乘子却为零。

激活约束与互补松弛对比图

主示例:带上界的一元最小化

求函数 f(x)=(x−2)2f(x)=(x-2)^2 在约束 x≤1x\le 1 下的最小值。把约束写成:

g(x)=x−1≤0g(x)=x-1\le 0

拉格朗日函数为:

L(x,λ)=(x−2)2+λ(x−1)\mathcal{L}(x,\lambda)=(x-2)^2+\lambda(x-1)

无约束最优点是 x=2x=2,但它不可行,因此约束会在最优点激活。令 x∗=1x^*=1,驻点条件给出:

2(x∗−2)+λ∗=02(x^*-2)+\lambda^*=0

所以 λ∗=2\lambda^*=2。它满足 x∗−1=0x^*-1=0、λ∗≥0\lambda^*\ge 0,并且 λ∗(x∗−1)=0\lambda^*(x^*-1)=0。下面逐项验证 KKT 条件:

python
def check_kkt(x: float, multiplier: float) -> None:
    constraint = x - 1
    stationarity = 2 * (x - 2) + multiplier
    complementarity = multiplier * constraint

    # 对应原始可行性、对偶可行性、驻点和互补松弛
    print(f"primal_feasible = {constraint <= 0}")
    print(f"dual_feasible = {multiplier >= 0}")
    print(f"stationarity = {stationarity:.1f}")
    print(f"complementarity = {complementarity:.1f}")

check_kkt(x=1.0, multiplier=2.0)

预期输出:

text
primal_feasible = True
dual_feasible = True
stationarity = 0.0
complementarity = 0.0

四项同时满足,说明 (x∗,λ∗)=(1,2)(x^*,\lambda^*)=(1,2) 是 KKT 点。本例目标凸、约束仿射,因此这个满足四项条件的点是全局最优解。

什么时候 KKT 足够

对光滑问题,若局部最优点满足约束资格,例如活跃不等式与等式的梯度线性无关,就存在乘子使其满足 KKT。凸问题中常用的 Slater 条件,则要求在适当的定义域内有满足等式且严格满足相关凸不等式的点。若资格条件失效,最优点可能没有 KKT 乘子,例如最小化 xx 且 x2≤0x^2\le0,唯一可行点 00 是最优点,但驻点方程变成 1+2λ⋅0=01+2\lambda\cdot0=0,无解。

充分性是另一个判断。如果目标函数和不等式约束凸、等式约束仿射,一个已经满足 KKT 的点就是全局最优,证明充分性时无需再要求 Slater。非凸问题中,KKT 点仍需用二阶条件或目标值比较进行验证。

常见错误

  • 忘记统一约束方向,导致乘子符号写反
  • 只检查驻点方程,没有检查原始可行性和互补松弛
  • 混淆约束资格与凸性,对非凸 KKT 点直接宣称全局最优
按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

不等式约束与KKT条件

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通