Best way to enforce a distance between coefficients

Question

I am using basinhopping to perform a global optimization. My simple code is:

from scipy.optimize import basinhopping, rosen

def build_show_bh(MIN=None):
    if MIN is None:
        MIN = [0]
    def fn(xx, f, accept):
        if f < MIN[-1]:
            print([round(x, 2) for x in xx], f)
            MIN.append(f)
    return fn

x0 = (0.4, 0.6, 0.8)
bounds = [(0,1)]*3
minimizer_kwargs = dict(method="L-BFGS-B", bounds=bounds)
progress_f = [0]
c = build_show_bh(progress_f)
print("Optimizing using basinhopping")
res = basinhopping(
    rosen, 
    x0,
    minimizer_kwargs=minimizer_kwargs,
    niter=10,
    callback=c, 
    disp=True
)
print(f"external way of keeping track of MINF: {progress_f}")

I would like to add a constraint that each of the coefficients must be at last 0.1 from both the other coefficients. I am happy for them to be in sorted order if that helps. What is the best way of doing that?

Answer 1

I would solve this problem by creating a constraint on the difference between successive values.

def constraint(x, use_epsilon=True):
    difference_between_coeffs = np.diff(x)
    epsilon = 1e-6  # Use this to make constraint slightly more conservative
    min_difference = 0.1 + (epsilon if use_epsilon else 0)
    difference_metric = difference_between_coeffs - min_difference
    difference_metric_capped = np.minimum(0, difference_metric)
    return np.sum(difference_metric_capped)

(Note: this constraint also requires the coefficients to be in sorted order.)

While writing this program, I had the problem that sometimes SLSQP would give me points which slightly violated the constraint, which I solved by requiring points to be slightly further apart. I found that an epsilon = 1e-6 was sufficient to fix this.

You then have to tell the minimizer to use this constraint:

constraints = [
    {"type": "eq", "fun": constraint}
]
minimizer_kwargs = dict(method="SLSQP", bounds=bounds, constraints=constraints)

Note: I switched the method from L-BFGS-B to SLSQP, as BFGS does not support constraints. You can use trust-constr as well - this is the only other method which supports both constraints and bounds.

Next, I had the problem that sometimes basinhopping picked a point which violated the constraint, which caused minimization to fail, which then considers the point picked by basinhopping to be correct. I fixed this by using an acceptance test for basinhopping. This avoid accepting points if they fail the constraint.

def accept(x_new, **kwargs):
    return constraint(x_new) == 0

res = basinhopping(
    ...
    accept_test=accept,
)

Full code:

from scipy.optimize import basinhopping, rosen
import numpy as np

def build_show_bh(MIN=None):
    if MIN is None:
        MIN = [0]
    def fn(xx, f, accept):
        if f < MIN[-1]:
            print([round(x, 2) for x in xx], f)
            MIN.append(f)
    return fn

def constraint(x, use_epsilon=True):
    difference_between_coeffs = np.diff(x)
    epsilon = 1e-6  # Use this to make constraint slightly more conservative
    min_difference = 0.1 + (epsilon if use_epsilon else 0)
    difference_metric = difference_between_coeffs - min_difference
    difference_metric_capped = np.minimum(0, difference_metric)
    return np.sum(difference_metric_capped)


def accept(x_new, **kwargs):
    return constraint(x_new) == 0


constraints = [
    {"type": "eq", "fun": constraint}
]
x0 = (0.4, 0.6, 0.8)
bounds = [(0,1)]*3
minimizer_kwargs = dict(method="SLSQP", bounds=bounds, constraints=constraints)
progress_f = [100]
c = build_show_bh(progress_f)
print("Optimizing using basinhopping")
res = basinhopping(
    rosen, 
    x0,
    minimizer_kwargs=minimizer_kwargs,
    accept_test=accept,
    niter=10,
    callback=c, 
    disp=True
)
print(f"external way of keeping track of MINF: {progress_f}")