手推支持向量机07-约束优化问题-对偶关系之slater condition的解释

女爷i 2022-11-25 13:28 173阅读 0赞

**目录**

1.写在前面

2.slater条件是什么？

3.slater条件在几何上

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

# 1.写在前面 #

我们接着看一下凸优化问题，或者说强对偶关系，上一篇文章我们介绍了几何意义，对偶关系在几何表达上的样子。**对于任意一个凸优化问题，并不能直接说满足强对偶关系，但是弱对偶关系肯定是可以满足的。我们说凸优化+一定的限制条件可以推出强对偶关系。其中slater条件就是其中一个，但是这个属于充分非必要条件，一个满足强对偶关系的函数不一定是满足slater条件的**。

# 2.slater条件是什么？ #

slater条件非常简单，我们可以先看定义：![\\exists \\hat\{x\}\\varepsilon relintD,s.t. \\forall i=1,...,M,m\_\{i\}\\left ( \\hat\{x\} \\right )< 0][exists _hat_x_varepsilon relintD_s.t. _forall i_1_..._M_m_i_left _ _hat_x_ _right _ 0]，换句话说，relint是相对内部的概念，relative interior。如果D有边界，相对内部就是指把边界去掉的内部，如果没有边界，那相对内部就是其本身。另外我们还需要着重说下面几点：

1.  对于大多数凸优化问题，通常情况下slater是成立的，当然我们也可以构造一个凸优化不满足slater条件。
2.  放松slater条件，如果M个不等式约束中，如果有一部分满足![m\_\{i\}\\left ( \\hat\{x\} \\right )< 0][m_i_left _ _hat_x_ _right _ 0]，![m\_\{i\}\\left ( \\hat\{x\} \\right )][m_i_left _ _hat_x_ _right]是仿射函数，仿射函数是简单函数，就是一节多项式函数，和线性函数有关系。也就是如果M中K个仿射函数，则这K个仿射函数不必校验，直接校验剩下的M-K个函数。

我们为什么讲到上面那一堆呢，因为如果我们的问题是**凸二次规划问题，就是目标函数f是凸优化的，不等式约束![m\_\{i\}\\left ( \\hat\{x\} \\right )][m_i_left _ _hat_x_ _right]是仿射函数。nj本身也是仿射函数，天然满足slater条件**。我们的**SVM问题本质上就是一个凸二次规划问题，也就是说SVM凸优化问题默认强对偶关系一定是成立的**。

# 3.slater条件在几何上 #

slater条件在几何上是什么意思呢？至少存在一个点，使得约束条件小于0。假设只有一个约束条件m1，也就是说存在一个点，使得m1小于0，m1我们上篇文章指代了u，也就是坐标轴的横轴，表示在G范围内在u<0地方一定存在一个点。这个东西是对G集合进行限制的。**G必须在u<0坐标轴左半边一定要有点存在。从而限定了绿色的那条切线不能是垂直的，这就是slater条件在几何层面表达的含义**。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1N1eWViaXViaXU_size_16_color_FFFFFF_t_70][]

[exists _hat_x_varepsilon relintD_s.t. _forall i_1_..._M_m_i_left _ _hat_x_ _right _ 0]: https://private.codecogs.com/gif.latex?%5Cexists%20%5Chat%7Bx%7D%5Cvarepsilon%20relintD%2Cs.t.%20%5Cforall%20i%3D1%2C...%2CM%2Cm_%7Bi%7D%5Cleft%20%28%20%5Chat%7Bx%7D%20%5Cright%20%29%3C%200
[m_i_left _ _hat_x_ _right _ 0]: https://private.codecogs.com/gif.latex?m_%7Bi%7D%5Cleft%20%28%20%5Chat%7Bx%7D%20%5Cright%20%29%3C%200
[m_i_left _ _hat_x_ _right]: https://private.codecogs.com/gif.latex?m_%7Bi%7D%5Cleft%20%28%20%5Chat%7Bx%7D%20%5Cright%20%29
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1N1eWViaXViaXU_size_16_color_FFFFFF_t_70]: /images/20221124/a18218ba9c1d42728e441d5f129e66f3.png