Automatically determine the penalty factor#

1. Penalty coefficient#

In the process of modeling real problems through QUBO, a common way to deal with constraints is to convert them into penalty terms and add them to the objective function.Determining the appropriate penalty factor for a constraint sometimes takes time.

For the traditional method, too large penalty coefficient will cause the algorithm to ignore the objective function, resulting in the feasible solution does not have a good objective function.When using a real machine, too large penalty factor may also cause problems with accuracy. In contrast, too small penalty factor may result in constraints not being satisfied first. Therefore, it is meaningful to estimate the appropriate penalty coefficient.

2. Estimation method#

When a discrete variable changes, if the change caused by the objective functionis always smaller than the change caused by the penalty term, the penalty term can be satisfied preferentially. So if you estimate the proportion of the change caused by each variable, you get the penalty coefficient.

The maximum change of the objective function can be estimated by an upper bound.

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

In QUBO expressions, the terms including x_i can be separated out.

When x_i changes from 0 to 1

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

When x_i changes from 1 to 0

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

Estimate the minimum non-zero variation of the penalty term, the ratio of them can be used as a penalty coefficient

3. Examples#

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