切割平面法 在数学优化中切割平面法是通过线性不等式对可行集或目标函数进行迭代性优化即切割的优化方法的涵盖性术语该过程通常用来发现混合整数线性规划MILP问题的整数解也可以用来解决常规的未必可微的凸优化问题利用切割平面法求解 MILP 由 Ralph E Gomory 引入 MILP 的切割平面法通过将整数问题线性松弛为非整数线性问题并对其进行求解来求解 MILP 问题线性规划理论说明在温和的假定下如果线性规划存在最优解并且可行域不包含一条线总存在一个极值点或顶点是最优的 检验所获的最优解是否为整数解如否则必然存在一线性不等式将最优点和真可行集的凸包分离找到这样的不等式是分离问题而这样的不等式就是切割 切割可以被加入到被松弛的线性规划中使得当前的非整数解对松弛不再可行该过程不断重复直到找到最优整数解 用于普遍的凸连续优化和变体的切割平面法有不同的名称 Kelley 法 KelleyCheneyGoldstein 法和捆绑法它们常用于不可微的凸最小化问题对于这类问题通常的可微优化的梯度法无法使用而使用这些方法可以高效地得到凸目标函数及其次梯度这种情况最常出现在双拉格朗日函数的凹优化中另一种常见情形是 DantzigWolfe 分解应用于结构优化问题中这类问题通常有含有指数级变量的表达式通过延迟列生成法按需生成这些变量等同于在对应的对偶问题上切割平面