手推支持向量机08-约束优化问题-对偶关系之KKT条件

刺骨的言语ヽ痛彻心扉 2022-11-27 00:45 152阅读 0赞

**目录**

1.写在前面

2.什么是KKT条件（3组，5个条件）

--------------------

# 1.写在前面 #

上一节，我们介绍了slater条件，假如说我们遇到一个凸优化问题+slater条件，那么一定满足强对偶关系。强对偶关系是说p\*是原问题的解，d\*是对偶函数的解，满足p\*=d\*。p\*对应最优解是x\*，d\*对应最优解是λ\*和η\*。怎么求出来这三个最优解呢？KKT就给定了这三者之间的一个关系，可以求出这三个最优解。并且KKT条件和强对偶关系属于充要条件，可以互相推导。我们这一节就介绍什么是KKT条件。

![20200812184556867.png][]

# 2.什么是KKT条件（3组，5个条件） #

KKT条件可以分为3组，第一组是满足可行域或者可行条件；第二组是满足互补松弛条件；第三组是梯度为0。

![20200812184904442.png][]

互补松弛条件是什么呢？我们思考d\*是什么，是对偶问题的最优值，可以直接代入λ\*和η\*：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1N1eWViaXViaXU_size_16_color_FFFFFF_t_70][]

上面那个式子我们可以得到互补松弛条件，如果d\*=p\*，只能取等号。下面蓝框中就是我们推出的互补松弛条件。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1N1eWViaXViaXU_size_16_color_FFFFFF_t_70 1][]

![2020081218585566.png][]

我们看第三组梯度等于0，因为上面绿色公式推导中要取等号，我们可以单独拿出来讨论：当x=x\*时候，取得最小值。

![20200812190117977.png][]

所以如果L对x求偏导，在x=x\*时候，一定会等于0，因为必须要有最小值。其实第二组互补松弛条件和第三组梯度为0条件都是从不等式取等号推导出来的。最后的KTT三组条件为（三组+五个条件）：

![20200812190641412.png][]

[20200812184556867.png]: /images/20221124/f218698cc9b74622a71945c19a55a99f.png
[20200812184904442.png]: /images/20221124/328fdd69597d4f53b21167a1e916c9b8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1N1eWViaXViaXU_size_16_color_FFFFFF_t_70]: /images/20221124/72e3ed52b08b43d0a6f946128b1ff644.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1N1eWViaXViaXU_size_16_color_FFFFFF_t_70 1]: /images/20221124/bea706a2920840ff85826172c5bf76cb.png
[2020081218585566.png]: /images/20221124/a7c19748c6df4892abda5a72a68bf258.png
[20200812190117977.png]: /images/20221124/fc028b722b2b443dbb64876b262fa7cc.png
[20200812190641412.png]: /images/20221124/49a51668e7a5428184058cc64db91a68.png