Hi Gilles,
Le 08/11/2011 16:29, Gilles Sadowski a écrit :
>>> Hi all,
>
> Hi Luc.
>
>>>
>>> Gilles has started adding an API for simple bounds constraints in
>>> optimization, which will soo be available for both Bobyqa and CMA-ES, as
>>> both method naturally support such constraints.
>>>
>>> I wondered if we could take the opportunity to set up a poor man
>>> implementation in the abstract base class for optimizers that do not
>>> support constraints, such as Nelder-Mead and Virginia Torczon's
>>> multi-directional algorithm. Gilles work on the proper API plus this
>>> poor man implementation would allow solving the old issue MATH-196 I
>>> created 3 years and an half ago ...
>>>
>>> A basic implementation can be based on an array of mappers inserted
>>> between the user variables and the variables the optimizer manages. For
>>> each component of the current point x[i] considered in user space, we
>>> would map it to an optimizer variable y[i] using:
>>>
>>> for (int i = 0; i < n; ++i) {
>>> y[i] = mapper[i].encode(x[i]);
>>> }
>>>
>>> and a similar setting for retrieving x[i] from y[i] using a decode
>>> function. The x[i] variables would be subject to bounds (some may be
>>> bounded and others not bouded), whereas y[i] would all be unbounded.
>>>
>>> Mapper would be an interface with four implementations, depending on bounds.
>>>
>>> NoBoundsMapper would be used for components x[i] which are nturally
>>> unbounded, encode and decode would be the identity function.
>>>
>>> LowerBoundMapper would be used for components x[i] that must be larger
>>> than a lower bound a:
>>> encode(x) = ln(x - a)
>>> decode(y) = a + exp(y).
>>>
>>> UpperBoundMapper would be used for components x[i] that must be lesser
>>> than an upper bound b:
>>> encode(x) = -ln(b -x)
>>> decode(y) = b - exp(-y).
>>>
>>> LowerUpperBoundMapper would be used for components x[i] that must be
>>> betwee lower bound a and upper bound b:
>>> encode(x) = ln((x - a) / (b - x))
>>> decode(y) = (a + b exp(y)) / (1 + exp(y))
>>
>> I forgot to say all these classes would be internal ones, the user would
>> never see them, he will simply see Gilles API with the bounds arrays,
>> where some elements of the array could be set to infinity, or some
>> arrays could be null which would be equivalent to set all their
>> components to infinity with the proper sign.
>>
>> Luc
>>
>>>
>>> Due to numerical considerations and the fact infinity can be
>>> represented, I'm not sure if the bounds can be reached or not, it
>>> probably depends on how we implement the encode/decode functions.
>>>
>>> For sure, it does not replace proper handling of bounds, but it would be
>>> quite useful. It is what we suggested as a fallback solution to several
>>> users who needed constrained optimization.
>>>
>>> If you agree with this, I could implement it in the next few days, so
>>> Gilles could set up the proper handling for CMA-ES and fine-tune the API.
>>>
>>> What do you think about this ?
>
> I wonder whether this feature should be "prominent" rather than "internal".
> By having it an implementation detail we run the risk of giving a false
> impression of an algorithm's ability to correctly/efficiently deal with the
> constraints. It seems dangerous to hide a feature that is in fact not part
> of the "standard" implementation (cf. another discussion where this point
> was also raised).
In this case, the new API with boundaries setting should not be set at
the level of the abstract class that is share by CMA-ES, Bobyqa,
Nelder-Mead and MultiDirectional.
I proposed this implementation, as a way to provide this even for the
last two methods. Of course, we should document this. In this case, it
is not a modification of the algorithm, and in fact we do rely on the
original ones. We simply add another method, which uses an internal adapter.
> An alternative would be to create an adapter class (which users would have
> to explicitly instantiate) that would take care of the conversion from
> bounded to unbounded.
> Concerning the mapping itself, it migh be useful to be able to select the
> "encode" and "decode" functions.[1]
Fine, I missed this.
>
> Another argument for not hiding the mapping is that another poor man's
> approach is to use a penalty (when the optimizer's "guess" falls out of
> bounds) and I wonder whether some algorithm could behave better with one or
> the other approach.
As far as I understand, direct methods that do not rely on derivatives
support well penalty functions. Gradients based methods do not.
>
> It would be nice to have an optimization specialist's opinion on this whole
> issue.
Sure.
best regards,
Luc
>
>
> Regards,
> Gilles
>
> [1] The classes "Logit" and "Sigmoid" (in "o.a.c.m.analysis.function") were
> introduced for exactly this purpose.
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org
> For additional commands, e-mail: dev-h...@commons.apache.org
>
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org
For additional commands, e-mail: dev-h...@commons.apache.org
