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

[Enrico Avventi]

my function tends to infinity as you approach the boundary, as it is the
case for all convex functions that can be defined only inside an open convex
set.

On Wed, Sep 15, 2010 at 12:18 PM, Sebastian Walter <
sebastian.walter at gmail.com> wrote:

> I can't quite follow the reasoning that another line search would solve the
> problem.
> If the current iterate is at the boundary and the new search direction
> points into the infeasible set, then a line search is unlikely to help.
>
> Example:
> min_x dot([2,1],x)
> s.t. x >= 0
>
> the minimizer is x_* = [0,0]. If the current iterate x_k is at [3,0], then
> the new search direction woud be
> s_k = -[2,1] which points directly into the infeasible set which would
> yield infty.
>
> I'm not sure what the best approach for your problem is.
> Since  SDP is still an active topic of research one could conjecture that
> possibly it's not as easy as you think.
> If you find a good solution I'd be happy to hear about it.
>
> regards,
> Sebastian
>
>
>
>
> On Wed, Sep 15, 2010 at 11:19 AM, Matthieu Brucher <
> matthieu.brucher at gmail.com> wrote:
>
>> 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 at 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 at 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 at 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 at 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 at scipy.org
>>>> http://mail.scipy.org/mailman/listinfo/scipy-user
>>>>
>>>>
>>>
>>> _______________________________________________
>>> SciPy-User mailing list
>>> SciPy-User at 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 at scipy.org
>> http://mail.scipy.org/mailman/listinfo/scipy-user
>>
>>
>
> _______________________________________________
> SciPy-User mailing list
> SciPy-User at scipy.org
> http://mail.scipy.org/mailman/listinfo/scipy-user
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.scipy.org/pipermail/scipy-user/attachments/20100915/6cdda8e0/attachment.html>