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