拉格朗日对偶是优化理论中的一个重要概念，它允许我们将一个复杂的约束最优化问题转换为一个更容易求解的对偶问题。以下是拉格朗日对偶的基本原理和步骤：
原问题和对偶问题的定义
-
原问题 ：给定目标函数 \( f(x) \) 和约束条件 \( h_i(x) = 0 \)(等式约束)和 \( g_j(x) \leq 0 \)(不等式约束)，寻找 \( x \) 使得 \( f(x) \) 最小化，同时满足所有约束条件。
-
对偶问题 ：通过引入拉格朗日乘子 \( \lambda \) 和 \( \mu \)，构造拉格朗日函数 \( L(x, \lambda, \mu) \)，然后最小化这个函数，同时满足对偶约束条件。
拉格朗日对偶函数
- 定义 ：拉格朗日对偶函数 \( l(\lambda, \mu) \) 是拉格朗日函数关于 \( x \) 取的最小值，即对于给定的 \( \lambda \) 和 \( \mu \)，找到 \( x \) 使得 \( L(x, \lambda, \mu) \) 最小。
原问题和对偶问题的关系
-
等价性 ：原问题和对偶问题是等价的，即它们的最优解集相同。
-
最优值下界 ：对偶问题的最优值是原问题的最优值的下界。
-
对偶可行性 ：只有当 \( \lambda \) 和 \( \mu \) 趋于无穷大时，对偶函数才能给出原目标函数一个非平凡有意义的下界，这时的 \( \lambda \) 和 \( \mu \) 被称为对偶可行的。
应用拉格朗日对偶的步骤
-
构造 广义拉格朗日函数 ，包含原目标函数和所有约束条件。
-
对广义拉格朗日函数求 对偶问题 ，即最小化该函数，同时满足对偶约束条件。
-
解对偶问题，得到 对偶解 。
-
利用对偶解，回代到原问题中，得到原问题的 原解 。
鞍点解释
- 鞍点 ：在拉格朗日函数中，存在一个点，在该点上，目标函数和对偶函数都取得极值。这个点称为鞍点。
特殊情况
- 强对偶性 ：在某些情况下，即使原问题不满足Slater条件(即存在可行域内无界解的情况)，仍然可能是强对偶的。
结论
拉格朗日对偶提供了一种将复杂优化问题简化为更容易求解的对偶问题的方法，它在理论分析和实际应用中都有重要的作用。