转自 http://www.cnblogs.com/90zeng/p/Lagrange_duality.html 原作者：博客园-90Zeng
1.原始问题
假设
称为约束最优化问题的原始问题。
现在如果不考虑约束条件，原始问题就是：
因为假设其连续可微，利用高中的知识，对
引进广义拉格朗日函数（generalized Lagrange function）:
不要怕这个式子，也不要被拉格朗日这个高大上的名字给唬住了，让我们慢慢剖析！这里
.
现在，如果把
再次注意
其中
是否满足约束条件两方面来分析这个函数:
，那么：
注意中间的最大化式子就是确定
就是个常量，常量的最大值显然是本身.
通过上面两条分析可以得出：
那么在满足约束条件下：
即
代表原始问题，下标 P 表示原始问题，定义原始问题的最优值：
原始问题讨论就到这里，做一个总结：通过拉格朗日这位大神的办法重新定义一个无约束问题（大家都喜欢无拘无束），这个无约束问题等价于原来的约束优化问题，从而将约束问题无约束化！
2.对偶问题
定义关于
注意等式右边是关于
，即
这就是原始问题的对偶问题，再把原始问题写出来：
形式上可以看出很对称，只不过原始问题是先固定
定义对偶问题的最优值：
3. 原始问题与对偶问题的关系
定理：若原始问题与对偶问题都有最优值，则
证明：对任意的
即
由于原始问题与对偶问题都有最优值，所以
即
也就是说原始问题的最优值不小于对偶问题的最优值，但是我们要通过对偶问题来求解原始问题，就必须使得原始问题的最优值与对偶问题的最优值相等，于是可以得出下面的推论：
推论：设
4. KKT 条件
定理：对于原始问题和对偶问题，假设函数
关于KKT 条件的理解：前面三个条件是由解析函数的知识，对于各个变量的偏导数为0（这就解释了一开始为什么假设三个函数连续可微，如果不连续可微的话，这里的偏导数存不存在就不能保证），后面四个条件就是原始问题的约束条件以及拉格朗日乘子需要满足的约束。
，这个知识点会在 SVM 的推导中用到.
5. 总结
一句话，某些条件下，把原始的约束问题通过拉格朗日函数转化为无约束问题，如果原始问题求解棘手，在满足KKT的条件下用求解对偶问题来代替求解原始问题，使得问题求解更加容易。
