淘先锋技术网

首页 1 2 3 4 5 6 7

       最近学习支持向量机,出现了多次对偶问题以及KKT条件。有些不懂,专门了解了一下。写下这篇博客。加深对拉格朗日对偶性的理解。本篇博客以三个部分进行叙述,原始问题,对偶问题,以及两者的关系(KKT条件)。

1 原始问题

       首先提出一个约束最优化问题:

       这里的c(x)称为不等约束,h(x)称为等式约束。

       称这个最优化问题是原始最优化问题。

       然后引入广义拉格朗日函数,形式即f(x)+拉格朗日乘子*不等约束+拉格朗日乘子*等式约束:

      

       这里观察(C.4),如果不满足(C.2)或(C.3),那么我们可以令拉格朗日乘子的值令其第二项或第三项无穷大。如果满足的话,就可以认为:

    

       如果考虑极小化,那么


       (C.8)  称为广义拉格朗日的极小极大问题。这样一来,原始最优化问题即为广义拉格朗日函数的极小极大化问题。

 

2 对偶问题

      

 

3 原始问题和对偶问题的关系

       定义原始问题的最优解为

      

       定义对偶问题的最优解为:

      

      


我们发现d和p有可能相等的,那么,要满足什么条件呢?也就是满足


并且满足KKT条件: