在约束最优化问题中，常常利用拉格朗日对偶性将原始问题转换为对偶问题，通过解对偶问题而得到原始问题的解。该方法用在许多统计学习方法中，例如学习笔记|最大熵模型的学习、学习笔记|最大熵模型学习举例、学习笔记|线性可分支持向量机学习的对偶算法。

1. 原始问题

称此约束最优化问题为原始最优化问题或原始问题。

首先，引进广义拉格朗日函数

（注意，这里的拉格朗日函数与学习笔记|广义拉格朗日函数与KKT条件的应用中的广义拉格朗日函数是一致的）

这里，下标P表示原始问题。

相反地，如果x满足约束条件，则

因此，

所以如果考虑极小化问题

它与原始最优化问题等价，称为广义拉格朗日函数的极小极大问题。

这样一来，就把原始最优化问题表示为广义拉格朗日函数的极小极大问题。为了方便，定义原始问题的最优值

称为原始问题的值。

2. 对偶问题

定义

它称为广义拉格朗日函数的极大极小问题。

可以将广义拉格朗日函数的极大极小问题表示为约束最优化问题：

称为原始问题的对偶问题。定义对偶问题的最优值

称为对偶问题的值。

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

下面讨论原始问题和对偶问题的关系。

定理1： 若原始问题和对偶问题都有最优值，则

证明： 对任意α,β和x，有

即

由于原始问题和对偶问题均有最优值，所以

即

（KKT条件可参见学习笔记|KKT条件与拉格朗日乘子法和学习笔记|广义拉格朗日函数与KKT条件的应用）

参考文献

【1】统计学习方法（第2版），李航著，清华大学出版社