[SciPy-User] optimization routines can not handle infinity values

Matthieu Brucher matthieu.brucher@gmail....
Wed Sep 15 04:19:52 CDT 2010


Hi,

The line search used in scipy is based on Wolfe-Powell rules and the search
for appropriate values is done by interpolation. This is why it cannot be
used for your kind of problems. All Wolfe-Powel line searches I've found in
the litterature are based on such interpolations.
It could be changed to fit your purpose, but it would be slower for 99.99%
of the other optimizations. So you may add some additional constraints here.

Matthieu

2010/9/15 Enrico Avventi <eavventi@yahoo.it>

> Hi Matthieu,
>
> thanx for the reply. as far as i know it shouldn't be a problem at all in
> theory. in fact convergence theorems for newton methods and, in general,
> descent method do not require the function to be defined everywhere. you
> need just a function defined in an open convex set that has compact sublevel
> sets - e.g f(x) = x - log(x). this is exactly my situation.
> it is just a matter of slightly changing the line search method to reject
> steps that would lead to an infinite value.
> i will look at how it is implemented in scipy and see if it can be fixed
> easily.
>
> /Enrico
>
>
> On Tue, Sep 14, 2010 at 5:51 PM, Matthieu Brucher <
> matthieu.brucher@gmail.com> wrote:
>
>> Hi,
>>
>> There are two categories of contraints optimizations:
>> - you can evaluate the function outside the constraints
>> - you cannot evaluate the function outsde the constraints.
>>
>> If the first one can be handled by more general algorithms providing some
>> tricks, you cannot use them for the second one. Your problem is clearly a
>> second category problem, so you must use appropriate algorithms (which may
>> not be available in scipy directly, you may want to check OpenOpt).
>>
>> It's not a problem of routines, it's a problem of appropriate algorithms.
>>
>> Matthieu
>>
>> 2010/9/14 enrico avventi <eavventi@yahoo.it>
>>
>>> hello all,
>>>
>>> i am trying out some of the optimization routines for a problem of mine
>>> that is on the form:
>>>
>>> min f(x)
>>>
>>> s.t M(x) is positive semidefinite
>>>
>>> where f is strictly convex in the feasible region with compact sublevel
>>> sets, M is linear and takes value in some subspace of hermitian matrices.
>>>
>>> the problem is convex but the costraint can not be handled directly by
>>> any of the optimization routines in scipy. So i choose to change it to an
>>> uncostrained problem with objective function:
>>>
>>> f1(x) = f(x) for M(x) pos semi def
>>> f1(x) = Inf otherwise
>>>
>>> the problem is that it seems the routines can not handle the infinity
>>> values correctly.
>>>
>>> Some of the routines (fmin_cg comes to mind) wants to check the gradient
>>> at points where the objective function is infinite. Clearly in such cases
>>> the gradient is not defined - i.e the calculations fail - and the algorithm
>>> terminates.
>>>
>>> Others (like fmin_bfgs) strangely converge to a point where the objective
>>> is infinite despite the fact that the initial point was not.
>>>
>>> Do you have any suggestion to fix this problem?
>>>
>>> regards,
>>>
>>> Enrico
>>>
>>>
>>>
>>>
>>> _______________________________________________
>>> SciPy-User mailing list
>>> SciPy-User@scipy.org
>>> http://mail.scipy.org/mailman/listinfo/scipy-user
>>>
>>>
>>
>>
>> --
>> Information System Engineer, Ph.D.
>> Blog: http://matt.eifelle.com
>> LinkedIn: http://www.linkedin.com/in/matthieubrucher
>>
>> _______________________________________________
>> SciPy-User mailing list
>> SciPy-User@scipy.org
>> http://mail.scipy.org/mailman/listinfo/scipy-user
>>
>>
>
> _______________________________________________
> SciPy-User mailing list
> SciPy-User@scipy.org
> http://mail.scipy.org/mailman/listinfo/scipy-user
>
>


-- 
Information System Engineer, Ph.D.
Blog: http://matt.eifelle.com
LinkedIn: http://www.linkedin.com/in/matthieubrucher
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mail.scipy.org/pipermail/scipy-user/attachments/20100915/563e0859/attachment.html 


More information about the SciPy-User mailing list