×

zbMATH — the first resource for mathematics

A progressive barrier derivative-free trust-region algorithm for constrained optimization. (English) Zbl 1409.90180
Summary: We study derivative-free constrained optimization problems and propose a trust-region method that builds linear or quadratic models around the best feasible and around the best infeasible solutions found so far. These models are optimized within a trust region, and the progressive barrier methodology handles the constraints by progressively pushing the infeasible solutions toward the feasible domain. Computational experiments on 40 smooth constrained problems indicate that the proposed method is competitive with COBYLA, and experiments on two nonsmooth multidisciplinary optimization problems from mechanical engineering show that it can be competitive with the NOMAD software.

MSC:
90C30 Nonlinear programming
90C56 Derivative-free methods and methods using generalized derivatives
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Abramson, MA; Audet, C.; Dennis, JE, Filter pattern search algorithms for mixed variable constrained optimization problems, Pac. J. Optim., 3, 477-500, (2007) · Zbl 1138.65043
[2] Arouxét, MB; Echebest, NE; Pilotta, EA, Inexact restoration method for nonlinear optimization without derivatives, J. Comput. Appl. Math., 290, 26-43, (2015) · Zbl 1321.65093
[3] Audet, C.; Pardalos, PM (ed.); Rassias, TM (ed.), A survey on direct search methods for blackbox optimization and their applications, chapter 2, 31-56, (2014), Berlin
[4] Audet, C.; Béchard, V.; Digabel, S., Nonsmooth optimization through mesh adaptive direct search and variable neighborhood search, J. Glob. Optim., 41, 299-318, (2008) · Zbl 1157.90535
[5] Audet, C.; Dennis, JE, Analysis of generalized pattern searches, SIAM J. Optim., 13, 889-903, (2003) · Zbl 1053.90118
[6] Audet, C.; Dennis, JE, A pattern search filter method for nonlinear programming without derivatives, SIAM J. Optim., 14, 980-1010, (2004) · Zbl 1073.90066
[7] Audet, C.; Dennis, JE, Mesh adaptive direct search algorithms for constrained optimization, SIAM J. Optim., 17, 188-217, (2006) · Zbl 1112.90078
[8] Audet, C.; Dennis, JE, A progressive barrier for derivative-free nonlinear programming, SIAM J. Optim., 20, 445-472, (2009) · Zbl 1187.90266
[9] Audet, C.; Dennis, JE; Digabel, S., Globalization strategies for mesh adaptive direct search, Comput. Optim. Appl., 46, 193-215, (2010) · Zbl 1190.90204
[10] Audet, C., Hare, W.: Derivative-Free and Blackbox Optimization. Springer Series in Operations Research and Financial Engineering. Springer International Publishing, Berlin (2017) · Zbl 1391.90001
[11] Audet, C.; Ianni, A.; Digabel, S.; Tribes, C., Reducing the number of function evaluations in mesh adaptive direct search algorithms, SIAM J. Optim., 24, 621-642, (2014) · Zbl 1297.90149
[12] Audet, C.; Digabel, S.; Peyrega, M., Linear equalities in blackbox optimization, Comput. Optim. Appl., 61, 1-23, (2015) · Zbl 1311.90185
[13] Augustin, F., Marzouk, Y.M.: NOWPAC: a provably convergent derivative-free nonlinear optimizer with path-augmented constraints. Technical report, arXiv (2014)
[14] Bandeira, AS; Scheinberg, K.; Vicente, LN, Convergence of trust-region methods based on probabilistic models, SIAM J. Optim., 24, 1238-1264, (2014) · Zbl 1311.90186
[15] Bertsekas, D.P.: Constrained Optimization and Lagrangian Multiplier Methods. Academic, New York (1982) · Zbl 0572.90067
[16] Conejo, PD; Karas, EW; Pedroso, LG, A trust-region derivative-free algorithm for constrained optimization, Optim. Methods Softw., 30, 1126-1145, (2015) · Zbl 1328.90160
[17] Conn, AR; Gould, NIM; Toint, PhL, A globally convergent augmented Lagrangian algorithm for optimization with general constraints and simple bounds, SIAM J. Numer. Anal., 28, 545-572, (1991) · Zbl 0724.65067
[18] Conn, A.R., Gould, N.I.M., Toint, Ph.L.: Trust-Region Methods. SIAM, MPS-SIAM Series on Optimization (2000)
[19] Conn, AR; Digabel, S., Use of quadratic models with mesh-adaptive direct search for constrained black box optimization, Optim. Methods Softw., 28, 139-158, (2013) · Zbl 1270.90073
[20] Conn, AR; Scheinberg, K.; Vicente, LN, Global convergence of general derivative-free trust-region algorithms to first and second order critical points, SIAM J. Optim., 20, 387-415, (2009) · Zbl 1187.65062
[21] Conn, A.R., Scheinberg, K., Vicente, L.N.: Introduction to Derivative-Free Optimization. MOS-SIAM Series on Optimization. SIAM, Philadelphia (2009) · Zbl 1163.49001
[22] Custódio, AL; Scheinberg, K.; Vicente, LN; Terlaky, T. (ed.); Anjos, MF (ed.); Ahmed, S. (ed.), Methodologies and software for derivative-free optimization, chapter 37, (2017), Philadelphia
[23] Dennis, JE; Price, CJ; Coope, ID, Direct search methods for nonlinearly constrained optimization using filters and frames, Optim. Eng., 5, 123-144, (2004) · Zbl 1085.90054
[24] Echebest, N.; Schuverdt, ML; Vignau, RP, An inexact restoration derivative-free filter method for nonlinear programming, Comput. Appl. Math., 36, 693-718, (2017) · Zbl 1359.65092
[25] Fletcher, R.; Leyffer, S., Nonlinear programming without a penalty function, Math. Program. Ser. A, 91, 239-269, (2002) · Zbl 1049.90088
[26] Gould, Nicholas I. M.; Orban, Dominique; Toint, Philippe L., CUTEst: a Constrained and Unconstrained Testing Environment with safe threads for mathematical optimization, Computational Optimization and Applications, 60, 545-557, (2014) · Zbl 1325.90004
[27] Gould, NIM; Toint, PhL, Nonlinear programming without a penalty function or a filter, Math. Program., 122, 155-196, (2010) · Zbl 1216.90069
[28] Gumma, EAE; Hashim, MHA; Ali, MM, A derivative-free algorithm for linearly constrained optimization problems, Comput. Optim. Appl., 57, 599-621, (2014) · Zbl 1304.90193
[29] Kolda, T.G., Lewis, R.M., Torczon, V.: A generating set direct search augmented Lagrangian algorithm for optimization with a combination of general and linear constraints. Technical Report SAND2006-5315, Sandia National Laboratories, USA (2006)
[30] Kolda, TG; Lewis, RM; Torczon, V., Stationarity results for generating set search for linearly constrained optimization, SIAM J. Optim., 17, 943-968, (2006) · Zbl 1126.90076
[31] Digabel, S., Algorithm 909: NOMAD: nonlinear optimization with the MADS algorithm, ACM Trans. Math. Softw., 37, 44:1-44:15, (2011) · Zbl 1365.65172
[32] Le Digabel, S., Wild, S.M.: A Taxonomy of Constraints in Simulation-Based Optimization. Technical Report G-2015-57, Les cahiers du GERAD (2015)
[33] Lewis, RM; Shepherd, A.; Torczon, V., Implementing generating set search methods for linearly constrained minimization, SIAM J. Sci. Comput., 29, 2507-2530, (2007) · Zbl 1166.90368
[34] Lewis, RM; Torczon, V., Active set identification for linearly constrained minimization without explicit derivatives, SIAM J. Optim., 20, 1378-1405, (2009) · Zbl 1198.90398
[35] Liuzzi, G.; Lucidi, S., A derivative-free algorithm for inequality constrained nonlinear programming via smoothing of an \(\ell_\infty \) penalty function, SIAM J. Optim., 20, 1-29, (2009) · Zbl 1187.65065
[36] Liuzzi, G.; Lucidi, S.; Sciandrone, M., Sequential penalty derivative-free methods for nonlinear constrained optimization, SIAM J. Optim., 20, 2614-2635, (2010) · Zbl 1223.65045
[37] Moré, JJ; Wild, SM, Benchmarking derivative-free optimization algorithms, SIAM J. Optim., 20, 172-191, (2009) · Zbl 1187.90319
[38] Perez, R., Liu, H.H.T., Behdinan, K.: Evaluation of multidisciplinary optimization approaches for aircraft conceptual design. In: AIAA/ISSMO Multidisciplinary Analysis and Optimization Conference, Albany, NY, September (2004)
[39] Powell, MJD; Gomez, S. (ed.); Hennart, J-P (ed.), A direct search optimization method that models the objective and constraint functions by linear interpolation, No. 275, 51-67, (1994), Dordrecht · Zbl 0826.90108
[40] Powell, MJD, On fast trust region methods for quadratic models with linear constraints, Math. Program. Comput., 7, 237-267, (2015) · Zbl 1325.65084
[41] Sampaio, PhR; Toint, PhL, A derivative-free trust-funnel method for equality-constrained nonlinear optimization, Comput. Optim. Appl., 61, 25-49, (2015) · Zbl 1311.90187
[42] Sampaio, PhR; Toint, PhL, Numerical experience with a derivative-free trust-funnel method for nonlinear optimization problems with general nonlinear constraints, Optim. Methods Softw., 31, 511-534, (2016) · Zbl 1369.90138
[43] Sobieszczanski-Sobieski, J.; Agte, JS; Sandusky, RR, Bilevel integrated system synthesis, AIAA J., 38, 164-172, (2000)
[44] Tribes, C.; Dubé, J-F; Trépanier, J-Y, Decomposition of multidisciplinary optimization problems: formulations and application to a simplified wing design, Eng. Optim., 37, 775-796, (2005)
[45] Tröltzsch, A., A sequential quadratic programming algorithm for equality-constrained optimization without derivatives, Optim. Lett., 10, 383-399, (2016) · Zbl 1343.90093
[46] Xue, D.; Sun, W., On convergence analysis of a derivative-free trust region algorithm for constrained optimization with separable structure, Sci. China Math., 57, 1287-1302, (2014) · Zbl 1306.65217
[47] Yuan, Y., Recent advances in trust region algorithms, Math. Program., 151, 249-281, (2015) · Zbl 1317.65141
[48] Yuan, Y-X; Yuan, Y-X (ed.), An example of non-convergence of trust region algorithms, 205-215, (1998), Dordercht · Zbl 0909.90249
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.