AI 与工程数学 / 系统课时

用 KKT 条件检查不等式最优性

用 KKT 条件检查不等式最优性

这节课把不等式约束下的最优性检查拆成四组条件:原始可行、对偶可行、驻点和互补松弛。你会看到它们如何共同筛掉不合格候选点,并用一个一维凸优化问题完整检查一次 KKT 条件。

学习目标

  • 能写出不等式约束问题的四类 KKT 条件。
  • 能根据约束是否激活判断拉格朗日乘子的取值。
  • 能对简单凸问题逐项验证候选解是否满足 KKT。

四组条件分别约束什么

考虑标准形式

min⁡x f(x)\min_x\ f(x)

满足

gi(x)≤0,i=1,…,mg_i(x)\le 0,\quad i=1,\dots,m

拉格朗日函数定义为

L(x,λ)=f(x)+∑i=1mλigi(x)L(x,\lambda)=f(x)+\sum_{i=1}^m\lambda_i g_i(x)

KKT 条件由四部分组成:

  • 原始可行:gi(x∗)≤0g_i(x^*)\le 0,候选点必须先满足原问题约束。
  • 对偶可行:λi∗≥0\lambda_i^*\ge 0,不等式约束对应的乘子不能为负。
  • 驻点:∇f(x∗)+∑iλi∗∇gi(x∗)=0\nabla f(x^*)+\sum_i\lambda_i^*\nabla g_i(x^*)=0。
  • 互补松弛:λi∗gi(x∗)=0\lambda_i^*g_i(x^*)=0,每个约束要么未激活且乘子为零,要么激活并允许乘子非零。

KKT 四类条件与激活约束关系

其中最容易忽略的是互补松弛。它把“几何上是否碰到边界”与“该约束是否对最优点施加作用”连接起来,是筛选候选解的关键。

用激活与未激活理解互补松弛

若某个约束在最优点严格满足,即 gi(x∗)<0g_i(x^*)<0,说明最优点没有贴在这条边界上。为了满足 λi∗gi(x∗)=0\lambda_i^*g_i(x^*)=0,只能有 λi∗=0\lambda_i^*=0,这条约束在驻点方程中不起作用。

若约束恰好取等号,即 gi(x∗)=0g_i(x^*)=0,称它为激活约束。此时互补松弛自动满足,λi∗\lambda_i^* 可以为正,也可以为零,具体数值由驻点条件决定。

逐项检查一个简单问题

考虑

min⁡x x2\min_x\ x^2

满足

x≥1x\ge 1

为了符合 KKT 的标准形式,把约束改写为 g(x)=1−x≤0g(x)=1-x\le 0。拉格朗日函数为

L(x,λ)=x2+λ(1−x)L(x,\lambda)=x^2+\lambda(1-x)

驻点条件为 2x−λ=02x-\lambda=0。由于无约束最小点 x=0x=0 不可行,直觉上最优点应落在边界 x=1x=1,于是令约束激活,可得 x∗=1x^*=1、λ∗=2\lambda^*=2。

下面逐项验证四类条件。

python
x = 1.0
lam = 2.0

g = 1.0 - x
stationarity = 2.0 * x - lam
complementarity = lam * g

print("primal feasible:", g <= 0)
print("dual feasible:", lam >= 0)
print("stationarity:", stationarity)
print("complementarity:", complementarity)

预期输出

text
primal feasible: True
dual feasible: True
stationarity: 0.0
complementarity: 0.0

四项全部通过,因此 (x∗,λ∗)=(1,2)(x^*,\lambda^*)=(1,2) 满足 KKT 条件。这里约束恰好激活,且乘子为正,说明这个边界确实阻止了目标函数继续朝无约束极小点 x=0x=0 移动。

KKT 什么时候足以证明最优

一般非凸问题中,KKT 条件通常只是局部最优点需要满足的必要条件之一,满足 KKT 的候选点不一定是全局最优点。

如果问题是凸优化问题,且满足适当的约束资格条件,例如存在严格可行点使所有不等式都严格成立,那么 KKT 条件具有更强地位:满足 KKT 的点就是全局最优解。本例中 f(x)=x2f(x)=x^2 是凸函数,g(x)=1−xg(x)=1-x 是仿射函数,而且例如 x=2x=2 严格满足约束,因此 (1,2)(1,2) 不只是候选解,而可以由 KKT 条件直接确认其全局最优性。

实际检查时可以按固定顺序进行:先看原始可行性,再判断激活约束,用互补松弛确定哪些乘子必须为零,接着解驻点方程,最后检查所有乘子是否满足非负性。这样能最快发现候选解在哪一条 KKT 条件上失败。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

用 KKT 条件检查不等式最优性

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

登录哪都通