注意，本文内容来自于吴恩达老师cs229课堂笔记的中文翻译项目:https://github.com/Kivy-CN/Stanford-CS-229-CN 中的凸优化部分的内容进行翻译学习。
为了看到一个更复杂的拉格朗日对偶例子，我们来推导以前课堂上给出的SVM L 1 L_1 L1范数的软边界的原对偶问题，以及相应的KKT互补（即，互补松弛）条件。我们有：
min w , b , ξ 1 2 ∥ w ∥ 2 + C ∑ i = 1 m ξ i s u b j e c t t o y ( i ) ( w T x ( i ) + b ) ≥ 1 − ξ i , i = 1 , . . . , m ξ i ≥ 0 , i = 1 , . . . , m \begin{aligned} \min_{w,b,\xi} \quad & \frac 12 \parallel w\parallel^2+C\sum^m_{i=1}\xi_i \\ subject\quad to \quad& y^{(i)}(w^Tx^{(i)}+b) \geq1-\xi_i,\quad &i=1,...,m\\ & \xi_i \geq 0, &i=1,...,m \end{aligned} w,b,ξminsubjectto21∥w∥2+Ci=1∑mξiy(i)(wTx(i)+b)≥1−ξi,ξi≥0,i=1,...,mi=1,...,m
首先，我们使用“ ≤ 0 \le 0 ≤0”的不等式形式把它化成标准形式：
min w , b , ξ 1 2 ∥ w ∥ 2 + C ∑ i = 1 m ξ i s u b j e c t t o 1 − ξ i − y ( i ) ( w T x ( i ) + b ) ≤ 0 , i = 1 , . . . , m − ξ i ≤ 0 , i = 1 , . . . , m \begin{aligned} \min_{w,b,\xi} \quad & \frac 12 \parallel w\parallel^2+C\sum^m_{i=1}\xi_i \\ subject\quad to \quad& 1-\xi_i-y^{(i)}(w^Tx^{(i)}+b) \le 0,\quad &i=1,...,m\\ & -\xi_i \le 0, &i=1,...,m \end{aligned} w,b,ξminsubjectto21∥w∥2+Ci=1∑mξi1−ξi−y(i)(wTx(i)+b)≤0,−ξi≤0,i=1,...,mi=1,...,m
接下来，我们构造广义拉格朗日函数： 7 ^7 7
7 在这里，非常重要的一点是要注意到全体 ( w , b , ξ ) (w,b,\xi) (w,b,ξ)在“ x x x”原变量中占据的角色。类似的，要注意到全体 ( α , β ) (\alpha,\beta) (α,β)在“ α \alpha α”对偶变量中占据的角色，通常是用于不等式约束的。因为在本问题中并没有仿射不等式约束，因此在这里就没有“ β \beta β”对偶变量。
L ( w , b , ξ , α , β ) = 1 2 ∥ w ∥ 2 + C ∑ i = 1 m ξ i + ∑ i = 1 m α i ( 1 − ξ i − y ( i ) ( w T x ( i ) + b ) ) − ∑ i = 1 m β i ξ i \mathcal{L}(w,b,\xi,\alpha,\beta)=\frac 12 \parallel w\parallel^2+C\sum^m_{i=1}\xi_i+\sum^m_{i=1}\alpha_i(1-\xi_i-y^{(i)}(w^Tx^{(i)}+b))-\sum_{i=1}^m\beta_i\xi_i L(w,b,ξ,α,β)=21∥w∥2+Ci=1∑mξi+i=1∑mαi(1−ξi−y(i)(wTx(i)+b))−i=1∑mβiξi
上式给出了原始和对偶优化问题：
max α , β : α i ≥ 0 , β i ≥ 0 θ D ( α , β ) 其 中 θ D ( α , β ) : = min w , b , ξ L ( w , b , ξ , α , β ) , ( S V M − D ) min w , b , ξ θ P ( w , b , ξ ) 其 中 θ P ( w , b , ξ ) : = max α , β : α i ≥ 0 , β i ≥ 0 L ( w , b , ξ , α , β ) , ( S V M − P ) \begin{aligned} \max_{\alpha,\beta:\alpha_i\ge0,\beta_i\ge0}\theta_{\mathcal{D}}(\alpha,\beta) \qquad&其中\qquad\theta_{\mathcal{D}}(\alpha,\beta) := \min_{w,b,\xi}\mathcal{L}(w,b,\xi,\alpha,\beta),\quad&(SVM-D)\\ \min_{w,b,\xi}\theta_{\mathcal{P}}(w,b,\xi)\qquad&其中\qquad\theta_{\mathcal{P}}(w,b,\xi) := \max_{\alpha,\beta:\alpha_i\ge0,\beta_i\ge0}\mathcal{L}(w,b,\xi,\alpha,\beta),\quad&(SVM-P) \end{aligned} α,β:αi≥0,βi≥0maxθD(α,β)w,b,ξminθP(w,b,ξ)其中θD(α,β):=w,b,ξminL(w,b,ξ,α,β),其中θP(w,b,ξ):=α,β:αi≥0,βi≥0maxL(w,b,ξ,α,β),(SVM−D)(SVM−P)
不过，要把对偶问题化成讲义中所示的形式，我们还有一些工作要做。特别是,
θ D ( α , β ) = min w , b , ξ L ( w , b , ξ , α , β ) \theta_{\mathcal{D}}(\alpha,\beta)=\min_{w,b,\xi}\quad \mathcal{L}(w,b,\xi,\alpha,\beta) θD(α,β)=w,b,ξminL(w,b,ξ,α,β)
上式是一个无约束优化问题，其中目标函数 L ( w , b , ξ , α , β ) \mathcal{L}(w,b,\xi,\alpha,\beta) L(w,b,ξ,α,β)是可微的。拉格朗日函数是关于 w w w的严格凸二次函数，到目前为止，对于任意给定的 ( α , β ) (\alpha,\beta) (α,β)来说，如果有 ( w ^ , b ^ , ξ ^ ) (\hat{w},\hat{b},\hat{\xi}) (w^,b^,ξ^)使得拉格朗日函数最小化，必须满足下式：
∇ w L ( w ^ , b ^ , ξ ^ , α , β ) = w ^ − ∑ i = 1 m α i y ( i ) x ( i ) = 0 ( 24 ) \nabla_w\mathcal{L}(\hat{w},\hat{b},\hat{\xi},\alpha,\beta) = \hat{w}-\sum_{i=1}^m\alpha_iy^{(i)}x^{(i)}=0\qquad\qquad(24) ∇wL(w^,b^,ξ^,α,β)=w^−i=1∑mαiy(i)x(i)=0(24)
跟进一步来说，拉格朗日函数是关于 b b b和 ξ \xi ξ的线性函数。通过类似于前一节简单对偶例子中描述的推理。我们可以设置对 b b b和 ξ \xi ξ求导等于零，并将得到的条件作为显式约束添加到对偶优化问题中：
∂ ∂ b L ( w ^ , b ^ , ξ ^ , α , β ) = − ∑ i = 1 m α i y ( i ) = 0 ( 25 ) ∂ ∂ ξ i L ( w ^ , b ^ , ξ ^ , α , β ) = C − α i − β i = 0 ( 26 ) \frac{\partial}{\partial_b}\mathcal{L}(\hat{w},\hat{b},\hat{\xi},\alpha,\beta)=-\sum_{i=1}^m\alpha_iy^{(i)}=0\qquad\qquad(25) \\ \frac{\partial}{\partial_{\xi_i}}\mathcal{L}(\hat{w},\hat{b},\hat{\xi},\alpha,\beta)=C-\alpha_i-\beta_i=0\qquad\qquad(26) ∂b∂L(w^,b^,ξ^,α,β)=−i=1∑mαiy(i)=0(25)∂ξi∂L(w^,b^,ξ^,α,β)=C−αi−βi=0(26)
我们可以用这些条件来计算对偶目标为：
θ D ( α , β ) = L ( w ^ , b ^ , ξ ^ ) = 1 2 ∥ w ^ ∥ 2 + C ∑ i = 1 m ξ i ^ + ∑ i = 1 m α i ( 1 − ξ ^ i − y ( i ) ( w ^ T x ( i ) + b ^ ) ) − ∑ i = 1 m β i ξ i ^ = 1 2 ∥ w ^ ∥ 2 + C ∑ i = 1 m ξ i ^ + ∑ i = 1 m α i ( 1 − ξ ^ i − y ( i ) ( w ^ T x ( i ) ) ) − ∑ i = 1 m β i ξ i ^ = 1 2 ∥ w ^ ∥ 2 + ∑ i = 1 m α i ( 1 − y ( i ) ( w ^ T x ( i ) ) ) \begin{aligned} \theta_{\mathcal{D}}(\alpha,\beta) &= \mathcal{L}(\hat{w},\hat{b},\hat{\xi})\\ &= \frac 12 \parallel \hat{w}\parallel^2+C\sum^m_{i=1}\hat{\xi_i}+\sum^m_{i=1}\alpha_i(1-\hat{\xi}_i-y^{(i)}(\hat{w}^Tx^{(i)}+\hat{b}))-\sum_{i=1}^m\beta_i\hat{\xi_i} \\ &= \frac 12 \parallel \hat{w}\parallel^2+C\sum^m_{i=1}\hat{\xi_i}+\sum^m_{i=1}\alpha_i(1-\hat{\xi}_i-y^{(i)}(\hat{w}^Tx^{(i)}))-\sum_{i=1}^m\beta_i\hat{\xi_i} \\ &= \frac 12 \parallel \hat{w}\parallel^2 + \sum^m_{i=1}\alpha_i(1-y^{(i)}(\hat{w}^Tx^{(i)})) \end{aligned} θD(α,β)=L(w^,b^,ξ^)=21∥w^∥2+Ci=1∑mξi^+i=1∑mαi(1−ξ^i−y(i)(w^Tx(i)+b^))−i=1∑mβiξi^=21∥w^∥2+Ci=1∑mξi^+i=1∑mαi(1−ξ^i−y(i)(w^Tx(i)))−i=1∑mβiξi^=21∥w^∥2+i=1∑mαi(1−y(i)(w^Tx(i)))
其中第一个等式来自于给定 ( α , β ) (\alpha,\beta) (α,β)最优的 ( w ^ , b ^ , ξ ^ ) (\hat{w},\hat{b},\hat{\xi}) (w^,b^,ξ^)，第二个等式使用广义拉格朗日函数的定义，第三个等式和第四个等式分别来自 ( 25 ) (25) (25)和 ( 26 ) (26) (26)。最后，使用 ( 24 ) (24) (24)，可得：
1 2 ∥ w ^ ∥ 2 + ∑ i = 1 m α i ( 1 − y ( i ) ( w ^ T x ( i ) ) ) = ∑ i = 1 m α i + 1 2 ∥ w ^ ∥ 2 − w ^ T ∑ i = 1 m α i y ( i ) x ( i ) = ∑ i = 1 m α i + 1 2 ∥ w ^ ∥ 2 − ∥ w ^ ∥ 2 = ∑ i = 1 m α i − 1 2 ∥ w ^ ∥ 2 = ∑ i = 1 m α i − 1 2 ∑ i = 1 m ∑ j = 1 m α i α i y ( i ) y ( j ) < x ( i ) , x ( j ) > \begin{aligned} \frac 12 \parallel \hat{w}\parallel^2 + \sum^m_{i=1}\alpha_i(1-y^{(i)}(\hat{w}^Tx^{(i)})) &= \sum^m_{i=1}\alpha_i + \frac 12 \parallel \hat{w}\parallel^2 - \hat{w}^T\sum^m_{i=1}\alpha_iy^{(i)}x^{(i)} \\ &= \sum^m_{i=1}\alpha_i + \frac 12 \parallel \hat{w}\parallel^2 - \parallel \hat{w}\parallel^2 \\ &= \sum^m_{i=1}\alpha_i - \frac 12 \parallel \hat{w}\parallel^2 \\ &= \sum^m_{i=1}\alpha_i - \frac 12\sum^m_{i=1}\sum^m_{j=1}\alpha_i\alpha_iy^{(i)}y^{(j)}<x^{(i)},x^{(j)}> \end{aligned} 21∥w^∥2+i=1∑mαi(1−y(i)(w^Tx(i)))=i=1∑mαi+21∥w^∥2−w^Ti=1∑mαiy(i)x(i)=i=1∑mαi+21∥w^∥2−∥w^∥2=i=1∑mαi−21∥w^∥2=i=1∑mαi−21i=1∑mj=1∑mαiαiy(i)y(j)<x(i),x(j)>
因此，我们的对偶问题（因为没有更多原始变量和所有的显式约束）就很简单了：
min α , β ∑ i = 1 m α i − 1 2 ∑ i = 1 m ∑ j = 1 m α i α i y ( i ) y ( j ) < x ( i ) , x ( j ) > s u b j e c t t o α i ≥ 0 , i = 1 , . . . , m β i ≥ 0 , i = 1 , . . . , m α i + β i = C , i = 1 , . . . , m ∑ i = 1 m α i y ( i ) = 0 \begin{aligned} \min_{\alpha,\beta} \quad & \sum^m_{i=1}\alpha_i - \frac 12\sum^m_{i=1}\sum^m_{j=1}\alpha_i\alpha_iy^{(i)}y^{(j)}<x^{(i)},x^{(j)}> \\ subject\quad to \quad&\alpha_i \geq 0,\quad &i=1,...,m\\ & \beta_i \geq 0, &i=1,...,m \\ & \alpha_i + \beta_i = C, &i=1,...,m \\ &\sum^m_{i=1}\alpha_iy^{(i)}=0 \end{aligned} α,βminsubjecttoi=1∑mαi−21i=1∑mj=1∑mαiαiy(i)y(j)<x(i),x(j)>αi≥0,βi≥0,αi+βi=C,i=1∑mαiy(i)=0i=1,...,mi=1,...,mi=1,...,m
α i ∗ ( 1 − ξ i ∗ − y ( i ) ( w ∗ T x ( i ) + b ∗ ) ) = 0 β i ∗ ξ i ∗ = 0 \begin{aligned} \alpha_i^*(1-\xi_i^*-y^{(i)}(w^{*T}x^{(i)}+b^*)) &= 0 \\ \beta_i^*\xi_i^* &= 0 \end{aligned} αi∗(1−ξi∗−y(i)(w∗Tx(i)+b∗))βi∗ξi∗=0=0
对于 i = 1 , … , m i = 1,\dots,m i=1,…,m。根据第一个条件我们可以得出如果 α i ∗ > 0 \alpha_i^*>0 αi∗>0那么为了使乘积为零，则 1 − ξ i ∗ − y ( i ) ( w ∗ T x ( i ) + b ∗ ) = 0 1-\xi_i^*-y^{(i)}(w^{*T}x^{(i)}+b^*)=0 1−ξi∗−y(i)(w∗Tx(i)+b∗)=0。由此断定：
y ( i ) ( w ∗ T x ( i ) + b ∗ ) ≤ 1 y^{(i)}(w^{*T}x^{(i)}+b^*)\le 1 y(i)(w∗Tx(i)+b∗)≤1
根据原可行性有 ξ ∗ ≥ 0 \xi^*\ge 0 ξ∗≥0，类似的，如果 β i ∗ > 0 \beta_i^*>0 βi∗>0，则需要 ξ i ∗ = 0 \xi_i^*=0 ξi∗=0来确保互补性。根据原约束条件 y ( i ) ( w ∗ T x ( i ) + b ∗ ) ≥ 1 − ξ i y^{(i)}(w^{*T}x^{(i)}+b^*)\ge 1-\xi_i y(i)(w∗Tx(i)+b∗)≥1−ξi，可以得出：
y ( i ) ( w ∗ T x ( i ) + b ∗ ) ≥ 1 y^{(i)}(w^{*T}x^{(i)}+b^*)\ge 1 y(i)(w∗Tx(i)+b∗)≥1
最后，因为 β i ∗ > 0 \beta_i^*>0 βi∗>0等价于 α i ∗ < C \alpha_i^*<C αi∗<C（因为 α ∗ + β i ∗ = C \alpha^* + \beta_i^* = C α∗+βi∗=C），我们可以将KKT条件总结为如下式子：
α i ∗ < C ⇒ y ( i ) ( w ∗ T x ( i ) + b ∗ ) ≥ 1 , α i ∗ > 0 ⇒ y ( i ) ( w ∗ T x ( i ) + b ∗ ) ≤ 1 \alpha_i^*<C\quad\Rightarrow\quad y^{(i)}(w^{*T}x^{(i)}+b^*)\ge 1, \\ \alpha_i^*>0\quad\Rightarrow\quad y^{(i)}(w^{*T}x^{(i)}+b^*)\le 1 αi∗<C⇒y(i)(w∗Tx(i)+b∗)≥1,αi∗>0⇒y(i)(w∗Tx(i)+b∗)≤1
或者等价的表示为：
α i ∗ = 0 ⇒ y ( i ) ( w ∗ T x ( i ) + b ∗ ) ≥ 1 , 0 < α i ∗ < C ⇒ y ( i ) ( w ∗ T x ( i ) + b ∗ ) = 1 , α i ∗ = C ⇒ y ( i ) ( w ∗ T x ( i ) + b ∗ ) ≤ 1 \alpha_i^*=0\quad\Rightarrow\quad y^{(i)}(w^{*T}x^{(i)}+b^*)\ge 1, \\ 0<\alpha_i^*<C\quad\Rightarrow\quad y^{(i)}(w^{*T}x^{(i)}+b^*)= 1, \\ \alpha_i^*=C\quad\Rightarrow\quad y^{(i)}(w^{*T}x^{(i)}+b^*)\le 1 αi∗=0⇒y(i)(w∗Tx(i)+b∗)≥1,0<αi∗<C⇒y(i)(w∗Tx(i)+b∗)=1,αi∗=C⇒y(i)(w∗Tx(i)+b∗)≤1
β i ≥ 0 α i + β i = C \beta_i\ge 0\qquad\qquad \alpha_i + \beta_i = C βi≥0αi+βi=C
上面的式子等价于一个单约束 α i ≤ C \alpha_i\le C αi≤C；也就是说，如果我们相约解决下面的约束问题：
min α , β ∑ i = 1 m α i − 1 2 ∑ i = 1 m ∑ j = 1 m α i α i y ( i ) y ( j ) < x ( i ) , x ( j ) > s u b j e c t t o 0 ≤ α i ≤ C , i = 1 , . . . , m , ( 27 ) ∑ i = 1 m α i y ( i ) = 0 \begin{aligned} \min_{\alpha,\beta} \quad & \sum^m_{i=1}\alpha_i - \frac 12\sum^m_{i=1}\sum^m_{j=1}\alpha_i\alpha_iy^{(i)}y^{(j)}<x^{(i)},x^{(j)}> \\ subject\quad to \quad&0\le\alpha_i \le C,\quad &i=1,...,m,\qquad\qquad(27)\\ &\sum^m_{i=1}\alpha_iy^{(i)}=0 \end{aligned} α,βminsubjecttoi=1∑mαi−21i=1∑mj=1∑mαiαiy(i)y(j)<x(i),x(j)>0≤αi≤C,i=1∑mαiy(i)=0i=1,...,m,(27)
并且随后设置 β i = C − α i \beta_i=C-\alpha_i βi=C−αi，则 ( α , β ) (\alpha,\beta) (α,β)对于前面的对偶问题是最优的。最后一种形式实际上是课堂讲稿中给出的软边界SVM对偶形式。
在许多实际任务中， 90 % 90\% 90%的挑战都涉及如何以凸优化的形式来改写优化问题。一旦找到了正确的形式，就可以使用软件包。因为许多已有的用于凸优化的软件包已经进行了很好的调优，以处理不同类型的优化问题。下面是一小部分可用的软件包：
我们特别指出CVX作为一个易于使用的通用工具可以基于MATLAB求解凸优化问题，还有CVXOPT作为一个强大的基于Python库，其独立于MATLAB运行。 8 ^8 8 如果你对上诉列表中出现的其他包感兴趣的话，可以很容易的在web中搜索到。简而言之，如果你需要一个特定的凸优化算法，现有的软件包提供了一种快速的原型化方法来让你实现该算法，而无需你自己完整的完成凸优化的所有数值计算。
8 CVX 在网址 http://cvxr.com/cvx/ 可以找到。CVXOPT 在网址 http://cvxopt.org/ 可以找到。
另外，如果你觉得本材料很有趣，一定要看看Stephen Boyd的课程EE364: Optimization I，它将在冬季学期提供。EE364的课程教材（在参考资料[1]注：参考资料[1]见文章最下方中列出）包含丰富的凸优化知识，可以在线浏览。
[1] Stephen Boyd and Lieven Vandenberghe. Convex Optimization. Cambridge UP, 2004. Online: http://www.stanford.edu/~boyd/cvxbook/
