有关KKT条件,一直都看的云里雾里,但是还是很好奇其内在的逻辑,最后花时间整理了一下,有不足之处请指正。
有关原问题和对偶问题的转化知乎回答解释的更详细。
正文开始之前,介绍一些概念
Duality,对偶性
(1)比如极大极小问题和极小极大问题就是对偶问题,当把极大极小问题转化成极小极大问题来求解时,得到的最优解分别是d和p,那么最优解之间可能会存在一个差值,叫做duality gap。
(2)当遵循强对偶时,gap值=0,通常在凸问题中;当遵循弱对偶时,对偶值为正,凸问题和非凸问题都存在。
(3)对偶问题的函数表达理解
Convex optimization,凸优化(1)求解凸函数在凸集上的最小值,此时求解的局部最小值就是全局最小值(原因请自己查凸函数和凸集的定义)。
(2)凸函数的最小值 <=> 求解凹函数的最大值
(3)一阶偏导数为0是求解优化的充分条件。
(4)凸优化的情况可以分为两大类:有限制条件和没有限制条件
KKT一般都是用来求解具有限之条件的优化问题(最小值)。如下展开对于极小值的求解:
1. 无限制条件的极小值的求解
(1)一阶偏导数为0
(2)Hessian矩阵半正定
2. 有限定条件的极小值的求解
(1)优化问题的正式表达
(2)Lagrange函数表达(原问题)
(3)Lagrange对偶函数表达(对偶问题):当λ≥0时,G≤存在最大值。与f(X)正好相反。
注:对偶问题一定是凸的,i.e. , G一定是凹的
(4)KKT条件:原问题最优解,对偶问题最优解和
① 与满足条件(L对λ的偏导)<=> 原问题的限制条件
② ≥0 <=> 对偶问题的限制条件
③ 稳定条件,假设对偶问题的最优解和已知,求解原问题的最优解,即L的最小化,所以L对X的偏导可以求解。
④ complementary slackness:
条件①和②的满足意味着:
所以 ,由于,所以令其全部为0。
因此,,,是最优解 <=> KKT条件。充分性和必要性可以自己证明。