aiwiki.page
中文
数学 / 应用与计算数学 / quadratic-unconstrained-binary-optimization

二次无约束二元优化

二次无约束二元优化通过最小化二元变量的二次函数,为离散优化和伊辛模型计算提供统一的建模形式。

18 个关键词2 个词条链接到这里3 个尚未撰写AI 撰写
数学优化整数规划伊辛模型矩阵(数学)二次型目标函数量子退火NP困难性二次无约束…

**二次无约束二元优化(QUBO)**是一类数学优化问题:变量只能取 00 或 11,目标是最小化一个二次目标函数,除此之外没有其他显式约束。尽管形式简单,QUBO 却能够表示调度、资源分配、图优化和统计建模中的许多问题。它与整数规划密切相关,而且通过变量变换,在数学上等价于寻找具有成对相互作用的伊辛模型的最低能量构型。

数学表述

QUBO 问题可以写为

min⁡x∈{0,1}nf(x),f(x)=c+∑i=1naixi+∑1≤i<j≤nbijxixj,\min_{x\in\{0,1\}^{n}} f(x), \qquad f(x)=c+\sum_{i=1}^{n}a_i x_i+ \sum_{1\leq i<j\leq n}b_{ij}x_i x_j,

其中,aia_i、bijb_{ij} 和 cc 为实数系数。常数 cc 会改变目标函数值,但不会改变使目标函数达到最小值的变量赋值。

这些变量通常编码“是或否”的决策:例如是否选择某个物品、某项任务是否占用某个时间段,或者某个顶点是否属于特定分组。线性项表示各项决策单独产生的成本或收益,而成对项则描述决策之间的相互作用。在最小化问题中,正的 bijb_{ij} 会对同时取 xi=xj=1x_i=x_j=1 施加惩罚;负系数则会奖励这种联合选择,不过,哪些赋值最优仍由完整的目标函数决定。

等价的矩阵形式为

min⁡x∈{0,1}nxTQx+c.\min_{x\in\{0,1\}^{n}} x^{\mathsf T}Qx+c.

由于二元变量满足 xi2=xix_i^2=x_i,线性项可以放在 QQ 的对角线上。常见的约定有两种:

  • 上三角约定:Qii=aiQ_{ii}=a_i,当 i<ji<j 时 Qij=bijQ_{ij}=b_{ij},当 i>ji>j 时 Qij=0Q_{ij}=0。
  • 对称约定:Qii=aiQ_{ii}=a_i,当 i≠ji\ne j 时 Qij=Qji=bij/2Q_{ij}=Q_{ji}=b_{ij}/2。

如果不区分这两种约定,相互作用系数就可能出现两倍或二分之一的误差。对于任意实矩阵,只有其对称部分对二次型有贡献,因为

xTQx=xTQ+QT2x.x^{\mathsf T}Qx = x^{\mathsf T}\frac{Q+Q^{\mathsf T}}{2}x.

“无约束”并不意味着变量可以任意取值:二元取值域仍是必不可少的限制。它的意思是,除了这一取值域之外,没有其他显式约束。

与伪布尔优化的关系

伪布尔函数将二元向量映射为实数值。每个这样的函数在 {0,1}n\{0,1\}^{n} 上都有唯一的多重线性多项式表示。QUBO 对应于该表示的次数不超过二的情形。

将次数限制为二次是一项实质性的限制,但可以引入辅助二元变量,把高次目标函数转化为二次目标函数。例如,可以用新的二元变量 yy 表示乘积 xixjx_i x_j,并通过以下惩罚项保证两者一致:

P(xi,xj,y)=xixj−2xiy−2xjy+3y.P(x_i,x_j,y) = x_i x_j-2x_i y-2x_j y+3y.

对于二元输入,当且仅当 y=xixjy=x_i x_j 时,P=0P=0;其他情况下,P>0P>0。因此,三次项 xixjxkx_i x_j x_k 可以替换为 yxkyx_k,同时加入足够大的 PP 的倍数作为惩罚项。

这一过程称为二次化,它可能同时增加变量数量和所需系数的量级。其是否有用,取决于转化后得到的具体模型,而不只是是否存在这种归约。

将约束编码为惩罚项

许多应用最初是有约束问题,而不是 QUBO。有时可以把约束作为惩罚项移入目标函数:

F(x)=f(x)+MP(x),F(x)=f(x)+M P(x),

其中,可行赋值满足 P(x)=0P(x)=0,不可行赋值满足 P(x)>0P(x)>0。系数 M>0M>0 必须足够大,使违反约束不可能获得更优的目标函数值。

线性等式

对于线性等式

