Quantum Opt’z: Constraints and Penalties
Equality, Inequality and constant P
In this article, we discuss about the quadratic Loss and it’s corresponding constraints to apply penalty over the QUBO problem. Also we discuss about the importance of the constant P.
convert any constraint in to the form (expression) ≤ 0
f(x) -> 𝑥 ≤ 5 becomes: 𝑥–5 ≤ 0If we are trying to minimize f(x), this means we need to add value when the constraint is violated.
Otherwise, if we are trying to maximize f(x), then the penalty shall be subtract value.
Below is the table which shows some of the constraints and it’s equivalent penalty.
Quadratic Loss: Inequalities
With the constraint 𝑥–5 ≤ 0, we need a penalty that is:
- 0 when 𝑥–5 ≤ 0
- positive when 𝑥–5 is > 0
This can be done using the operation 𝑃(𝑥) = max(0, 𝑥–5)
which returns the maximum of the two values, either 0 or whatever (x-5) is.
We can make the penalty more severe by using 𝑃(𝑥) = max(0, 𝑥–5)²
This is known as a quadratic loss function.
Quadratic Loss: Equalities
It is even easier to convert equality constraints into quadratic loss functions because we don’t need to worry about the operation (max, f(x)).
We can convert h(x) = c into h(x)-c = 0, then use 𝑃(𝑥) = (h(x)-c)²
The lowest value of 𝑃(x) will occur when h(x) = c, in which case the penalty 𝑃(x) = 0.
This is exactly what we want.
Once you have converted our constraints into penalty functions, the basic idea is to add all the penalty functions on to the original objective function and minimize from there:
minimize 𝑇(𝑥) = 𝑓(𝑥) + 𝑃(𝑥)
Example : minimize 𝑓(𝑥)=100/𝑥 subject to x ≤ 5 with constraint.
minimize 𝑇(𝑥) = 100/𝑥 + max(0, 𝑥–5)²
The addition of penalty functions can create severe slope changes in the graph at the boundary, which interferes with typical minimization programs. As shown below
multiply the quadratic loss function by a constant, P. This controls how severe the penalty is for violating the constraint.
The accepted method is to start with P = 10, which is a mild penalty.
It will not form a very sharp point in the graph, but the minimum point found using P = 10 will not be a very accurate answer because the penalty is not severe enough.
Then, P is increased to 100 and the function minimized again starting from the minimum point found when P was 10.
The higher penalty increases accuracy, and as we narrow in on the solution, the sharpness of the graph is less of a problem.
We continue to increase P values until the solutions converge.
References: Wikipedia, open sources
