拉格朗日松弛法是一种通过引入拉格朗日乘子，将部分约束转化到目标函数的一种方法。其主要作用在于：

（1）对于特定结构的问题（如线性规划），可以将所有约束全部放入拉格朗日函数（目标函数）当中，进而等效转化为决策拉格朗日乘子（对偶问题）；

（2）可以将求Min/Max问题转化为Max/Min问题，利于求上下界(Benders分解)，或将Min/Max结构转化为Min结构（两阶段法，主从问题）；

（3）使得解空间只和目标函数和系数矩阵相关，极点集合不变（Benders分解）；

（4）可以将耦合约束放入目标函数，从而实现对问题的解耦。（基于拉格朗日松弛法的UC问题求解）。

KKT条件

本文采用KKT条件来说明拉格朗日松弛法的基本框架，先简单介绍KKT条件。

KKT条件的核心：张紧的不等式约束可以当等式约束处理，不张紧的不等式约束没用。

配合下式可以说：假设最优解出现在其中n个g(x)上，那么他们可以被放到拉格朗日松弛目标函数中，其余的如果不满足约束说明假设错了，如果满足约束证明是一种可行解。

可以被转化为：

对于任意的X，要想使L满足要求()。考虑到g_i(X)≤0。问题就转化为求L关于的最大值。

这样，自然的可以写出KKT条件。

用等式2分情况，等式1尝试求解（对求梯度相当于加了等式约束），用不等式3、4验证是否求解正确。

若g_i(X*)等于0，说明约束张紧， 。若g_i(X*)不等于0，说明约束不起作用（满足时）， 。

为什么呢？

g_i(x)的梯度方向仍然是可行的。

求目标函数的最小值时，若目标函数的梯度方向与g_i(x)的梯度同向， 说明目标函数仍然可以继续下降，并没有取到最优值。

因此，

最小值需要整理为小于等与0的形式

（1）若,求无约束极值问题：

需要检查g_i(X*)是否小于0，若满足上式成立，一种可行解。

（2）若，

检查是否大于0，g₁(X*)是否小于0，都满足是一种可行解

拉格朗日松弛与对偶性

为方便表达，以线性规划为例说明问题。

将KKT条件的目标函数定义为拉格朗日松弛函数：

注意，如果不加KKT条件的相关约束，此时的仅仅是的下界（弱对偶性）。

如果问题满足KKT条件，对于原问题存在最优解x*，存在对应有：

因此有：

这个性质被称为强对偶性，如果用KKT条件证明，其成立条件等于KKT条件成立条件。

线性规划的对偶

根据上文的推导，如果问题是线性规划问题，相信大家都可以很轻松的找到其中一个

由于：

显然，对于而言， 每一个分量都大于等于0。(因为x≥0，若有小于0的分量，一定是负无穷)。假设满足条件，无论取条件内的什么值，此时x取0的拉格朗日函数的值一定大于等于取任何正数。

这时问题转化为如下形式：

即：

对偶问题的标准形式

针对上述的推导，我们进行一定的拓展：

（1）若原问题存在等式约束

KKT条件退化为拉格朗日松弛，不需要对进行限制

（2）若原问题存在自由变量

若想使L有界，需要对系数项置0，不等式约束转化为等式约束。

综上，对偶问题的转化关系如下：

原问题：

对偶问题:

参考资料

KKT参考链接: “https://zhuanlan.zhihu.com/p/556832103

---

本文转载自微信公众号：非功利者的功利人生

拉格朗日松弛法是一种通过引入拉格朗日乘子，将部分约束转化到目标函数的一种方法。其主要作用在于：

（1）对于特定结构的问题（如线性规划），可以将所有约束全部放入拉格朗日函数（目标函数）当中，进而等效转化为决策拉格朗日乘子（对偶问题）；

（2）可以将求Min/Max问题转化为Max/Min问题，利于求上下界(Benders分解)，或将Min/Max结构转化为Min结构（两阶段法，主从问题）；

（3）使得解空间只和目标函数和系数矩阵相关，极点集合不变（Benders分解）；

（4）可以将耦合约束放入目标函数，从而实现对问题的解耦。（基于拉格朗日松弛法的UC问题求解）。

KKT条件

本文采用KKT条件来说明拉格朗日松弛法的基本框架，先简单介绍KKT条件。

KKT条件的核心：张紧的不等式约束可以当等式约束处理，不张紧的不等式约束没用。

配合下式可以说：假设最优解出现在其中n个g(x)上，那么他们可以被放到拉格朗日松弛目标函数中，其余的如果不满足约束说明假设错了，如果满足约束证明是一种可行解。

可以被转化为：

对于任意的X，要想使L满足要求()。考虑到g_i(X)≤0。问题就转化为求L关于的最大值。

这样，自然的可以写出KKT条件。

用等式2分情况，等式1尝试求解（对求梯度相当于加了等式约束），用不等式3、4验证是否求解正确。

若g_i(X*)等于0，说明约束张紧， 。若g_i(X*)不等于0，说明约束不起作用（满足时）， 。

为什么呢？

g_i(x)的梯度方向仍然是可行的。

求目标函数的最小值时，若目标函数的梯度方向与g_i(x)的梯度同向， 说明目标函数仍然可以继续下降，并没有取到最优值。

因此，

最小值需要整理为小于等与0的形式

（1）若,求无约束极值问题：

需要检查g_i(X*)是否小于0，若满足上式成立，一种可行解。

（2）若，

检查是否大于0，g₁(X*)是否小于0，都满足是一种可行解

拉格朗日松弛与对偶性

为方便表达，以线性规划为例说明问题。

将KKT条件的目标函数定义为拉格朗日松弛函数：

注意，如果不加KKT条件的相关约束，此时的仅仅是的下界（弱对偶性）。

如果问题满足KKT条件，对于原问题存在最优解x*，存在对应有：

因此有：

这个性质被称为强对偶性，如果用KKT条件证明，其成立条件等于KKT条件成立条件。

线性规划的对偶

根据上文的推导，如果问题是线性规划问题，相信大家都可以很轻松的找到其中一个

由于：

显然，对于而言， 每一个分量都大于等于0。(因为x≥0，若有小于0的分量，一定是负无穷)。假设满足条件，无论取条件内的什么值，此时x取0的拉格朗日函数的值一定大于等于取任何正数。

这时问题转化为如下形式：

即：

对偶问题的标准形式

针对上述的推导，我们进行一定的拓展：

（1）若原问题存在等式约束

KKT条件退化为拉格朗日松弛，不需要对进行限制

（2）若原问题存在自由变量

若想使L有界，需要对系数项置0，不等式约束转化为等式约束。

综上，对偶问题的转化关系如下：

原问题：

对偶问题:

参考资料

KKT参考链接: “https://zhuanlan.zhihu.com/p/556832103

---

本文转载自微信公众号：非功利者的功利人生