Add support for constrained optimization

[SimonBlanke]

I want to add the support for constrained optimization. The interface design could look like this:

import numpy as np
from gradient_free_optimizers import HillClimbingOptimizer

def parabola_function(para):
    loss = para["x1"] * para["x1"] + para["x2"] * para["x2"]
    return -loss

search_space = {
    "x1": np.arange(-10, 10, 0.1),
    "x2": np.arange(-10, 10, 0.1),
}

def constraint_1(para):
    return para["x1"] ** 2 + para["x2"] ** 2 <= 2

constraints_list = [constraint_1]

opt = HillClimbingOptimizer(search_space, constraints=constraints_list)
opt.search(parabola_function, n_iter=100000)

Implementing this in the optimization algorithms will need various solutions:

• For hill-climbing based algorithms I could just repeat the iteration step if the new position is not inside the constrained search-space
• Sequence-mode-based optimizers might be the easiest to implement, because I could just remove the positions outside the constrained search-space from the list of all possible positions. Therefore the surrogate model would not make a prediction for those positions.
• The difficult cases are the more deterministic algorithms like PSO or DIRECT. Repeating the iteration will just return the same position, so I'll have to think about this one.

[SimonBlanke]

Here is an example search-path-gif with a constraint at the optimum around the [0, 0] position for the Hill-climbing algorithm:

[SimonBlanke]

A similar example for Bayesian Optimization. Very interesting to see:

[SimonBlanke]

A similar example for Grid Search. That way easier than expected:

[SimonBlanke]

Multiple constraints (xx+yy > 5 && x > -3) are not a problem:

[SimonBlanke]

From my current progress I see the following optimization algorithms as non-trivial for the constraint optimization implementation:

• DownhillSimplexOptimizer
• PatternSearch
• EvolutionStrategyOptimizer
• DirectAlgorithm

[SimonBlanke]

I managed to add support for constrained optimization to all optimization algorithms and added some tests in dda3b6125f20ab79d93e43d5969f32c3ed4ba0d3.

Next I will add more tests, write the documentation and add examples. After that I will release this new feature in version 1.3.

About the implementation

There are three different ways this feature is implemented in the algorithms:

• The easiest to do was for the sequence-model-based optimizers. I implemented constrained optimization by filtering out the positions in the search-space that are within the constrained areas from the list of all positions.
• Hill climbing based algorithms, random search and grid search repeat the iteration step until a position outside if a constrained area is found.
• Some more deterministic algorithms (like listed in the comment above) required some idea-testing. I then came up with the following solution: If a new position would be inside a constrained area the algorithm will call a hill climbing method to find a close position around the new position.

[SimonBlanke]

I added an example for constrained optimization to the repository and released v1.3 for the documentation for GFO. All tests look good.

I just released version 1.3 and will close this issue.

This is a big new feature, so feedback is appreciated and can be submitted in this issue.