4.2 调整惩罚系数

1. 引言

在数学、计算机科学、工程学和经济学等领域，约束是一种条件或限制，规定着变量对象必须满足的特定关系或范围。在优化问题与机器学习任务中，往往会面临复杂多样且数量较多的约束条件，这使得自动确定能满足约束条件的惩罚系数成为关键问题。 例如，在附带约束条件的优化任务里，惩罚系数需被用于目标函数中，对违反约束的行为进行惩罚，从而确保最终求解的结果符合特定条件。需要注意，调整惩罚系数与处理约束问题在本质上是相通的，基于此，我们也为大家梳理了一些调整惩罚系数的实用思路。

首先，我们将给出三种确定惩罚系数的方法——惩罚法（Penalty Method）、有效性下界法以及迭代法。对于惩罚法的相关介绍，可直接参考【处理约束问题】章节；随后将以一代码案例讲解如何在kaiwu SDK中实现自动确定惩罚系数；最后将以JSP（Job Shop Scheduling Problem） 任务调度问题为例讲解如何应用下界法确定各约束的惩罚系数。

2. 有效性下界法确定惩罚系数

当某个离散变量的值变化时，如果在目标函数引起的变化量恒小于在惩罚项引起的变化量，则惩罚项能够被优先满足。通过计算目标函数最大变化量和惩罚项最小变化量的比值，就可以计算合理的惩罚系数。

给定一个QUBO问题目标函数的一般表达式：

$$x^{\mathrm{\top }}Qx=f(x_i)=\sum _j^n{q}_{ij}{x}_i{x}_j+\sum _{k\ne i,j}^n{q}_{kj}{x}_k{x}_j$$

（1）目标函数的最大变化量可以通过上界来估计。为了估计目标函数的最大变化量，我们单独考虑某个变量$x_i$，当$x_i$从0变化为1时，目标函数的变化量$\mathrm{\Delta }f(x_i)$：

$$\mathrm{\Delta }f\left(x_i\right)=f(x^{\prime })-f(x)=\sum _j^n{q}_{ij}{x}_j<\sum _{q_{ij}>0}{q}_{ij}$$

其中，$x=(x_1,\cdots ,x_{i-1},0,x_{i+1},\cdots x_n{)}^T$变为$x^{\prime }=(x_1,\cdots ,x_{i-1},1,x_{i+1},\cdots x_n{)}^T$。因为$x_j\in \{0,1\}$，所以$\mathrm{\Delta }f(x_i)$的上界可以通过只考虑 $q_{ij}>0$的项来估计，即：

$$\mathrm{\Delta }f\left(x_i\right)=\sum _j^n{q}_{ij}{x}_j\le \sum _{q_{ij}>0}^n{q}_{ij}$$

同理，当$x_i$从1变化为0时：

$$\mathrm{\Delta }f(x_i)=-\sum _j{q}_{ij}{x}_j<\sum _{q_{ij}<0}{q}_{i}j$$

我们可以取所有变量 $x_i$ 变化时目标函数最大变化量的上界作为目标函数的最大变化量估计值，记为 $\mathrm{\Delta }{f}_{max}$，也即全局最大变化量上界为：

$$\mathrm{\Delta }{f}_{max}=\underset{1\le i\le n}{max}(U_i^{+},U_i^{-})$$

（2）下一步是估计惩罚项的最小非零变化量。 惩罚项的最小非零变化量难以准确计算，一种可行的估计方法是对惩罚项中的参数两两计算差值，然后选取其中最小的非零值并取绝对值。假设惩罚项可以表示为$P(x)=\sum _{k=1}^m{p}_k{g}_k(x)$，其中$p_k$是惩罚项的系数，$g_k(x)$是关于$x$的函数，我们可以考虑$p_k$这些参数。计算所有可能的两两差值$|p_k-p_l|$（$k\ne l$），然后从中选取最小的非零值，记为$\mathrm{\Delta }{P}_{min}$，设惩罚项集合$\{P_k{\}}_{k=1}^m$，其最小有效变化量定义为：

