当前位置：首页 > news >正文

python学智能算法（三十一）|SVM-Slater条件理解

news 2025/8/4 5:35:02

【1】引言

前序学习进程中，对KKT条件进行了翻来覆去担仍然不够深入的理解，文章链接包括且不限于：KKT条件引入、KKT条件理解、KKT条件数学表达溯源等。
实际上，为保障KKT条件的应用是准确的，还需要问题满足Slater条件。
Slater条件是凸优化问题中，判断KKT条件是否为最优解的充要条件，它主要用于保证凸优化问题的强对偶性成立。

【2】对偶函数

既然上述提及了强对偶性成立，也就是可能涉及对偶函数和对偶问题，这就先来学习相关概念。
对偶函数的目的是找出原目标函数在可行域上的“下界函数”。

【2.1】原问题的标准形式

这批给出原问题的标准形式，适用于一般约束的优化问题。
最小化目标函数： $min_{x} f(x)$
约束条件：
不等式约束： $gi(x)≤0(i=1,2,...,m)g_{i}(x)\leq0(i=1,2,...,m)$
等式约束： $h_{j}(x)=0(j=1,1,...,p)$
定义域： $x∈Rnx\in R^{n}$

构造对偶函数，实际上也是构造拉格朗日函数，通过引入拉格朗日乘子，将约束代入目标函数，再在定义域上取最小值。
如果不了解如何构造拉格朗日函数，可以通过拉格朗日乘数法理解和拉格朗日函数构造两篇文章学习。

【2.2】构造拉格朗日函数

如何构造拉格朗日函数，将两种约束代入目标函数，有两个步骤：
对不等式约束 $gi(x)≤0g_{i}(x)\leq0$ 引入对偶变量 $λi≥0\lambda_{i}\geq0$ ，这里也要求了非负性，非负性的构成不会改变 $g_{i}$ 在函数中的方向；
对等式约束 $h_{j}(x)=0$ 引入对偶变量 $μj(μj∈R)\mu_{j}(\mu_{j}\in R)$ ，此处的 $μj\mu_{j}$ 没有任何符号限制。
需要强调的是，取值范围上， $μj∈R\mu_{j}\in R$ 而不是 $μj∈Rn\mu_{j} \in R^{n}$ 。
$R^{n}$ 原问题的定义域，而 $μj\mu_{j}$ 是 $h_{j}$ 的乘数因子， $μj\mu_{j}$ 是量化等式约束条件对于原问题最优解的“影响程度”。原问题有m个等式约束，就会有m个 $μ\mu$ 来担任影响因子，每个 $μ\mu$ 都是标量，它们在实数域 $R$ 上取值已经完全足够。
所以从本质上来说， $x$ 和 $μ\mu$ 是完全不同的定义域，所以它们没有必要取值范围统一。

下一步是构造拉格朗日函数：

$L(x,λ,μ)=f(x)+∑i=1mλigi(x)+∑j=1pμjhjL(x,\lambda,\mu)=f(x)+\sum_{i=1}^{m}\lambda_{i}g_{i}(x)+\sum_{j=1}^{p}\mu_{j}h_{j}$
对偶函数 $d(λ,μ)d(\lambda,\mu)$ 定义为拉格朗日函数对原变量x的下确界：
$d(λ,μ)=infx∈RL(x,λ,μ)=f(x)+∑i=1mλigi(x)+∑j=1pμjhj(x)d(\lambda,\mu)=inf_{x\in R}L(x,\lambda,\mu)=f(x)+\sum_{i=1}^{m}\lambda_{i}g_{i}(x)+\sum_{j=1}^{p}\mu_{j}h_{j}(x)$

