割平面法

割平面法（cutting-plane method）逐步加入有效线性不等式，缩小仍可能包含解的区域，或建立目标函数的分段线性下界。这里讨论凸优化中的切面构造及可验证的上下界；整数规划中的有效不等式也称割平面，但“保留哪些点”的依据需要按模型另行说明。

切线给出的信息是全局下界

设 $C\subset {ℝ}^n$ 为非空紧凸集，$f$ 在其邻域为凸函数，且在查询点 $x_i\in C$ 能得到次梯度 $g_i\in \partial f(x_i)$。次梯度的含义就是对每个 $z\in C$ 都有 $$f(z)\ge f(x_i)+g_i^{𝖳}(z-x_i)=:{\ell }_i(z).$$ 把已有切面取最大，得到 $q_k(z)=\underset{1\le i\le k}{max}{\ell }_i(z)\le f(z)$。用上图形式引入标量 $t$，求解 $$L_k=\underset{z\in C,t}{min}t\text{使得}t\ge {\ell }_i(z)(i=1,\dots ,k).$$ 若 $C$ 是多面体，这是线性规划。已评价点中的最好目标值记作 $U_k=\underset{i}{min}f(x_i)$。两类信息一低一高地夹住真实最优值。

三次评价夹住一个抛物线的最小值

取 $C=[-1,3]$，$f(x)=(x-1{)}^2$。先在 $x_1=-1$ 评价，得 $f=4,g=-4$，切面为 ${\ell }_1(x)=-4x$。单切面在区间内的最小点为三，故当前下界 $L_1=-12$，上界 $U_1=4$。

包络 q₂ 在 x=1 的值为 −4，仍低于原函数的最小值零。

接着评价 $x_2=3$，得到 $f=4,g=4$，新切面为 ${\ell }_2(x)=4x-8$。两直线相交于 $x=1$，最大包络在该点取最小值 $-4$。于是 $L_2=-4,U_2=4$。注意负的下界完全合法，虽然本例的原目标非负：下界只须不超过真实目标，不必满足目标本身的其他性质。

第三次在 $x_3=1$ 评价，得到 $f=0,g=0$，增加水平切面 ${\ell }_3=0$。此时包络的最小值为零，已有点也达到零，故 $L_3=U_3=0$。图中第三条线抬高下界；不是把抛物线附近的一整段可行点从 $C$ 中删掉。

第三次查询提供水平切面，使下界与已知可行值同时为零。

上下界不变量及停止证据

记原问题最优值为 $f^{\ast }=\underset{C}{min}f$；连续性和紧性保证其存在。由于 $q_k(z)\le f(z)$ 对所有 $z\in C$ 成立，取各自最小值便得 $L_k\le f^{\ast }$。已知查询点可行，故 $f^{\ast }\le U_k$。新加切面只会抬高或保持包络，所以 $L_{k+1}\ge L_k$；增加候选点只会使 $U_{k+1}\le U_k$。因此始终保持 $$L_k\le f^{\ast }\le U_k.$$ 若 $U_k-L_k\le \epsilon$，达到 $U_k$ 的可行点就是绝对目标误差不超过 $\epsilon$ 的解。这一论证覆盖任意有效切面和可行查询点。它并不单独证明任意选点策略都能缩小差距；重复查询同一点就可能没有新进展。实际定位算法用中心选择、稳定化等规则来控制进度。

若要处理凸约束 $h(z)\le 0$，在违反约束的点 $x$ 取其次梯度 $a$。每个真正可行的 $z$ 都满足 $h(x)+a^{𝖳}(z-x)\le h(z)\le 0$，因此该线性不等式有效。目标切面放在上图变量中，约束切面直接限制决策变量，二者不要混写。

凸性失去后的反例与变式

对非凸 $f(x)=-x^2$，在零点的切线是零，但 $f(1)=-1<0$。把它当作全局下界会抬得过高，进而给出错误最优性证书。一般光滑函数有切线，并不足以保证切面有效。

变式把查询区间改为 $[2,3]$，仍用原来的抛物线。先在二处评价：$f=1,g=2$，切面为 $2x-3$。它在新区间最小值为一，正好等于已知点的目标值，所以一次评价就证明最优解为二。这里最优点在边界，梯度不必为零。

一维包络子问题的标准库实现

下例输入一维区间和初始查询点，输出查询值、上下界。函数不改写输入，所有数据都是新建列表。线性包络在区间内是分段线性的；最小值可在端点或两条非平行直线的交点取得，若整段平坦，端点也能代表。因此枚举这些候选足以精确解本例的子问题。$k$ 条切面产生 $O(k^2)$ 个候选，每个评价包络花 $O(k)$，故本教学实现每轮为 $O(k^3)$，当前轮显式保存候选还需 $O(k^2)$ 额外空间，不适合替代高维线性规划求解器。

Python 3

def cutting_plane(a=-1.0, b=3.0, first=-1.0, budget=10):
    if not a < b or not a <= first <= b or budget < 1:
        raise ValueError("invalid interval, initial point or budget")
    cuts, trace, upper, x = [], [], float("inf"), float(first)
    for _ in range(budget):
        f, g = (x-1)**2, 2*(x-1)
        cuts.append((g, f-g*x))
        upper = min(upper, f)
        candidates = [float(a), float(b)]
        for i, (u,v) in enumerate(cuts):
            for r,s in cuts[:i]:
                if u != r:
                    z = (s-v)/(u-r)
                    if a <= z <= b:
                        candidates.append(z)
        envelope = lambda z: max(u*z+v for u,v in cuts)
        next_x = min(candidates, key=envelope)
        lower = envelope(next_x)
        trace.append((x,f,lower,upper))
        if upper-lower <= 1e-12:
            return trace
        x = next_x
    return trace

for row in cutting_plane():
    print(row)
assert cutting_plane(2,3,2)[-1] == (2.0,1.0,1.0,1.0)

输出的 (查询点, 目标, 下界, 上界) 依次是 (-1,4,-12,4)、(3,4,-4,4)、(1,0,0,0)；误差容限检查的是证书差距，不是两次查询点的距离。