拉格朗日乘数 KKT 条件

机器算法验证 支持向量机 优化
2022-03-23 20:19:35

我正在查看 SVM,并查看拉格朗日乘数。假设使用约束函数我正在最大化直观上看,由于约束函数没有提供有限的约束区域,所以没有解,可以无限增大。

g(x,y)=x2+y21>0,
f(x,y)=x+y1.
f(x,y)

但是,如果我只是简单地进行拉格朗日乘数计算, 我得到了解决方案: 这仍然满足 KKT 条件,尽管解是错误的。

L(x,λ)=(x+y1)+λ(x2+y21)
y,x=2/2,λ=1/2
g(x)=>0,λ=>0,λg(x)=0.

我预计我会得到一些与 KKT 条件相冲突的结果,但没有任何违反。

这是否意味着 KKT 条件下的拉格朗日乘数可以产生无法解决的解决方案,而没有任何难以处理的迹象?

如果函数很复杂,那么确认不等式约束函数的优化可以使用拉格朗日乘数求解的系统方法是什么?

1个回答

一般来说,优化的一个关键概念,特别是 KKT 条件是区分:

  • 最优化的必要条件
  • 最优的充分条件

在最基本的形式中,KKT 条件是优化的必要条件。如果存在最优且满足一定的规律性条件,则最优必须满足 KKT 条件。

考虑一个更简单的情况:

maximize (over x)x2

KKT 条件为2x=0. 每个最优值都满足这些条件,但没有最优值!

要使 KKT 条件成为充分条件,还需要更多条件!例如,如果优化问题是的并且满足 Slater 条件,那么 KKT 条件也是最优的充分条件(并且满足 KKT 条件的每个点都是最优的)。

例如,

minimize (over x)x2

是一个凸的、无约束的问题,因此 KKT 条件是充分条件,因此条件2x=0暗示x=0是一个解决方案。

回答你的直接问题:

如果函数很复杂,那么确认不等式约束函数的优化可以使用拉格朗日乘数求解的系统方法是什么?

不幸的是,这里的答案有些细微差别。优化问题有许多不同的条件,这意味着 KKT 条件对于优化是必要的或充分的。

KKT 条件是最优的充分条件的最有用的问题类别之一是当优化问题是凸的并且 Slater 条件成立时。查看斯坦福教授 Boyd 的凸优化课程,但基本思想是凸优化问题可以写成:

minimize (over x)f(x)subject tojgj(x)0Ax=b

在哪里x是一个向量,目标函数fx, 约束gj是凸的x, 等式约束是仿射的。Slater 的条件是在可行集的相对内部存在一个点(例如,您没有像x20仅满足一个点)。

在满足 Slater 条件的凸问题的情况下,最优对是拉格朗日的鞍点(x,λ)

另一个必要的 KKT 条件的有用规律性条件是 LICQ 约束条件。KKT Wikipedia 页面有一个完整的可能规律性条件列表。优化的数学是一个大而广泛的话题!无论如何,这将有望使您朝着正确的方向前进!在进行过程中,请务必区分:

  • 暗示 KKT 条件的优化问题的条件对于优化是必要的。
  • 暗示 KKT 条件的优化问题的条件足以实现最优。