这里的下确界有两种解释：
第一种，拉格朗日函数 $L(x,λ,μ)L(x,\lambda,\mu)$ 可以取到最小值，这个最小值就是下确界；
第二种，拉格朗日函数 $L(x,λ,μ)L(x,\lambda,\mu)$ 不可以取到最小值，但有一个无线逼近的界限，类似负指数函数 $e^{-x}$ ，随着 $x$ 的逐渐增加，函数无限接近于0而不等于0，0就是负指数函数的下确界。
对偶函数的核心性质：找出原问题最优解的下确界。
假设原问题的最优值为 $p∗=minf(x)∣gi(x)≤0,hj(x)=0p*=min{f(x)|g_{i}(x)\leq0,h_{j}(x)=0}$ ，则对任意可行的对偶变量 $λ>0\lambda>0$ 和 $μ∈R\mu \in R$ 均满足： $d(λ,μ)≤p∗d(\lambda,\mu)\leq p^{*}$
这个理解起来也非常直观，因为 $d(λ,μ)d(\lambda,\mu)$ 是拉格朗日函数的最小值，显然任何实际的取值会比这个最小值要大。但这个解释依然粗糙，详细说明为：

因为 $h_{j}=0$ ，所以必定会有 $μjhj=0\mu _{j}h_{j}=0$ ；
因为 $gi(x)≤0(i=1,2,...,m)g_{i}(x)\leq0(i=1,2,...,m)$ 和 $λi≥0\lambda_{i}\geq0$ ，所以 $∑i=1mλigi(x)≤0\sum_{i=1}^{m}\lambda_{i}g_{i}(x)\leq0$ ；
所以代回拉格朗日函数有：
$L(x,λ,μ)=f(x)+∑i=1mλigi(x)+∑j=1pμjhj=f(x)+∑i=1mλigi(x)≤f(x)L(x,\lambda,\mu)=f(x)+\sum_{i=1}^{m}\lambda_{i}g_{i}(x)+\sum_{j=1}^{p}\mu_{j}h_{j}=f(x)+\sum_{i=1}^{m}\lambda_{i}g_{i}(x)\leq f(x)$ ；

$p^{*}$ 是 $f (x)$ 的一个最佳取值， $d(λ,μ)d(\lambda,\mu)$ 是拉格朗日函数的下确界，所以一定会满足：
$d(λ,μ)≤p∗d(\lambda,\mu)\leq p^{*}$

【3】对偶问题

对偶问题是在对偶变量的可行域上 $(λ≥0,μ∈R)(\lambda \geq 0,\mu \in R)$ 最大化对偶函数。
为何要找这个最大的对偶函数，因为 $d(λ,μ)d(\lambda,\mu)$ 的实际取值上会随 $λ,μ\lambda,\mu$ 的变化而变化，所以对偶问题就是最大化对偶函数问题：
$maxλ,μd(λ,μ)max_{\lambda,\mu} d(\lambda,\mu)$
由于 $μ\mu$ 没有取值限制，所以对偶问题唯一的约束是： $λi≥0(i=1,2,...,m)\lambda_{i}\geq0 (i=1,2,...,m)$
可以将对偶问题的最优值记为 $d∗=max⁡{d(λ,μ)∣λ≥0}d^*=\max \{{d(\lambda,\mu)|\lambda \geq0}\}$

【3.1】强对偶性与弱对偶性

由于对偶函数依然是在拉格朗日函数的下确界中进行取值，所以依然满足：
$d∗≤p∗d^* \leq p^*$
对偶问题的最优值始终小于原问题的最优值。
定义对偶间隙为：
$p^*-d^*$
当 $p^*-d^*>0$ ，对偶间隙大于0，称为弱对偶性；
当 $p^*-d^*=0$ ，对偶间隙等于0，称为强对偶性。此时对偶问题的最优值等于原问题的最优值，求解对偶问题即可等价获得原问题的最优解。
强对偶并非总能成立，但在凸优化问题中，若满足Slater条件，则强对偶性一定成立。
对偶问题是在对偶可行域上最大化对偶函数，目的是找到最紧的下界。

【4】仿射函数

【4.1】仿射函数定义

