Lagrange函数及其对偶函数
对于标准形式的优化问题：
拉格朗日函数为：
向量和是对偶变量或者是这个式子的Lagrange乘子
Lagrange对偶函数是Lagrange函数关于取得的最小值：
对偶函数是一族关于(, )的放射函数的逐点下确界，所以即使原问题不是凸的，对偶函数也是凹的
对偶函数构成了原问题最优值的下界：即对任意和，下式成立：
证明：
设是原问题的一个可行点，即，则有：
代入Lagrange函数有：
因此：
考虑标准形式的线性规划问题：
其拉格朗日函数为：
对偶函数为：
线性函数只有恒为0时才有下界，因此：
Lagrange对偶问题
Lagrange对偶函数给出了优化问题最优值的一个下界，一个自然的问题是：从Lagrange函数能够得到的最好下界是什么？可以将这个问题表述为优化问题：
Lagrange对偶问题是一个凸优化问题，这是因为极大化的目标函数是凹函数，且约束集合是凸集
很多情况下，我们可以识别出函数g的定义域的仿射包，并将其表示为一系列线性等式约束，这样处理之后可以得到一个等价的问题
对于标准形式的线性规划，它的对偶问题是在满足约束的条件下极大化对偶函数g。当且仅当时对偶函数有界。因此，可得一个等价问题：
这个问题可进一步表述为：
KKT最优性条件
原问题最优值用表示，Lagrange对偶问题的最优值用表示，则有：
即使原问题不是凸问题，这个不等式也成立，这个性质称为弱对偶性。当原问题很难求解时，弱对偶不等式可以给原问题最优值一个下界
如果等式成立，即最优对偶间隙是零，那么强对偶性成立。一般情况下，强对偶性是不成立的。但如果原问题是凸问题，强对偶性一般成立
假设强对偶性成立，令是原问题的最优解，是对偶问题的最优解，因此：
因此有：
这个条件称为互补松弛性
非凸问题的KKT条件
假设强对偶性成立，令是原问题的最优解，是对偶问题的最优解。因为处取得最小值，因此，函数在处的导数必须为零，即：
由此可得：
上述式子就是KKT条件。如果强对偶性成立，那么任意一对原问题和对偶问题的最优解必须满足KKT条件
凸问题的KKT条件
当原问题是凸问题时，满足KKT条件的点也是原、对偶问题的最优解。换言之，是满足KKT条件的点，那么和分别是原问题和对偶问题的最优解，对偶间隙是零
附录
凸集的定义：如果集合C中任意两点间的线段仍然在C中，即对于任意和都有：
那么集合C是凸集
凸函数的定义：函数的定义域是，如果是凸集，且对于任意和任意，有：
从几何意义上来看，上述不等式意味着点和之间的线段在函数的上方
如果函数是凸的，那么函数是凹的
凸函数与逐点上确界：几乎所有的凸函数都可以表示成一组仿射函数的逐点上确界
凸优化问题定义：凸优化问题是形如：
的问题，凸优化问题有三个附加的要求：
