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

网站建设这个行业怎么样网站价格套餐

news 2025/9/17 20:23:52

网站建设这个行业怎么样,网站价格套餐,做网站开发经营范围,自己做钓鱼网站目录原问题与对偶问题的定义定义该原问题的对偶问题如下在定义了函数的基础上，对偶问题如下： 综合原问题和对偶问题的定义得到： 定理一对偶差距（Duality Gap） 强对偶定理（Strong Duality Theo…

原问题与对偶问题的定义

定义该原问题的对偶问题如下

在定义了函数的基础上，对偶问题如下：

综合原问题和对偶问题的定义得到：

定理一

对偶差距（Duality Gap）

强对偶定理（Strong Duality Theorem）

假如成立，又根据定理一推出不等式

转化为对偶问题

首先将

得到

最小化：

限制条件：

再整理一下

最小化：或

限制条件：

用对偶理论求解该问题的对偶问题

对偶问题

按照对偶问题的定义，可以将对偶问题写成如下形式：

如何将原问题化为对偶问题

原问题（Prime Problem）

对偶问题（Dual Problem）

原问题与对偶问题的定义

最小化（Minimize）： $f\left ( \omega \right )$

限制条件（Subject to）： $g_i(\omega )\leq 0,i=1\sim K$

$h_i(\omega )= 0,i=1\sim m$

自变量为 $\omega\Leftarrow$ 多维向量

目标函数是 $f\left ( \omega \right )$

定义该原问题的对偶问题如下

定义函数：

$L(\omega ,\alpha ,\beta )=f(\omega )+\displaystyle\sum_{i=1}^{K}\alpha _ig_i(\omega )+\displaystyle\sum_{i=1}^{K}\beta _ih_i(\omega )$

向量的形式 $\Rightarrow$ $=f(\omega )+\alpha ^Tg(\omega )+\beta ^Th(\omega )$

其中 $\alpha =[\alpha _1,\alpha _2,...,\alpha _k]^T$ ， $\beta =[\beta _1,\beta _2,...,\beta _M]^T$

$g(\omega )=[g_1(\omega ),g_2(\omega ),...,g_K(\omega )]^T$ ， $h(\omega )=[h_1(\omega ),h_2(\omega ),...,h_M(\omega )]^T$

在定义了函数 $L(\omega ,\alpha ,\beta )$ 的基础上，对偶问题如下：

最大化： $\theta (\alpha ,\beta )=inf\text{ }L(\omega ,\alpha ,\beta )$ ，所有定义域内的 $\omega$

限制条件： $\alpha _i\geq 0,i=1\sim K$

综合原问题和对偶问题的定义得到：

定理一

如果 $\omega ^*$ 是原问题的解， $(\alpha ^*,\beta ^*)$ 是对偶问题的解则有：

$f(\omega ^*)\geqslant \theta (\alpha ^*,\beta ^*)$

证明： $\theta (\alpha^* ,\beta ^*)=inf\text{ }L(\omega ,\alpha^* ,\beta ^*)$

$\leq L(\omega^* ,\alpha^* ,\beta^* )$

$=f(\omega ^)+\alpha ^{T}g(\omega ^)+\beta ^{T}h(\omega ^*)$

$\leq f(\omega ^*)$

$\because$ $\omega ^*$ 是原问题的解

$\therefore$ $g(\omega ^*)\leqslant 0$ ， $h(\omega ^*)= 0$

$\because$ $(\alpha ^*,\beta ^*)$ 是对偶问题的解

$\therefore$ $\alpha (\omega ^*)\geqslant 0$

对偶差距（Duality Gap）

$f(\omega ^*)- \theta (\alpha ^*,\beta ^*)$

根据定理一，对偶差距 $\geqslant 0$

强对偶定理（Strong Duality Theorem）

如果 $g(\omega )=A\omega +b$ ， $h(\omega )=C\omega +d$ ， $f(\omega )$ 为凸函数，则有 $f(\omega ^*)= \theta (\alpha ^*,\beta ^*)$ ，则对偶差距为0。

如果：原问题的目标函数是凸函数，限制条件是线性函数。

那么原问题的解 $f(\omega ^*)= \theta (\alpha ^*,\beta ^*)$ ，对偶差距等于0。

假如 $f(\omega ^)= \theta (\alpha ^,\beta ^*)$ 成立，又根据定理一推出不等式

若 $f(\omega ^*)= \theta (\alpha ^*,\beta ^*)$ ，则定理一中必然能够推出，对于所有的 $i=1\sim K$ ，要么 $\alpha _i=0$ ，要么 $g_i(\omega ^*)=0$ 。这个条件成为KKT条件。

转化为对偶问题

支持向量机的原问题满足强对偶定理

首先将

$\delta _i\geq 0(i=1\sim N)$ 转换成 $\delta _i\leq 0(i=1\sim N)$

得到

最小化： $\frac{1}{2}\left \| \omega \right \|^2-C \displaystyle\Sigma _{i=1}^N \delta _i$

限制条件：

（1） $\delta _i\leq 0(i=1\sim N)$

（2） $y_i[\omega ^T\varphi (X_i)+b]\geq 1+\delta _i,(i=1\sim N)$

再整理一下

最小化： $\frac{1}{2}\left \| \omega \right \|^2-C \displaystyle\Sigma _{i=1}^N \delta _i$ 或 $\frac{1}{2}\left \| \omega \right \|^2+C \displaystyle\Sigma _{i=1}^N \delta _i$

$\Uparrow$ 情况1 $\Uparrow$ 情况2

限制条件：

（1） $\delta _i\leq 0(i=1\sim N)$

（2） $1+\delta _i-y_i\omega ^T\varphi (X_i)-y_ib\leq 0 ,(i=1\sim N)$

两个限制条件都是线性的，支持向量机的目标函数是凸的，它满足强对偶定理。

用对偶理论求解该问题的对偶问题

对偶问题

自变量 $\omega$ 等于这里的 $\left ( \omega ,b,\delta _i \right )$

不等式 $g_i(\omega )\leq 0$ 在这里被分成了两部分，

一部分： $\delta _i\leq 0(i=1\sim N)$

另一部分： $1+\delta _i-y_i\omega ^T\varphi (X_i)-y_ib\leq 0 ,(i=1\sim N)$

不存在 $h_i(\omega )$

按照对偶问题的定义，可以将对偶问题写成如下形式：

最大化：

$\theta (\alpha ,\beta )=inf_{\omega ,\delta _i,b} \left \{ \frac{1}{2}\left \| \omega \right \|^2-C \sum_{i=1}^{N}\beta _i\delta _i+\sum_{i=1}^{N} \alpha _i\left [1+\delta _i-y_i\omega ^T\varphi (X_i)-y_ib \right ] \right \}$

限制条件：

（1） $\alpha _i\geq 0$

（2） $\beta _i\geq 0$

如何将原问题化为对偶问题

遍历所有 $\left ( \omega ,b,\delta _i \right )$ 求最小值

对 $\left ( \omega ,b,\delta _i \right )$ 求导并令导数为 $\textbf{0}$

（1） $\frac{\partial \theta }{\partial\omega }=\omega-\sum_{i=1}^{N}\alpha _i\varphi (X_i)y_i=0 \text{ } \Rightarrow \text{ } \omega=\sum_{i=1}^{N}\alpha _iy_i\varphi (X_i)$