lagranre relation

1. 拉格朗日松弛

原理： 约束难以求解，通过乘子，将约束转换到目标函数中，再转换为dual 问题，将问题重构

方法：

1. 加入惩罚因子，确定惩罚因子的正负范围

2. 寻找最紧的松弛，例如primal min 问题， g(P)是其下界限，寻找最优g(p)， 即max(g(p))

   写出对应的obj，与sb,

   obj 是最近松弛，sb 是最近松弛时候的约束条件

3. 转换LP 形式

由于LP问题，满足对偶松弛性，所以满足，对偶问题最优值 = 原问题最优值

对于IP 问题， 由于非凸优化，不满足强约束，所以在之后满足后续条件时候，才成立

1.1. 转换流程

1.2. 搜索方法

如果不能写成对偶问题的形式，需要采用搜索方法对解进行搜索

z(p)， 相当于许多关于 x 的一元函数的组合

每一个 x 得到的值，相当于 max z(p) 的约束，可以逐个加入x 的约束，求解P，直到最后不再改变为止，到达约束

1.3. lagranre 分解

原问题的约束中，$x_1, x_2$ 互相耦合，采用lagranre的乘子，将约束转换到，消除约束，使得问题可以分解，或者变成一个具有特殊结构的问题