Originally authored in August 2024, but didn’t publish because of the math formatting. I didn’t come up with a solution to that, so here it is with bad math formatting.

Unconstrained formulations of constrained optimization problems are common when it comes to analog and quantum computers. The general approach to solving these with an analog device is to convert the constraints into penalties. Along with these penalty functions, a factor is required to appropriately weight the functions so they enforce the constraints they represent.

These multipliers can be notoriously difficult to choose. There is a simple analysis that guarantees the choice of a minimally sufficient multiplier which guarantees all feasible solutions have a lower value than all infeasible solutions. Of course, an optimal solution is the desired solution. So, setting the multiplier large enough to separate all feasible solutions can be excessive. One issue that can arise due to choosing a large multiplier is that the precision required to distinguish an optimal solution from a sub-optimal one can be too great for the device being used to solve the problem.

The method of analysis is based on the linear relationship between the objective function of the constrained problem P and the unconstrained problem U for some solution x. The problem U can be defined as U(x)=P(x)+aW(x) where W is the function of penalties for violating constraints and a is a scalar weight. Each violation of the constraints must result in a positive value in W(x) for the method to work, so simply weighting the constraint functions will not produce the same guarantees noted here. Linear equality constraints can be converted to positive penalties with the manipulation of constraints Ax=b -> (Ax-b)² =0 such that (Ax-b)² is positive when the constraint does not hold.

Iterating to find sufficiently large a

Each solution x₁ for U, if not feasible, will have a positive W(x₁), so P(x₁)+aW(x₁) can be made any value greater than P(x) for any x by choosing a significantly large enough. Thus, if we know the least upper bound for P(x), a value for a can be found by
a=(u-P(x₁))/W(x₁)
where u is the least upper bound for P(x). The least upper bound is not a necessary choice for u, but it does guarantee that any feasible solution to P produces a lower value than U_a(x₁). Note that a in the subscript denotes U with some specific a.
With this a a new solution to P can be sought, let’s say we come across x₂ such that U_a(x₂)<U_a(x₁). If x₂ is feasible, No further progress can be made because W(x₂)=0. If x₂ is infeasible, then the process can be repeated and an x₃ may be found. This process can be repeated until no infeasible solution is found. We know this search has en end because the solutions to this problem can be enumerated within a discretized domain, such as in a computer, and the algorithm will not enter a cycle. The number of iterations could be astronomical, but so can the iterations of Dantzig’s Simplex Method and it is still effective, many decades later. We know the algorithm will not enter a cycle because of this theorem. This is true in theory, but without a solver that finds min_x U_a(x), the algorithm could enter a cycle or fail instead of achieving a sufficiently large penalty multiplier.