6
$\begingroup$

In my github project, I have come up with a very simple function that seems to cause problems for all the optimizers I have thrown it at, and I am wondering why. There is an obvious downhill direction at all points, and a single global minimum. I call it the "treacle function", because it seems to bog optimizers down in a pretty consistent manner.

$$\sum_{i=0}^{n-1} \sqrt{|x_i|}$$

From a non-expert inspection I would say it is definitely non-convex, in "bulk" as well as along the axes, but is that really what makes it hard to solve, or is that a red herring? Here is what it looks like in 2D:

Treacle Function

Incidentally, I actually code it as:

$$\sum_{i=0}^{n-1} \sqrt{|x_i - (i + 1)|}$$

to help defeat biased optimization algorithms (related question here), but I wanted to make the structure crystal clear at the outset!

My code is available here.

[EDIT] I am beginning to think there is something inherently "difficult" with fractional powers in general. Perhaps the mechanism of this difficulty is to do with the slope (and therefore the rapid variation) of $f$ at the solution point. This has (IMO) more to do with "gluing" non-convex functions together, but is certainly related to non-convexity.

$\endgroup$
25
  • 2
    $\begingroup$ The function is nowhere convex, and it's not differentiable along the axes as well as at the minimum. No wonder it's hard to find a minimum. $\endgroup$ Apr 2 at 15:23
  • 1
    $\begingroup$ @OscarSmith if I said they seem to make gradually less and less progress as they approach the minimum (eventually "terminating" early) would that give you a useful vision? Have you tired the function yourself? $\endgroup$
    – m4r35n357
    Apr 2 at 17:12
  • 1
    $\begingroup$ Can you describe in some sort of quantitative way what behavior these solvers are showing? $\endgroup$
    – whpowell96
    Apr 2 at 19:27
  • 2
    $\begingroup$ I'm not sure what your question is. As several of us have pointed out, the function is neither convex nor differentiable. This is known to make things difficult for algorithms. What else do you want to know? $\endgroup$ Apr 2 at 22:49
  • 1
    $\begingroup$ @m4r35n357 Yes, I would absolutely expect a derivative-free algorithm to work slower on a non-differentiable objective function than on a differentiable one. That's because generally you compute the error reduction using a Taylor expansion, but you can only take Taylor expansions so far if the function lacks smoothness. $\endgroup$ Apr 3 at 19:41

2 Answers 2

5
$\begingroup$

Perhaps not quite an answer to the question you are asking, but perhaps still useful:

If you take, for example, the Nelder-Mead simplex algorithm, you might be forgiven to think that because it never asks the objective function for a gradient (i.e., it is "derivative-free"), that the performance of the algorithm should not suffer if the objective function is not differentiable. But that is not true.

Let's for simplicity look at it in 2d. If you think about how the algorithm works, it is clear that if you take a reflection of a point (i.e., you flip the triangle over an edge), then the new point will be a good choice only if the function continues to go downhill in this direction. You know that that direction is a good direction based on the three points you currently have. In essence, reflecting the point with the worst function value across the edge connecting the two points with the better function values will definitely yield a new point with an even better function value if the function is linear, and will likely yield a better point if the function is approximately linear. For smooth functions, Taylor's theorem guarantees that the function is approximately linear if the triangle you currently have is small enough. In essence, what that means is that while the algorithm never actually asks for a gradient, it is still following a gradient direction of some sort.

But imagine a situation where the objective function is not differentiable along a line just past the edge between the two better points. Say that it has a "crease" or "fold", like in your figure. In that case, all assumptions about whether that reflected point will be better than the old one are invalid, and in many cases it may not actually be. What happens in that case is that the algorithm will continue to shrink the triangle until eventually it may make progress again, but it is clear that you shouldn't expect it to converge rapidly.

