×

A discussion on variational analysis in derivative-free optimization. (English) Zbl 1473.49019

Derivative-Free Optimization (DFO) is the mathematical study of algorithms for continuous optimization that do not use first-order information. Thus, by definition, DFO studies algorithms that do not use derivatives, gradients, directional derivatives, subgradients, normal cones, tangent cones, etc. As such, it might seem that Variational Analysis would have limited value in DFO research. However, a study of DFO shows that this is a false conclusion. In fact, the many of the most successful DFO algorithms rely heavily on tools and results from Variational Analysis. In this paper, the author highlights some of this research and argue that Variational Analysis is a critical component to studying DFO.

MSC:

49J52 Nonsmooth analysis
90C56 Derivative-free methods and methods using generalized derivatives
65K05 Numerical mathematical programming methods
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] Amaioua, N.; Audet, C.; Conn, AR; Le Digabel, S., Efficient solution of quadratically constrained quadratic subproblems within the mesh adaptive direct search algorithm, Eur. J. Oper. Res., 268, 1, 13-24 (2018) · Zbl 1403.90618
[2] Audet, C., Convergence results for generalized pattern search algorithms are tight, Optim. Eng., 5, 2, 101-122 (2004) · Zbl 1085.90053
[3] Audet, C.; Béchard, V.; Le Digabel, S., Nonsmooth optimization through mesh adaptive direct search and variable neighborhood search, J Glob Optim, 41, 299-318 (2008) · Zbl 1157.90535
[4] Audet, C.; Côté, P.; Poissant, C.; Tribes, C., Monotonic grey box direct search optimization, Optim. Lett., 14, 3-18 (2020) · Zbl 1433.90200
[5] Audet, C.; Dennis, JEJr, Analysis of generalized pattern searches, SIAM J. Optim., 13, 3, 889-903 (2003) · Zbl 1053.90118
[6] Audet, C.; Dennis, JE, Jr. Mesh adaptive direct search algorithms for constrained optimization, SIAM J. Optim., 17, 1, 188-217 (2006) · Zbl 1112.90078
[7] Audet, C.; Dennis, JEJr; Le Digabel, S., Globalization strategies for mesh adaptive direct search, Comput. Optim. Appl., 46, 2, 193-215 (2010) · Zbl 1190.90204
[8] Audet, C.; Hare, W., Derivative-Free and Blackbox Optimization (2017), Switzerland: Springer International Publishing AG, Switzerland · Zbl 1391.90001
[9] Audet, C.; Hare, W., Algorithmic construction of the subdifferential from directional derivatives, Set-Valued Var. Anal., 26, 3, 431-447 (2018) · Zbl 1403.52009
[10] Audet, C., Hare, W.: Model-based methods in derivative-free nonsmooth optimization, chapter 18. In: Bagirov, A., Gaudioso, M., Karmitsa, N., Mäkelä, M (eds.) Numerical nonsmooth optimization. Springer (2020)
[11] Audet, C.; Ianni, A.; Le Digabel, S.; Tribes, C., Reducing the number of function evaluations in mesh adaptive direct search algorithms, SIAM J. Optim., 24, 2, 621-642 (2014) · Zbl 1297.90149
[12] Audet, C.; Ihaddadene, A.; Le Digabel, S.; Tribes, C., Robust optimization of noisy blackbox problems using the mesh adaptive direct search algorithm, Optim. Lett., 12, 4, 675-689 (2018) · Zbl 1403.90619
[13] Audet, C.; Le Digabel, S.; Tribes, C., The mesh adaptive direct search algorithm for granular and discrete variables, SIAM J. Optim., 29, 2, 1164-1189 (2019) · Zbl 1411.90229
[14] Audet, C.; Savard, G.; Zghal, W., A mesh adaptive direct search algorithm for multiobjective optimization, Eur. J. Oper. Res., 204, 3, 545-556 (2010) · Zbl 1181.90137
[15] Audet, C.; Tribes, C., Mesh-based nelder?mead algorithm for inequality constrained optimization, Comput. Optim. Appl., 71, 2, 331-352 (2018) · Zbl 1409.90181
[16] Aziz, M.; Hare, W.; Jaberipour, M.; Lucet, Y., Multi-fidelity algorithms for the horizontal alignment problem in road design, Eng. Optim., 0, 1-20 (2019)
[17] Bagirov, AM; Karasözen, B.; Sezer, M., Discrete gradient method: derivative-free method for nonsmooth optimization, J. Optim. Theory Appl., 137, 2, 317-334 (2008) · Zbl 1165.90021
[18] Bajaj, I.; Iyer, SS; Hasan, MMF, A trust region-based two phase algorithm for constrained black-box and grey-box optimization with infeasible initial point, Comput. Chem. Eng., 116, 306-321 (2018)
[19] Berahas, AS; Byrd, RH; Nocedal, J., Derivative-free optimization of noisy functions via quasi-N,ewton methods, SIAM J. Optim., 29, 2, 965-993 (2019) · Zbl 1411.90359
[20] Berghen, F.V.: CONDOR: A Constrained, Non-Linear, Derivative-Free Parallel Optimizer for Continuous, High Computing Load, Noisy Objective Functions. PhD Thesis, Université Libre de Bruxelles, Belgium (2004)
[21] Berghen, FV; Bersini, H., CONDOR, a new parallel, constrained extension of Powell’s UOBYQA algorithm: experimental results and comparison with the DFO algorithm, jcomam, 181, 157-175 (2005) · Zbl 1072.65088
[22] Bottou, L.; Curtis, FE; Nocedal, J., Optimization methods for large-scale machine learning, SIAM Rev., 60, 2, 223-311 (2018) · Zbl 1397.65085
[23] Burke, JV; Lewis, AS; Overton, ML, A robust gradient sampling algorithm for nonsmooth, nonconvex optimization, SIAM J. Optim., 15, 3, 751-779 (2005) · Zbl 1078.65048
[24] Chen, R.; Menickelly, M.; Scheinberg, K., Stochastic optimization using a trust-region method and random models, Math. Program., 169, 447-487 (2018) · Zbl 1401.90136
[25] Cocchi, G.; Liuzzi, G.; Papini, A.; Sciandrone, M., An implicit filtering algorithm for derivative-free multiobjective optimization with box constraints, Comput. Optim. Appl., 69, 2, 267-296 (2018) · Zbl 1400.90269
[26] Conn, A.R., Scheinberg, K., Toint, Ph.L.: A derivative free optimization algorithm in practice. In: Proceedings of 7th AIAA/USAF/NASA/ISSMO Symposium on Multidisciplinary Analysis and Optimization. http://perso.fundp.ac.be/phtoint/pubs/TR98-11.ps (1998)
[27] Conn, A.R., Scheinberg, K., Toint, P. h. L.: DFO (Derivative Free Optimization) https://projects.coin-or.org/Dfo (2001) · Zbl 1042.90617
[28] Conn, AR; Scheinberg, K., L.n. Vicente. Geometry of sample sets in derivative free optimization Polynomial regression and underdetermined interpolation, IMA J. Numer. Anal., 28, 4, 721-749 (2008)
[29] Conn, AR; Scheinberg, K.; Vicente, LN, Introduction to Derivative-Free MOS-SIAM Optimization. Series on Optimization (2009), Philadelphia: SIAM, Philadelphia
[30] Conn, AR; Toint, PhL, An Algorithm using Quadratic Interpolation for Unconstrained Derivative Free Optimization, 27-47 (1996), Berlin: Springer, Berlin · Zbl 0976.90102
[31] Coope, I.D., Tappenden, R.: Efficient calculation of regular simplex gradients. Comput. Optim. Appl. To appear (2019) · Zbl 1414.90363
[32] Custódio, AL; Madeira, JFA; Vaz, AIF; Vicente, LN, Direct multisearch for multiobjective optimization, SIAM J. Optim., 21, 3, 1109-1140 (2011) · Zbl 1230.90167
[33] Gramacy, RB; Le Digabel, S., The mesh adaptive direct search algorithm with treed Gaussian process surrogates, Pacific J. Optim., 11, 3, 419-447 (2015) · Zbl 1327.90308
[34] Hare, W., Compositions of convex functions and fully linear models, Optim. Lett., 11, 7, 1217-1227 (2017) · Zbl 1408.90323
[35] Hare, W.; Jaberipour, M., Adaptive interpolation strategies in derivative-free optimization: a case study, Pac. J. Optim., 14, 2, 327-347 (2018)
[36] Hare, W.; Jarry-Bolduc, G., Calculus identities for generalized simplex gradients Rules and applications, SIAM J. Optim., 30, 1, 853-884 (2020)
[37] Hare, W.; Nutini, J., A derivative-free approximate gradient sampling algorithm for finite minimax problems, Comput. Optim. Appl., 56, 1, 1-38 (2013) · Zbl 1300.90064
[38] Hare, W.; Nutini, J.; Tesfamariam, S., A survey of non-gradient optimization methods in structural engineering, Adv. Eng. Softw., 59, 19-28 (2013)
[39] Hare, W., Planiden, C., Sagastizábal, C.: A derivative-free VU-algorithm for convex finite-max problems. Optim. Methods Softw., (to appear). doi:10.1080/10556788.2019.1668944 · Zbl 1443.90331
[40] Hare, W.; Sagastizábal, C.; Solodov, M., A proximal bundle method for nonsmooth nonconvex functions with inexact information, Comput. Optim Appl., 63, 1, 1-28 (2016) · Zbl 1343.90069
[41] Hare, WL; Lucet, Y., Derivative-free optimization via proximal point methods, J. Optim. Theory Appl., 160, 1, 204-220 (2014) · Zbl 1291.90317
[42] Hooke, R.; Jeeves, TA, “Direct Search” solution of numerical and statistical problems, J. Assoc. Comput. Mach., 8, 2, 212-229 (1961) · Zbl 0111.12501
[43] Khan, KA; Larson, J.; Wild, SM, Manifold sampling for optimization of nonconvex functions that are piecewise linear compositions of smooth components, SIAM J. Optim., 28, 4, 3001-3024 (2018) · Zbl 1407.90351
[44] Larson, J.; Menickelly, M.; Wild, SM, Manifold sampling for ℓ1 nonconvex optimization, SIAM J. Optim., 26, 4, 2540-2563 (2016) · Zbl 1351.90167
[45] Larson, J.; Menickelly, M.; Wild, SM, Derivative-free optimization methods, Acta Numerica, 28, 287-404 (2019) · Zbl 1461.65169
[46] Lera, D.; Sergeyev, YD, GOSH: derivative-free global optimization using multi-dimensional space-filling curves, J. Global Optim., 71, 1, 193-211 (2018) · Zbl 1402.90133
[47] Liuzzi, G.; Lucidi, S.; Rinaldi, F.; Vicente, LN, Trust-region methods for the derivative-free optimization of nonsmooth black-box functions, SIAM J. Optim., 29, 4, 3012-3035 (2019) · Zbl 1427.90298
[48] Menickelly, M.; Wild, SM, Derivative-free robust optimization by outer approximations, Math. Program., 179, 1-2, 157-193 (2020) · Zbl 1435.90096
[49] Mifflin, R., A superlinearly convergent algorithm for minimization without evaluating derivatives, Math. Program., 9, 1, 100-117 (1975) · Zbl 0327.90027
[50] Müller, J., Day, M.: Surrogate optimization of computationally expensive black-box problems with hidden constraints. INFORMS J. Comput. To appear (2019)
[51] Nelder, JA; Mead, R., A simplex method for function minimization, Comput. J., 7, 4, 308-313 (1965) · Zbl 0229.65053
[52] Oeuvray, R.; Bierlaire, M., Boosters: a derivative-free algorithm based on radial basis functions, Int. J. Model. Simul., 29, 1, 26-36 (2009)
[53] Paquette, C., Scheinberg, K.: A stochastic line search method with convergence rate analysis (2018) · Zbl 1431.90153
[54] Polak, E.; Wetter, M., Precision control for generalized pattern search algorithms with adaptive precision function evaluations, SIAM J. Optim., 16, 3, 650-669 (2006) · Zbl 1113.90148
[55] Powell, M.J.D.: A direct search optimization method that models the objective and constraint functions by linear interpolation. In: Gomez, S., Hennart, J.-P. (eds.) Advances in Optimization and Numerical Analysis, Proceedings of the 6th Workshop on Optimization and Numerical Analysis, Oaxaca, Mexico, vol. 275, pp. 51-67, Kluwer Academic Publishers, Dordrecht (1994) · Zbl 0826.90108
[56] Powell, M.J.D.: UOBYQA: Unconstrained optimization by quadratic approximation. Technical Report DAMTP 2000/NA14, Department of Applied Mathematics and Theoretical Physics, University of Cambridge, Silver Street, Cambridge CB3 9EW, England (2000) · Zbl 1014.65050
[57] Powell, MJD, UOBYQA: Unconstrained Optimization by quadratic approximation, Math. Program., 92, 3, 555-582 (2002) · Zbl 1014.65050
[58] Powell, MJD, On trust region methods for unconstrained minimization without derivatives, Math. Program., 97, 3, 605-623 (2003) · Zbl 1106.90382
[59] Powell, MJD, Least Frobenius norm updating of quadratic models that satisfy interpolation conditions, Math. Program., 100, 1, 183-215 (2004) · Zbl 1146.90526
[60] Powell, M.J.D.: The BOBYQA algorithm for bound constrained optimization without derivatives. Technical report, Department of Applied Mathematics and Theoretical Physics, Cambridge University, UK (2009)
[61] Regis, RG, The calculus of simplex gradients, Optim. Lett., 9, 5, 845-865 (2015) · Zbl 1351.90168
[62] Regis, RG, On the properties of positive spanning sets and positive bases, Optim. Eng., 17, 1, 229-262 (2016) · Zbl 1364.90364
[63] Regis, RG; Shoemaker, CA, Parallel radial basis function methods for the global optimization of expensive functions, Eur. J. Oper. Res., 182, 2, 514-535 (2007) · Zbl 1178.90279
[64] Rios, LM; Sahinidis, NV, Derivative-free optimization: a review of algorithms and comparison of software implementations, J. Glob. Optim., 56, 3, 1247-1293 (2013) · Zbl 1272.90116
[65] Shashaani, S.; Hashemi, FS; Pasupathy, R., ASTRO-DF: a class of adaptive sampling trust-region algorithms for derivative-free stochastic optimization, SIAM J. Optim., 28, 4, 3145-3176 (2018) · Zbl 1403.90541
[66] Torczon, V., On the convergence of pattern search algorithms, SIAM J. Optim., 7, 1, 1-25 (1997) · Zbl 0884.65053
[67] Verdério, A.; Karas, EW; Pedroso, LG; Scheinberg, K., On the construction of quadratic models for derivative-free trust-region algorithms, EURO J. Comput Optim, 5, 501-527 (2017) · Zbl 1386.90181
[68] Wild, SM; Regis, RG; Shoemaker, CA, ORBIT: optimization by radial basis function interpolation in trust-regions, SIAM J. Sci. Comput., 30, 6, 3197-3219 (2008) · Zbl 1178.65065
[69] Wild, SM; Shoemaker, CA, Global convergence of radial basis function trust region derivative-free algorithms, SIAM J. Optim., 21, 3, 761-781 (2011) · Zbl 1397.65024
[70] Winfield, D.: Function and Functional Optimization by Interpolation in Data Tables. PhD thesis Harvard University USA (1969)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.