Le 09/11/2011 22:44, Luc Maisonobe a écrit :
>
>
>
> Gilles Sadowski <gil...@harfang.homelinux.org> a écrit :
>
>> Hello.
>>
>>>>>>
>>>>>> 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.
>>
>> You are right but this was considered as a compromise in order to avoid
>> an
>> additional level in the hierarchy:
>> BaseAbstractSimpleBoundsScalarOptimizer<FUNC extends
>> MultivariateRealFunction>
>> extends BaseAbstractScalarOptimizer<FUNC>
>>
>> Shall I add it?
>> If there aren't any drawbacks apart from an additional class, it is
>> indeed
>> clearer.
>
> If you think it's clearer, then go ahead.
>
>>
>>> 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.
>>
>> With the new class, I think that it will be necessary to figure out how
>> to use
>> the "adapter" pattern instead of hiding the "poor man's" handling of
>> bounds.
>> Do you agree?
>
> Yes. And we should make it clear in the documentation that there are classes
> that already handle bounds by themselves and classes that do not and hence
> should use the adaptor. So each approach should have an @see reference to
> the other approach, so user understand there are two approaches and can
> decide which one is more suited to the problem at hand.
>
>>
>>>> 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.
>>
>> We could thus implement two adapters, one that will do a mapping of the
>> variables and another that will use the penalty approach.
Done in subversion repository as of r1200516. In the documentation, the
adapters refer directly to the CMAES and BOBYQA optimizers as better
ways to handle constraints. These references may be updated with the new
intermediate abstract class when it will be available.
Luc
>
> Yes.
>
> Best regards
> Luc
>
>>
>>
>> Regards,
>> Gilles
>>
>> ---------------------------------------------------------------------
>> 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
>
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org
For additional commands, e-mail: dev-h...@commons.apache.org
