[Numpy-discussion] N dimensional dichotomy optimization

Sebastian Walter sebastian.walter@gmail....
Tue Nov 23 04:37:02 CST 2010


On Tue, Nov 23, 2010 at 11:17 AM, Gael Varoquaux
<gael.varoquaux@normalesup.org> wrote:
> On Tue, Nov 23, 2010 at 11:13:23AM +0100, Sebastian Walter wrote:
>> I'm not familiar with dichotomy optimization.
>> Several techniques have been proposed to solve the problem: genetic
>> algorithms, simulated annealing, Nelder-Mead and Powell.
>> To be honest, I find it quite confusing that these algorithms are
>> named in the same breath.
>
> I am confused too. But that stems from my lack of knowledge in
> optimization.
>
>> Do you have a continuous or a discrete problem?
>
> Both.
>
>> Is your problem of the following form?
>
>> min_x f(x)
>> s.t.   lo <= Ax + b <= up
>>            0 = g(x)
>>            0 <= h(x)
>
> No constraints.

didn't you say that you operate only in some convex hull?

>
>> An if yes, in which space does x live?
>
> Either in R^n, in the set of integers (unidimensional), or in the set of
> positive integers.
According to  http://openopt.org/Problems
this is a mixed integer nonlinear program http://openopt.org/MINLP . I
don't have experience with the solver though,
but it may take a long time to run it since it uses branch-and-bound.
In my field of work we typically relax the integers to real numbers,
perform the optimization and then round to the next integer.
This is often sufficiently close a good solution.

>
> Gaël
> _______________________________________________
> NumPy-Discussion mailing list
> NumPy-Discussion@scipy.org
> http://mail.scipy.org/mailman/listinfo/numpy-discussion
>


More information about the NumPy-Discussion mailing list