未进行Slater条件的解读，好需要补充一个仿射函数的小知识。
仿射函数是指具有以下形式的函数：
定义域为 $R^n$ （n维实数空间）、值域为 $R^m$ （m维实数空间）的函数可以记为： $Rn→RmR^n \rightarrow R^m$
如果存在一个线性变换（矩阵） $\in R^{m \times n}$ 和一个常数 $\in R^m$ ，使得对任意的 $\in R^n$ ，都满足： $f (x) = A x + b$
则称 $f (x)$ 维仿射函数。
仿射函数式线性函数+常数项的组合，仿射函数对应的图像可以理解为是线性空间平移后的表现，比如：
$f (x) = a x + b$ 是一条直线，当 $b = 0$ 直线过原点，否则就是过原点直线的平移；
$f(x_{1},x_{2})=a_{1}x_{1}+a_{2}x_{2}+b$ 是三维空间中的一个面，当 $b = 0$ 平面过原点，否则就是过原点平面的平移；线动成面，无数的线组成了面，可以将一个维度理解为一个线性子空间，面就是两个线性子空间的组合；
进入更高维度，仿射函数对应的图像就是线性子空间平移后的综合表现。

【4.2】仿射函数凹凸性

最易于理解的仿射函数就是 $f (x) = a x + b$ ，这是一条直线。
那推广到任意仿射函数，会发现所有仿射函数既满足凸函数的定义，又满足非凸函数的定义。
这里回顾一下凸函数的定义：
首先定义域是凸集，也就是定义域内任意两点的连线一定还在定义域上；
然后还需满足：
$f(λx+(1−λ)y)≤λf(x)+(1−λ)f(y)(0≤λ≤1)f(\lambda x+(1-\lambda)y)\leq \lambda f(x)+(1-\lambda)f(y)(0 \leq \lambda \leq 1)$
非凸函数的定义：
$f(λx+(1−λ)y)≥λf(x)+(1−λ)f(y)(0≤λ≤1)f(\lambda x+(1-\lambda)y)\geq \lambda f(x)+(1-\lambda)f(y)(0 \leq \lambda \leq 1)$
凸函数和非凸函数有一个共同的交集是等号，刚好仿射函数全部都是等号，所以可以认为仿射函数既是凸函数又是非凸函数。
仿射函数的梯度和导数实常数，不会随着 $x$ 变化。

【5】Slater条件

对于凸优化问题，如果Slater条件满足，则原问题与对偶问题的最优值相等，也就是强对偶性成立。

【5.1】凸优化问题定义

先考虑标准形式的凸优化问题：
最小化目标函数： $min_{x} f(x)$
约束条件：
不等式约束： $gi(x)≤0(i=1,2,...,m)g_{i}(x)\leq0(i=1,2,...,m)$
等式约束： $h_{j}(x)=0(j=1,2,...,p)$
定义域： $x∈Rnx\in R^{n}$
这里会有新要求：
$f (x)$ 和 $g_{i}(x)$ 是凸函数；
$h_{j}(x)$ 是仿射函数。

【5.2】Slater条件

Slater条件：存在一个严格可行点 $x∈dom(f)x\in dom(f)$ ，使得：
$g_{i}(x)< 0(i=1,2,...,m)$ 和 $h_{j}=0(j=1,1,...,p)$
dom(f)是domain of f的英文缩写，也就是要求这个严格可行点 $x$ 必须落在目标函数 $f$ 的定义域里，这样计算才是有效的。

【5.3】证明Slater条件保证强对偶性

记原问题的可行域为 $X={x∣gi(x)≤0(i=1,2,...,m),hj=0(j=1,2,...,p)}X={\{x|g_{i}(x)\leq 0(i=1,2,...,m),h_{j}=0}(j=1,2,...,p)\}$
原问题最优解为 $p∗=infx∈Xf(x)p^*=inf_{x \in X}f(x)$
对偶问题最优解 $d∗=supλ≥0,μd(λ,μ)d^*=sup_{\lambda \geq 0,\mu}d(\lambda ,\mu)$ ，且满足对偶间隙 $d∗≤p∗d^*\leq p^*$
证明目的：Slater条件成立， $d^*=p^*$

