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

概述

我们在讲解约束优化问题中经过拉格朗日乘子法获得了优化函数：

m i n x m a x λ , η L ( x , λ , η ) min_xmax_{\lambda,\eta}L(x,\lambda,\eta)minxmaxλ,ηL(x,λ,η)

s . t . λ i ≥ 0 s.t.\quad \lambda_i\geq0s.t.λi≥0

我们可以经过转化将上面的优化函数转换成：

m a x λ , η m i n x L ( x , λ , η ) max_{\lambda,\eta}min_xL(x,\lambda,\eta)maxλ,ηminxL(x,λ,η)

这是利用了对偶关系，如果要完全转换需要满足强对偶关系，本文先证明弱对偶关系：

即：

m a x λ , η m i n x L ( x , λ , η ) ≤ m i n x m a x λ , η L ( x , λ , η ) max_{\lambda,\eta}min_xL(x,\lambda,\eta)\leq min_xmax_{\lambda,\eta}L(x,\lambda,\eta)maxλ,ηminxL(x,λ,η)≤minxmaxλ,ηL(x,λ,η)

强对偶就是只满足等号。

那么这个式子怎么理解呢？

举个例子：专科学校中的学霸要弱于清华中的菜鸡，是不是很通俗易懂。

那么怎么通过数学进行证明上面的不等式呢？

m i n x L ( x , λ , η ) ≤ L ( x , λ , η ) ≤ m a x λ , η L ( x , λ , η ) min_xL(x,\lambda,\eta)\leq L(x,\lambda,\eta) \leq max_{\lambda,\eta}L(x,\lambda,\eta)minxL(x,λ,η)≤L(x,λ,η)≤maxλ,ηL(x,λ,η)

上面的等式显然是成立的。

为了表达方便我们另：

m i n x L ( x , λ , η ) = A ( λ , η ) min_xL(x,\lambda,\eta)=A(\lambda,\eta)minxL(x,λ,η)=A(λ,η)

m a x λ , η = B ( x ) max_{\lambda,\eta}=B(x)maxλ,η=B(x)

这里解释一下，因为 m i n x L ( x , λ , η ) min_xL(x,\lambda,\eta)minxL(x,λ,η) 的意思是当x取一定值的时候的最小值，所以最终的式子是关于 λ , η \lambda,\etaλ,η 的等式，B ( x ) B(x)B(x) 与之对应。

所以此时满足：

A ( λ , η ) ≤ B ( x ) A(\lambda,\eta)\leq B(x)A(λ,η)≤B(x)

我们知道，如果要满足这个不等式就要满足A的最大值小于B的最小值才能使该式永远成立，所以有：

m a x A ( λ , η ) ≤ m i n B ( x ) maxA(\lambda,\eta)\leq minB(x)maxA(λ,η)≤minB(x)

即：

m a x λ , η m i n x L ( x , λ , η ) ≤ m i n x m a x λ , η L ( x , λ , η ) max_{\lambda,\eta}min_xL(x,\lambda,\eta)\leq min_xmax_{\lambda,\eta}L(x,\lambda,\eta)maxλ,ηminxL(x,λ,η)≤minxmaxλ,ηL(x,λ,η)