前面已经铺垫两篇科普:
直观理解:为什么一阶导为0不是极值点的充分条件?
看图理解 拉格朗日乘子法
里面提到了半正定二次型为什么会出现在凸优化中,以及为什么会有拉格朗日乘子法,主要参考瑞典皇家理工学院非常棒的PPT,
即便这样,总结仍有不严谨之处,希望指正,共同进步。
- 如何推导得出KKT条件 -
正是在求解凸优化的含不等式约束时,推导出了KKT条件,下面通过图形和符号一步一步推导。
带求解问题
f(x) 最小值为 0 ,如下图,同时给出了带约束极小值与无约束一致需要满足的两个条件(第二个条件正是正定二次型)
以上情况,我们称此约束失效(not active),如下图所示:
为了让以上约束生效,重新定义目标函数:
即等同于圆心位置移动:
容易看出,如果不带约束,目标函数的最小值位于圆心处取得,但是此处不能满足约束:
因此,直观感觉,目标函数的最小值是在恰好与约束区域边界外切处取得,如下图所示:
用数学公式描述,即满足:
正是基于这个等式,定义了著名的拉格朗日乘子法:
总结以上两种情况(无约束极小值取得位置是否位于可行域内):
合并以上两种,追求简约,总结了约束条件,这就是:KKT条件
具体来说:
1)
合并为KKT条件:
2)
比较容易观察
3)
合并为KKT条件4:
4)
合并为条件3:
上式等式正是支持向量机中为什么真正只有两个点起到分类作用的原因
5)半正定二次型约束,等价于凸优化
以上,KKT条件一种直观的推导和理解方法。如果文章觉得有帮助,欢迎点赞。