【5.3.1】反证法假设存在对偶间隙

假设 $d^*<p^*$ ，现在的目标是推出矛盾：

定义集合：
$A={f(x),g1(x),...,gm(x),h1(x),...,hp(x)∣x∈dom(f)}A={\{f(x),g_{1}(x),...,g_{m}(x),h_{1}(x),...,h_{p}(x)}|x \in dom(f)\}$
$B={(t,s1,...sm,r1,...,rp)∣t<p∗,si≤0,rj=0}B={\{(t,s_{1},...s_{m},r_{1},...,r_{p})|t<p^*,s_{i}\leq 0,r_{j}=0}\}$
A是原问题目标函数与约束函数在定义域上的取值集合；
B是“目标值小于 $p^*$ 且约束满足” 的集合
$t$ 对应原问题目标函数 $f (x)$ 的取值，要求 $t<p^*$ （ $p^*$ 是原问题的最优值），所以 $t$ 是比原问题最优目标值更小的目标函数值；
$s_{i}$ 对应原问题不等式约束 $g_{i}(x)$ 的取值，要求 $si≤0s_{i}\leq0$ 和原问题里的不等式约束 $gi(x)≤0g_{i}(x)\leq0$ 相对应，代表“满足不等式约束的函数值”；
$r_{j}$ 对应原问题等式约束 $h_{j}(x)$ 的取值，要求 $r_{j}=0$ 和原问题里的等式约束 $g_{i}(x)=0$ 相对应，代表“满足等式约束的函数值”。
集合B是在“目标函数值-约束函数值”这个空间里，刻画比原问题最优情况更优（但实际上达不到的）虚拟集合：
$t<p^*$ 就假设存在比最优还小的目标值；
$si≤0,rj=0s_{i}\leq0,r_{j}=0$ 继续维持了原问题的约束要求。
很显然，这两个集合必然满足： $\cap B=\varnothing$

此时存在非零向量 $(μ,v1,...,vm,w1,...,wp)(\mu,v_{1},...,v_{m},w_{1},...,w_{p})$ 和常数 $c$ ，使得对所有的 $α∈A\alpha \in A$ 和 $\in B$ ，满足：
$\cdot \alpha_{1}+\sum v_{i}\alpha_{i+1}+\sum w_{j}\alpha_{m+j+1}\geq c \geq u \cdot b_{1}+\sum v_{i}b_{i+1}+\sum w_{j}b_{m+j+1}$
这个公式其实无需证明，因为 $B$ 集合和值小于 $A$ 集合的值，所以上述式子成立也在情理之中，但它确实有一个名字：凸集分离定理。

【5.3.1.1】证明 $u > 0$

