Abstract
This paper presents basic features of a new family of algorithms for unconstrained derivative-free optimization, based on line searches along directions generated from QR factorizations of past direction matrices. Emphasis is on fast descent with a low number of function values, so that the algorithm can be used for fairly expensive functions. The theoretical total time overhead needed per function evaluation is of order O(n 2), where n is the problem dimension, but the observed overhead is much smaller. Numerical results are given for a particular algorithm VXQR1 from this family, implemented in Matlab, and evaluated on the scalability test set of Herrera et al. (http://www.sci2s.ugr.es/eamhco/CFP.php, 2010) for problems in dimensions n ∈ {50, 100, 200, 500, 1,000}. Performance depends a lot on the graph \(\{(t,f(x+th))\mid t\in[0,1]\}\) of the function along line segments. The algorithm is typically very fast on smooth problems with not too rugged graphs, and on problems with a roughly separable structure. It typically performs poorly on problems where the graph along many directions is highly multimodal without pronounced overall slope (e.g., for smooth functions with superimposed oscillations of significant size), where the graphs along many directions are piecewise constant (e.g., for problems minimizing a maximum norm), or where the function overflows on the major part of the search region and no starting point with finite function value is known.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.References
Ashlock D (2006) Evolutionary computation for modeling and optimization. Springer, Berlin
Auger A, Hansen N (2005) A restart CMA evolution strategy with increasing population size. In: The 2005 IEEE congress on evolutionary computation, vol 2, pp 1769–1776
Bélisle CJ, Romeijn HE, Smith RL (1993) Hit-and-run algorithms for generating multivariate distributions. Math Oper Res 18:255–266
Conn AR, Scheinberg K, Vicente LN (2009) Introduction to derivative-free optimization. SIAM, Philadelphia, PA
Csendes T, Pál L, Sendin JOH, Banga JR (2008) The GLOBAL optimization method revisited. Optim Lett 2:445–454
Dorigo M, Stützle T (2004) Ant colony optimization. MIT Press, Cambridge
Eberhart R, Kennedy J (1995) A new optimizer using particle swarm theory. In: Proceedings of sixth international symposium micro machine and human science. Nagoya, Japan, pp 39–43
Eshelman LJ, Schaffer JD (1993) Real-coded genetic algorithm and interval schemata. In: Whitley D (ed) Foundations of genetic algorithms workshop (FOGA-92). Vail, CO, pp 187–202
Fan SS, Zahara E (2007) A hybrid simplex search and particle swarm optimization for unconstrained optimization. Eur J Oper Res 181:527–548
Gilmore P, Kelley CT (1995) An implicit filtering algorithm for optimization of functions with many local minima. SIAM J Optim 5:269–285
Glover F (1995) Tabu thresholding: Improved search by nonmonotonic trajectories. ORSA J Comput 7:426–442
Hansen N (2006) The CMA evolution strategy: a comparing review. In: Lozano JA (ed) Towards a new evolutionary computation. Advances on estimation of distribution algorithms. Springer, Berlin, pp 75–102
Hansen N, Auger A, Ros R, Finck S, Pošik P (2010) Comparing results of 31 algorithms from the black-box optimization benchmarking BBOB-2009, Manuscript. http://www.lri.fr/hansen/gecco09-results-2010.pdf
Herrera F, Lozano M, Molina D (2010) Test suite for the special Issue of soft computing on scalability of evolutionary algorithms and other metaheuristics for large scale continuous optimization problems. http://www.sci2s.ugr.es/eamhco/CFP.php
Hooke R, Jeeves TA (1961) “Direct Search” solution of numerical and statistical problems. J ACM 8:212–229
Huyer W, Neumaier A (1999) Global optimization by multilevel coordinate search. J Glob Optim 14:331–355
Huyer W, Neumaier A (2008) SNOBFIT—stable noisy optimization by branch and Fit. ACM Trans Math Softw 35 (Article 9)
Jones DR, Schonlau M, Welch WJ (1998) Efficient global optimization of expensive black-box functions. J Glob Optim 13:455–492
Jones DR, Perttunen CD, Stuckman BE (1993) Lipschitzian optimization without the Lipschitz constant. J Optim Theory Appl 79:157–181
Kelley CT (1999) Detection and remediation of stagnation in the Nelder-Mead algorithm using a sufficient decrease condition. SIAM J Optim 10:43–55
Kolda TG, Lewis RM, Torczon VJ (2003) Optimization by direct search: new perspectives on some classical and modern methods. SIAM Rev 45:385–482
Michalewicz Z, Fogel DB (2004) How to solve it: modern heuristics. Springer, Berlin
NAG Library Chapter Contents (2009) E05−global optimization of a function. NAG Library, Mark 22. http://www.nag.co.uk/numeric/FL/nagdoc_fl22/xhtml/E05/e05conts.xml
Nelder JA, Mead R (1965) A simplex method for function minimization. Comput J 7:308–313
Neumaier A (2001) Introduction to numerical analysis. Cambridge University Press, Cambridge
Pintér JD (1995) Global optimization in action: continuous and Lipschitz optimization. Implementations and applications. Kluwer, Dordrecht
Powell MJD (2008) Developments of NEWUOA for minimization without derivatives. IMA J Numer Anal 28:649–664
Rios LM (2009) Algorithms for derivative-free optimization. PhD thesis, University of Illinois at Urbana-Champaign
Rios LM, Sahinidis NV (2009) Derivative-free optimization: a review of algorithms and comparison of software implementations. In: Advances in optimization II (AIChE 2009)
Sacks J, Welch WJ, Mitchell TJ, Wynn HP (1989) Design and analysis of computer experiments (with discussion). Stat Sci 4:409–435
Storn R, Price K (1997) Differential evolution—a simple and efficient heuristic for global optimization over continuous spaces. J Glob Optim 11:341–359
Torczon V (1991) On the convergence of multidirectional search algorithms. SIAM J Optim 1:123–145
Törn A, Žilinskas A (1989) Global optimization. Springer, New York
Van Laarhoven PJM, Aarts EHL (1987) Simulated annealing: theory and applications. Kluwer, Dordrecht
Author information
Authors and Affiliations
Corresponding author
Appendices
Appendices
The appendices contain figures and tables recording more details about the behavior of VXQR1 on the test problems. “Appendix A” displays for dimensions n = 100 and n = 1,000 the history of best function values for the test problems that were solved successfully for n = 100. Results for the other test problems and for all dimensions tested can be found in the web supplement (Neumaier, VXQR1. http://www.mat.univie.ac.at/∼neum/software/vxqr1/).
“Appendix B” gives median function values after 5,000n function values together with the corresponding results for the reference algorithms DE, CHC, and (for n ≠ 1,000) G_CMA-ES, taken from Herrera et al. (2010). Corresponding tables for minimum, maximum, and mean function values after 5,000n function values can also be found in the web supplement (Neumaier, VXQR1. http://www.mat.univie.ac.at/∼neum/software/vxqr1/).
Appendix A: Progress figures
The following figures give a dynamical view of the difference between the best function value in each run and the global minimum, as a function of the number of function values. The final value of each run, rounded upwards towards the target (if needed) is indicated by a circled dot. A nearly vertical dropdown of a curve indicates that the close neighborhood of the global minimum was reached. To avoid the figure scaling to be determined by huge initial function values (sometimes of the order of ≫10200), the cut-off value 1014 is used in the upper part of the figures.
The captions describe the function used, the dimension, and the median time needed to solve the resulting problem—rounded upwards to full seconds, ± the median of the absolute deviation. (Since some machines in our parallel environment were much slower than the others, mean values and standard deviations were not meaningful.)
The lower left corner reports the minimum, median, and maximum number of function values needed to reach the target value indicated, and the minimum, median, and maximum of the difference between the best function value and the global minimum.
F3 was run twice, first with 5,000n function values (for the tables), then with 50,000n function values (to see the scaling behavior). The present figures record the latter, more informative runs.
Appendix B: Comparison of final median results
| DE | CHC | G-CMA-ES | VXQR1 |
|---|---|---|---|---|
n = 50 | ||||
F1 | 0.00e+00 | 1.67e−11 | 0.00e+00 | 0.00e+00 |
F2 | 3.29e−01 | 6.19e+01 | 2.64e−11 | 1.66e+00 |
F3 | 2.90e+01 | 1.25e+06 | 0.00e+00 | 1.83e−09 |
F4 | 1.51e−13 | 7.43e+01 | 1.08e+02 | 0.00e+00 |
F5 | 0.00e+00 | 1.67e−03 | 0.00e+00 | 5.68e−14 |
F6 | 1.42e−13 | 6.15e−07 | 2.11e+01 | 2.84e−13 |
F7 | 0.00e+00 | 2.66e−09 | 7.67e−11 | 0.00e+00 |
F8 | 3.54e+00 | 2.24e+02 | 0.00e+00 | 0.00e+00 |
F9 | 2.73e+02 | 3.10e+02 | 1.61e+01 | 9.21e+00 |
F10 | 0.00e+00 | 7.30e+00 | 6.71e+00 | 0.00e+00 |
F11 | 5.60e−05 | 2.16e+00 | 2.83e+01 | 1.01e+01 |
F12 | 5.27e−13 | 9.57e−01 | 1.87e+02 | 1.34e+00 |
F13 | 2.44e+01 | 2.08e+06 | 1.97e+02 | 2.51e+00 |
F14 | 2.58e−08 | 6.17e+01 | 1.05e+02 | 1.37e−01 |
F15 | 0.00e+00 | 3.98e−01 | 8.12e−04 | 8.01e−08 |
F16* | 1.51e−09 | 2.95e−09 | 4.22e+02 | 4.33e+00 |
F17* | 6.83e−01 | 2.26e+04 | 6.71e+02 | 1.04e+01 |
F18* | 1.20e−04 | 1.58e+01 | 1.27e+02 | 4.75e−01 |
F19* | 0.00e+00 | 3.59e+02 | 4.03e+00 | 0.00e+00 |
n = 100 | ||||
F1 | 0.00e+00 | 3.56e−11 | 0.00e+00 | 0.00e+00 |
F2 | 4.34e+00 | 8.58e+01 | 1.62e−10 | 5.17e+01 |
F3 | 7.81e+01 | 4.19e+06 | 2.27e+00 | 1.86e−08 |
F4 | 4.23e−13 | 2.19e+02 | 2.50e+02 | 0.00e+00 |
F5 | 0.00e+00 | 3.83e−03 | 0.00e+00 | 0.00e+00 |
F6 | 3.13e−13 | 4.10e−07 | 2.13e+01 | 8.24e−13 |
F7 | 0.00e+00 | 1.40e−02 | 6.98e−07 | 0.00e+00 |
F8 | 3.47e+02 | 1.69e+03 | 0.00e+00 | 0.00e+00 |
F9 | 5.06e+02 | 5.86e+02 | 1.06e+02 | 1.85e+01 |
F10 | 0.00e+00 | 3.30e+01 | 1.68e+01 | 0.00e+00 |
F11 | 1.29e−04 | 7.32e+01 | 1.51e+02 | 1.74e+01 |
F12 | 6.18e−11 | 1.03e+01 | 4.20e+02 | 4.56e+00 |
F13 | 6.17e+01 | 2.70e+06 | 4.12e+02 | 1.08e+01 |
F14 | 1.30e−07 | 1.66e+02 | 2.52e+02 | 3.59e−01 |
F15 | 0.00e+00 | 8.13e+00 | 4.13e−01 | 1.21e−05 |
F16* | 3.53e−09 | 2.23e+01 | 8.48e+02 | 8.34e+00 |
F17* | 1.28e+01 | 1.47e+05 | 1.52e+03 | 2.92e+01 |
F18* | 2.86e−04 | 7.00e+01 | 3.13e+02 | 1.34e+00 |
F19* | 0.00e+00 | 5.45e+02 | 1.47e+01 | 1.16e−10 |
n = 200 | ||||
F1 | 0.00e+00 | 8.34e−01 | 0.00e+00 | 0.00e+00 |
F2 | 1.93e+01 | 1.03e+02 | 9.91e−10 | 8.68e+01 |
F3 | 1.77e+02 | 2.01e+07 | 8.95e+01 | 2.87e+01 |
F4 | 3.58e−12 | 5.40e+02 | 6.68e+02 | 0.00e+00 |
F5 | 0.00e+00 | 8.76e−03 | 0.00e+00 | 7.96e−13 |
F6 | 6.54e−13 | 1.23e+00 | 2.14e+01 | 2.70e−12 |
F7 | 0.00e+00 | 2.59e−01 | 2.61e−02 | 0.00e+00 |
F8 | 5.33e+03 | 9.38e+03 | 0.00e+00 | 0.00e+00 |
F9 | 1.01e+03 | 1.19e+03 | 3.81e+02 | 4.32e+01 |
F10 | 0.00e+00 | 7.13e+01 | 4.41e+01 | 0.00e+00 |
F11 | 2.59e−04 | 3.85e+02 | 7.93e+02 | 3.89e+01 |
F12 | 9.36e−10 | 7.44e+01 | 9.08e+02 | 2.71e+01 |
F13 | 1.36e+02 | 5.75e+06 | 9.34e+02 | 6.21e+01 |
F14 | 2.71e−07 | 4.29e+02 | 6.24e+02 | 8.56e−01 |
F15 | 0.00e+00 | 2.14e+01 | 2.10e+00 | 5.66e−03 |
F16* | 7.26e−09 | 1.60e+02 | 1.90e+03 | 2.94e+01 |
F17* | 3.70e+01 | 1.75e+05 | 3.33e+03 | 5.66e+01 |
F18* | 4.70e−04 | 2.12e+02 | 6.88e+02 | 4.18e+00 |
F19* | 0.00e+00 | 2.06e+03 | 5.74e+02 | 7.87e−07 |
n = 500 | ||||
F1 | 0.00e+00 | 2.84e−12 | 0.00e+00 | 0.00e+00 |
F2 | 5.33e+01 | 1.29e+02 | 3.31e−04 | 9.43e+01 |
F3 | 4.74e+02 | 1.14e+06 | 3.55e+02 | 2.11e+02 |
F4 | 9.22e−03 | 1.91e+03 | 2.07e+03 | 0.00e+00 |
F5 | 0.00e+00 | 6.98e−03 | 0.00e+00 | 5.32e−12 |
F6 | 1.65e−12 | 5.16e+00 | 2.15e+01 | 8.98e−12 |
F7 | 0.00e+00 | 1.27e−01 | 2.14e+143 | 0.00e+00 |
F8 | 6.11e+04 | 7.22e+04 | 2.31e−06 | 0.00e+00 |
F9 | 2.52e+03 | 3.00e+03 | 1.76e+03 | 5.95e+01 |
F10 | 0.00e+00 | 1.86e+02 | 1.27e+02 | 0.00e+00 |
F11 | 6.71e−04 | 1.81e+03 | 4.18e+03 | 7.32e+01 |
F12 | 6.98e−09 | 4.48e+02 | 2.59e+03 | 1.08e+02 |
F13 | 3.58e+02 | 3.22e+07 | 2.87e+03 | 2.40e+02 |
F14 | 9.01e−07 | 1.46e+03 | 1.95e+03 | 2.81e+00 |
F15 | 0.00e+00 | 6.01e+01 | 5.57e+258 | 1.19e−02 |
F16* | 2.05e−08 | 9.55e+02 | 5.43e+03 | 3.69e+01 |
F17* | 1.11e+02 | 8.40e+05 | 9.50e+03 | 1.47e+02 |
F18* | 1.22e−03 | 7.32e+02 | 2.06e+03 | 8.33e+00 |
F19* | 0.00e+00 | 1.76e+03 | 2.50e+06 | 8.48e−04 |
n = 1,000 | ||||
F1 | 0.00e+00 | 1.36e−11 |
| 0.00e+00 |
F2 | 8.44e+01 | 1.44e+02 |
| 9.64e+01 |
F3 | 9.69e+02 | 8.75e+03 |
| 6.05e+02 |
F4 | 1.32e+00 | 4.76e+03 |
| 5.68e−14 |
F5 | 0.00e+00 | 7.02e−03 |
| 1.09e−11 |
F6 | 3.30e−12 | 1.38e+01 |
| 1.67e−11 |
F7 | 0.00e+00 | 3.52e−01 |
| 0.00e+00 |
F8 | 2.46e+05 | 3.11e+05 |
| 0.00e+00 |
F9 | 5.13e+03 | 6.11e+03 |
| 9.99e+01 |
F10 | 0.00e+00 | 3.83e+02 |
| 0.00e+00 |
F11 | 1.35e−03 | 4.82e+03 |
| 1.12e+02 |
F12 | 1.70e−08 | 1.05e+03 |
| 2.24e+02 |
F13 | 7.29e+02 | 6.66e+07 |
| 5.39e+02 |
F14 | 9.95e−01 | 3.62e+03 |
| 5.64e+00 |
F15 | 0.00e+00 | 8.37e+01 |
| 2.70e−02 |
F16* | 4.19e−08 | 2.32e+03 |
| 6.35e+01 |
F17* | 2.35e+02 | 2.04e+07 |
| 2.97e+02 |
F18* | 2.37e−03 | 1.72e+03 |
| 1.57e+01 |
F19* | 0.00e+00 | 4.20e+03 |
| 1.37e−03 |
Rights and permissions
About this article
Cite this article
Neumaier, A., Fendl, H., Schilly, H. et al. VXQR: derivative-free unconstrained optimization based on QR factorizations. Soft Comput 15, 2287–2298 (2011). https://doi.org/10.1007/s00500-010-0652-5
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00500-010-0652-5