4.1 处理约束问题

1. 引言

到目前为止所说明的QUBO模型，本质上是一个无约束优化问题：

$$\underset{x\in \{0,1{\}}^n}{min}(\sum _{i=1}^n{c}_i{x}_i+\sum _{i<j}{q}_{ij}{x}_i{x}_j)={\mathbf{x}}^{T}Q\mathbf{x}$$

对于绝大多数实际问题而言，求解该问题的最优化解都存在着必须满足的约束。

比如，投资资金的分配问题，其主要目的是让投资回报达到最大化。不过，在这个过程中有一系列的约束条件——总预算不能超过1000万元（限制了投资的总体规模）；每个项目至少要分配50万元（确保每个项目都有足够的资金支持）；还要受到行业政策的限制，例如能源项目必须符合碳排放指标，不能超过规定的碳排放量（$E_{max}$）等等。将这个例子用数学形式表述，可以写成：

$$\begin{array}{rl}max& \sum _{i=1}^n{r}_i{x}_i\\ \text{s.t.}& \sum _{i=1}^n{x}_i\le 1000\\ & x_i\ge 50\mathrm{\forall }i\\ & \sum _{j\in \mathcal{E}}{c}_j{x}_j\le E_{\text{max}}\\ & x_i\ge 0\mathrm{\forall }i.\end{array}$$

在实际的优化过程中，这些约束条件可以分为硬约束和软约束。硬约束是必须严格遵守的，例如TSP（旅行商问题）中每个城市只能访问一次；软约束则可以通过调整目标函数来处理，例如通过惩罚函数来体现对某些约束的违反程度。通常来说，可以使用拉乘、惩罚法或者直接构造可行域等方法，将这些约束条件整合到优化模型中，从而找到最优解。

转换的思想很简单，假设我们的目的是计算目标函数的最小值，那么我们可以在目标函数上增加一个非负的惩罚函数（设计为关于决策变量的二次函数形式），也即Penalty Method（惩罚法）。用户可以使用Kaiwu SDK进行约束的惩罚法转换，通过将约束条件转化为惩罚项加入目标函数，从而避免直接求解带约束的优化问题，可以有效重构QUBO模型。

考虑到有约束优化问题一般使用惩罚法进行无约束形式的转换，所以本篇将详细讲述惩罚法在QUBO模型中的应用，特别是如何处理等式约束和不等式约束。

2. 数学表述

由于惩罚项只是原优化问题的约束条件，而不是最优化目标，因此Penalty Method所引入的惩罚项被设计为：

（1）如果当前解满足约束，那么惩罚函数的值等于0；

（2）如果当前解不满足约束，那么惩罚函数是一个很大的正数。

P是一个很大的正数，如果违反约束的话，目标函数会受到一个很大的惩罚，以至于我们最终得到的解会倾向于符合约束。

给定优化问题：

$$\begin{array}{rl}min& f(\mathbf{x})\\ \text{s.t.}& g_i(\mathbf{x})\le 0(i=1,2,...,m)\\ & h_j(\mathbf{x})=0(j=1,2,...,n)\\ & x_k\in \{0,1\}(k=1,2,...,d)\end{array}$$

可以通过惩罚法转化为无约束优化问题：

$$min\mathcal{L}(\mathbf{x},P)=f(\mathbf{x})+P\cdot \sum _{i=1}^m{\varphi }_i(g_i(\mathbf{x}))+P\cdot \sum _{j=1}^n{\psi }_j(h_j(\mathbf{x}))$$

其中，$f(\mathbf{x})$表示优化问题的目标函数；${\varphi }_i(g_i(\mathbf{x}))$为不等式约束惩罚项，即仅当$g_i(\mathbf{x})>0$（违反约束）时产生惩罚，本文主要采用松弛变量法处理不等式约束；

${\psi }_j(h_j(\mathbf{x}))$为等式约束惩罚项，满足${\psi }_j(h_j(\mathbf{x}))=h_j(\mathbf{x}{)}^2$ 即对等式约束的任何偏离$h_j(\mathbf{x})\ne 0$均施加惩罚；

