存在有原始优化问题如下所示:
\begin{array}{l}\tag{1}
\mathop{min}\limits_{\mathbf{w}_m\in\mathcal{H},\space\xi\in\mathcal{R}^l}\quad\quad
&\frac{1}{2}\sum_{m=1}^k\mathbf{w}_m^T\mathbf{w}_m+C\sum_{i=1}^l\xi_i
\\
\mathbf{subject\space to}\quad\quad
&\mathbf{w}_{y_i}^T\varphi(\mathbf{x}_i)-\frac{1}{k-1}\sum_{m\neq y_i}\mathbf{w}_m^T\varphi(\mathbf{x_i})\geq1-\xi_i,
\\
&\xi_i\geq 0,\quad i=1,\dots,l.
\end{array}
将其写成拉格朗日程式如下所示:
\begin{array}{l}\tag{2}
L(\mathbf{W},\xi,\alpha,\lambda)=&\frac{1}{2}\sum_{m=1}^k\mathbf{w}_m^T\mathbf{w}_m+C\sum_{i=1}^l\xi_i-\sum_{i=1}^l\lambda_i\xi_i
\\
\\
&-\sum_{i=1}^l\alpha_i
\left(
\mathbf{w}_{y_i}^T\varphi(\mathbf{x}_i)-\frac{1}{k-1}\sum_{m\neq{y_i}}\mathbf{w}_m^T\varphi(\mathbf{x}_i)-1+\xi_i
\right)
\end{array}
对其求偏微分:
\frac{\partial L}{\partial\mathbf{w}_m}=0\Longleftrightarrow\mathbf{w}_m=\sum_{i:y_i=m}\alpha_i\varphi(\mathbf{x_i})-\frac{1}{k-1}\sum_{i:y_i\neq m}\alpha_i\varphi(\mathbf{x}_i)\tag{3}
\frac{\partial L}{\partial\xi}=0\Longleftrightarrow C\mathbf{e}=\lambda+\alpha\tag{4}
\mathbf{subject\space to}\quad\alpha\geq 0,\space\lambda\geq 0
由**(3)**可以推得:
\begin{array}{l}
\mathbf{w}_m^T\mathbf{w}_m&=
\left(
\sum_{i:y_i=m}\alpha_i\varphi(\mathbf{x}_i)^T-\frac{1}{k-1}\sum_{i:y_i\neq m}\alpha_i\varphi(\mathbf{x}_i)^T
\right)
\left(
\sum_{j:y_j=m}\alpha_j\varphi(\mathbf{x}_j)-\frac{1}{k-1}\sum_{j:y_j\neq m}\alpha_j\varphi(\mathbf{x}_j)
\right)
\\
\\
&=\sum_{i:y_i=m}\alpha_i\varphi(\mathbf{x_i})^T\sum_{j:y_j=m}\alpha_j\varphi(\mathbf{x}_j)-\sum_{i:y_i=m}\alpha_i\varphi(\mathbf{x}_i)^T\frac{1}{k-1}\sum_{j:y_j\neq m}\alpha_j\varphi(\mathbf{x}_j)
\\
\\
&\quad -\frac{1}{k-1}\sum_{i:y_i\neq m}\alpha_i\varphi(\mathbf{x}_i)^T\sum_{j:y_j=m}\alpha_j\varphi(\mathbf{x}_j)+\frac{1}{k-1}\sum_{i:y_i\neq m}\alpha_i\varphi(\mathbf{x}_i)^T\frac{1}{k-1}\sum_{j:y_j\neq m}\alpha_j\varphi(\mathbf{x}_j)
\\
\\
&=\sum_{i:y_i=m}\sum_{j:y_j=m}\alpha_i\alpha_j\varphi(\mathbf{x}_i)^T\varphi(\mathbf{x}_j)-\frac{1}{k-1}\sum_{i:y_i=m}\sum_{j:y_j\neq m}\alpha_i\alpha_j\varphi(\mathbf{x}_i)^T\varphi(\mathbf{x}_j)
\\
\\
&\quad -\frac{1}{k-1}\sum_{i:y_i\neq m}\sum_{j:y_j=m}\alpha_i\alpha_j\varphi(\mathbf{x}_i)^T\varphi(\mathbf{x}_j)+
\left(
\frac{1}{k-1}
\right)^2\sum_{i:y_i\neq m}\sum_{j:y_j\neq m}\alpha_i\alpha_j\varphi(\mathbf{x}_i)^T\varphi(\mathbf{x}_j)
\\
\\
&=\sum_{i:y_i=m}\sum_{j:y_j=m}\alpha_i\alpha_j\varphi(\mathbf{x}_i)^T\varphi(\mathbf{x}_j)-\frac{2}{k-1}\sum_{i:y_i=m}\sum_{j:y_j\neq m}\alpha_i\alpha_j\varphi(\mathbf{x}_i)^T\varphi(\mathbf{x}_j)
\\
\\
&\quad +\left(
\frac{1}{k-1}
\right)^2\sum_{i:y_i\neq m}\sum_{j:y_j\neq m}\alpha_i\alpha_j\varphi(\mathbf{x}_i)^T\varphi(\mathbf{x}_j)………………………………(5)
\\
\\
\\
\\
\mathbf{w}_m^T\varphi(\mathbf{x}_i)
&=
\left(
\sum_{i:y_i=m}\alpha_i\varphi(\mathbf{x}_i)^T-\frac{1}{k-1}\sum_{i:y_i\neq m}\alpha_i\varphi(\mathbf{x}_i)^T
\right)\varphi(\mathbf{x}_i)
\\
\\
&=\sum_{i:y_i=m}\alpha_i\varphi(\mathbf{x}_i)^T\varphi(\mathbf{x}_i)-\frac{1}{k-1}\sum_{i:y_i\neq m}\alpha_i\varphi(\mathbf{x}_i)^T\varphi(\mathbf{x}_i)………………………(6)
\end{array}
将**(5)** 和**(6)** 代入**(2)** 中:
\begin{array}{l}
L(\mathbf{W},\xi,\alpha,\lambda)&=\frac{1}{2}\sum_{m=1}^k\mathbf{w}_m^T\mathbf{w}_m+C\sum_{i=1}^l\xi_i-\sum_{i=1}^l\lambda_i\xi_i
\\
\\
&\quad -\sum_{i=1}^l\alpha_i
\left(
\mathbf{w}_{y_i}^T\varphi(\mathbf{x}_i)-\frac{1}{k-1}\sum_{m\neq{y_i}}\mathbf{w}_m^T\varphi(\mathbf{x}_i)-1+\xi_i
\right)
\\
\\
&=\frac{1}{2}\sum_{m=1}^k\mathbf{w}_m^T\mathbf{w}_m+C\sum_{i=1}^l\xi_i-\sum_{i=1}^l\lambda_i\xi_i-\sum_{i=1}^l\alpha_i\mathbf{w}_{y_i}^T\varphi(\mathbf{x}_i)
\\
\\
&\quad+\frac{1}{k-1}\sum_{i=1}^l\sum_{m\neq{y_i}}\alpha_i\mathbf{w}_m^T\varphi(\mathbf{x}_i)+\sum_{i=1}^l\alpha_i-\sum_{i=1}^l\alpha_i\xi_i
\\
\\
&=\frac{1}{2}\sum_{m=1}^k\mathbf{w}_m^T\mathbf{w}_m-\sum_{i=1}^l\alpha_i\mathbf{w}_{y_i}^T\varphi(\mathbf{x}_i)+\frac{1}{k-1}\sum_{i=1}^l\sum_{m\neq{y_i}}\alpha_i\mathbf{w}_m^T\varphi(\mathbf{x}_i)+\sum_{i=1}^l\alpha_i
\\
\\
&=\frac{1}{2}
\left(
1×\alpha^2K-\frac{2}{k-1}\alpha^2K+
\left(
\frac{1}{k-1}
\right)^2\alpha^2K
\right)
\\
\\
&\quad-\sum_{i=1}^l\alpha_i
\left(
\alpha K-\frac{1}{k-1}\alpha K
\right)+\frac{1}{k-1}\sum_{i=1}^l\alpha_i
\left(
\alpha K-\frac{1}{k-1}\alpha K
\right)+\sum_{i=1}^l\alpha_i
\\
\\
&=\frac{1}{2}\alpha^2K
\left(
1-\frac{1}{k-1}
\right)^2-\alpha^2K+\frac{1}{k-1}\alpha^2 K+\frac{1}{k-1}\alpha^2 K-
\left(
\frac{1}{k-1}
\right)^2\alpha^2K+\alpha
\\
\\
&=-\frac{1}{2}\alpha^2K+\frac{1}{k-1}\alpha^2K-\frac{1}{2}
\left(
\frac{1}{k-1}
\right)^2\alpha^2K+e^T\alpha
\\
\\
&=-\frac{1}{2}\alpha^2
\end{array}