15
$\begingroup$

There seem to be two main kinds of test function for no-derivative optimizers:

  • one-liners like the Rosenbrock function ff., with start points
  • sets of real data points, with an interpolator

Is it possible to compare say 10d Rosenbrock with any real 10d problems ?
One could compare in various ways: describe the structure of local minima,
or run optimizers A B C on Rosenbrock and on some real problems;
but both of these seem difficult.

(Maybe theorists and experimenters are just two quite different cultures, so I'm asking for a chimera ?)

See also:

(Added in September 2014):
The plot below compares 3 DFO algorithms on 14 test functions in 8d from 10 random start points: BOBYQA PRAXIS SBPLX from NLOpt
$\times$ 14 N-dimensional test functions, Python under gist.github from this Matlab by A. Hedar
$\times$ 10 uniform-random startpoints in each function's bounding box.

On Ackley, for example, the top row shows that SBPLX is best and PRAXIS terrible; on Schwefel, the bottom right panel shows SBPLX finding a minimum on the 5 th random start point.

Overall, BOBYQA is best on 1, PRAXIS on 5, and SBPLX (~ Nelder-Mead with restarts) on 7 of 13 test functions, with Powersum a tossup. YMMV ! In particular, Johnson says, "I would advise you not to use function-value (ftol) or parameter tolerances (xtol) in global optimization."

Conclusion: don't put all your money on one horse, or on one test function.

enter image description here

Improve this question
$\endgroup$
7
  • $\begingroup$ After a long time making do with arbitrary test functions, I have recently come up with a really neat & compact real world function myself (based on RF filter synthesis), but I'm not sure such an old question is the place to mention it! Is this still a live issue here? I don't think it would count as a question, so I have to find one to answer ;) $\endgroup$
    – m4r35n357
    Commented Jun 13 at 15:35
  • $\begingroup$ @m4r35n357, "If you want to sell it, you'll have to explain it." Have you explained your idea on e.g. github.com, or in a kaggle.com contest ? Not to discourage you, but most academics are happy with Rosenbrock or variants like Nesterov. And in industry, people who optimize bridges or drugs or weapons ... have decades of experience, laugh at simple test functions. $\endgroup$
    – denis
    Commented Jun 20 at 16:27
  • $\begingroup$ It is not for sale, it is already downloadable on Github ;) I am an ageing hobbyist programmer who happens to have found something useful (to me), but I don't believe that this is the right or best place to "plug" it, as I said above. Electrical engineering has this great thing called the frequency domain, which provides more or less infinite test points/data for any circuit you can come up with. That is the key idea! $\endgroup$
    – m4r35n357
    Commented Jun 21 at 9:19
  • $\begingroup$ By "sell" I don't mean for cash, but how to get other people interested (where on github ?) You might try dsp.stackexchange.com/search?q=RF $\endgroup$
    – denis
    Commented Jun 21 at 9:31
  • $\begingroup$ I know (hence smiley), but this really is a take it or leave it thing. I certainly don't want the stress and pressure of "supporting" it! Although I am experimenting with doing actual filter designs with it, it is not a serious tool, and is IMO more useful to the optimization community than the RF one! $\endgroup$
    – m4r35n357
    Commented Jun 21 at 9:52

4 Answers 4

Reset to default
13
$\begingroup$

Simple functions like Rosenbrock's are used to debug and pre-test newly written algorithms: They are fast to implement and to execute, and a method that cannot solve the standard problems well is unlikely to work well on real life problems.

For a recent thorough comparison of derivative-free methods for expensive functions, see Derivative-free optimization: A review of algorithms and comparison of software implementations. L.M. Rios, N.V. Sahinidis - doi 10.1007/s10898-012-9951-y Journal of Global Optimization, 2012. (See also the accompanying webpage: http://archimedes.cheme.cmu.edu/?q=dfocomp)

Improve this answer
$\endgroup$
3
  • $\begingroup$ Prof. Neumaier, could you point to some real problems, evidence, for "a method that cannot solve the standard problems well is unlikely to work well on real life problems" ? I realize that that's not easy. (I'd be interested in your comments on Hooker.) Also, a quick look at c models from your link shows princetonlibgloballib requires AMPL, and source_convexmodels *.c all have a missing ";" after fscanf() -- trivial but $\endgroup$
    – denis
    Commented Aug 11, 2012 at 11:07
  • 1
    $\begingroup$ @Denis: Problems like Rosenbrock stem from the early days of automated optimization, where people isolated the typical difficulties in simple representative examples that can be studied without the numerical complexities of real-life problems. Thus they are not really artificial, but simplified models of real difficulties. For example, Rosenbrock illustrates the combined effect of strong nonlinearity and mild ill-condition. $\endgroup$
    – Arnold Neumaier
    Commented Aug 11, 2012 at 11:14
  • $\begingroup$ The AMPL site ampl.com offers a free student version for AMPL. $\endgroup$
    – Arnold Neumaier
    Commented Aug 11, 2012 at 11:15
8
$\begingroup$

The advantage of synthetic testcases like the Rosenbrock function is that there is existing literature to compare with, and there is a sense in the community how good methods behave on such testcases. If everyone used their own testcase it would be much harder to come to a consensus which methods work and which don't.

Improve this answer
$\endgroup$
1
$\begingroup$

(I hope there is no objection to my tacking onto the end of this discussion. I'm new here, so please let me know if I have transgressed!)

Test functions for evolutionary algorithms are now much more complicated than they were even 2 or 3 years ago, as can be seen by the suites used in competitions at conferences like the (very recent) 2015 Congress on Evolutionary Computation. See:

http://www.cec2015.org/

These test suites now include functions with several non-linear interactions between variables. The number of variables can be as large as 1000, and I would guess that might increase in the near future.

Another very recent innovation is a "Black Box Optimization Competition". See: http://bbcomp.ini.rub.de/

An algorithm can query the value f(x) for a point x, but it does not obtain gradient information, and in particular it cannot make any assumptions on the analytic form of the objective function.

In a sense, this might be closer to what you referred to as a "real problem" but in an organised, objective setting.

Improve this answer
$\endgroup$
4
0
$\begingroup$

You can have the best of both worlds. NIST has a set of problems for minimizers, like fitting this 10th degree polinomial, with expected results and uncertainties. Of course, proving that these values are the actual best solution, or the existence and properties of other local minima is more difficult than on a controlled mathematical expression.

Improve this answer
$\endgroup$
1

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.