等式约束优化与不等式约束优化

爱被打了一巴掌 2022-03-27 06:48 352阅读 0赞

在学习SVM的原理时，接触到了等式约束优化与不等式约束优化，下面是根据相关资料自己总结出来的自己的，希望对大家有所帮助，这是第一篇博客。

1.等式约束优化

1.1.问题描述

当目标函数加上等式约束条件之后，原本的非约束优化变成了等式约束优化，如下：

![\\min\_\{x\} f(x)][min_x_ f_x]  .....................................................................................(1)

![s.t. \\ \\ \\ h(x)=0][s.t. _ _ _ h_x_0]  ............................................................................(2)

因为存在约束条件，所以将![f(x)][f_x]的解限定在了一个可行域的区域，此时可能找不到可以使得![\\nabla\_xf(x)][nabla_xf_x]为0的点，但是我们的目的是找到可行域范围内![f(x)][f_x]的最小值即可。

1.2.解法

利用拉格朗日乘子法，引入拉格朗日算子 ![\\alpha \\in R^m][alpha _in R_m] ,构建拉格朗日函数如下：

![L(x,\\alpha)=f(x)+\\alpha\*h(x)][L_x_alpha_f_x_alpha_h_x] ..........................................................(3)

然后对拉格朗日函数![L(x,\\alpha)][L_x_alpha]求![x][]的偏导，令偏导为0，即：

![\\nabla\_xL(x,\\alpha)=0][nabla_xL_x_alpha_0] ..............................................................................(4)

对（2）（4）式进行求解即得到此类问题的最优解。

1.3.解释

假设我们的目标函数为二维的，即![f(x,y)][f_x_y]，在平面中画出![f(x,y)][f_x_y]的等高线，如下图的虚线所示

*  ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpZGljaGVuZ2ZvMDQxMg_size_16_color_FFFFFF_t_70][]

显而易见，只有当等高线与目标函数的曲线相切时才有可能得到可行解。因此拉格朗日取得极值的必要条件是目标函数与约束函数相切，这时两者的法向量是平行的，即

![\\nabla\_xf(x)-\\alpha\\nabla\_xh(x)=0][nabla_xf_x_-_alpha_nabla_xh_x_0] ................................................................(5)

所以正好可以得到（3）式，需要注意的是，![\\alpha][alpha]仅仅要求不等于0即可，正负号不需要确定。

2.不等式约束优化

2.1.问题描述

不等式约束优化问题为：

![\\min\_\{x\} f(x)][min_x_ f_x] ...........................................................................................(6)

![s.t. \\ \\ \\ g(x)\\leq0][s.t. _ _ _ g_x_leq0] ..................................................................................(7)

2.2.解法

首先构建拉格朗日函数如下：

![L(x,\\alpha)=f(x)+\\beta \*h(x)][L_x_alpha_f_x_beta _h_x] ...............................................................(8)

对(8)式关于![x][]求偏导，可得

![\\nabla\_xL(x,\\beta)=0][nabla_xL_x_beta_0] ...................................................................................(9)

另外还有KKT条件如下：

![\\beta=0 \\ and \\ h(x)> 0][beta_0 _ and _ h_x_ 0]  或者 ![\\beta> 0 \\ and \\ h(x)=0][beta_ 0 _ and _ h_x_0] .....................(10)

由（9）（10）两式可以得出最后的最优解。对于（10）式的解释请看2.3节。

2.3.解释

假设我们的目标函数为二维的，下图给出了目标函数的等高线与不等式约束：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpZGljaGVuZ2ZvMDQxMg_size_16_color_FFFFFF_t_70 1][]

根据上图可知，可行解存在于![g(x)< 0][g_x_ 0]或者![g(x)=0][g_x_0]的区域里取到，存在下列两种情况：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpZGljaGVuZ2ZvMDQxMg_size_16_color_FFFFFF_t_70 2][]

a)当可行解![x][]落在![g(x)< 0][g_x_ 0]的区域内，此时约束条件不起作用，直接极小化![f(x)][f_x]即可，所以（1）式![L(x,\\alpha)=f(x)+\\beta \*h(x)][L_x_alpha_f_x_beta _h_x]中，只需满足![\\beta=0][beta_0]即可。即上图左侧所示.

