支持向量机预备知识（一）kkt条件、凸函数

以你之姓@ 2023-06-12 08:38 1阅读 0赞

一、凸函数  
什么是凸函数。  
关于凸函数的定义：  
对于任意 λ ∈ \[ 0 , 1 \] \\lambda∈\[0,1\] λ∈\[0,1\],如果  
 f ( λ x + ( 1 − λ ) y ) < λ f ( x ) + ( 1 − λ ) f ( y ) f(\\lambda x+(1-\\lambda)y)<\\lambda f(x)+(1-\\lambda) f(y) f(λx\+(1−λ)y)<λf(x)\+(1−λ)f(y)  
我们则称，这个函数是凸函数。  
什么意思呢，我们在目标函数上取两个点，然后计算出 f ( λ x + ( 1 − λ ) y ) f(\\lambda x+(1-\\lambda)y) f(λx\+(1−λ)y)看点的值和这个值的大小来进行凸函数的比较。  
（2）如果这个处处二阶可导，那么我们可以采用二阶导数来判断  
即设目标函数为f(x),则f（x）是凸函数的必要条件为 f ( 2 ) ( x ) > 0 f^\{(2)\}(x)>0 f(2)(x)>0  
即函数的斜率不断在变大。  
这是凸函数的定义，那么我们用例子来看看：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTYxMTA0NQ_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTYxMTA0NQ_size_16_color_FFFFFF_t_70 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTYxMTA0NQ_size_16_color_FFFFFF_t_70 2]  
所以，我们寻找凸函数一般用凸函数的定义去寻找就行了，或者采用2阶导数的条件寻找。注意一般如果采用定义1去寻找的话，会采用多个点去找寻，避免随机性导致的判断  
1.2 凸集  
如果在函数的定义范围内，满足对于任意 λ ∈ \[ 0 , 1 \] \\lambda∈\[0,1\] λ∈\[0,1\]  
 f ( λ x + ( 1 − λ ) y ) < λ f ( x ) + ( 1 − λ ) f ( y ) f(\\lambda x+(1-\\lambda)y)<\\lambda f(x)+(1-\\lambda) f(y) f(λx\+(1−λ)y)<λf(x)\+(1−λ)f(y)的解的集合就被称为凸集。  
如上面 f ( x ) = x 3 f(x)=x^\{3\} f(x)=x3的 （ 0 ， + ∞ ） （0，+∞） （0，\+∞）为凸集， ( − ∞ ， 0 ) (-∞，0) (−∞，0)就不是。  
1.3 如何对多元函数进行凸函数的判断  
方法一：  
采用定义法，采用蒙特卡洛采样了很多很多次，每次都计算一次中间值和两边值分别进行比较，如果其中有个别点满足凸函数定义，那么这个函数就是凸函数。  
方法2：  
采用二阶偏导，看二阶偏导是否大于0。

对于非凸函数来说，我们可能不好求得函数的最小值，或者无约束条件下并不满足函数的最小值。

二、kkt条件  
kkt条件是用来解决不等值约束条件下，求解极值的最优解的问题。为了理解不等值约束我们先从最基本的求极值的思路开始。  
首先从无约束的优化问题讲起，一般就是要使一个表达式取到最小值：  
 m i n x f ( x ) \\mathop\{min\}\\limits\_\{x\}f(x) xminf(x)。对于这类问题在高中就学过怎么做。只要对它的每一个变量求导，然后让偏导为零，解方程组就行了。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTYxMTA0NQ_size_16_color_FFFFFF_t_70 3]  
所以在极值点处一定满足  d f ( x ) / d x = 0 df(x)/dx=0 df(x)/dx=0 （只是必要条件，比如  y = x 3 y=x^3 y=x3 在 x=0 处就不是极值点），然后对它进行求解，再代入验证是否真的是极值点就行了。  
1、等值优化问题最优性条件  
比如有一个等式约束：

