[Numpy-discussion] N dimensional dichotomy optimization

[Zachary Pincus]

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.

Something with a global optimum but spikes along the way is pretty  
well-suited to SA in general, and it's also an easy algorithm to make  
work on a lattice. If you're in high dimensions, there are also bolt- 
on methods for biasing the steps toward "good directions" as opposed  
to just taking isotropic random steps. Again, pretty easy to think of  
discrete implementations of this...

Zach