切割平面法
单位立方体与切割平面 x1+x2+x3≥ 2{displaystyle {displaystyle x_{1}+x_{2}+x_{3}geq 2}} 。 在三节点的旅行推销员问题中，该（弱）不等式表明每次旅行必须连接至少两个点。 在数学优化中， 切割平面法 是通过线性不等式对可行集或目标函数进行迭代性优化（即 切割 ）的优化方法的涵盖性术语。该过程通常用来发现混合整数线性规划（MILP）问题的整数解，也可以用来解决常规的、未必可微的凸优化问题。利用切割平面法求解 MILP 由 Ralph E. Gomory 引入。 MILP 的切割平面法通过将整数问题线性松弛为非整数线性问题，并对其进行求解，来求解 MILP 问题。线性规划理论说明，在温和的假定下（如果线性规划存在最优解，并且可行域不包含一条线），总存在一个极值点或顶点是最优的。 检验所获的最优解是否为整数解。如否，则必然存在一线性不等式将最优点和真可行集的凸包分离。找到这样的不等式是分离问题，而这样的不等式就是切割。 切割可以被加入到被松弛的线性规划中，使得当前的非整数解对松弛不再可行。该过程不断重复，直到找到最优整数解。 用于普遍的凸连续优化和变体的切割平面法有不同的名称： Kelley 法， Kelley-Cheney-Goldstein 法和捆绑法。它们常用于不可微的凸最小化问题。对于这类问题，通常的可微优化的梯度法无法使用，而使用这些方法可以高效地得到凸目标函数及其次梯度。这种情况最常出现在双拉格朗日函数的凹优化中。另一种常见情形是 Dantzig-Wolfe 分解应用于结构优化问题中，这类问题通常有含有指数级变量的表达式。通过延迟列生成法按需生成这些变量等同于在对应的对偶问题上切割平面。 目录 1 Gomory 切割 2 凸优化 3 另见 4 参考文献 5 外部链接 Gomory 切割 切割平面法由 Ralph Gomory 在 19 世纪 50 年代提出，用于解决整数规划和混合整数规划问题。然而，当时的大多数专家，包括 Gomory 自己都认为由于数值上的不稳定性，这种方法没有实际运用价值；同时由于求解过程中需要进行过多轮的切割，该方法可能是无效的。而在 19 世纪 90 年代中期，Gérard Corn...