最后，$P>0$控制约束违反的惩罚强度。对于一个有约束优化问题同时存在多个约束的情况，只需将其约束转换成惩罚项形式后，在不等式后直接逐一相加即可。

3. 常见约束类型的具体表达

惩罚法的基本思想是，将约束条件转化为惩罚项，并将惩罚项加入目标函数中。对于违反约束的解，惩罚项会增加目标函数的值，从而使优化算法倾向于找到满足约束的解。现实应用中，最常见的两种约束就是等式约束和不等式约束，下面我们将重点介绍如何对各类约束进行转换。

3.1 线性等式约束情况

原始约束为：

$$\sum _{i=1}^n{a}_i{x}_i=b$$

其QUBO形式的惩罚项可以写为：

$$P\cdot {(\sum _{i=1}^n{a}_i{x}_i-b)}^2$$

展开后可得：

$$P(\sum _{i=1}^n{a}_i^2{x}_i+2\sum _{i<j}{a}_i{a}_j{x}_i{x}_j-2b\sum _{i=1}^n{a}_i{x}_i+b^2)$$

其中常数项$b^2$可忽略，不影响优化方向。这种情况下，无论约束违反方向如何（正偏差或负偏差），平方项均施加相同惩罚，符合等式约束的对称性要求；并且平方函数在实数域上光滑可导，便于优化算法处理。

例子： 原始约束为$x_1+x_2+x_3=2$，对其展开后为二次项：

$$P\cdot {(x_1+x_2+x_3-2)}^2=P\cdot (x_1^2+x_2^2+x_3^2+4-4x_1-4x_2-4x_3+2x_1{x}_2+2x_1{x}_3+2x_2{x}_3)$$

由于$x_i$为二进制，$x_i^2=x_i$，化简为：

$$P\cdot (x_1+x_2+x_3+4-4x_1-4x_2-4x_3+2x_1{x}_2+2x_1{x}_3+2x_2{x}_3)$$

3.2 线性不等式约束

不等式约束通常表示为$g(\mathbf{x})\le 0$，也即“不超过”、“不少于”等等约束。例如，“某工厂需在总用电量不超过1000度的前提下，优化5台机器的运行时间以最大化产量”。为了将这种约束转化为惩罚项，可以引入松弛变量$s$，从而将不等式约束转化为等式约束形式。

假设原始约束为：

$$\sum _{i=1}^n{a}_i{x}_i-b\le 0$$

我们可以引入松弛变量$s$并且保证$s\ge 0$，将其转化为等式约束：

$$\sum _{i=1}^n{a}_i{x}_i-b+s=0$$

$s$代表约束的违反程度。其QUBO形式的惩罚项可以构造为：

$$P{(\sum _{i=1}^n{a}_i{x}_i+s-b)}^2$$

其中$P$是惩罚因子，控制松弛变量对目标函数的影响。如果$\sum _{i=1}^n{a}_i{x}_i-b>0$，则松弛变量$s$的值将大于零，惩罚项也会增加，从而使得违反约束的解在优化过程中不被优先选择。

为了使目标函数符合QUBO的标准形式，我们需要将松弛变量$s$转化为二进制变量。如果松弛变量$s$是一个整数变量（例如$s\in {\mathbb{Z}}^{+}$），可以通过二进制编码方法将其表示为一组二进制变量，即$s=\sum _{k=0}^m{2}^k{s}_k$，其中$s_k\in \{0,1\}$。此时，原惩罚项可以展开为：

$$P{(\sum a_i{x}_i+\sum 2^k{s}_k-b)}^2$$

这样修改后，目标函数就变成了一个包含二进制变量的二次型表达式，符合QUBO问题的标准形式。

3.3 逻辑约束的代数表达

实际上，以上两种情况已经能解决大部分问题，但为了更好地解释一部分非常重要也非常常用的约束情况——逻辑约束，这里对此类约束进行归纳总结。

（1）蕴含关系

假设原始约束为

$$x_1\to x_2(\text{若}{x}_1=1\text{，则}{x}_2=1)$$

