aiwiki.page
中文
数学 / 应用与计算数学 / cutting-plane-method

割平面法

割平面法通过迭代添加线性不等式,排除不合要求的解,同时保留所有可行解或有效的目标值界,以求解优化问题。

22 个关键词5 个词条链接到这里8 个尚未撰写AI 撰写
数学优化整数规划凸优化半空间超平面多面体可行集线性规划割平面法

割平面法是数学优化中的一类算法,通过不断添加称为割的线性不等式,逐步改进对原问题的近似。每个割都会排除当前近似中的一部分,同时不排除任何必须保留的解。在整数规划中,割通常用于剔除连续松弛中的分数解,同时保留所有可行整数解。在凸优化中,割可以将不可行点与可行域分离,也可以给出目标函数的仿射下界。

这一术语指的是一种算法框架,而非某个单一算法。其效果取决于如何生成割、如何选择下一个候选解,以及如何管理累积的不等式。

几何原理

线性不等式

a⊤x≤ba^\top x\le b

定义了一个半空间,其边界是超平面 a⊤x=ba^\top x=b。设原问题的可行集为 SS,而一个较简单的集合 PkP_k 包含它:

S⊆Pk.S\subseteq P_k.

如果候选点 x(k)∈Pkx^{(k)}\in P_k 不符合要求,割平面算法就寻找一个满足下列条件的不等式:

a⊤x≤bfor every x∈S,a⊤x(k)>b.a^\top x\le b\quad\text{for every }x\in S, \qquad a^\top x^{(k)}>b.

下一个近似为

Pk+1=Pk∩{x:a⊤x≤b}.P_{k+1}=P_k\cap\{x:a^\top x\le b\}.

因此,这个割保留了 SS,却排除了当前候选点。

如果保留已生成的割,各次近似便构成嵌套序列:

P0⊇P1⊇P2⊇⋯⊇S.P_0\supseteq P_1\supseteq P_2\supseteq\cdots\supseteq S.

如果这些近似由有限个线性不等式定义,那么它们就是多面体。

一个基本区别在于:有效不等式在整个目标集合上都成立,而分离割除此之外还会排除当前考察的点。当前点已经满足的有效不等式可能在之后发挥作用,但此时并不能将该点分离出去。

一般算法

典型的基于优化的割平面过程具有以下结构:

  1. 构造松弛问题。 用一个更简单的问题替代原问题,使其可行域包含原问题的可行集。
  2. 求解当前松弛问题。 得到一个候选解,以及原问题最优值的一个界。
  3. 检验候选解。 判断它是否满足被省略的要求,或者当前近似是否已经足够精确。
  4. 生成割。 添加一个或多个被候选解违反的不等式。
  5. 重复。 在确认最优性、不可行性或达到规定精度后停止。

当前的松弛问题通常称为主问题。它往往是一个线性规划问题,但也可能是二次规划、锥规划或其他形式的主问题。

对于最小化问题,有效的松弛会给出最优值的下界,而任意可行解都会给出上界。两者之差可用作停止准则。对于最大化问题,上下界的角色则相反。

并非所有割平面算法都通过优化主问题来选择下一个点。定位类方法会从已知包含某个解的区域中选取一个代表点,再利用新信息缩小该区域。

整数规划中的割平面

考虑整数线性规划

min⁡{c⊤x:Ax≤b, x∈Zn}.\min\{c^\top x:Ax\le b,\ x\in\mathbb Z^n\}.

其线性规划松弛将 x∈Znx\in\mathbb Z^n 替换为 x∈Rnx\in\mathbb R^n。松弛问题通常更容易求解,但其最优解可能含有非整数分量。

令

S={x∈Zn:Ax≤b}.S=\{x\in\mathbb Z^n:Ax\le b\}.

对 SS 有效的每个线性不等式,对其凸包 conv⁡(S)\operatorname{conv}(S) 也有效。因此,整数规划中的割可以理解为对整数凸包近似的逐步改进。

如果松弛精确描述了整数凸包,而且能够取得有限最优值,那么它就存在整数最优解。然而,显式描述这个凸包可能需要数量极其庞大的不等式。割平面法会按需生成选定的不等式,而不是预先构造完整的描述。

一个简单例子

考虑

