问题背景
其背景源于在解决优化问题时，有时直接求解原问题较为困难，而通过构建其对偶问题，可能会带来新的视角和更简便的求解方法。
在实际应用中，对偶问题的出现往往是为了更好地理解和处理原问题。例如，在经济学中，对偶理论可以帮助解释生产者和消费者的行为；在工程领域，它有助于优化资源分配和设计系统。
从理论角度来看，对偶问题与原问题存在着紧密的关系，例如强对偶性和弱对偶性等性质。强对偶性在一定条件下成立，意味着原问题和对偶问题的最优值相等，这为求解最优解提供了重要的理论依据。
总之，对偶问题的提出为优化问题的研究和解决提供了有力的工具和思路，促进了数学优化理论的发展，并在众多实际领域中得到了广泛的应用。
求解步骤
求解步骤如下
- 求带约束的最小值问题
- 拉格朗日乘子法，将约束项乘以一个参数因子加到原函数中，得到拉格朗日函数
- 转化成一个先把x作为常数， λ、v作为参数的函数求最大值，再将结果作为自变量x求最小值
- 转换为对偶问题求解，先找到一个对偶函数，可以转换成先求关于x的梯度最小值，再求对偶问题最大值
拉格朗日松弛
拉格朗日松弛技术是一种用于求解约束规划的数学方法。
其基本原理是将目标函数中造成问题困难的约束吸收到目标函数中，并保持目标函数的线性，使问题更易求解。
对于一个标准化为求最小值的优化问题，它通过放松约束，有可能得到目标函数值更小的解，从而求得原问题的一个下界，这可为评价其他算法的有效性提供途径，也为原问题的求解提供更多信息。该方法常用于整数规划和混合整数规划中。
假设一个问题的约束可以分为两部分：一部分是和所有变量都有关的复杂约束$a$；另一部分$d$（例如$d_1$、$d_2$、$d_3$）只和某一部分变量有关。拉格朗日松弛就是将复杂约束$a$放到目标函数中。
为了便于理解，这里给出一个简单的例子。求解下面的数学规划问题：
$\min f(x)=x^2 -2x +1$ ，约束条件为 $x -5 \geq 0$
构造拉格朗日函数：$l(x,λ)=x^2 -2x +1 -λ(x -5)$，其中$λ$称为拉格朗日乘子，且$λ≥0$。
在$x -5 \geq 0$时，$l(x,λ)$的极小值不会高于$f(x)$的极小值，且某些$λ$的值可使$l(x,λ)$的极小值等于$f(x)$的极小值。通过求$l(x,λ)$的最小值来找到合适的$λ$。
对$l(x,λ)$求关于$x$的偏导数并令其等于$0$：$\frac{∂l}{∂x}=2x -2 -λ =0$，可得$x =1 + \frac{λ}{2}$。
将其带入$l(x,λ)$可得：$\min_{x≥5} l(x,λ)=-\frac{λ^2}{4} + 4λ$。
利用二次函数求极值的方法，可推出$λ =8$时，得到该式的极大值。
拉格朗日松弛有多种用途，例如在一些组合优化中，可以减少原问题中的一些约束（难约束），使问题求解难度降低。
在实际应用中，拉格朗日松弛算法包含两部分内容：一方面可提供原问题的下界（求解对偶问题）；另一方面可演变为拉格朗日松弛启发式算法。求解对偶问题时，常引入次梯度的概念，因为拉格朗日松弛后的目标函数关于拉格朗日乘子通常是一个分段线性函数。
使用拉格朗日松弛方法时需注意一些问题，例如尽量松弛掉使问题不可分的约束（linked/coupling constraints），以让不可分问题变为可分问题；松弛后的子问题应尽量简单，最好不是 NP-hard 问题或规模较小可暴力求解；不要过度松弛约束；拉格朗日松弛得到的是原问题的一个下界，可能是不可行解，通常还需要一个启发式算法将其修复为可行解等。
拉格朗日松弛方法在机组组合、资源分配、调度、供应链和设施选址等领域都有应用。它能够为复杂的优化问题提供一种有效的求解途径，帮助找到较好的近似解或下界。但具体应用时，需要根据问题的特点和实际需求进行合理的选择和调整。
FQA
为什么转化为对偶问题
这涉及到对偶问题的一个重要性质，即不管原问题是否为凸函数，它的对偶函数一定是凸函数。
强对偶和弱对偶
数学上的强对偶问题除了满足上述条件，还需要满足一个slater条件。这个凸优化问题才是一个强对偶关系。
slater条件
- https://zhuanlan.zhihu.com/p/514876504
KKT条件
KKT是非线性规划领域的重要成果，它是判断某点是极值点的必要条件。对于凸规划，KKT条件就是充要条件了，只要满足就是一定是极值点，且一定得到是全局最优解。