Non-differentiable global optimization problem

Question

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.

Answer 1

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.

Answer 2

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