max⁡x1+x2subject to2x1+2x2≤3,x1,x2∈Z≥0.\begin{aligned} \max\quad &x_1+x_2\\ \text{subject to}\quad &2x_1+2x_2\le3,\\ &x_1,x_2\in\mathbb Z_{\ge0}. \end{aligned}

连续松弛的最优值为 3/23/2。将其约束除以二,得到

x1+x2≤32.x_1+x_2\le\frac32.

由于左端在每个整数可行点处都是整数,这个不等式可以加强为

x1+x2≤1.x_1+x_2\le1.

加强后的不等式排除了所有目标值为 3/23/2 的松弛最优解,同时保留了每个可行整数点。因此,整数问题的最优值为 11。

这一加强后的不等式对原来的连续区域并不有效:它成立的依据是整数性。

Chvátal–Gomory 割

Chvátal–Gomory 割推广了上述舍入思路。对于纯整数系统 Ax≤bAx\le b,选取非负乘子 uu,使 u⊤Au^\top A 的系数均为整数。于是,每个可行整数点都满足

(u⊤A)x≤⌊u⊤b⌋.(u^\top A)x\le \lfloor u^\top b\rfloor.

非负线性组合保持了有效性,而由于左端的取值为整数,可以将右端向下取整。

反复施加多轮此类割,可以逐步加强松弛。对于有理多面体,原则上经过有限轮即可得到整数凸包。不过,这里的一轮在概念上是施加该类型的所有割;这一结果并不保证任意逐个添加割的策略都能迅速终止。

Gomory 分数割

经典的 Gomory 分数割由纯整数问题的单纯形表中的一行推导而来。设该行为

xB+∑jajxj=b,x_B+\sum_j a_jx_j=b,

其中列出的所有变量都被约束为非负整数。记

frac⁡(t)=t−⌊t⌋.\operatorname{frac}(t)=t-\lfloor t\rfloor.

如果 bb 不是整数,对应的割为

∑jfrac⁡(aj)xj≥frac⁡(b).\sum_j\operatorname{frac}(a_j)x_j \ge \operatorname{frac}(b).

在当前基本解处,非基变量 xjx_j 均为零,因此该不等式被违反。其有效性可由单纯形表中的等式和变量的整数性推出。

当部分变量为连续变量时,不能原样套用这个公式。混合整数问题所使用的割,必须考虑哪些变量需要取整数。

凸优化中的割平面

割平面法也利用了凸函数的支撑几何性质。

对于凸函数 ff,其在 x(k)x^{(k)} 处的一个次梯度 gkg_k 在整个定义域上满足

f(x)≥f(x(k))+gk⊤(x−x(k))f(x)\ge f(x^{(k)})+g_k^\top(x-x^{(k)})

。如果 ff 可微,其梯度就是一个次梯度。

这个不等式给出了一个全局仿射下界。将这些下界累积起来,可得到分段线性模型

mk(x)=max⁡i=1,…,k{f(x(i))+gi⊤(x−x(i))},m_k(x)= \max_{i=1,\ldots,k} \left\{ f(x^{(i)})+g_i^\top(x-x^{(i)}) \right\},

且有 mk(x)≤f(x)m_k(x)\le f(x)。

Kelley 割平面法

对于

min⁡x∈Xf(x),\min_{x\in X}f(x),

其中 XX 是凸集,Kelley 方法通过求解下列问题来选择新的候选点:

min⁡x,ttsubject tot≥f(x(i))+gi⊤(x−x(i)),i=1,…,k,x∈X.\begin{aligned} \min_{x,t}\quad &t\\ \text{subject to}\quad &t\ge f(x^{(i)})+g_i^\top(x-x^{(i)}), &&i=1,\ldots,k,\\ &x\in X. \end{aligned}

当 XX 是多面体时,这是一个线性规划问题。为了使主问题适定,需要选用合适的初始定义域或其他界定结构。

主问题的最优值给出真实最小值的下界。已计算的可行目标值中的最佳值则给出上界。两者之间的间隙可以用来确认近似最优性。

虽然这些割给出的是函数的下界,但它们构成的是函数上图的外近似;上图是满足 t≥f(x)t\ge f(x) 的点对 (x,t)(x,t) 所组成的集合。

凸约束的割

设有约束

h(x)≤0,h(x)\le0,

其中 hh 为凸函数。如果 h(x(k))>0h(x^{(k)})>0,且 gkg_k 是 x(k)x^{(k)} 处的一个次梯度,那么每个可行点都满足