其QUBO形式的惩罚项可以写为：

$$P\cdot x_1(1-x_2)=P\cdot (x_1-x_1{x}_2)$$

比如，若某设备启用（$x_1=1$），则其配套安全系统必须激活（$x_2=1$）。

（2）互斥约束

假设原始约束为： $x_1+x_2\le 1$，此处表示$x_1$和$x_2$不能同时为1，其QUBO形式的惩罚项可以写为：

$$P\cdot x_1{x}_2$$

当$x_1=x_2=1$时惩罚项为$P$

比如，某会议时间不能同时选择两个冲突的演讲主题（$x_1$和$x_2$不能同时为1）。

（3）逻辑或约束

同样地，对于至少有一个1的约束$x_1+x_2\ge 1$，可以构造

$$(1-x)(1-y)=1-x-y+xy$$

使得QUBO形式的惩罚项可以写为：

$$P\cdot (1-x-y+xy)$$

当$x_1=x_2=0$时惩罚项为$P$

比如，某岗位招聘需至少满足 “有编程经验”（$x_1$）或 “有数学背景”（$x_2$）。

（4）依赖关系

假设原始约束为 $x_1+x_2\ge x_3$ ，表示若$x_3=1$，则$x_1$或$x_2$至少一个为1，则其QUBO形式的惩罚项可以写为：

$$P\cdot x_3(1-x_1-x_2)=P\cdot (x_3-x_1{x}_3-x_2{x}_3)$$

比如，若某项目需审批通过（$x_3=1$），则需至少有一个部门负责人签字（$x_1$或$x_2$为 1）。

（5）异或关系

异或（XOR）关系表示两个变量必须不同，即$x_1\ne x_2$。其 QUBO 形式的惩罚项可构造为：

$$P\cdot (x_1-x_2{)}^2=P\cdot (x_1^2-2x_1{x}_2+x^2)$$

此时当$x_1\ne x_2$时，惩罚项为 $P$；当 $x_1=x_2$时，惩罚项为0。

比如，某产品设计必须选择A供应商或B供应商，但不能同时选择两者（$x_1\ne x_2$）。

（6）其他

存在其它类型约束，如Rosenberg提出的通过引入辅助变量，构造惩罚项。当需要降次时，会用到该约束形式，在后篇的《处理降次问题》中将深入讨论这一问题。

对任意三次项$y_i{y}_j{y}_k$，引入辅助变量$q_{ij}=y_i{y}_j$，则原三次项变为二次项 $q_{ij}{y}_k$，添加惩罚项：

$$P(q_{ij},y_i,y_j)=3q_{ij}-2q_{ij}{y}_i-2q_{ij}{y}_j+y_i{y}_j$$

最终目标函数表示为：

$$q_{ij}{y}_k+\lambda P(q_{ij},y_i,y_j)$$

3.4 总结

约束类型	原始表达式	惩罚项形式
等式约束	$\sum a_i{x}_i=b$	$P(\sum a_i{x}_i-b{)}^2$
不等式约束	$\sum a_i{x}_i\le b$	$P(\sum a_i{x}_i-b+s{)}^2$
逻辑约束	$x_1\to x_2$等	$P{x}_1(1-x_2)$等
其它约束	$y_i{y}_j{y}_k$	$q_{ij}{y}_k+\lambda P(q_{ij},y_i,y_j)$

除此之外，下表给出了一些常见约束的惩罚项示例。注意表中所有变量均为二进制变量，参数$P$为正标量惩罚值，该值必须选择足够大以确保惩罚项确实等效于经典约束，但实际应用中通常很容易确定合适的$P$值。我们将在《调整惩罚系数》一节深入讨论这一问题。

原始表达式	惩罚项形式
$x+y\le 1$	$P(xy)$
$x+y\ge 1$	$P(1-x-y+xy)$
$x+y=1$	$P(1-x-y+2xy)$
$x\le y$	$P(x-xy)$
$x_1+x_2+x_3\le 1$	$P(x_1{x}_2+x_1{x}_3+x_2{x}_3)$
$x=y$	$P(x+y-2xy)$