SVM-part1-KKT条件

从三类优化问题开始:

1 无约束优化。

2 带等式约束带优化。

3 不等式约束优化。


而SVM的优化问题,即不等式约束优化,针对此类问题,

细分为两类情况:

1. 目标函数最优解在可行域内:此时不等式约束失效,问题即退化为无约束优化问题。

2. 目标函数最优解不在可行域内:此时带约束后,最优解一定在可行域边界; 且满足在该点处的两个函数的梯度方向相反。


上面是思路,下面具体到数学表达。

对于不等式约束问题:

min f(x)

subject to : g(x) < 0

定义拉格朗日表达式: L(x) = f(x) + \lambda g(x) 

如果是第一类情况: f(x) 最优解 x* 在可行域内:

满足:

1 g(x*) < 0   # 即在可行域内

梯度L(x*) = 0, 且\lambda  = 0  # 即代表拉格朗日表达式中不等式约束部分无效

对于第二类情况: f(x) 最优解 不在可行域内:

满足:

1 g(x*) = 0   # 代表一定在可行域边界上。

2 梯度 L(x*) = 0,  且\lambda > 0 # 代表 在最优解 x* 处, f(x*)与g(x*) 梯度方向相反,故\lambda 一定大于0。

两种情况合并起来:

1 g(x*) <= 0

2 梯度 L(x*) = 0, 且\lambda  >= 0.

3 \lambda * g(x*) = 0  # 综合两类情况的1,2两个条件,你都可以发现隐含着这个要求。

©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成,浏览时请结合常识与多方信息审慎甄别。
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

相关阅读更多精彩内容

友情链接更多精彩内容