[SciPy-User] optimization routines can not handle infinity values
Enrico Avventi
eavventi@yahoo...
Wed Sep 15 14:44:25 CDT 2010
you are right i didn't mention it. but it is indeed the case f(x) is finite
only for M(x) pos def.
On Wed, Sep 15, 2010 at 5:28 PM, Sebastian Walter <
sebastian.walter@gmail.com> wrote:
> you said you formulated your problem as follows:
>
>
> f1(x) = f(x) for M(x) pos semi def
> f1(x) = Inf otherwise
>
> I don't see any indication that anything goes to infinity when the sequence
> of iterates approaches a boundary.
> It seems to me that what you are describing is the behavior of a barrier
> function which is used in interior point methods, i.e. of the form
>
> min_x f(x) - a log( g(M(x))
>
> where g(M(x)) is a sufficiently smooth function in x and g(M(x)) = 0 if
> M(x) is not positive definite
> and a>0. Is this what you are doing?
>
>
> Sebastian
>
>
>
>
> On Wed, Sep 15, 2010 at 12:52 PM, Enrico Avventi <eavventi@yahoo.it>wrote:
>
>> 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@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@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@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
>>>>
>>>> _______________________________________________
>>>> 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
>>>
>>>
>>
>> _______________________________________________
>> 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
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mail.scipy.org/pipermail/scipy-user/attachments/20100915/19eccf4f/attachment.html
More information about the SciPy-User
mailing list