$$\mathrm{\Delta }{P}_{min}=\underset{\begin{array}{c}1\le k<l\le m\\ P_k\ne P_l\end{array}}{min}|P_k-P_l|$$

该值反映了惩罚系统的最小分辨能力，也对应了量子退火中的能级间隔。

（3）通过上述对目标函数最大变化量 $\mathrm{\Delta }{f}_{max}$ 和惩罚项最小非零变化量 $\mathrm{\Delta }{P}_{min}$的估计，可以推导出二者的比值是惩罚系数的有效性下界$\lambda$：

$$\lambda >\frac{\mathrm{\Delta }{f}_{max}}{\mathrm{\Delta }{P}_{min}}$$

而对于$m$个约束的情况，也可以取：

$$\lambda >\underset{1\le k\le m}{max}\left(\frac{\mathrm{\Delta }{f}_{max}^{(k)}}{\mathrm{\Delta }{P}_{min}^{(k)}}\right)$$

其中上标$(k)$表示第$k$个约束对应的参数，这样确定的惩罚系数将使得优化过程优先满足约束条件，即所有可行解的目标函数值（含惩罚项）严格小于任何不可行解的值。

3. 迭代法确定惩罚系数

使用迭代方法可以避免估计惩罚系数容易不准确的问题，但是迭代求解需要多次求解，花费的时间和计算资源更多。一种简单的方法是通过多次尝试，不断增加没有满足的惩罚系数的权重，从而最终确定合适的惩罚系数。惩罚系数的更新可以使用多种不同的更新方法，比如每次增加一个常数，按 $\mu =\mu +\lambda$ 更新，或者每次乘上一个倍率，按 $\mu =\lambda \mu$更新。

此外，还可以参考增广拉格朗日函数法（ALM）在连续问题上的应用，将ALM改变为适用于离散QUBO问题的方法。首先，将目标函数与约束条件结合，形成拉格朗日函数，对于每个约束，引入拉格朗日乘子；然后在拉格朗日函数中添加惩罚项，这一惩罚项通常是约束违反程度的平方，乘以一个惩罚因子，通过迭代的方式，逐步优化拉格朗日函数。每次迭代中，更新拉格朗日乘子和惩罚因子，以提高对约束的满足程度。该方法通过调整惩罚因子和拉格朗日乘子，逐步逼近最优解，确保在满足约束的同时优化目标函数。

迭代法确定惩罚系数的过程

4. 使用Kaiwu SDK自动确定惩罚系数

为了降低使用相干光量子计算机求解实际问题的难度，Kaiwu SDK提供了自动调整惩罚系数的函数。

下面这段代码案例通过构建一个简单的带有约束条件的QUBO模型，目标是在满足特定约束的情况下，最大化目标函数的值，并使用SDK中的get_min_penalty自动确定惩罚系数。

优化问题表示为：

$$\begin{array}{rl}& max3(x_0-x_1{)}^2-2x_2\\ & \text{s.t.}(x_0+x_1+2x_3-2{)}^2+2x_2=0\\ & where{x}_i\in \{0,1\},i=0,1,2,3\end{array}$$

使用Kaiwu SDK确定惩罚系数的过程如下所示：

import kaiwu as kw
   x = kw.qubo.ndarray(4, 'x', kw.qubo.Binary)
   cons = (x[0] + x[1] + 2*x[3] - 2)**2 + 2 * x[2]
   obj = 3*(x[0] - x[1])**2 - 2 * x[2]
   penalty = get_min_penalty(obj, cons)
   qubo_expr = obj + penalty * cons

此外，在Kaiwu SDK中，主要有两种方法对约束的惩罚系数进行自动确定：使用get_min_penalty_for_equal_constraint，或使用get_min_penalty。

两个函数使用场景上的区别如下表所示：

特性	get_min_penalty	get_min_penalty_for_equal_constraint
适用范围	任意二次约束	仅限线性等式约束
计算原理	定理一：全局变化量分析	单比特翻转最坏情况分析
计算复杂度	$O(n²)$	$O(n)$
精度保证	全局可行解优先	局部最优保证
典型应用场景	非线性约束/不等式转换约束	任务分配等线性等式约束