Constrained optimization

[hglaude]

Hello,

I was wondering how you would use that package for constrained optimization?

Let's say that you know how to project any candidate on the feasible set. Then, would it work to ask for many candidates, project them, evaluate them and then call tell on the new projected candidates?

If you don't know how to project, would you call many times the ask function until you get one candidate satisfying the constraints or, would you call tell with a very high value and then request another candidate?

Best, Hadrien

[jrapin]

Hi,

There a several ways to do this:

• ask for many candidates, project them, evaluate them: this could work but I would expect it to provide bad performance if the space is not dense in the real space, because the optimizer could get stuck in places where changes would have no more impact. On the other hand, if this is implemented within the parameter as clipping is for instance, the inner data in the algorithms cannot go past the constraint, so there is no problem and that works quite well.
• call many times the ask function until you get one candidate satisfying the constraints: this is basically what is implemented to make this work, but you should not do it manually because some algorithms will complain then you are not providing the answer to their questions :)
• call tell with a very high value and then request another candidate: that can work fine as well, you can even send float("inf").

So it really depends on your problem, if you have more information let us know, but I feel that often, the only way to know what works best is to try :s

[teytaud]

For the moment we only deal with cheap constraints. When such a constraint is declared (or when several such constraints are declared), basically we repeat "ask" until it finds a feasible point. The way we adapt parameters of the algorithm is the only subtle point here, it should be correct. This is ok when constraints are easy to satisfy by perturbations. We have to implement tools for other constraints, e.g. when we have a projection operator. After the Feb. 6th deadline possibly :-)

[teytaud]

(in terms of workaround, when you have a projection operator, you might replace f(x) by f(projection(x)), maybe, but experts in constraints might tell us that this is not optimal...)

[teytaud]

I assign the issue to me, I must definitely implement more stuff for constrained optimization, now that the multiobjective stuff and the YABBOB benchmarks are on-track (thanks Corwinpro for multiobjective improvements :-) ).

[hglaude]

Hello,

I was thinking about something like a projection onto the simplex.

As a workaround, I have implemented this projector as a transform (like clipping) and inherited the ng.p.Array class and added a set_projection method like set_bound.

class ArrayWithProjection(ng.p.Array):
    def __init__(self, *args, **kwargs):
        super(ArrayWithProjection, self).__init__(*args, **kwargs)
    def set_projection(self):
        if self.bound_transform is not None:
            raise RuntimeError("A bounding method has already been set")
        # update instance
        self.bound_transform = ProjectorTransform()
        self.bounds = (None, None)  # type: ignore
        self.full_range_sampling = False
        return self

The problem is that, as clipping the backward function is defined only on the feasible set. However, backward is called in _to_reduced_space in _internal_get_standardized_data in get_standardized_data in _internal_ask_candidate in ask on a value outside the feasible set. Is that expected?

Thank you, Hadrien

[jrapin]

This is surprising since I have never had this issue with clipping, can you print the traceback?

[hglaude]

Hello,

I found the issue. Because of finite precision I had small errors during the projection. After adding an extra margin (1e-10) to the boundary during the projection, it's working fine.

Thank you

[jrapin]

Perfect ;) I'll close the issue if this works now. Don't hesitate to reopen if you still have a problem. Also, if you have any idea of how we could simplify the process of adding such constraints, let us know. For now it's still a "work in progress" and it's probably a bit confusing...

[hglaude]

Thank you! Works like a charm.

[inikishev]

Out of curiosity, the way I am doing it is clipping values to bounds and adding penalty to avoid flat areas, because clipping params directly wouldn't work with integrations like scipy minimize since they have their own params. But is that known to be less efficient?