如题所述
KKT条件在处理有约束问题的时候很有用, 但是对KKT的适用性一直不是很理解, 看了这篇讲解整理一下.
问题
在等式约束条件:
及不等约束条件:
不妨就记
在不等式约束中, 即只有当我们所寻的极值点 处, 称之为激活不等式约束(active inequality constraints), 否则为不激活的, 我们记激活的不等式约束和等式约束为 .
注: 均连续可微.
对于任意一个可行点 , 令 为一连续路径, 满足 ，定义 为:
有如下性质:
其中, 我们假设梯度向量为行向量.
证明:
两边同除以 , 并令 即可得.
与上面同样的操作即可得.
我们把这些由路径引导出来的可行方向 的集合记为
而记满足 的一切 的集合记为 , 显然 , 且均为锥(即 属于此集合, 则 也属于此集合).
点 满足LICQ假设, 当
是线性独立的.
线性不独立: 当集合中存在一个向量能够由其他向量线性表出, 否则称此集合线性独立. 显然这是比线性无关更强的一个概念.
假设 是问题(1)在等式约束(2)以及不等式约束(3)的限制下的局部最小值点, 且满足LICQ假设. 则存在 满足:
且
记:
属于 的所有 的梯度的综合表示,
引理A : 当 满足LICQ假设, 则 .
证明:
既然 , 我们只需要证明 .
下面, , 我们将构造 , 为一连续的起点为 的路径, 且在 的足够小的一个邻域内 满足等式约束和不等式约束, 一旦找到这样的 , 证明也就完成了.
根据假设可知, dim( ) = , 则 的核的维数为 , 我们从核空间中抽取一组基作为行向量构建 , 则
是一个非奇异的 的方阵.
考虑如下的非线性方程系统(显然有解 )
关于 的加科比行列式为
非奇异, 所以根据隐函数定理可知, 在 足够小的时候, 存在连续可微函数 , 且 .
既然
我们有
也就是说
俩边令 , 可知 为 的一个连续路径.
又结合(25)
所以对于任意的 , 是可行路径, 对于未激活的不等式约束, 既然 是连续的, 当 足够效地时候容易得到 . 这样便证明了, , 均为可行方向, 故 .
Farkas 引理 : 令 和 为 维行向量且
则 当且仅当存在非负向量 使得
证明:
,
故 .
若不存在这样的 , 即对于任意的 , , 则 不能由 线性表出. 不妨假设 与 按序进行施密特正交化过程, 可得 为 的一正交向量组, 为
则
不妨设 (否则 ), 则 , 这与 矛盾.
证毕.
定义问题 :
定义问题 :
推论 : 要么问题 存在解, 要么 存在解, 二者不能同时成立.
既然 是一局部极值点, 则
将 视作Farkas引理中的 , 即为我们最开始定义的 , 则 , , 这是因为所有等式约束 , 都可以变成俩个不等式约束 . 这也就是说, 问题 无解, 则 有解, 即存在 :
对于任意的 , 我们只需取 , (39)依然成立, 同时原定理(18)中的(i)(ii)也同样容易证明.
