![cover image](https://wikiwandv2-19431.kxcdn.com/_next/image?url=https://upload.wikimedia.org/wikipedia/commons/thumb/3/31/TSP_cutting_plane.png/640px-TSP_cutting_plane.png&w=640&q=50)
切割平面法
数学概念 / 維基百科,自由的 encyclopedia
在數學最佳化中,切割平面法是通過線性不等式對可行集或目標函數進行迭代性最佳化(即切割)的最佳化方法的涵蓋性術語。該過程通常用來發現混合整數線性規劃(MILP)問題的整數解,也可以用來解決常規的、未必可微的凸最佳化問題。利用切割平面法求解 MILP 由 Ralph E. Gomory 引入。
![](http://upload.wikimedia.org/wikipedia/commons/thumb/3/31/TSP_cutting_plane.png/640px-TSP_cutting_plane.png)
MILP 的切割平面法通過將整數問題線性鬆弛為非整數線性問題,並對其進行求解,來求解 MILP 問題。線性規劃理論說明,在溫和的假定下(如果線性規劃存在最佳解,並且可行域不包含一條線),總存在一個極值點或頂點是最佳的。 檢定所獲的最佳解是否為整數解。如否,則必然存在一線性不等式將最佳點和真可行集的凸包分離。找到這樣的不等式是分離問題,而這樣的不等式就是切割。 切割可以被加入到被鬆弛的線性規劃中,使得當前的非整數解對鬆弛不再可行。該過程不斷重複,直到找到最佳整數解。
用於普遍的凸連續最佳化和變體的切割平面法有不同的名稱: Kelley 法, Kelley-Cheney-Goldstein 法和捆綁法。它們常用於不可微的凸最小化問題。對於這類問題,通常的可微最佳化的梯度法無法使用,而使用這些方法可以高效地得到凸目標函數及其次梯度。這種情況最常出現在雙拉格朗日函數的凹最佳化中。另一種常見情形是 Dantzig-Wolfe 分解應用於結構最佳化問題中,這類問題通常有含有指數級變數的表達式。通過延遲列生成法按需生成這些變數等同於在對應的對偶問題上切割平面。