强对偶性、弱对偶性以及KKT条件的证明（对偶问题的几何证明）

不念不忘少年蓝@ 2023-03-04 06:58 106阅读 0赞

### 目录 ###

*  1.原问题
 *  2.对偶问题
 *   *  2.1弱对偶性的一般证明
     *  2.2弱对偶性的几何证明
     *  2.3强对偶性的几何表示以及条件
     *  2.4 slater condition
 *  3.KKT条件的证明
 *   *  3.1可行条件
     *  3.2互补松弛条件
     *  3.3偏导为0条件

# 1.原问题 #

首先给出问题的一般形式：  
![在这里插入图片描述][20200802095758206.gif]  
  上式表明我们一共有**M+N**个约束条件，对于不是求最小值或者约束条件大于等于0的情况，我们添加一个负号就可以变成上面这种形式。  
  上述问题我们一般称之为带约束的原问题。

利用**拉格朗日乘子法**，我们构造一个新的函数以及约束条件如下：  
![在这里插入图片描述][20200802100232159.gif_pic_center]  
其中：![在这里插入图片描述][20200802103032941.gif]

我们称上面的问题为无约束的原问题（对x不再有约束）。上述L是拉格朗日乘子法的基本形式，这个就不再证明。

# 2.对偶问题 #

对于无约束的原问题，我们先直接给出它的对偶问题形式（其实就是简单**交换min和max**）：  
![在这里插入图片描述][2020080210063650.gif_pic_center]  
  上述问题我们称之为原问题的对偶问题。

## 2.1弱对偶性的一般证明 ##

所谓弱对偶性，指的是：  
![在这里插入图片描述][2020072719433211.png_pic_center]  
  在[再谈SVM（hard-margin和soft-margin详细推导、KKT条件、核技巧）][SVM_hard-margin_soft-margin_KKT]中，我们大致口头证明了弱对偶性的成立，即“凤尾”>=“鸡头”。何谓“凤尾”？我先选出最强的一批人( max ⁡ f \\max f maxf)，然后组成实验班，实验班倒数第一就是 min ⁡   max ⁡ f \\min \\ \\max f min maxf；何谓“鸡头”？我先选出最弱的一批人( min ⁡ f \\min f minf)，然后在这批比较弱的人当中选出最强的那个人，也即是 max ⁡   min ⁡ f \\max \\ \\min f max minf，那么“鸡头”与“凤尾”孰强孰弱，是显而易见的。  
  现在我们利**用数学推导**来大致证明一下弱对偶性。  
  对于 L ( x , λ , η ) L(x,\\lambda,\\eta) L(x,λ,η)这个函数，我们知道下面这个不等式一定成立：  
![在这里插入图片描述][20200802101812290.gif_pic_center]  
上面这个不等式很好理解，中间 L ( x , λ , η ) L(x,\\lambda,\\eta) L(x,λ,η)我们可以理解为**L的值域**，值域里面的任何一个数，必然是大于等于它的最小值，小于等于它的最大值。其实这一步已经证明出弱对偶性了，不过为了更容易理解，我们可以进一步说明。  
  上述不等式**最左边的表达式最后是关于 λ , η \\lambda,\\eta λ,η的一个函数，而最右边是一个关于 x x x的函数**，因此我们又令：  
![在这里插入图片描述][20200802102216890.gif_pic_center]  
因此我们有：  
![在这里插入图片描述][20200802102552162.gif_pic_center]  
证毕。

## 2.2弱对偶性的几何证明 ##

为了使问题简化，同时方便证明，我们去掉原问题中等式的约束条件，同时不等式约束条件只保留一个，即原问题变成：  
![在这里插入图片描述][20200802103258368.gif_pic_center]  
那么拉格朗日函数就变成：  
![在这里插入图片描述][20200802103441395.gif_pic_center]  
我们又令：  
![在这里插入图片描述][20200802103715349.gif_pic_center]  
即 p ∗ p^\* p∗是原问题的最优解， d ∗ d^\* d∗是对偶问题的最优解。证明弱对偶性实际上就是证明 d ∗ ≤ p ∗ d^\*\\leq p^\* d∗≤p∗。  
  我们令区域G的表达形式为：  
![在这里插入图片描述][20200802104302832.gif_pic_center]

D是**原问题的定义域**，G表示一个个**点的集合**，点的横坐标是约束条件 u = m 1 ( x ) u=m\_\{1\}(x) u=m1(x)，纵坐标是原函数 t = f ( x ) t=f(x) t=f(x)。  
  有了上述集合G的定义之后，我们就可以对 p ∗ , d ∗ p^\*,d^\* p∗,d∗进行变式。  
  首先对 p ∗ p^\* p∗进行变式：  
