[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