$\endgroup$
8
  • $\begingroup$ Thanks, that is an interesting take on things, I'll ponder on this. As for the OP, what baffles me is that there is an obvious downhill path at all points towards the (known!) minimum, so the reflections should IMO tend to be downhill at all times. That this does not happen (for NM to terminate early it needs to "reflect in" or shrink many times) seems odd on the face of it. $\endgroup$
    – m4r35n357
    Apr 4 at 17:25
  • $\begingroup$ If the fold is near the good edge, then the reflected point on the other side is no better than the original one. The algorithm's choice in that case is to shrink the triangle, but you will soon again be in the same situation. $\endgroup$ Apr 4 at 23:20
  • $\begingroup$ That sounds right to me - I was grappling for the right words myself. I suppose we must also conclude that "sliding into the groove" at some point is pretty much inevitable (perhaps even more so in higher dimensions?), in other words the "clear" downhill path is "divergent/unstable". $\endgroup$
    – m4r35n357
    Apr 5 at 9:18
  • 2
    $\begingroup$ @m4r35n357 All (good) derivative-free algorithms have the property that they choose a search direction or a new point based on something that, when looked at carefully, is an approximation of the gradient of the objective function computed from the already accumulated knowledge. That's why they're efficient -- you somehow need to come up with a descent direction. But as a consequence, they all also suffer if the objective function is not differentiable. $\endgroup$ Apr 5 at 17:08
  • 1
    $\begingroup$ @m4r35n357 The algorithm shrinks the search domain $\Omega_n$ towards the currently best point (and consequently away from the currently worst points). Your gradient is right there. $\endgroup$ Apr 6 at 21:13
7
$\begingroup$

Interesting question - just like the previous one.

Your test function is indeed annoying for quite a few solvers, and it appears to me that it might belong to the Schwefel family (see, for example, the Schwefel20 function):

enter image description here

And its 3D representation:

enter image description here

Other Schwefel functions are catalogued in my benchmarks here:

https://infinity77.net/go_2021/scipy_test_functions_nd_S.html

I have run a few optimizers here and there on your (modified) test function, with these specs:

  • Varying dimensionality (2 to 9)
  • With random starting points in the interval -512 < x < 512 (the random starting point is the same for all solvers)
  • Maximum 50,000 functions evaluations

I have tried most of the (global) solvers described in my benchmark page:

https://infinity77.net/go_2021/index.html#algorithms-tested-algorithms

And I get this nice table of objective function value vs. dimensionality vs. minimizers:

enter image description here

Basically, the vast majority of the really robust global solvers got to the global minimum without breaking a sweat. That said, global solvers that rely on gradient-based local minimizers in the minimization phase do take a hit compared to the others (I have set AMPGO and Dual Annealing to use L-BFGS-B as the local minimizer).

Since you seem passionate about optimization, I'd suggest you to throw your optimizers at the "HappyCat" test function:

enter image description here

Often defined like this:

enter image description here

I found that it's a hard one to properly minimize.

Back to your problem, fun would be to test local solvers (gradient-based or gradient-free) with varying dimensionality, and possibly report on the success rate and on the number of functions evaluations used. NLOpt and SciPy are a good starting point, with large collections of local minimizers.

$\endgroup$
4
  • $\begingroup$ Yes, I found "treacle" after experimenting with simple things like sum(|x_i|). But the abs() on its own it trivially "easy", the sqrt() is what makes "treacle" sticky ;) I am engrossed in my "vanity" project(s), so I am happy to do experiments within that environment (including "Happy Cat" - thanks for that!), but not so inclined to set up other environments (e.g. my models are all shared between algorithms that I have coded myself, in c). Incidentally the only "Schwefel" function I am familiar with is this beast: sfu.ca/~ssurjano/schwef.html $\endgroup$
    – m4r35n357
    Apr 4 at 9:06
  • $\begingroup$ Incidentally, I am using equation (3) from researchgate.net/publication/…. I think your exponent in the first term is off by a factor of two compared with that. Apologies if I have messed up ;) $\endgroup$
    – m4r35n357
    Apr 4 at 11:01
  • $\begingroup$ There are different formulations of the HappyCat function - in my Python code, the exponent in the first term is actually a variable, i.e., you can make it 1/4, 1/8, whatever you like, to test different behaviors. $\endgroup$
    – Infinity77
    Apr 4 at 11:07
  • $\begingroup$ Yes, it is variable in that paper, too (which looks like the original), it just looks like your equation above is missing a power of two, or includes it in $\alpha$. Incidentally, it is starting to look (to me) like the "hard part" in general is fractional powers. I suppose I should be enquiring whether these functions are representative of real-life problems, or just good for testing optimizers ;) $\endgroup$
    – m4r35n357
    Apr 4 at 11:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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