![在这里插入图片描述][20200802105009810.gif_pic_center]  
因为 t = f ( x ) t=f(x) t=f(x)，所以 p ∗ p^\* p∗实际上就是t的最小值，反映到集合G中去就是指一个点的纵坐标，这个点要满足两个条件：一是肯定要在G中，二是 m 1 ( x ) ≤ 0 m\_\{1\}(x)\\leq0 m1(x)≤0也就是该点的横坐标小于等于0。  
如下图所示：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0N5cmlsX0tJ_size_16_color_FFFFFF_t_70]  
  我们对 u ≤ 0 u\\leq0 u≤0那部分，也就是图中阴影部分上的每个点，找到一个最低的点，它的纵坐标就是 p ∗ p^\* p∗。  
  接着对 d ∗ d^\* d∗进行变形：  
![在这里插入图片描述][20200802110331509.gif_pic_center]  
上述 t + λ u t+\\lambda u t\+λu的来源为：  
![在这里插入图片描述][20200802103441395.gif_pic_center]  
对变形后 d ∗ d^\* d∗我们令：  
![在这里插入图片描述][20200802110640531.gif_pic_center]  
我们先找到 g ( λ ) g(\\lambda) g(λ)在图中的位置：我们知道 t + λ u t+\\lambda u t\+λu实际上也是一个值，我们不妨令 t + λ u = k t+\\lambda u=k t\+λu=k，该式表示一条斜率为 − λ -\\lambda −λ并过(0,k)的直线，我们要找的是 t + λ u t+\\lambda u t\+λu的最小值，实际上就是k的最小值，实际上就是该直线与纵轴交点的最小值。而在求 min ⁡ x   t + λ u \\min \\limits\_\{x\}\\ t+\\lambda u xmin t\+λu的最小值时， λ \\lambda λ是**固定**的，因此斜率 − λ -\\lambda −λ也是固定的：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0N5cmlsX0tJ_size_16_color_FFFFFF_t_70 1]  
  我们保持**斜率不变**移动直线，不断往上移动，则该直线与纵轴交点的纵坐标k也不断增大，因为限制条件还有一个就是 ( u , t ) ∈ G (u,t)\\in G (u,t)∈G，因此该直线必须经过区域G，我们一直往上移动，**直到直线第一次与G相交**，记下相应的k值为 k 1 k\_\{1\} k1，再继续往上也都满足条件，知道该直线与G不再相交，但是现在我们求得是最小值，那么最小值其实就是 k 1 k\_\{1\} k1，即 g ( λ ) g(\\lambda) g(λ)就等于 k 1 k\_\{1\} k1。  
  进一步，我们要求：  
![在这里插入图片描述][20200802111915960.gif_pic_center]  
这里要重点注意：**上一步我们求得了 g ( λ ) g(\\lambda) g(λ)就等于 k 1 k\_\{1\} k1，但是这种情况只是一种情况，在上一步求 g ( λ ) g(\\lambda) g(λ)时，我们假若改变斜率 − λ -\\lambda −λ，那么 k 1 k\_\{1\} k1的值是会变的**，如下所示：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0N5cmlsX0tJ_size_16_color_FFFFFF_t_70 2]  
  我们换一个 λ \\lambda λ固定时， g ( λ ) g(\\lambda) g(λ)也就是 k 1 k\_\{1\} k1自然也就在变。  
  第二步要干的其实就是让我们**求这个 g ( λ ) g(\\lambda) g(λ)的最大值**。那什么时候是最大的？实际上就是以G的最低点为轴，我们旋转直线，直到与左上方最低点相交时， g ( λ ) g(\\lambda) g(λ)是最大的。如下所示：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0N5cmlsX0tJ_size_16_color_FFFFFF_t_70 3]

可能很多人就有疑问了：我为什么不可以让斜率继续增大？让直线穿过G？这里有疑问的同学不妨回忆一下第一个步骤：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0N5cmlsX0tJ_size_16_color_FFFFFF_t_70 2]  
我们在确定 g ( λ ) g(\\lambda) g(λ)的时候，**第一次相切我们就停止了**，而后改变斜率继续相切：如上图所示，**假如你继续增大斜率，那么该直线就不跟G的最低点相切了**。我们是先推第一步再推第二步，而推第二步的时候肯定必须满足第一步的条件，所以 d ∗ d^\* d∗只能是在那个位置。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0N5cmlsX0tJ_size_16_color_FFFFFF_t_70 4]  
  从上图也可以看出来： d ∗ ≤ p ∗ d^\*\\leq p^\* d∗≤p∗，也就是对偶问题的解是小于等于原问题的解的，也即是说**满足弱对偶性**。因此这里我们进一步证明了弱对偶性。

