Survey of derivative-free optimization

Min Xi; Wenyu Sun; Jun Chen

doi:10.3934/naco.2020050

Article Contents

2020, Volume 10, Issue 4: 537-555. Doi: 10.3934/naco.2020050

This issue Previous Article Two-stage stochastic variational inequalities for Cournot-Nash equilibrium with risk-averse players under uncertainty Next Article A parallel Gauss-Seidel method for convex problems with separable structure

Survey of derivative-free optimization

1.
School of Mathematical Sciences, Jiangsu Key Laboratory for NSLSCS, Nanjing Normal University, Nanjing 210023, China
2.
School of Mathematics and Statistics, Guangdong University of Foreign Studies, Guangzhou 510006, China
3.
School of Information Engineering, Nanjing Xiaozhuang University, Nanjing 211171, China

^* Corresponding author: Min Xi
^* Corresponding author: Min Xi

Received: April 2020

Revised: September 2020

Published: September 2020

This research was supported by the National Natural Science Foundation of China under grants 11571178

Abstract Full Text(HTML) Related Papers Cited by

Abstract

In this survey paper we present an overview of derivative-free optimization, including basic concepts, theories, derivative-free methods and some applications. To date, there are mainly three classes of derivative-free methods and we concentrate on two of them, they are direct search methods and model-based methods. In this paper, we first focus on unconstrained optimization problems and review some classical direct search methods and model-based methods in turn for these problems. Then, we survey a number of derivative-free approaches for problems with constraints, including an algorithm we proposed for spherical optimization recently.

Keywords:

Mathematics Subject Classification: Primary: 90C56; Secondary: 90C30.

Citation:

FullText(HTML)

Related Papers

Cited by

References