b)当可行解![x][]落在![g(x)= 0][g_x_ 0 1]的区域内，此时等价于等式约束优化问题。即上图右侧所示。此时目标函数的梯度方向为指向中心位置的反方向，而约束函数![h(x)][h_x]由约束区域指向非约束区域。由下图可以看出，在最优解的位置，约束函数的梯度方向于目标函数的梯度方向正好相反，从而有：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpZGljaGVuZ2ZvMDQxMg_size_16_color_FFFFFF_t_70 3][]

![\-\\nabla\_xf(x)=\\beta\*\\nabla\_xg(x)][-_nabla_xf_x_beta_nabla_xg_x] ..................................................(11)

（11）式其实就是（9）式的变形。当然（11）式有一个限制条件 ![\\beta> 0][beta_ 0]。

[min_x_ f_x]: https://private.codecogs.com/gif.latex?%5Cmin_%7Bx%7D%20f%28x%29
[s.t. _ _ _ h_x_0]: https://private.codecogs.com/gif.latex?s.t.%20%5C%20%5C%20%5C%20h%28x%29%3D0
[f_x]: https://private.codecogs.com/gif.latex?f%28x%29
[nabla_xf_x]: https://private.codecogs.com/gif.latex?%5Cnabla_xf%28x%29
[alpha _in R_m]: https://private.codecogs.com/gif.latex?%5Calpha%20%5Cin%20R%5Em
[L_x_alpha_f_x_alpha_h_x]: https://private.codecogs.com/gif.latex?L%28x%2C%5Calpha%29%3Df%28x%29&plus;%5Calpha*h%28x%29
[L_x_alpha]: https://private.codecogs.com/gif.latex?L%28x%2C%5Calpha%29
[x]: https://private.codecogs.com/gif.latex?x
[nabla_xL_x_alpha_0]: https://private.codecogs.com/gif.latex?%5Cnabla_xL%28x%2C%5Calpha%29%3D0
[f_x_y]: https://private.codecogs.com/gif.latex?f%28x%2Cy%29
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpZGljaGVuZ2ZvMDQxMg_size_16_color_FFFFFF_t_70]: /images/20220327/cb65512f1e7b423e9dab1bd123097117.png
[nabla_xf_x_-_alpha_nabla_xh_x_0]: https://private.codecogs.com/gif.latex?%5Cnabla_xf%28x%29-%5Calpha%5Cnabla_xh%28x%29%3D0
[alpha]: https://private.codecogs.com/gif.latex?%5Calpha
[s.t. _ _ _ g_x_leq0]: https://private.codecogs.com/gif.latex?s.t.%20%5C%20%5C%20%5C%20g%28x%29%5Cleq0
[L_x_alpha_f_x_beta _h_x]: https://private.codecogs.com/gif.latex?L%28x%2C%5Calpha%29%3Df%28x%29&plus;%5Cbeta%20*h%28x%29
[nabla_xL_x_beta_0]: https://private.codecogs.com/gif.latex?%5Cnabla_xL%28x%2C%5Cbeta%29%3D0
[beta_0 _ and _ h_x_ 0]: https://private.codecogs.com/gif.latex?%5Cbeta%3D0%20%5C%20and%20%5C%20h%28x%29%3E%200
[beta_ 0 _ and _ h_x_0]: https://private.codecogs.com/gif.latex?%5Cbeta%3E%200%20%5C%20and%20%5C%20h%28x%29%3D0
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpZGljaGVuZ2ZvMDQxMg_size_16_color_FFFFFF_t_70 1]: /images/20220327/aca68961c2594609a8ee7ae077c89cba.png
[g_x_ 0]: https://private.codecogs.com/gif.latex?g%28x%29%3C%200
[g_x_0]: https://private.codecogs.com/gif.latex?g%28x%29%3D0
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpZGljaGVuZ2ZvMDQxMg_size_16_color_FFFFFF_t_70 2]: /images/20220327/1f7cb7d43ca2428db84ed198edb2437c.png
[beta_0]: https://private.codecogs.com/gif.latex?%5Cbeta%3D0
[g_x_ 0 1]: https://private.codecogs.com/gif.latex?g%28x%29%3D%200
[h_x]: https://private.codecogs.com/gif.latex?h%28x%29
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpZGljaGVuZ2ZvMDQxMg_size_16_color_FFFFFF_t_70 3]: /images/20220327/2b4202b9270746d38e7137dcce93481f.png
[-_nabla_xf_x_beta_nabla_xg_x]: https://private.codecogs.com/gif.latex?-%5Cnabla_xf%28x%29%3D%5Cbeta*%5Cnabla_xg%28x%29
[beta_ 0]: https://private.codecogs.com/gif.latex?%5Cbeta%3E%200