## 2.3强对偶性的几何表示以及条件 ##

什么是强对偶性？就是指**原问题的解与对偶问题的解是相同的**，也即是： d ∗ = p ∗ d^\*=p^\* d∗=p∗。  
  画个图：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0N5cmlsX0tJ_size_16_color_FFFFFF_t_70 5]  
  假设G是一个**凸集**，那么根据上面找 d ∗ d^\* d∗和 p ∗ p^\* p∗的思路，我们很容易知道这个时候二者是**相等**的，也就是满足强对偶关系。  
  那上面这句话的意思就是说：只要是凸集就一定满足强对偶关系。这句话不是正确的，不是所有的凸集都满足强对偶关系，但是加上slater条件就一定满足。

## 2.4 slater condition ##

先直接给出slater条件的定义：对于x的定义域D，如果它存在一个**内点**（不是边界上的点） x ∗ x^\* x∗满足对任意的 m i ( x ) < 0 , i = 1 , 2 , . . . , M m\_\{i\}(x)\\lt0,i=1,2,...,M mi(x)<0,i=1,2,...,M，则说明该问题满足slater条件。  
  对slater条件做两点说明：

1.  **对于大多数的凸优化问题来说，slater condition都是成立的**
2.  **放松**的slater条件：如果约束函数 m i ( x ) , i = 1 , 2 , . . . , M m\_\{i\}(x),i=1,2,...,M mi(x),i=1,2,...,M中有K个是**仿射函数**，则我们只需要那M-K个约束函数满足第一个条件，我们也说该问题满足slater条件。
3.  什么是仿射函数？仿射函数，即最高次数为1的多项式函数。常数项为零的仿射函数称为线性函数。简单来说，就是**比较简单**的函数。

对第一个条件进一步说明：为什么我们要满足这个条件？第一个条件放在G中的意思就是：**G在u<0部分必须有点存在**：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0N5cmlsX0tJ_size_16_color_FFFFFF_t_70 2]  
**假设纵坐标左边没有点，那么在我们寻找 g ( λ ) g(\\lambda) g(λ)时，那条直线实际上就会是纵坐标轴。**

# 3.KKT条件的证明 #

通过上面的推导我们知道了：  
![在这里插入图片描述][20200802121852958.gif_pic_center]  
满足强对偶关系之后我们就得到一个结论： d ∗ = p ∗ d^\*=p^\* d∗=p∗，但是也到此为止了，我们肯定得解出那些未知最优参数（**带 \* 的变量**），KKT条件就是干这件事。  
  KKT条件有三部分：**可行条件、互补松弛条件以及偏导为0条件**，我们一个一个推导。

## 3.1可行条件 ##

所谓可行条件，指的是一开始就满足的一些条件：  
![在这里插入图片描述][20200802123952721.gif_pic_center]

这三个条件肯定得满足，这个没啥可说的，**天然满足**。

## 3.2互补松弛条件 ##

我们知道：  
![在这里插入图片描述][20200802122847382.gif_pic_center]  
带星号的都是最优解的意思。根据可行条件我们知道： λ i ≥ 0 , m i ≤ 0 \\lambda\_\{i\}\\geq0,m\_\{i\}\\leq0 λi≥0,mi≤0，所以 λ i m i ≤ 0 \\lambda\_\{i\}m\_\{i\}\\leq0 λimi≤0，所以上面继续变换：  
![在这里插入图片描述][20200802123205252.gif_pic_center]  
**因为最后一步等于第一步，所以中间推导步骤中的 ≤ \\leq ≤都应该变成=**，倒数第三步等于倒数第二步，所以我们有：  
![在这里插入图片描述][20200802123456513.gif_pic_center]  
而前面我们又知道 λ i m i ≤ 0 \\lambda\_\{i\}m\_\{i\}\\leq0 λimi≤0，所以互补松弛条件如下：  
![在这里插入图片描述][20200802123701644.gif_pic_center]

## 3.3偏导为0条件 ##