min f(x)
    s.t h(x)=0

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTYxMTA0NQ_size_16_color_FFFFFF_t_70 4]  
这时相当于我们的f(x)的负梯度方向为图中的中心，由中心向外为函数的等高线，当等高线和h（x）想切时刚好为约束条件下的极值点。但是要注意f(x)与g（x）的约束条件必须是凸函数和凸集才行，否则我们求出来的点也不一定是最小值点。  
例  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTYxMTA0NQ_size_16_color_FFFFFF_t_70 5]  
因为f(x)不是凸函数，且所以求出来的值不是最优解，且在约束条件g(x)所在的范围内也不是凸集。因为  
当 x ∈ （ − ∞ ， + ∞ ） x∈（-∞，+∞） x∈（−∞，\+∞）时， y ∈ ( − ∞ ， 0 ) y∈(-∞，0) y∈(−∞，0),而所以只要y不断减小，x不断变大，此时目标函数只有最大值，没有最小值。  
如果f(x)是凸函数，h(x)=0所在的集合又是凸集。那么我们只需要对多个约束条件，分别求偏导，对求出来的多个极值点带入目标函数进行检验，最后选出一个极小值解就行了。  
即：  
![在这里插入图片描述][20191106112343715.png]  
2、不等式约束优化问题  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTYxMTA0NQ_size_16_color_FFFFFF_t_70 6]  
![在这里插入图片描述][20191106112608103.png]  
此时g(x)<0。  
（2）边界解：当解集在边界时，此时λ>0。且g(x)=0。  
但不管解集是否在边界，一定满足一下条件：  
![在这里插入图片描述][20191106112933893.png]  
这些条件合称为Karush-Kuhn-Tucker (KKT)条件。但是我们在运用kkt条件时一般会有一些约束条件。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTYxMTA0NQ_size_16_color_FFFFFF_t_70 7]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTYxMTA0NQ_size_16_color_FFFFFF_t_70 8]  
当然kkt条件的使用必须有一定的限制，即regularity条件。

2、regularity条件。  
（1）如果h（x）与g(x)都是形如 a x + b ax+b ax\+b这样的映射函数，则kkt条件的值一定是最小值  
（2）起作用的g(x)和h（x)的在极值处的梯度要线性无关  
（3）优化问题是凸优化问题  
3、 缺少regularity条件KKT还是最优解的必要条件吗？  
若满足regularity条件，KKT就是最优解的必要条件。所谓必要条件的意思是满足KKT条件的不一定是最优解（例如鞍点就满足KKT，但鞍点就不是最优解），但是如果不满足KKT条件就一定不是最优解，缺少了regularity条件，KKT条件就并非最优解的必要条件。  
那么我们怎么判断，这个目标函数的优化是否是符合regularity条件的呢。我们可以采用fritz条件来判断  
3、fritz条件  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTYxMTA0NQ_size_16_color_FFFFFF_t_70 9]  
即我们要求利用kkt条件求出来的解为最小解，那么在目标函数前的 μ 0 \\mu\_0 μ0一定是大于0的。此时  
若满足fritz条件，那么求出的解为最优解。若 μ 0 \\mu\_0 μ0=0代表此时目标函数不受约束，即无最小值。  
4、例子  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTYxMTA0NQ_size_16_color_FFFFFF_t_70 10]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTYxMTA0NQ_size_16_color_FFFFFF_t_70]: /images/20230531/a9cb150716de49f5afceb4a8bc254609.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTYxMTA0NQ_size_16_color_FFFFFF_t_70 1]: /images/20230531/a67c5e849ea04f6a9da66ac61cee8c26.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTYxMTA0NQ_size_16_color_FFFFFF_t_70 2]: /images/20230531/992938dec6fe4494bffeda866ccbc72b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTYxMTA0NQ_size_16_color_FFFFFF_t_70 3]: /images/20230531/136f7fa834014976ab9160c0aadd26cd.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTYxMTA0NQ_size_16_color_FFFFFF_t_70 4]: /images/20230531/4fed06c589cf4410b9469a9c8c3d2a51.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTYxMTA0NQ_size_16_color_FFFFFF_t_70 5]: /images/20230531/9bea8b122098418eaaed2d0b2def2b4e.png
[20191106112343715.png]: /images/20230531/844cf2b6d2d14c3fbe044950665e1142.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTYxMTA0NQ_size_16_color_FFFFFF_t_70 6]: /images/20230531/0ec3e65c5e404227b69e865e02c5629c.png
[20191106112608103.png]: /images/20230531/4701e1d027134e9daa569474a8909af7.png
[20191106112933893.png]: /images/20230531/5655537ffdf74294a257ecbf0ef04f42.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTYxMTA0NQ_size_16_color_FFFFFF_t_70 7]: /images/20230531/f211eea283d04db3812cd01dcd2760af.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTYxMTA0NQ_size_16_color_FFFFFF_t_70 8]: /images/20230531/82360bbbafad4ed4aa040d44fd19c276.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTYxMTA0NQ_size_16_color_FFFFFF_t_70 9]: /images/20230531/9f798289555f478e918b471eea5dbbcb.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTYxMTA0NQ_size_16_color_FFFFFF_t_70 10]: /images/20230531/6293672507154631bb41c8b9548223e5.png