6
$\begingroup$

I am trying to solve the following test problem which is well-known in the community in different variants:

Place N = 15 points in the 3-dim. unit cube such that the minimal distance between them is maximal, e.g. like in the case of repellent but confined electrons. Here are Matlab-like non-vectorized/vectorized forms of the function to be optimized (where we assume n = 3*N):

---- non-vectorized -------------------------------------------------

function d = balls(x)
  d = 2.0;
  for i = 1:14
    for j = (i+1):15
      s = (x(i)-x(j))^2 + (x(i+15)-x(j+15))^2 + (x(i+30)-x(j+30))^2;
      s = sqrt(s);
      if s < d, d = s; end
    end
  end
  d = -d;
end

---- vectorized -----------------------------------------------------

function d = balls(x)
X = reshape(x, [], 3);
d = -min(pdist(X));
end

The function is continuous, but not smooth; gradient-based methods will not work. Multi-start and stochastic approaches have a problem, too, because with 45 dimensions the search space is already quite big. The boundary is also a problem, compared for example to the problem of placing electrons on a sphere where there is no boundary.

It will have many local minima, e.g. permuting ball indices or interchanging dimensions. I guess all these local minima have the same function value, like an energy level that will always end in a similar configuration (is that true?). I am only interested in this minimal value, so calculating one local minimum exactly and reliably should be enough.

From applying Matlab' fmincon() with several restarts I know the minimum will be below -0.62... Still I would like to compute this value more accurately and with open source software only! Please no hints to powerful commercial solvers.

$\endgroup$
  • 3
    $\begingroup$ You could convert it to a smooth constrained optimization problem. The constraints would be d <= s for all s and the objective is to maximize d. $\endgroup$ – Opt Mar 3 '12 at 18:44
  • $\begingroup$ Is your boundary periodic? $\endgroup$ – Deathbreath Mar 3 '12 at 23:25
  • $\begingroup$ @Deathbreath It's the boundary of the unit cube, i.e. 0<=xi<=1; what do you mean with 'periodic'? $\endgroup$ – Hans W. Mar 4 '12 at 7:44
  • $\begingroup$ @HansWerner: Periodic conditions would imply that your unit box was replicated indefinitely in all three dimensions. This is case in crystal structures for instance. $\endgroup$ – Deathbreath Mar 4 '12 at 18:46
  • $\begingroup$ Have you tried any genetic algorithms? Your objective function can be calculated extremely fast. $\endgroup$ – Beni Bogosel Jun 11 '14 at 14:26
7
$\begingroup$

Smooth reformulation

As Sid points out, there's no need to treat this problem as non-smooth, since you'd just be making it harder on yourself.

Let's assume for the sake of notation that $\mathbf{x}_{1}, \ldots, \mathbf{x}_{15} \in [0,1]^{3} \subset \mathbb{R}^{3}$ are the coordinates of your 15 particles in the unit cube. A smooth formulation, as Sid suggests, presented in standard form (for nonlinear programming), would be:

$\begin{alignat}{1} &\min_{\mathbf{x}_{1}, \ldots, \mathbf{x}_{15} \in [0,1]^{3}} -E \\ \mathrm{s.t.} & \quad E - \|\mathbf{x}_{i} - \mathbf{x}_{j}\|^{2} \leq 0, \,\, i, j = 1, \ldots, 15, \,\, i \neq j \end{alignat}$

where $E$ is a proxy for the minimum distance, which I'm assuming is related to minimizing some sort of energy. There might be a way to reformulate this problem as an equivalent convex problem, but I don't think there is.

This formulation probably isn't convex, because the left-hand sides of the nonlinear constraints aren't convex, so you'll need to use a nonconvex nonlinear programming solver to be assured of a global optimal solution (unless you can prove convexity of the feasible set, but I doubt that). Deterministic global solvers that will work for nonconvex problems include (but aren't limited to):

  • BARON (which is commercial, but you can submit jobs for free via the NEOS optimization server run by University of Wisconsin-Madison)
  • LINDOGlobal (also commerical, also available through the NEOS optimization server)
  • Couenne (open-source, part of the COIN-OR suite of open-source solvers)
  • Bonmin (also part of COIN-OR)
  • LaGO (again, part of COIN-OR)
  • icos (available as open-source, or through NEOS)