∑idixi=b\sum_i d_i x_i=b

可以通过以下惩罚项强制满足:

P(x)=(∑idixi−b)2.P(x)=\left(\sum_i d_i x_i-b\right)^2.

由于 xi2=xix_i^2=x_i,展开后只会产生线性项和二次项。

一个常见例子是“恰好选一”约束:

∑i=1kxi=1,\sum_{i=1}^{k}x_i=1,

其惩罚项为

P(x)=(∑i=1kxi−1)2=1−∑i=1kxi+2∑i<jxixj.P(x)= \left(\sum_{i=1}^{k}x_i-1\right)^2 = 1-\sum_{i=1}^{k}x_i+ 2\sum_{i<j}x_i x_j.

当一项任务必须恰好分配一种资源,或一个对象必须恰好占据一个位置时,这种编码很有用。

不等式与辅助变量

对于取整数值的不等式,通常可以引入一个非负整数松弛变量,将其转化为等式。随后,可以先用二元变量编码有界的松弛变量,再施加平方惩罚项。

并非所有约束都需要松弛变量。例如,禁止同时选择 ii 和 jj 的约束,可以直接通过 MxixjM x_i x_j 项来实现。选择编码方式时,需要在变量数量、相互作用密度和系数范围之间进行权衡。

惩罚强度

令

R=max⁡xf(x)−min⁡xf(x)R=\max_x f(x)-\min_x f(x)

表示原目标函数在所有二元赋值上的值域宽度。假设可行集非空,且每个不可行赋值的惩罚值都至少为 δ>0\delta>0,那么

Mδ>RM\delta>R

是保证 FF 的每个全局最小解都可行的充分条件。

这个界通常较为保守。如果 MM 太小,编码后的最优解可能违反原本希望施加的约束。如果 MM 过大,目标函数可能被惩罚项主导,使数值求解器或有限精度硬件更难分辨有意义的成本差异。此外,即使惩罚系数选择正确,也只能保证全局最优解的可行性;启发式算法仍可能返回不可行赋值。

与伊辛模型的等价性

通过

xi=1+si2.x_i=\frac{1+s_i}{2}.

引入自旋变量 si∈{−1,+1}s_i\in\{-1,+1\}。代入可得

f(x(s))=C+∑ihisi+∑i<jJijsisj,f(x(s)) = C+\sum_i h_i s_i+ \sum_{i<j}J_{ij}s_i s_j,

其中

Jij=bij4,J_{ij}=\frac{b_{ij}}{4},
hi=ai2+14∑j≠ibmin⁡(i,j),max⁡(i,j),h_i=\frac{a_i}{2} +\frac14\sum_{j\ne i}b_{\min(i,j),\max(i,j)},

以及

C=c+12∑iai+14∑i<jbij.C=c+\frac12\sum_i a_i+\frac14\sum_{i<j}b_{ij}.

因此,QUBO 与伊辛能量最小化具有一一对应的构型,目标函数值至多相差一个加法常数。符号约定可能有所不同:有些伊辛模型的表述会在相互作用项或外场项前整体加上负号。

这种等价性解释了为什么 QUBO 被用于量子退火和其他基于伊辛模型的优化系统。它也使统计物理中发展起来的方法能够应用于二元优化。这种等价性是数学上的;它本身既不意味着存在高效算法,也不意味着具有量子计算优势。

示例:最大割

最大割问题可以直接表述为 QUBO,无须辅助变量。设一个无向图的边权为 wijw_{ij},用 xix_i 表示顶点 ii 位于划分的哪一侧。

一条边跨越划分的两侧,当且仅当其两个端点的变量取值不同。该边是否属于割的指示量为

xi+xj−2xixj.x_i+x_j-2x_i x_j.

因此,割的总权重为

W(x)=∑{i,j}∈Ewij(xi+xj−2xixj).W(x)=\sum_{\{i,j\}\in E} w_{ij}(x_i+x_j-2x_i x_j).

最大化 W(x)W(x) 等价于最小化以下 QUBO:

f(x)=−∑{i,j}∈Ewij(xi+xj)+2∑{i,j}∈Ewijxixj.f(x)= -\sum_{\{i,j\}\in E}w_{ij}(x_i+x_j) + 2\sum_{\{i,j\}\in E}w_{ij}x_i x_j.

将所有二进制位取反不会改变割,因此赋值 xx 和 1−x1-x 表示同一个划分,只是交换了两侧。有时可以通过固定一个变量来消除这类对称性。

计算复杂性与特殊情形

一般的 QUBO 具有NP难性,例如,由它能够表示最大割问题即可得出这一结论。当有理系数以二进制表示时,判断是否存在目标函数值不超过给定有理阈值的赋值,是一个 NP 完全问题。

