手推支持向量机06-约束优化问题-对偶关系的几何解释

电玩女神 2023-03-04 08:21 0阅读 0赞

**目录**

1.写在前面

2.模型假设和定义

3.p\*和d\*的集合表示

4.p\*的几何表示

5.g(λ)和d\*的几何表示

6.总结

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

# 1.写在前面 #

上一小结我们证明了弱对偶关系，这篇博客我们从几何关系上思考对偶关系。、

# 2.模型假设和定义 #

为了解释方便，我们对原问题进行了部分简化，目标函数依然写成：![\\left\\\{\\begin\{matrix\} \\begin\{matrix\} minf(x)\\\\x\\epsilon \\mathbb\{R\}^\{\\Phi \} \\end\{matrix\} \\\\ s.t. m\_\{1\}(x)\\leqslant 0 \\end\{matrix\}\\right.][left_begin_matrix_ _begin_matrix_ minf_x_x_epsilon _mathbb_R_Phi _ _end_matrix_ _ s.t. m_1_x_leqslant 0 _end_matrix_right.]，定义D为其定义域，并且![D=domf\\bigcap domm\_\{1\}][D_domf_bigcap domm_1]，x∈D。

有了上面简化函数，我们可以直接写他的拉格朗日函数表达形式：L(x,λ)=f(x)+λ![m\_\{1\}(x)][m_1_x]，λ≥0，然后我们假设原问题的最优解用![P^\{\*\}][P]表示，并且![P^\{\*\}=minf(x)][P_minf_x]，对偶最优解我们表示成![d^\{\*\}][d]，![d^\{\*\}=\\underset\{\\lambda\}\{max \}\\underset\{x\}\{min\}L(x,\\lambda)][d_underset_lambda_max _underset_x_min_L_x_lambda]。我们思考怎么把一个优化问题以及他的对偶问题映射到一个图上面（二维坐标系下）。我们假设一个G是一个点的集合，是二维坐标的一个区域，我们令![G=\\begin\{Bmatrix\} \\left ( m\_\{1\}(x),f(x) \\right )\\mid x\\epsilon D \\end\{Bmatrix\}][G_begin_Bmatrix_ _left _ m_1_x_f_x_ _right _mid x_epsilon D _end_Bmatrix]。G我们用下面这幅图区域表示：为了不失普适性，我们用一个非凸函数（一个爱心）代表集合G在坐标系内的分布。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1N1eWViaXViaXU_size_16_color_FFFFFF_t_70][]

# 3.p\*和d\*的集合表示 #

有了上面那个图之后，我们思考P\*,d\*怎么用集合的方式来进行解答，再次简化，我们进行符号替换：

![20200809183904347.png][]

P\*应该怎么表示呢？![P^\{\*\}=minf(x)=mint][P_minf_x_mint]，推出![p^\{\*\}=inf\\left \\\{ t\\mid (u,t)\\epsilon G ,u\\leqslant 0\\right \\\}][p_inf_left _ t_mid _u_t_epsilon G _u_leqslant 0_right]，此处说明，inf表示下确界，可以理解为几何意义上的取”最低点“。

看完了原问题的最优解，我们再看看其对偶问题(dual problem)的解，d\*怎么表示呢？![d^\{\*\}=\\underset\{\\lambda\}\{max \}\\underset\{x\}\{min\}L(x,\\lambda)][d_underset_lambda_max _underset_x_min_L_x_lambda]，推出：

![20200809185033944.png][]

问题就转化为了g(λ)怎么用集合表示出来。g(λ)=min(t+λu)：

![20200809190616712.png][]

# 4.p\*的几何表示 #

我们通过构造一个集合G，然后借助G，表达p\*，d\*。我们只写出这个集合意义还不大，我们想着怎么在图上进行表示出来。我们的主要目的是进行几何表示。G我们假设已经画出来了，在这个假设前提下。p\*和g(λ)应该怎么表达呢？

首先看一下p\*的表示：![p^\{\*\}=inf\\left \\\{ t\\mid (u,t)\\epsilon G ,u\\leqslant 0\\right \\\}][p_inf_left _ t_mid _u_t_epsilon G _u_leqslant 0_right]，inf表示下界。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1N1eWViaXViaXU_size_16_color_FFFFFF_t_70 1][]

# 5.g(λ)和d\*的几何表示 #

![20200809190616712.png][]

u,t取值只能在G上面取到，t+λu=0是一条直线，而且是过原点的一条直线。-λ就是斜率，斜率小于0。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1N1eWViaXViaXU_size_16_color_FFFFFF_t_70 2][]

我们给定一个λ之后，可以得到一条直线，这条直线可以上下平移。往下平移是没有意义的，我们要和G发生关系，往上平移才可能相交。u等于0的时候，t=△，△就是直线与纵坐标相交的点的截距。当假定△1，开始相切。通过平移可以与G相交得到无数多个△，一直到最后相切出去，比如这个时候是△100，也就是说我们通过不停的相切，得到一个集合\{△1，△2，△3，...，△100\}。那么我们的g(λ)已经很明显了就是上面那个集合的下确界，也即是△1。g(λ)=△1，我们可以在图上进行标注，这个时候**我们已经得到了p\*和g(λ)的几何表示**。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1N1eWViaXViaXU_size_16_color_FFFFFF_t_70 3][]

