[SciPy-user] fmin using spherical bounds

[Robert Kern]

On Thu, May 21, 2009 at 11:36,  <josef.pktd at gmail.com> wrote:
> On Thu, May 21, 2009 at 12:27 PM, Anne Archibald
> <peridot.faceted at gmail.com> wrote:
>> 2009/5/21 ElMickerino <elmickerino at hotmail.com>:
>>>
>>> Hello Fellow SciPythonistas,
>>>
>>> I have a seemingly simple task: minimize a function inside a (hyper)sphere
>>> in parameter space.  Unfortunately, I can't seem to make fmin_cobyla do what
>>> I'd like it to do, and after reading some of the old messages posted to this
>>> forum, it seems that fmin_cobyla will actually wander outside of the allowed
>>> regions of parameter space as long as it smells a minimum there (with some
>>> appropriate hand-waving).
>>>
>>> The function I'd like to minimize is only defined in this hypersphere (well,
>>> hyperellipsoid, but I do some linear algebra), so ideally I'd use something
>>> like fmin_bounds to strictly limit where the search can occur, but it seems
>>> that fmin_bounds can only handle rectangular bounds.  fmin_cobyla seems to
>>> be happy to simply ignore the constraints I give it (and yes, I've got print
>>> statements that make it clear that it is wandering far, far outside of the
>>> allowed region of parameter space).  Is there a simple way to use
>>> fmin_bounds with a bound of the form:
>>>
>>>      x^2 + y^2 + z^2 + .... <= 1.0 ?
>>>
>>> or more generally:
>>>
>>>      transpose(x).M.x <= 1.0  where x is a column vector and M is a
>>> positive definite matrix?
>>>
>>>
>>> It seems very bizarre that fmin_cobyla is perfectly happy to wander very,
>>> very far outside of where it should be.
>>>
>>> Thanks very much,
>>> Michael
>>
>> My experience with this sort of thing has been that while constrained
>> optimizers will only report a minimum satisfying the constraints, none
>> of them (that I have used) can work without evaluating the function
>> outside the bounded region. This is obviously a problem if your
>> function doesn't make any sense out there.
>>
>> I have to agree that reparameterizing your function is the way to go.
>> Rectangular constraints are possible. If evaluating the gradient is
>> too hard, just let the minimizer approximate it (though it shouldn't
>> be too hard to come up with a gradient-conversion matrix so that it's
>> a simple matrix multiply). There's no need to rewrite your function at
>> all; you just use a wrapper function that converts coordinates back
>> from spherical to what your function wants.
>>
>>
>> Anne
>>
>
> Do you know how well these optimization functions would handle
> discontinuities at the boundary? e.g
>
> def wrapobjectivefn(x):
>     if transpose(x).M.x > 1.0:
>          return a_large_number
>    else:
>          return realobjectivefn(x)
>
> I don't know what the appropriate wrapper for the gradient would be,
> maybe also some large vector.
>
> I'm doing things like this in matlab, but I haven't tried with the
> scipy minimizers yet.

You would probably want some gradient out there to point it back to
the feasible region, at least roughly.

-- 
Robert Kern

"I have come to believe that the whole world is an enigma, a harmless
enigma that is made terrible by our own mad attempt to interpret it as
though it had an underlying truth."
  -- Umberto Eco