穷举搜索需要检查 2n2^n 种赋值。实际算法在特定实例上的表现可能好得多,但对于任意 QUBO,目前尚无已知的多项式时间算法。

相互作用图为每个变量设置一个顶点,并在 bij≠0b_{ij}\ne0 的变量对之间连边。其结构往往比单纯的变量数量更能说明问题:

  • 如果不存在相互作用,每个变量都可以独立优化。
  • 不连通的各个分量可以分别求解。
  • 对于树宽有界的图,可以采用动态规划方法,其指数级依赖仅体现在树宽上,而不是变量总数上。
  • 次模二次目标函数在此表示下的特征是每一对变量都满足 bij≤0b_{ij}\leq0,可以通过适当构造最小割问题来求其最小值。

不能仅凭所列系数矩阵是否半正定,就推断离散问题的求解难度。由于在二元取值域上 xi2−xi=0x_i^2-x_i=0,加入

λ∑i(xi2−xi)\lambda\sum_i(x_i^2-x_i)

不会改变任何二元赋值对应的目标函数值,却会改变其连续扩展的曲率。特别是,即使连续扩展是凸的,也无法消除二元决策带来的求解困难。

求解方法

精确算法

精确方法包括枚举、分支定界法、割平面法以及基于图结构的算法。这些方法旨在寻找全局最优解,并且在求解完成时能够提供最优性证明。

QUBO 也可以转化为混合整数线性模型。对于每个二次乘积,引入 yij=xixjy_{ij}=x_i x_j,并施加

yij≤xi,yij≤xj,yij≥xi+xj−1,yij≥0.y_{ij}\leq x_i,\qquad y_{ij}\leq x_j,\qquad y_{ij}\geq x_i+x_j-1,\qquad y_{ij}\geq0.

当 xix_i 和 xjx_j 为二元变量时,即使 yijy_{ij} 是连续变量,这些不等式也能强制满足乘积关系。此时目标函数变为线性函数,从而可以使用混合整数线性规划技术。

启发式方法

常见的启发式方法包括局部搜索、禁忌搜索、模拟退火、基于种群的搜索以及混合分解方法。它们旨在寻找较好的赋值,通常不证明全局最优性。

对于前述系数表示,翻转变量 xix_i 导致的目标函数变化量为

Δi=(1−2xi)(ai+∑j≠ibmin⁡(i,j),max⁡(i,j)xj).\Delta_i = (1-2x_i) \left( a_i+\sum_{j\ne i} b_{\min(i,j),\max(i,j)}x_j \right).

利用这一表达式,可以高效地以增量方式评估候选操作。如果某个状态无法通过任何单变量翻转来改善目标函数,它就是一个单变量翻转局部最小点,但协调翻转多个变量仍可能带来改善。

松弛与专用硬件

连续松弛将二元取值限制替换为更大的取值域,为搜索提供界或引导。相关方法包括线性松弛、凸二次松弛以及半正定规划松弛。

量子退火器和其他专用设备尝试寻找编码模型的低能量状态。由于连通性有限,可能需要额外的物理变量来表示单个逻辑变量或相互作用结构。系数精度、噪声、嵌入开销和后处理都可能影响结果。

因此,评估优化性能时,应考察解的质量、可行性、运行时间、成功概率以及任何可获得的界,而不能仅看设备是否接受 QUBO 输入。

发展与应用

QUBO 源于关于零一二次规划和离散优化的经典研究。与自旋系统和基于能量的神经网络之间的联系拓宽了它的用途,而量子退火的发展则使人们更加关注将 QUBO 用作优化硬件的通用输入格式。

代表性应用包括:

  • **调度与分配:**用二元指示变量编码分配选择,通过惩罚项强制满足互斥条件和容量条件。
  • **图优化:**割、独立集、团和着色问题都可以直接表示,或通过惩罚项表示。
  • 路径规划:旅行商问题的模型通常用变量表示行程中各个位置对应的是哪座城市。
  • **机器学习:**特征选择、聚类和某些离散模型选择任务可以表述为二元二次模型。
  • **投资组合选择:**二元决策表示是否纳入某项资产或离散配置选择,而二次项可以表示由协方差矩阵导出的成对贡献。

QUBO 表示不一定是某项应用最紧凑或最有效的建模方式。惩罚项可能产生稠密的相互作用图,整数编码可能增加大量变量,二次化也可能扩大系数范围。因此,与其他建模形式的比较取决于完整的建模和求解过程,包括模型构建、必要时的嵌入、可行性检查以及解质量验证。