g(λ)毕竟不是我们最后的d\*，通过我们上面推导我们得到：![d^\{\*\}=\\underset\{\\lambda \}\{max\}g\\left ( \\lambda \\right )][d_underset_lambda _max_g_left _ _lambda _right]，λ我们上面也说过是决定了斜率，也就是说我们可以找到一个斜率，当这条线同时经过G中左下角和右下角两个点的时候，g(λ)最大。两个点同时相切时候才能保证g(λ)最大，以为过大或者过小都会提前切到两个点其中一点，也就是直线最晚和G发生接触的下边界。

# 6.总结 #

我们**可以得到g(λ)一定是小于等于p\*的，d\*一定是小于等于p\*的。这个也就是我们所说的弱对偶关系，我们可以想一下什么时候，d\*=p\*，也就是强对偶关系成立呢？假如G是下图中的一个凸函数，p\*就会等于d\*，强对偶关系的证明首先需要证明原问题是一个凸优化问题，另外还需要个月slater条件，通过这两个条件才可以推出强对偶关系d\*=p\*。slater条件也并不是充要条件，有一些凸优化问题，满足相对偶关系，但是却满足slater条件。slater条件是一个充分非必要条件，我们svm问题是一个二次规划问题，是天然满足slater条件的，二次规划问题一定满足强对偶关系。**

![20200809195349578.png][]

[left_begin_matrix_ _begin_matrix_ minf_x_x_epsilon _mathbb_R_Phi _ _end_matrix_ _ s.t. m_1_x_leqslant 0 _end_matrix_right.]: https://private.codecogs.com/gif.latex?%5Cleft%5C%7B%5Cbegin%7Bmatrix%7D%20%5Cbegin%7Bmatrix%7D%20minf%28x%29%5C%5Cx%5Cepsilon%20%5Cmathbb%7BR%7D%5E%7B%5CPhi%20%7D%20%5Cend%7Bmatrix%7D%20%5C%5C%20s.t.%20m_%7B1%7D%28x%29%5Cleqslant%200%20%5Cend%7Bmatrix%7D%5Cright.
[D_domf_bigcap domm_1]: https://private.codecogs.com/gif.latex?D%3Ddomf%5Cbigcap%20domm_%7B1%7D
[m_1_x]: https://private.codecogs.com/gif.latex?m_%7B1%7D%28x%29
[P]: https://private.codecogs.com/gif.latex?P%5E%7B*%7D
[P_minf_x]: https://private.codecogs.com/gif.latex?P%5E%7B*%7D%3Dminf%28x%29
[d]: https://private.codecogs.com/gif.latex?d%5E%7B*%7D
[d_underset_lambda_max _underset_x_min_L_x_lambda]: https://private.codecogs.com/gif.latex?d%5E%7B*%7D%3D%5Cunderset%7B%5Clambda%7D%7Bmax%20%7D%5Cunderset%7Bx%7D%7Bmin%7DL%28x%2C%5Clambda%29
[G_begin_Bmatrix_ _left _ m_1_x_f_x_ _right _mid x_epsilon D _end_Bmatrix]: https://private.codecogs.com/gif.latex?G%3D%5Cbegin%7BBmatrix%7D%20%5Cleft%20%28%20m_%7B1%7D%28x%29%2Cf%28x%29%20%5Cright%20%29%5Cmid%20x%5Cepsilon%20D%20%5Cend%7BBmatrix%7D
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1N1eWViaXViaXU_size_16_color_FFFFFF_t_70]: /images/20230208/546ce9e3e8de469d83682778ebbf6ba6.png
[20200809183904347.png]: /images/20230208/3e523a9721494c12ac7539c3617aafce.png
[P_minf_x_mint]: https://private.codecogs.com/gif.latex?P%5E%7B*%7D%3Dminf%28x%29%3Dmint
[p_inf_left _ t_mid _u_t_epsilon G _u_leqslant 0_right]: https://private.codecogs.com/gif.latex?p%5E%7B*%7D%3Dinf%5Cleft%20%5C%7B%20t%5Cmid%20%28u%2Ct%29%5Cepsilon%20G%20%2Cu%5Cleqslant%200%5Cright%20%5C%7D
[20200809185033944.png]: /images/20230208/7b6faca4ebae4d00ba07408e7e1f0907.png
[20200809190616712.png]: /images/20230208/981adc1b85df4626aba6a5018cc0a758.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1N1eWViaXViaXU_size_16_color_FFFFFF_t_70 1]: /images/20230208/6a50a30a76b54c40b2b787d93a232b82.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1N1eWViaXViaXU_size_16_color_FFFFFF_t_70 2]: /images/20230208/3a5e97d2b7784af2a0ff8a3199e76162.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1N1eWViaXViaXU_size_16_color_FFFFFF_t_70 3]: /images/20230208/e25a55070f99400d8a04f97d8eb3eed7.png
[d_underset_lambda _max_g_left _ _lambda _right]: https://private.codecogs.com/gif.latex?d%5E%7B*%7D%3D%5Cunderset%7B%5Clambda%20%7D%7Bmax%7Dg%5Cleft%20%28%20%5Clambda%20%5Cright%20%29
[20200809195349578.png]: /images/20230208/ff7338ef5c574926994203226b7b34a6.png