It's important to note that one solver may work on your problem when others won't; BARON is generally considered the best, but it's fallible, and there are cases where, for example, Couenne will solve a problem to (epsilon) global optimality, but BARON won't (and vice versa).

Solving nonsmooth problems

Let's suppose for the sake of argument that you (like Hans) want to solve a non-smooth nonlinear programming problem. This type of problem isn't my area of expertise, but I know of a couple references.

The most famous person in the field (who, as far as I can tell, developed the most important parts of the theory early on) is Frank H. Clarke. The gist of non-smooth optimization seems to be: replace gradients with Clarke's generalized gradients. Using Clarke's generalized gradients, you're supposed to be able to formulate a non-smooth analogue of Newton's method, as well as algorithms for optimization. His textbook on the theory (Optimization and Nonsmooth Analysis by Frank H. Clarke; the link goes to Amazon) is considered a classic.

In terms of software, the best links I can find are to Napsu Karmitsa's home page; she's developed a couple non-smooth optimization solvers, and she links to other non-smooth optimization solvers. The methods I've heard of most often are called bundle methods, and should be deterministic. (I favor deterministic methods over stochastic methods.) More links to non-smooth codes can be found here; your mileage may vary, because like I said, I don't work with these methods.

I do know that just because a method is developed for non-smooth problems does not mean it will work for non-smooth, non-convex problems, so you will need to make sure that the solver you choose can handle both non-smoothness and non-convexity.

Finally, as Hans points out in the comments, non-smooth formulations regularly appear in science and engineering. However, my first instinct as someone in the optimization field is to try and find an equivalent smooth reformulation because methods for solving smooth problems are generally much faster than methods for solving non-smooth methods (a labmate uses non-smooth solvers, and has made this observation). If you can reformulate the problem as a smooth optimization problem, it generally behooves you to do so.

$\endgroup$
  • $\begingroup$ I want to make it hard. I want to solve it as a non-smooth, non-convex problem. And it is still unclear (to me) if it will be sufficient to hit one local minimum. I do know COIN-OR and NEOS, but a more concrete plan would be welcome. As I said, no hints to commercial solvers. $\endgroup$ – Hans W. Mar 4 '12 at 7:29
  • $\begingroup$ The formulation above will be equivalent; it has the same set of global optima as the original formulation you proposed, except that the formulation I proposed is smooth. If the optimal objective function value of my formulation is $-E'$, then the optimal objective function value of your formulation is $\sqrt{E'}$. There's no need to make it non-smooth, unless, of course, you still want to, in which case, I can recommend a different solver. (You'll want to look at non-smooth bundle solvers in that case.) $\endgroup$ – Geoff Oxberry Mar 4 '12 at 7:41
  • $\begingroup$ In engineering, non-smooth problems emerge regularly, quite often because of minimax formulations, and special techniques have been developed to solve these kinds of optimization tasks, see for example Smoothing-out techniqes for min-max problems , or Non-linear minimax optimization as least pth optimization Perhaps I should set up a new question asking specifically for such approaches in free solvers. $\endgroup$ – Hans W. Mar 4 '12 at 9:32
  • $\begingroup$ So yes, I would like to solve the function as is. I really admire your know-how in optimization theory, but sometimes I find lists of solvers a bit boring. I had hoped for answers describing some real experience with such tasks. $\endgroup$ – Hans W. Mar 4 '12 at 9:34
  • $\begingroup$ I don't solve non-smooth optimization problems, but a labmate of mine does. I've updated my answer based on what I've seen in his presentations. Right now, the number of people involved in optimization research on scicomp is pretty small (based on the number of people who have answered questions on that tag; I have as many upvotes on the "optimization" tag as the next top 7 users on the tag), but I'm hoping that'll grow over time. $\endgroup$ – Geoff Oxberry Mar 4 '12 at 17:24
3
$\begingroup$

You might wish to try one of the (local) nonsmooth solvers at my web page http://www.mat.univie.ac.at/~neum/glopt/software_l.html#nonsm using multiple starting points to globalize the search.

I found CMA-ES quite robust in dimensions up to 50. (It gets very slow though when the dimension is large.)

$\endgroup$

protected by Community Jul 31 '12 at 4:59

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.