自动确定惩罚系数#

1. 惩罚系数#

在通过QUBO对实际问题建模的过程中，约束条件的一种常见处理方式是将其转化为惩罚项，添加到目标函数中。 确定约束条件的合适的惩罚系数有时是一个花费时间的事情。

对于传统方法，过大的惩罚系数会导致算法忽略了目标函数，导致求到的可行解没有一个较好的目标函数。 对于真机，过大的惩罚系数也可能导致精度方面的问题。 与此相反，过小的惩罚系数可能会导致约束没有被优先满足。 因此，估计出合适的惩罚系数是有意义的。

2. 估计方法#

当某个离散变量的值变化时，如果在目标函数引起的变化量恒小于在惩罚项引起的变化量，则惩罚项能够被优先满足。 所以只要估计出每个变量引起的变化量的比例，就能得到惩罚系数。

目标函数的最大变化量可以通过上界来估计

x^\top Q x = f(x_i) = \sum_j q_{ij}x_i x_j + \sum_{k\neq i,j} q_{kj} x_k x_j

QUBO表达式中，与 x_i 相关的项可以分离出来。

当x_i从0变化为1时

\Delta f(x_i) = \sum_j q_{ij} x_j < \sum_{q_{ij}>0} q_ij

当x_i从1变化为0时

\Delta f(x_i) = -\sum_j q_{ij} x_j < \sum_{q_{ij}<0} q_ij

估计惩罚项的最小非零变化量，二者比值可以作为惩罚系数

3. 例子#

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 = kw.qubo.get_min_penalty(obj, cons)
qubo_expr = obj + penalty * cons