[Numpy-discussion] N dimensional dichotomy optimization

Gael Varoquaux gael.varoquaux@normalesup....
Tue Nov 23 04:43:19 CST 2010


On Tue, Nov 23, 2010 at 11:37:02AM +0100, Sebastian Walter wrote:
> >> 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?

No. I have an initial guess that allows me to specify a convex hull in
which the minimum should probably lie, but its not a constraint: nothing
bad happens if I leave that convex hull.

> > 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 . 

It is indead the name I know for it, however I have additional hypothesis
(namely that f is roughly convex) which makes it much easier.

> 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.

Yes, this is too brutal: this is for non convex optimization. 
Dichotomy seems well-suited for finding an optimum on the set of
intehers.

> 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.

This is pretty much what I am doing, but you have to be careful: if the
algorithm does jumps that are smaller than 1, it gets a zero difference
between those jumps. If you are not careful, this might confuse a lot the
algorithm and trick it into not converging.

Thanks for your advice,

Gaël


More information about the NumPy-Discussion mailing list