[Numpy-discussion] N dimensional dichotomy optimization

[Matthieu Brucher]

2010/11/23 Zachary Pincus <zachary.pincus at yale.edu>:
>
> On Nov 23, 2010, at 10:57 AM, Gael Varoquaux wrote:
>
>> On Tue, Nov 23, 2010 at 04:33:00PM +0100, Sebastian Walter wrote:
>>> At first glance it looks as if a relaxation is simply not possible:
>>> either there are additional rows or not.
>>> But with some technical transformations it is possible to reformulate
>>> the problem into a form that allows the relaxation of the integer
>>> constraint in a natural way.
>>
>>> Maybe this is also possible in your case?
>>
>> Well, given that it is a cross-validation score that I am optimizing,
>> there is not simple algorithm giving this score, so it's not obvious
>> at
>> all that there is a possible relaxation. A road to follow would be to
>> find an oracle giving empirical risk after estimation of the penalized
>> problem, and try to relax this oracle. That's two steps further than
>> I am
>> (I apologize if the above paragraph is incomprehensible, I am
>> getting too
>> much in the technivalities of my problem.
>>
>>> Otherwise, well, let me know if you find a working solution ;)
>>
>> Nelder-Mead seems to be working fine, so far. It will take a few weeks
>> (or more) to have a real insight on what works and what doesn't.
>
> Jumping in a little late, but it seems that simulated annealing might
> be a decent method here: take random steps (drawing from a
> distribution of integer step sizes), reject steps that fall outside
> the fitting range, and accept steps according to the standard
> annealing formula.

There is also a simulated-annealing modification of Nelder Mead that
can be of use.

Matthieu
-- 
Information System Engineer, Ph.D.
Blog: http://matt.eifelle.com
LinkedIn: http://www.linkedin.com/in/matthieubrucher