定义集合：
通过分析 $B$ 集合中元素的极限： $\rightarrow -\infty,s_{i} \rightarrow -\infty$
可以推出：
$u≥0u\geq 0$ ，否则不等式无法对 $\in B$ 成立
如 $u = 0$ ，则 $vi≥0v_{i}\geq 0$ 且不全为零，为证明这一点，我们把前面的凸集分离定理换一个更好读懂的写法：
$\cdot f+\sum_{i}^{m}v_{i}\cdot g_{i}+\sum_{j=1}^{p}w_{j}\cdot h_{j}\geq u\cdot t+\sum_{i=1}^{m}v_{i}\cdot s_{i}+\sum_{j=1}^{p}w_{j}\cdot r_{j}$
然后此时只讨论适用于集合 $B$ 的右侧部分：
$\cdot t+\sum_{i=1}^{m}v_{i}\cdot s_{i}+\sum_{j=1}^{p}w_{j}\cdot r_{j}\leq c$
当 $u = 0$ 的时候，如果出现 $v_{i}<0$ ，由于此时已经假设了 $si→−∞s_{i}\rightarrow -\infty$ ，所以就会有 $visi→+∞v_{i}s_{i}\rightarrow +\infty$ 的情况，这会破坏上式的成立，所以 $v_{i}$ 必然非负。
此外 $v_{i}$ 不能全0，之后再详细分析。
此时对于集合 $A$ ，会有： $\cdot f+\sum_{i}^{m}v_{i}\cdot g_{i}+\sum_{j=1}^{p}w_{j}\cdot h_{j}=\sum_{i}^{m}v_{i}\cdot g_{i}+\sum_{j=1}^{p}w_{j}\cdot h_{j}\geq c$ 因为 $h_{j}=0$ 恒成立，所以上式进一步化简为 $∑j=1mvi⋅gi≥c\sum_{j=1}^{m}v_{i}\cdot g_{i}\geq c$
因为 $gi<0,vi≥0g_{i}<0,v_{i}\geq0$ ，所以 $vi⋅gi≤0v_{i}\cdot g_{i}\leq 0$ ，所以此时 $c≤0c\leq0$ 。
此时对于 $vi⋅si≤cv_{i} \cdot s_{i}\leq c$ ，因为 $si≤0,vi≥0s_{i}\leq 0,v_{i}\geq0$ ,所以要求 $\geq 0$ ，此时只有 $c = 0$ 满足条件。
但实际上一定存在 $KaTeX parse error: Undefined control sequence: \< at position 11: v_{i}g_{i}\̲<̲0$ 的情况，所以 $c = 0$ 不能满足 $∑vi⋅gi<0≥c=0\sum v_{i}\cdot g_{i}<0 \geq c=0$
所以到这一步， $u = 0$ 不可取，那就只有 $u > 0$ 。

【5.3.1.2】证明 $d^=p^$

面对 $u > 0$ 这一条件，可以通过等比例缩放所有系数使得 $u = 1$ .
此时对集合 $A$ 有：
$f(x)+∑i=1mvi⋅gi+∑j=1pwj⋅hj≥cf(x)+\sum_{i=1}^{m}v_{i}\cdot g_{i}+\sum_{j=1}^{p}w_{j}\cdot h_{j}\geq c$
对集合 $B$ 有：
$t+∑i=1mvi⋅si+∑j=1pwj⋅rj≤ct+\sum_{i=1}^{m}v_{i}\cdot s_{i}+\sum_{j=1}^{p}w_{j}\cdot r_{j}\leq c$
因为在 $B$ 中，要求 $t<p^*$ （ $p^*$ 是原问题的最优值），也就是 $t$ 是比原问题最优目标值更小的目标函数值；
这时候进一步设置 $s_{i}=0$ ，因为 $si≥0s_{i}\geq 0$ ，所以直接取 $s_{i}=0$ 不影响结果，会对集合B有：
$t≤ct\leq c$
当 $t$ 无限接近 $p^*$ 时，上式转化为 $p∗≥cp^* \geq c$

此时的对偶函数可以定义为：
$d(λ,μ)=infx∈dom(f)[f(x)+∑i=1mλigi+∑j=1pμjhj]d(\lambda,\mu)=inf_{x\in dom(f)}{[f(x)+\sum_{i=1}^{m}\lambda_{i}g_{i}+\sum_{j=1}^{p}\mu_{j}h_{j}]}$

将对偶函数的系数代入集合A，有：
$f(x)+∑i=1mλi⋅gi+∑j=1pμj⋅hj≥cf(x)+\sum_{i=1}^{m}\lambda_{i}\cdot g_{i}+\sum_{j=1}^{p}\mu_{j}\cdot h_{j}\geq c$
由于对偶函数取的是下确界，所以有 $d(λ,μ)≥cd(\lambda,\mu)\geq c$
那所有函数的实际取值都不会小于下确界，所以有 $p∗≥d∗≥cp^* \geq d^*\geq c$ 所以只能取值 $p^*=d^*$
所以强对偶成立。