![在这里插入图片描述][20200802123205252.gif_pic_center]  
继续看这个推导，第二、三步之间应该用等号连接，即：  
![在这里插入图片描述][20200802124311743.gif_pic_center]  
意思就是说L在 x = x ∗ x=x^\* x=x∗处有最小值，于是偏导为0条件就出来了：  
![在这里插入图片描述][20200802124515853.gif_pic_center]  
于是KKT条件为：  
![在这里插入图片描述][20200802124910141.gif_pic_center]  
证毕。

[20200802095758206.gif]: /images/20230208/2c844e76083f447598950af9b430e28b.png
[20200802100232159.gif_pic_center]: /images/20230208/20504dbe56c4452aa07f538e03169d91.png
[20200802103032941.gif]: /images/20230208/232d704c02274e33b56f0e81501882c7.png
[2020080210063650.gif_pic_center]: /images/20230208/a75ddc552ad64d12bb155951d3cf6254.png
[2020072719433211.png_pic_center]: /images/20230208/6d71acc0c3cc4b0987e5791dd322ee5b.png
[SVM_hard-margin_soft-margin_KKT]: https://blog.csdn.net/Cyril_KI/article/details/107601621
[20200802101812290.gif_pic_center]: /images/20230208/56d6a833329f4587b338d4c6cfb07e32.png
[20200802102216890.gif_pic_center]: /images/20230208/d78978a2dbdc443eb4dfb878fb330576.png
[20200802102552162.gif_pic_center]: /images/20230208/e438cda24b2f4af7ac169d65eb14c710.png
[20200802103258368.gif_pic_center]: /images/20230208/6b3e1ecd47c6428da92da4bf383187ad.png
[20200802103441395.gif_pic_center]: /images/20230208/15d9fac219d54983a77aa7ea8152b417.png
[20200802103715349.gif_pic_center]: /images/20230208/58d37dd97ce74750be56b1ea6709b927.png
[20200802104302832.gif_pic_center]: /images/20230208/23a259bdb9f54f2e983020e8e80ba1ff.png
[20200802105009810.gif_pic_center]: /images/20230208/ac3f67c0a14e4a75a8572f4fb535aa23.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0N5cmlsX0tJ_size_16_color_FFFFFF_t_70]: /images/20230208/e1546afb2e1b46ae82fdfc88665edbeb.png
[20200802110331509.gif_pic_center]: /images/20230208/5a162ae277d1405e93f6a168448545eb.png
[20200802110640531.gif_pic_center]: /images/20230208/7c1f75a7e1044b6e8a432ae72a4fc92e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0N5cmlsX0tJ_size_16_color_FFFFFF_t_70 1]: /images/20230208/fa2a62013af14b3fbc242b2cb6d2f8b4.png
[20200802111915960.gif_pic_center]: /images/20230208/1ca6d59d066f4d65a92b9da9c69e2a02.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0N5cmlsX0tJ_size_16_color_FFFFFF_t_70 2]: /images/20230208/bfadd94a4eeb43ea8a49c24dd2776d4c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0N5cmlsX0tJ_size_16_color_FFFFFF_t_70 3]: /images/20230208/0a82003fec3545c9943d6339160621d5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0N5cmlsX0tJ_size_16_color_FFFFFF_t_70 4]: /images/20230208/f8b2c1cb6852458988e77345a6e3b8e3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0N5cmlsX0tJ_size_16_color_FFFFFF_t_70 5]: /images/20230208/dc08ee589d6a41aa8273d7b202c77ba9.png
[20200802121852958.gif_pic_center]: /images/20230208/acb151ef149d4651a2db20e560484184.png
[20200802123952721.gif_pic_center]: /images/20230208/4f0e8f9561564230a5f8122a0e52a866.png
[20200802122847382.gif_pic_center]: /images/20230208/9b85f72f998a4a0c96ef99dcb6310f53.png
[20200802123205252.gif_pic_center]: /images/20230208/0bd41984cacd4d1ca680de5a28f776e8.png
[20200802123456513.gif_pic_center]: /images/20230208/6d2fd9539eb844c3867aabe84cf3b7ac.png
[20200802123701644.gif_pic_center]: /images/20230208/750467a355c949a08d17488f3d0953b7.png
[20200802124311743.gif_pic_center]: /images/20230208/b5fc7c1ed3f048fc802ca60e42544582.png
[20200802124515853.gif_pic_center]: /images/20230208/8739e3f59d964e45a097cf78877f5a53.png
[20200802124910141.gif_pic_center]: /images/20230208/77d0528802be4ce788020ebfa72f2088.png