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