[1]	M. A. Abramson and C. Audet, Convergence of mesh adaptive direct search to second-order stationary points, SIAM Journal on Optimization, 17 (2006), 606-609. doi: 10.1137/050638382.
[2]	P. Alberto, F. Nogueira, H. Rocha and L. N. Vicente, Pattern search methods for user-provided points: Application to molecular geometry problems, SIAM Journal on Optimization, 14 (2004), 1216-1236. doi: 10.1137/S1052623400377955.
[3]	Audet, Dennis and Jr., A pattern search filter method for nonlinear programming without derivatives, SIAM Journal on Optimization, 14 (2004), 980-1010. doi: 10.1137/S105262340138983X.
[4]	Audet, Dennis and Jr., Mesh adaptive direct search algorithms for constrained optimization, SIAM Journal on Optimization, 17 (2006), 188-217. doi: 10.1137/040603371.
[5]	C. Audet, Convergence results for generalized pattern search algorithms are tight, Optimization and Engineering, 5 (2004), 101-122. doi: 10.1023/B:OPTE.0000033370.66768.a9.
[6]	A. S. Bandeira, K. Scheinberg and L. N. Vicente, Convergence of trust-region methods based on probabilistic models, Mathematical Programming, 24 (2014), 1238-1264. doi: 10.1137/130915984.
[7]	A. J. Booker, J. E. Dennis, Jr., P. D. Frank, D. W. Moore and D. B. Serafini, Managing surrogate objectives to optimize a helicopter rotor design-Further experiments, in AIAA Paper 1998–4717, 8th AIAA/ISSMO Symposium on Multidisciplinary Analysis and Optimization, St. Louis, MO, 1998.
[8]	M. J. Box, A new method of constrained optimization and a comparison with other methods, Computer Journal, 8 (1965), 42-52. doi: 10.1093/comjnl/8.1.42.
[9]	T. D. Choi and C. T. Kelley, Superlinear convergence and implicit filtering, SIAM Journal on Optimization, 10 (2000), 1149-1162. doi: 10.1137/S1052623499354096.
[10]	B. Colson and Ph. L. Toint, Exploiting band structure in unconstrained optimization without derivatives, in Trends in Industrial and Applied Mathematics, Vol. 72 Applied Optimization, (eds. A.H. Siddiqi and M. Kocvera), Kluwer, (2002), 131–147. doi: 10.1023/A:1016090421852.
[11]	B. Colson and Ph. L. Toint, Optimizing partially separable functions without derivatives, Optimization Methods and Software, 20 (2005), 493-508. doi: 10.1080/10556780500140227.
[12]	P. Conejo, E. Karas and P. Ledroso, A trust-region derivative-free algorithm for constrained optimization, Optimization Methods and Software, 30 (2015), 1126-1145. doi: 10.1080/10556788.2015.1026968.
[13]	A. R. Conn, N. I. M. Gould and Ph. L. Toint, Trust-Region Methods, SIAM, Philadephia, 2000. doi: 10.1137/1.9780898719857.
[14]	A. R. Conn, K. Scheinberg and Ph. L. Toint, On the convergence of derivative-free methods for unconstrained optimization, in Approximation Theory and Optimization: Tributes to M. J. D. Powell(eds. A. Iserles and M. Buhmann), Cambridge University Press, Cambridge, (1996), 83–108.
[15]	A. R. Conn, K. Scheinberg and Ph. L.Toint, Recent progress in unconstrained nonlinear optimization without derivatives, Mathematical Programming, 79 (1997), 397-414. doi: 10.1016/S0025-5610(97)00054-3.
[16]	A. R. Conn, K. Scheinberg and L. N. Vicente, Geometry of interpolation sets in derivative free optimization, Mathematical Programming, 111 (2008), 141-172. doi: 10.1007/s10107-006-0073-5.
[17]	A. R. Conn, K. Scheinberg and L. N. Vicente, Global convergence of general derivative-free trust-region algorithms to first- and second-order critical points, SIAM Journal on Optimization, 20 (2009), 387-415. doi: 10.1137/060673424.
[18]	A. R. Conn, K. Scheinberg and L. N. Vicente, Introduction to Derivative-free Optimization, MPS/SIAM Ser. Optim. 8, SIAM, Philadelphia, 2009. doi: 10.1137/1.9780898718768.
[19]	A. R. Conn and Ph. L. Toint, An algorithm using quadratic interpolation for unconstrained derivative-free optimization, in Nonlinear Optimization and Application (eds. G. Di. Pillo and F. Giannessi), Plenium Publishing, New York, (1996), 27–47.
[20]	J. E. Dennis Jr. and V. J. Torczon, Direct search methods on parallel machines, SIAM Journal on Optimization, 1 (1991), 448-474. doi: 10.1137/0801027.
[21]	L. C. W. Dixon, ASCIM-an accelerated constrained simplex technique, Computer-aided Design, 5 (1973), 22-32.
[22]	R. Duvigneau and M. Visonneau, Hydrodynamic design using a derivative-free method, Structural and Multidisciplinary Optimization, 28 (2004), 195-205.
[23]	E. Fermi and N. Metropolis, Los Alamos Unclassified Report LS–1492, in Technical Report, Los Alamos National Laboratory, Los Alamos, NM, 1952.
[24]	K. R. Fowler, J. P. Reese, C. E. Kees, J. E. Dennis, Jr., C. T. Kelley, C. T. Miller, C. Audet, A. J. Booker, G. Couyure, R. W. Darwin, M. W. Farthing, D. E. Finkel, J. M. Gablonsky, G. Gray and T. G. Kolda, A comparison of derivative-free optimization methods for groundwater supply and hydraulic capture community problems, Advances in Water Resources, 31 (2007), 743-757.
[25]	P. Gilmore and C. T. Kelley, An implicit filtering algorithm for optimization of functions with many local minima, SIAM Journal on Optimization, 5 (1995), 269-285. doi: 10.1137/0805015.
[26]	G. N. Grapiglia, J. Yuan and Y. Yuan, A derivative-free trust-region algorithm for composite nonsmooth optimization, Journal of Computational and Applied Mathematics, 35 (2016), 475-499. doi: 10.1007/s40314-014-0201-4.
[27]	W. L. Hare and R. A. Poliquin, Prox-regularity and stability of the proximal mapping, Journal of Convex Analysis, 14 (2007), 589-606.
[28]	G. H. Golub and C. F. Van Loan, Matrix Computations, Johns Hopkins University Press, Baltimore, MD, 2013.
[29]	R. Hooke and T. A. Jeeves, Direct search solution of numerical and statistical problems, Journal of the Association for Computing Machinery, 8 (1961), 212-229.
[30]	X. J. Huang and D. T. Zhu, An interior affine scaling cubic regularization algorithm for derivative-free optimization subject to bound constraints, Journal of Computational and Applied Mathematics, 321 (2017), 108-127. doi: 10.1016/j.cam.2017.02.028.
[31]	D. L. Keefer, Simpat: Self-bounding direct search method for optimization, Industrial and Engineering Chemistry Process Design and Development, 12 (1973), 92-99.
[32]	C. T. Kelley, Iterative Methods for Optimization, Frontiers Appl. Math. 18, SIAM, Philadelphia, 1999. doi: 10.1137/1.9781611970920.
[33]	T. G. Kolda and V. J. Torczon, On the convergence of asynchronous parallel pattern search, SIAM Journal on Optimization, 14 (2004), 939-964. doi: 10.1137/S1052623401398107.
[34]	J. Larson and S. C. Billups, Stochastic derivative-free optimization using a trust region framework, Computational Optimization and Applications, 64 (2016), 619-645. doi: 10.1007/s10589-016-9827-z.
[35]	T. Levina, Y. Levin, J. Mcgill and M. Nediak, Dynamic pricing with online learning and strategic consumers: An application of the aggregating algorithm, Operations Research, 57 (2009), 327-341.
[36]	R. M. Lewis and V. Torczon, Pattern search algorithms for bound constrained minimization, SIAM Journal on Optimization, 9 (1999), 1082-1099. doi: 10.1137/S1052623496300507.
[37]	R. M. Lewis and V. Torczon, Pattern search methods for linearly constrained minimization, SIAM Journal on Optimization, 10 (2000), 917-941. doi: 10.1137/S1052623497331373.
[38]	R. M. Lewis and V. Torczon, A globally convergent augmented Lagrangian pattern search algorithm for optimization with general constraints and simple bounds, SIAM Journal on Optimization, 12 (2002), 1075-1089. doi: 10.1137/S1052623498339727.
[39]	R. M. Lewis, V. Torczon and M. W. Trosset, Direct search methods: then and now, Journal of Computational and Applied Mathematics, 124 (2000), 191-207. doi: 10.1016/S0377-0427(00)00423-4.
[40]	S. Lucidi and M. Sciandrone, On the global convergence of derivative-free methods for unconstrained minimization, SIAM Journal on Optimization, 13 (2002), 97-116. doi: 10.1137/S1052623497330392.
[41]	G. Liuzzi, S. Lucidi and M. Sciandrone, Sequential penalty derivative-free methods for nonlinear constrained optimization, SIAM Journal on Optimization, 20 (2010), 2614-2635. doi: 10.1137/090750639.
[42]	A. L. Marsden, Aerodynamic Noise Control by Optimal Shape Design, Ph.D thesis, Stanford University, Stanford, CA, 2004.
[43]	J. H. May, Linearly Constrained Nonlinear Programming: A Solution Method That Does Not Require Analytic Derivatives, Ph.D thesis, Yale University, New Haven, CT, 1974.
[44]	J. C. Meza and M. L. Martinez, On the use of direct search methods for the molecular conformation problem, Journal of Computational Chemistry, 15 (1994), 627-632.
[45]	K. I. M. McKinnon, Convergence of the Nelder-Mead simplex method to a nonstationary point, SIAM Journal on Optimization, 9 (1998), 148-158. doi: 10.1137/S1052623496303482.
[46]	J. J. Moré and S. M. Wild, Benchmarking derivative-free optimization algorithms, SIAM Journal on Optimization, 20 (2009), 172-191. doi: 10.1137/080724083.
[47]	L. Nazareth and P. Tseng, Gilding the lily: A variant of the Nelder-Mead algorithm based on golden-section search, Computational Optimization and Applications, 22 (2002), 133-144. doi: 10.1023/A:1014842520519.
[48]	J. A. Nelder and R. Mead, A simplex method for function minimization, Computer Journal, 7 (1965), 308-313. doi: 10.1093/comjnl/7.4.308.
[49]	J. Nocedal and S. J. Wright, Numerical Optimization, 2$^nd$ edition, Springer-Verlag, New York, 2006.
[50]	M. J. D. Powell, A direct search optimization method that models the objective and constraint functions by linear interpolation, in Advances in Optimization and Numerical Analysis(eds. S. Gomez and J-P. Hennart), Kluwer Academic Publishers, Dordrecht, (1994), 52–67.
[51]	M. J. D. Powell, A direct search optimization method that models the objective by quadratic interpolation, in Presentation at the 5th Stockholm Optimization Days, 1994.
[52]	M. J. D. Powell, UOBYQA: Unconsrained optimization by quadratic approximation, Mathematical Programning, 92 (2002), 555-582. doi: 10.1007/s101070100290.
[53]	M. J. D. Powell, The NEWUOA software for unconstrained optimization without derivatives, in Large-Scale Nonlinear Optimization(eds. G. Di Pillo and M. Roma), Springer, New York, 2006. doi: 10.1007/0-387-30065-1_16.
[54]	M. J. D. Powell, The BOBYQA algorithm for bound constrained optimization without derivatives, Technical Report, Department of Applied Mathematics and Theoretical Physics, University of Cambridge, 2009.
[55]	C. J. Price, I. D. Coope and D. Byatt, A convergent variant of the Nelder Mead algorithm, Journal of Optimization Theory and Applications, 113 (2002), 5-19. doi: 10.1023/A:1014849028575.
[56]	P. R. Sampaio and Ph. L. Toint, A derivative-free trust-funnel method for equality-constrained, Computational Optimization and Applications, 61 (2015), 25-49. doi: 10.1007/s10589-014-9715-3.
[57]	M. Schäfer, B. Karasözen, Y. Uluda$\breve{g}$, K. Yapici and Ö. U$\breve{g}$ur, Numerical method for optimizing stirrer configurations, Computers and Chemical Engineering, 30 (2005), 183-190.
[58]	K. Scheinberg, Manual for Fortran Software Package DFO v2.0, 2003.
[59]	K. Scheinberg and Ph. L. Toint, Self-correcting geometry in model-based algorithms for derivative-free unconstrained optimization, SIAM Journal on Optimization, 20 (2010), 3512-3532. doi: 10.1137/090748536.
[60]	W. Spendley, G. R. Hext and F. R. Himsworth, Sequential application for simplex designs in optimisation and evolutionary operation, Technometrics, 4 (1962), 441-461. doi: 10.2307/1266283.
[61]	J. Takaki and N. Yamashita, A derivative-free trust-region algorithm for unconstrained optimization with controlled error, Numerical Algebra, Control and Optimization, 1 (2011), 117-145. doi: 10.3934/naco.2011.1.117.
[62]	V. Torczon, Multi-directional Search: A Direct Search Algorithm For Parallel Machines, Ph.D thesis, Rice University, Houston, TX, 1989.
[63]	V. Torczon, On the convergence of multidirectional search algorithms, SIAM Journal on Optimization, 1 (1991), 123-145. doi: 10.1137/0801010.
[64]	V. Torczon, On the convergence of pattern search algorithms, SIAM Journal on Optimization, 7 (1997), 1-25. doi: 10.1137/S1052623493250780.
[65]	P. Tseng, Fortified-descent simplicial search method: A general approach, SIAM Journal on Optimization, 10 (2000), 269-288. doi: 10.1137/S1052623495282857.
[66]	D. Winfield, Function and Functional Optimization by Interpolation in Data Table, Ph.D Thesis, Harvard University, Cambridge, MA, 1969.
[67]	D. Winfield, Function minimization by interpolation in a data table, J. Inst. Math. Appl., 12 (1973), 339-347.
[68]	J.-H. Yoon and C. A. Shoemaker, Comparison of optimization methods for ground-water bioremediation, Journal of Water Resources Planning and Management, 125 (1999), 54-63.