2021人工智能领域新星创作者，带你从入门到精通，该博客每天更新，逐渐完善机器学习各个知识体系的文章，帮助大家更高效学习。

概述

引言

之前我们在讲解支持向量机的时候，我们最初目标优化函数为：

m i n 1 2 w T w min\frac{1}{2}w^Twmin21wTw

s . t . y i ( w T x i + b ) ≥ 1 s.t. \quad y_i(w^Tx_i+b)\geq1s.t.yi(wTxi+b)≥1

由于是带有约束条件的优化，所以我们构造了拉格朗日函数：

L ( w , b , λ ) = 1 2 w T w + ∑ i = 1 m λ i ( 1 − y i ( w T x i + b ) ) L(w,b,\lambda)=\frac{1}{2}w^Tw+\sum_{i=1}^m\lambda_i(1-y_i(w^Tx_i+b))L(w,b,λ)=21wTw+i=1∑mλi(1−yi(wTxi+b))

其中 λ i \lambda_iλi >=0。

在高数中我们学习过拉格朗日乘法是带有等式约束条件的，那么此时的不等式怎么搞呢？而且为什么 λ i \lambda_iλi 是大于0的呢？

下面来进行证明

约束优化证明

我们假设现有优化函数：

{ m i n f ( x ) s . t . g i ( x ) ≤ 0 ( i = 1 , 2 , . . . m ) s . t . h j ( x ) = 0 ( j = 1 , 2 , . . . n )

⎧⎩⎨minf(x)s.t.gi(x)≤0(i=1,2,...m)s.t.hj(x)=0(j=1,2,...n){minf(x)s.t.gi(x)≤0(i=1,2,...m)s.t.hj(x)=0(j=1,2,...n)

⎩⎪⎨⎪⎧minf(x)s.t.gi(x)≤0(i=1,2,...m)s.t.hj(x)=0(j=1,2,...n)

注意不等式的约束条件都要写成小于号，至于为什么是为了下面表达方便。

现在我们要构造拉格朗日函数：

L ( x , λ , η ) = f ( x ) + ∑ i = 1 m λ i g i ( x ) + ∑ j = 1 n η j h j ( x ) L(x,\lambda,\eta)=f(x)+\sum_{i=1}^m\lambda_ig_i(x)+\sum_{j=1}^n\eta_jh_j(x)L(x,λ,η)=f(x)+i=1∑mλigi(x)+j=1∑nηjhj(x)

其中 λ i \lambda_iλi 是大于等于0的数，而 η j \eta_jηj 可以为任何值的数。

现在拉格朗日函数已经构造出来了，那么接下来我们将带有约束条件的原问题就转化为了不带约束条件的优化函数。

不带约束条件的优化函数：

{ m i n x m a x λ , η L ( x , λ , η ) s . t . λ i ≥ 0

{minxmaxλ,ηL(x,λ,η)s.t.λi≥0{minxmaxλ,ηL(x,λ,η)s.t.λi≥0

{minxmaxλ,ηL(x,λ,η)s.t.λi≥0

下面给出证明为什么两个优化函数可以相互转换：

证明：

1.如果变量x违反了 g i ( x ) g_i(x)gi(x) 的约束条件，那么此时 g i ( x ) > 0 g_i(x)>0gi(x)>0 ，而 λ i \lambda_iλi 有时大于等于0的数，那么此时 m a x L ( x , λ , η ) maxL(x,\lambda,\eta)maxL(x,λ,η) 趋于正无穷，因为 g i ( x ) g_i(x)gi(x) 是正的，而且 λ i \lambda_iλi 可以为任何整数。

2.如果x服从 g i ( x ) g_i(x)gi(x) 的约束条件，那么此时 g i ( x ) ≤ 0 g_i(x)\leq0gi(x)≤0 ，而 λ i ≥ 0 \lambda_i\geq0λi≥0 ，那么它们两个异号，所以最大值就是乘积为0，所以此时的 m a x L ( x , λ , η ) = f ( x ) + ∑ j = 1 n η j h j ( x ) maxL(x,\lambda,\eta)=f(x)+\sum_{j=1}^n\eta_jh_j(x)maxL(x,λ,η)=f(x)+∑j=1nηjhj(x)

所以 m a x L ( x , λ , η ) = m a x ( + ∞ , f ( x ) + ∑ j = 1 n η j h j ( x ) ) = f ( x ) + ∑ j = 1 n η j h j ( x ) maxL(x,\lambda,\eta)=max(+\infty,f(x)+\sum_{j=1}^n\eta_jh_j(x))=f(x)+\sum_{j=1}^n\eta_jh_j(x)maxL(x,λ,η)=max(+∞,f(x)+∑j=1nηjhj(x))=f(x)+∑j=1nηjhj(x)

那么 m i n x m a x λ , η L ( x , λ , η ) = m i n f ( x ) + ∑ j = 1 n η j h j ( x ) min_xmax_{\lambda,\eta}L(x,\lambda,\eta)=min\quad f(x)+\sum_{j=1}^n\eta_jh_j(x)minxmaxλ,ηL(x,λ,η)=minf(x)+∑j=1nηjhj(x)

得到的式子就是带有等式的拉格朗日约束，即服从 h j ( x ) = 0 h_j(x)=0hj(x)=0 的条件下的约束，而且要得到 m i n x m a x λ , η L ( x , λ , η ) = m i n f ( x ) + ∑ j = 1 n η j h j ( x ) min_xmax_{\lambda,\eta}L(x,\lambda,\eta)=min\quad f(x)+\sum_{j=1}^n\eta_jh_j(x)minxmaxλ,ηL(x,λ,η)=minf(x)+∑j=1nηjhj(x) 这个优化函数的前提是第2点，x服从 g i ( x ) g_i(x)gi(x) 的约束条件，即 g i ( x ) ≤ 0 g_i(x)\leq0gi(x)≤0 ，那么这样就解释清楚了，我们不带优化函数的代数意义就是在服从不等式的条件下，且服从等式的条件下获得了：

{ m i n x m a x λ , η L ( x , λ , η ) s . t . λ i ≥ 0

{minxmaxλ,ηL(x,λ,η)s.t.λi≥0{minxmaxλ,ηL(x,λ,η)s.t.λi≥0

{minxmaxλ,ηL(x,λ,η)s.t.λi≥0