[Numpy-discussion] N dimensional dichotomy optimization

Zachary Pincus zachary.pincus@yale....
Tue Nov 23 10:31:10 CST 2010


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


More information about the NumPy-Discussion mailing list