×

zbMATH — the first resource for mathematics

Efficient solution of quadratically constrained quadratic subproblems within the mesh adaptive direct search algorithm. (English) Zbl 1403.90618
Summary: The mesh adaptive direct search algorithm (MADS) is an iterative method for constrained blackbox optimization problems. One of the optional MADS features is a versatile search step in which quadratic models are built leading to a series of quadratically constrained quadratic subproblems. This work explores different algorithms that exploit the structure of the quadratic models: the first one applies an \(l_{1}\)-exact penalty function, the second uses an augmented Lagrangian and the third one combines the former two, resulting in a new algorithm. It is notable that this latter approach is uniquely suitable for quadratically constrained quadratic problems. These methods are implemented within the NOMAD software package and their impact are assessed through computational experiments on 65 analytical test problems and 4 simulation-based engineering applications.

MSC:
90C30 Nonlinear programming
90C56 Derivative-free methods and methods using generalized derivatives
65K05 Numerical mathematical programming methods
90C20 Quadratic programming
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Ablow, C.; Brigham, G., An analog solution of programming problems, Journal of the Operations Research Society of America, 3, 4, 388-394, (1955) · Zbl 1414.90026
[2] Agte, J.; Sobieszczanski-Sobieski, J.; Sandusky, R., Supersonic business jet design through bilevel integrated system synthesis, Proceedings of the world aviation conference, (1999), MCB University Press, Bradford, UK San Francisco, CA
[3] Arreckx, S.; Lambe, A.; Martins, J.; Orban, D., A matrix-free augmented Lagrangian algorithm with application to large-scale structural design optimization, Optimization and Engineering, 17, 2, 359-384, (2016) · Zbl 1364.90388
[4] Audet, C., A survey on direct search methods for blackbox optimization and their applications, (Pardalos, P.; Rassias, T., Mathematics without boundaries: Surveys in interdisciplinary research. chapter 2, (2014), Springer), 31-56 · Zbl 1321.90125
[5] Audet, C.; Béchard, V.; Le Digabel, S., Nonsmooth optimization through mesh adaptive direct search and variable neighborhood search, Journal of Global Optimization, 41, 2, 299-318, (2008) · Zbl 1157.90535
[6] Audet, C.; Dennis, J., Mesh adaptive direct search algorithms for constrained optimization, SIAM Journal on Optimization, 17, 1, 188-217, (2006) · Zbl 1112.90078
[7] Audet, C.; Dennis, J., A progressive barrier for derivative-free nonlinear programming, SIAM Journal on Optimization, 20, 1, 445-472, (2009) · Zbl 1187.90266
[8] Audet, C.; Hare, W., Derivative-free and blackbox optimization, Springer series in operations research and financial engineering, (2017), Springer International Publishing · Zbl 1391.90001
[9] Audet, C.; Kokkolaras, M.; Le Digabel, S.; Talgorn, B., Order-based error for managing ensembles of surrogates in derivative-free optimization, Technical Report G-2016-36, (2017), Les cahiers du GERAD., To appear in Journal of Global Optimization
[10] Audet, C.; Le Digabel, S.; Peyrega, M., A derivative-free trust-region augmented Lagrangian algorithm, Technical Report G-2016-53, (2016), Les cahiers du GERAD
[11] Audet, C.; Savard, G.; Zghal, W., A mesh adaptive direct search algorithm for multiobjective optimization, European Journal of Operational Research, 204, 3, 545-556, (2010) · Zbl 1181.90137
[12] Booker, A.; Dennis, J.; Frank, P.; Serafini, D.; Torczon, V.; Trosset, M., A rigorous framework for optimization of expensive functions by surrogates, Structural and Multidisciplinary Optimization, 17, 1, 1-13, (1999)
[13] Boukouvala, F.; Misener, R.; Floudas, C., Global optimization advances in mixed-integer nonlinear programming, MINLP, and constrained derivative-free optimization, CDFO, European Journal of Operational Research, 252, 3, 701-727, (2016) · Zbl 1346.90677
[14] Charalambous, C., A lower bound for the controlling parameters of the exact penalty functions, Mathematical programming, 15, 1, 278-290, (1978) · Zbl 0395.90071
[15] Coleman, T.; Conn, A., Second-order conditions for an exact penalty function, Mathematical Programming, 19, 1, 178-185, (1980) · Zbl 0441.65053
[16] Coleman, T.; Conn, A., Nonlinear programming via an exact penalty function: asymptotic analysis, Mathematical programming, 24, 1, 123-136, (1982) · Zbl 0501.90078
[17] Coleman, T.; Conn, A., Nonlinear programming via an exact penalty function: global analysis, Mathematical Programming, 24, 1, 137-161, (1982) · Zbl 0501.90077
[18] Conn, A., Constrained optimization using a nondifferentiable penalty function, SIAM Journal on Numerical Analysis, 10, 4, 760-784, (1973) · Zbl 0259.90039
[19] Conn, A.; Gould, N.; Toint, P., LANCELOT: A Fortran package for large-scale nonlinear optimization (release A), (1992), Springer New-York · Zbl 0761.90087
[20] Conn, A.; Gould, N.; Toint, P., A note on exploiting structure when using slack variables, Mathematical Programming, 67, 1, 89-97, (1994) · Zbl 0827.90126
[21] Conn, A.; Gould, N.; Toint, P., Numerical experiments with the LANCELOT package (release A) for large-scale nonlinear optimization, Mathematical Programming, 73, 1, 73-110, (1996) · Zbl 0848.90109
[22] Conn, A.; Gould, N.; Toint, P., Trust region methods, (2000), SIAM · Zbl 0958.65071
[23] Conn, A.; Le Digabel, S., Use of quadratic models with mesh-adaptive direct search for constrained black box optimization, Optimization Methods and Software, 28, 1, 139-158, (2013) · Zbl 1270.90073
[24] Conn, A.; Scheinberg, K.; Vicente, L., Introduction to derivative-free optimization, MOS-SIAM series on optimization, (2009), SIAM Philadelphia · Zbl 1163.49001
[25] Conn, A.; Vicente, L.; Visweswariah, C., Two-step algorithms for nonlinear optimization with structured applications, SIAM Journal on Optimization, 9, 4, 924-947, (1999) · Zbl 0997.90077
[26] Fortin, C.; Wolkowicz, H., The trust region subproblem and semidefinite programming, Optimization Methods and Software, 19, 1, 41-67, (2004) · Zbl 1070.65041
[27] Garg, H., Solving structural engineering design optimization problems using an artificial bee colony algorithm, Journal of Industrial and Management Optimization, 10, 3, 777-794, (2014) · Zbl 1292.90212
[28] Gould, N.; Lucidi, S.; Toint, P., Solving the trust-region subproblem using the Lanczos method, SIAM Journal on Optimization, 9, 2, 504-525, (1999) · Zbl 1047.90510
[29] Gould, N.; Orban, D.; Toint, P., Cuter (and sifdec): A constrained and unconstrained testing environment, revisited, ACM Transactions on Mathematical Software, 29, 4, 373-394, (2003) · Zbl 1068.90526
[30] Gould, N.; Orban, D.; Toint, P., Galahad, a library of thread-safe Fortran 90 packages for large-scale nonlinear optimization, ACM Transactions on Mathematical Software, 29, 4, 353-372, (2003) · Zbl 1068.90525
[31] Gould, N.; Robinson, D.; Thorne, H., On solving trust-region and other regularised subproblems in optimization, Mathematical Programming Computation, 2, 1, 21-57, (2010) · Zbl 1193.65098
[32] Gramacy, R.; Gray, G.; Le Digabel, S.; Lee, H.; Ranjan, P.; Wells, G.; Wild, S., Modeling an augmented Lagrangian for blackbox constrained optimization, Technometrics, 58, 1, 1-11, (2016)
[33] Griva, I.; Nash, S.; Sofer, A., Linear and nonlinear optimization, (2009), Society for Industrial and Applied Mathematics · Zbl 1159.90002
[34] Hager, W., Minimizing a quadratic over a sphere, SIAM Journal on Optimization, 12, 1, 188-208, (2001) · Zbl 1058.90045
[35] Hedar, A.-R. Global optimization test problems. http://www-optima.amp.i.kyoto-u.ac.jp/member/student/hedar/Hedar_files/TestGO.htm. [last accessed on 20 October 2017] http://goo.gl/0vxil.
[36] Hestenes, M., Multiplier and gradient methods, Journal of Optimization Theory and Applications, 4, 5, 303-320, (1969) · Zbl 0174.20705
[37] Hock, W.; Schittkowski, K., Test examples for nonlinear programming codes, Lecture notes in economics and mathematical systems, vol. 187, (1981), Springer Berlin, Germany · Zbl 0452.90038
[38] Jamil, M.; Yang, X.-S., A literature survey of benchmark functions for global optimisation problems, International Journal of Mathematical Modelling and Numerical Optimisation, 4, 2, 150-194, (2013) · Zbl 1280.65053
[39] Kannan, A.; Wild, S., Benefits of deeper analysis in simulation-based groundwater optimization problems, Proceedings of the XIX international conference on computational methods in water resources (CMWR 2012), (2012)
[40] Le Digabel, S., Algorithm 909: NOMAD: nonlinear optimization with the MADS algorithm, ACM Transactions on Mathematical Software, 37, 4, 44:1-44:15, (2011) · Zbl 1365.65172
[41] Luenberger, D., Control problems with kinks, IEEE Transactions on Automatic Control, 15, 5, 570-575, (1970)
[42] Lukšan, L.; Vlček, J., Test problems for nonsmooth unconstrained and linearly constrained optimization, Technical Report V-798, (2000), ICS AS CR
[43] Matott, L.; Rabideau, A.; Craig, J., Pump-and-treat optimization using analytic element method flow models, Advances in Water Resources, 29, 5, 760-775, (2006)
[44] Michalewicz, Z.; Schoenauer, M., Evolutionary algorithms for constrained parameter optimization problems, Evolutionary computation, 4, 1, 1-32, (1996)
[45] Mladenović, N.; Petrović, J.; Kovačević-Vujčić, V.; Čangalović, M., Solving spread spectrum radar polyphase code design problem by tabu search and variable neighbourhood search, European Journal of Operational Research, 151, 2, 389-399, (2003) · Zbl 1053.90055
[46] Moré, J.; Sorensen, D., Computing a trust region step, SIAM Journal on Scientific Computing, 4, 3, 553-572, (1983) · Zbl 0551.65042
[47] Moré, J.; Toraldo, G., On the solution of large quadratic programming problems with bound constraints, SIAM Journal on Optimization, 1, 1, 93-113, (1991) · Zbl 0752.90053
[48] Moré, J.; Wild, S., Benchmarking derivative-free optimization algorithms, SIAM Journal on Optimization, 20, 1, 172-191, (2009) · Zbl 1187.90319
[49] Nocedal, J.; Wright, S., Numerical optimization, Springer series in operations research, (1999), Springer New York · Zbl 0930.65067
[50] Pong, T.; Wolkowicz, H., The generalized trust region subproblem, Computational Optimization and Applications, 58, 2, 273-322, (2014) · Zbl 1329.90100
[51] Powell, M., A method for nonlinear constraints in minimization problems, (Fletcher, R., Optimization, (1969), Academic Press New York), 283-298
[52] Rendl, F.; Wolkowicz, H., A semidefinite framework for trust region subproblems with applications to large scale minimization, Mathematical Programming, 77, 1, 273-299, (1997) · Zbl 0888.90137
[53] Schwefel, H.-P., Numerical optimization of computer models, (1981), John Wiley & Sons, Inc New York, NY, USA
[54] Sobieszczanski-Sobieski, J.; Agte, J.; Sandusky, R., Bi-level integrated system synthesis (BLISS), Technical Report NASA/TM-1998-208715, (1998), NASA, Langley Research Center
[55] Pietrzykowski, T., An exact potential method for constrained maxima, SIAM Journal on numerical analysis, 6, 2, 299-304, (1969) · Zbl 0181.46501
[56] Tribes, C.; Dubé, J.-F.; Trépanier, J.-Y., Decomposition of multidisciplinary optimization problems: formulations and application to a simplified wing design, Engineering Optimization, 37, 8, 775-796, (2005)
[57] Wächter, A.; Biegler, L. T., On the implementation of a primal-dual interior point filter line search algorithm for large-scale nonlinear programming, Mathematical Programming, 106, 1, 25-57, (2006) · Zbl 1134.90542
[58] Zangwill, W., Nonlinear programming by sequential unconstrained maximization, Technical Report Working Paper 131, (1965), University of California, Berkeley
[59] Zangwill, W., Non-linear programming via penalty functions, Management science, 13, 5, 344-358, (1967) · Zbl 0171.18202
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.