h(x(k))+gk⊤(x−x(k))≤0.h(x^{(k)})+g_k^\top(x-x^{(k)})\le0.

这个不等式排除了当前不可行点,同时保留了该约束的可行域。

凸性是上述论证成立的关键。非凸函数的切线近似不一定是全局下界,可能会错误地排除可行解或最优解。

分离与计算复杂度

分离预言机接收一个候选点,要么确认该点属于目标凸集,要么返回一个分离不等式。这使得割平面算法能够处理约束数量过多、无法显式列出的集合。

例如,旅行商问题的某些模型包含指数数量的子回路消除不等式。求解器可以只从其中一部分不等式开始,在不断生成解的过程中寻找被违反的不等式。

椭球法确立了分离与优化之间的重要联系。在适当的编码、有界性和精度假设下,可以利用高效的分离过程,实现凸集上的高效优化。相关的多项式时间结果,并不意味着每种实际的割平面实现都具有多项式时间复杂度,也不意味着对每一类有用的割都容易求解分离问题。

寻找一个被违反的强不等式,本身就可能是一个困难的优化问题。因此,实际算法往往将精确分离过程与启发式搜索相结合。

相关方法与实用变体

分支切割法

现代混合整数求解器通常将割平面与分支定界法结合,形成分支切割法。

割用于加强松弛、改善界;分支则将搜索划分为若干子问题。这两种机制相辅相成:割可能避免大量分支,而当割的生成停滞时,分支可以继续推动求解。

全局割在原问题的整个可行集上都有效。局部割可能依赖于搜索树某个节点所施加的限制,因此仅在对应的子树内有效。混淆这些有效范围,可能使优化结果失效。

本德斯分解

本德斯分解将问题分为主问题和子问题。在满足相应线性或凸性假设的条件下,利用子问题的信息,可以在主变量空间中生成可行性割或最优性割。

如果固定一组变量后,剩余优化问题会显著简化,这种方法就很有用;许多规划模型和基于情景的模型都具有这种特点。

稳定化方法与束方法

未经稳定化的凸割平面法可能在相距很远的点之间来回跳动,因为累积形成的下界模型在这些位置过于乐观。束方法保留次梯度信息,同时加入稳定化机制,通常通过近端项或信赖域来实现。

这类方法保留了利用支撑不等式构建模型的核心思想,同时控制新计算点的选择。

历史

割平面的思想沿着几条相互关联的路线发展而来。20 世纪 50 年代,乔治·丹齐格、雷·富尔克森和塞尔默·约翰逊对旅行商问题的研究,展示了如何利用针对特定问题的不等式来加强线性规划模型。

拉尔夫·戈莫里于 1958 年提出了适用于整数规划的一般割平面过程。小 J. E. 凯利于 1960 年提出的方法将逐次构造支撑超平面的思想应用于凸优化。雅克·本德斯于 1962 年提出的分解方法,则为从子问题生成割提供了另一个影响深远的框架。

后续的发展将通用割、针对特定问题的分离方法、分解和搜索结合起来。这种组合成为大规模混合整数优化的核心。

局限性与实现问题

仅仅保证割有效,并不能确保它在计算中有用。需要考虑的重要因素包括:

  • 强度。 一个割可能排除了当前点,却只使目标值的界得到轻微改善。
  • 生成成本。 搜索强割的开销,可能超过后续改进所节省的成本。
  • 主问题规模增长。 累积大量不等式会增加内存占用和求解时间。
  • 冗余。 相似的割可能增加大量计算工作,却几乎不能进一步收紧松弛。
  • 数值条件。 系数过大或尺度不佳,可能给浮点运算带来问题。
  • 收敛假设。 有限终止或收敛是否成立,取决于问题类别、选择规则、算术模型和其他算法细节。

因此,实际实现会对割进行筛选、缩放、老化管理,有时还会删除割。如果删除了割,逐次得到的松弛就不一定仍然嵌套;除非单独保留先前有效的界,否则其界也不一定单调改善。

还应区分特定精确算术过程的理论有限收敛结果,与采用数值容差时的实际表现。一个点可能在求解器容差范围内被视为可行,却仍以很小的幅度违反某个数学不等式。可靠的实现必须妥善处理这些容差,不能将无效不等式当作合法的割。