×

Constrained stochastic blackbox optimization using a progressive barrier and probabilistic estimates. (English) Zbl 1512.90148

Summary: This work introduces the StoMADS-PB algorithm for constrained stochastic blackbox optimization, which is an extension of the mesh adaptive direct-search (MADS) method originally developed for deterministic blackbox optimization under general constraints. The values of the objective and constraint functions are provided by a noisy blackbox, i.e., they can only be computed with random noise whose distribution is unknown. As in MADS, constraint violations are aggregated into a single constraint violation function. Since all function values are numerically unavailable, StoMADS-PB uses estimates and introduces probabilistic bounds for the violation. Such estimates and bounds obtained from stochastic observations are required to be accurate and reliable with high, but fixed, probabilities. The proposed method, which allows intermediate infeasible solutions, accepts new points using sufficient decrease conditions and imposing a threshold on the probabilistic bounds. Using Clarke nonsmooth calculus and martingale theory, Clarke stationarity convergence results for the objective and the violation function are derived with probability one.

MSC:

90C15 Stochastic programming
90C30 Nonlinear programming
90C56 Derivative-free methods and methods using generalized derivatives

Software:

ASTRO-DF; OrthoMADS
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Abramson, MA; Audet, C.; Dennis, JE Jr; Le Digabel, S., OrthoMADS: a deterministic MADS instance with orthogonal directions, SIAM J. Optim., 20, 2, 948-966 (2009) · Zbl 1189.90202
[2] Alarie, S.; Audet, C.; Bouchet, P-Y; Le Digabel, S., Optimization of noisy blackboxes with adaptive precision, SIAM J. Optim., 31, 4, 3127-3156 (2021) · Zbl 1483.90089
[3] Anderson, EJ; Ferris, MC, A direct search algorithm for optimization with noisy function evaluations, SIAM J. Optim., 11, 3, 837-857 (2001) · Zbl 1035.90106
[4] Angün, E.; Kleijnen, J.; den Hertog, D.; Gürkan, G., Response surface methodology with stochastic constraints for expensive simulation, J. Oper. Res. Soc., 60, 6, 735-746 (2009) · Zbl 1171.90554
[5] Armijo, L., Minimization of functions having Lipschitz continuous first partial derivatives, Pac. J. Math., 16, 1, 1-3 (1966) · Zbl 0202.46105
[6] Audet, C.: A survey on direct search methods for blackbox optimization and their applications. In: Pardalos, P.M., Rassias, T.M. (eds.) chapter 2 Mathematics Without Boundaries: Surveys in Interdisciplinary Research, pp. 31-56. Springer (2014) · Zbl 1321.90125
[7] Audet, C.; Dennis, JE Jr, A pattern search filter method for nonlinear programming without derivatives, SIAM J. Optim., 14, 4, 980-1010 (2004) · Zbl 1073.90066
[8] Audet, C.; Dennis, JE Jr, Mesh adaptive direct search algorithms for constrained optimization, SIAM J. Optim., 17, 1, 188-217 (2006) · Zbl 1112.90078
[9] Audet, C.; Dennis, JE Jr, A progressive barrier for derivative-free nonlinear programming, SIAM J. Optim., 20, 1, 445-472 (2009) · Zbl 1187.90266
[10] Audet, C.; Dennis, JE Jr; Le Digabel, S., Parallel space decomposition of the mesh adaptive direct search algorithm, SIAM J. Optim., 19, 3, 1150-1170 (2008) · Zbl 1180.90363
[11] Audet, C.; Dzahini, KJ; Kokkolaras, M.; Le Digabel, S., Stochastic mesh adaptive direct search for blackbox optimization using probabilistic estimates, Comput. Optim. Appl., 79, 1, 1-34 (2021) · Zbl 1469.90095
[12] Audet, C., Hare, W.: Derivative-Free and Blackbox Optimization. Springer Series in Operations Research and Financial Engineering. Springer (2017) · Zbl 1391.90001
[13] 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
[14] 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
[15] Augustin, F., Marzouk, Y.M.: NOWPAC: A provably convergent derivative-free nonlinear optimizer with path-augmented constraints. Technical report, arXiv (2014)
[16] Augustin, F., Marzouk, Y.M.: A trust-region method for derivative-free nonlinear constrained stochastic optimization. Technical Report 1703.04156, arXiv (2017)
[17] Bandeira, AS; Scheinberg, K.; Vicente, LN, Convergence of trust-region methods based on probabilistic models, SIAM J. Optim., 24, 3, 1238-1264 (2014) · Zbl 1311.90186
[18] Barton, RR; Ivey, JS Jr, Nelder-Mead simplex modifications for simulation optimization, Manag. Sci., 42, 7, 954-973 (1996) · Zbl 0884.90118
[19] Bertsimas, D.; Nohadani, O.; Teo, KM, Nonconvex robust optimization for problems with constraints, Informs J. Comput., 22, 1, 44-58 (2010) · Zbl 1243.90176
[20] Bhattacharya, R.N., Waymire, E.C.: A basic course in probability theory, vol. 69. Springer (2007) · Zbl 1138.60001
[21] Blanchet, J.; Cartis, C.; Menickelly, M.; Scheinberg, K., Convergence Rate Analysis of a Stochastic Trust Region Method via Submartingales, Informs J. Optim., 1, 2, 92-119 (2019)
[22] Chang, KH, Stochastic nelder-mead simplex method—a new globally convergent direct search method for simulation optimization, Eur. J. Oper. Res., 220, 3, 684-694 (2012) · Zbl 1253.90178
[23] Chen, R.; Menickelly, M.; Scheinberg, K., Stochastic optimization using a trust-region method and random models, Math. Program., 169, 2, 447-487 (2018) · Zbl 1401.90136
[24] Chen, X.; Wang, N., Optimization of short-time gasoline blending scheduling problem with a DNA based hybrid genetic algorithm, Chem. Eng. Process., 49, 10, 1076-1083 (2010)
[25] Clarke, F.H.: Optimization and Nonsmooth Analysis. John Wiley and Sons, New York (1983). Reissued in 1990 by SIAM Publications, Philadelphia, as Vol. 5 in the series Classics in Applied Mathematics
[26] Conn, A.R., Scheinberg, K., Vicente, L.N.: Introduction to Derivative-Free Optimization. MOS-SIAM Series on Optimization. SIAM, Philadelphia (2009) · Zbl 1163.49001
[27] Curtis, FE; Scheinberg, K., Adaptive stochastic optimization: A framework for analyzing stochastic optimization algorithms, IEEE Signal Process. Mag., 37, 5, 32-42 (2020)
[28] Curtis, FE; Scheinberg, K.; Shi, R., A stochastic trust region algorithm based on careful step normalization, Informs J. Optim., 1, 3, 200-220 (2019)
[29] Diniz-Ehrhardt, MA; Ferreira, DG; Santos, SA, A pattern search and implicit filtering algorithm for solving linearly constrained minimization problems with noisy objective functions, Optim. Methods Softw., 34, 4, 827-852 (2019) · Zbl 1415.90148
[30] Diniz-Ehrhardt, M.A., Ferreira, D.G., Santos, S.A.: Applying the pattern search implicit filtering algorithm for solving a noisy problem of parameter identification. Comput. Optim. Appl. 1-32 (2020)
[31] Dolan, ED; Moré, JJ, Benchmarking optimization software with performance profiles, Math. Program., 91, 2, 201-213 (2002) · Zbl 1049.90004
[32] Durrett, R.: Probability: Theory and Examples. Cambridge University Press (2010) · Zbl 1202.60001
[33] Dzahini, K.J.: Expected complexity analysis of stochastic direct-search. Comput. Optim. Appl. 81(1), 179-200 (2022) · Zbl 1484.90054
[34] Gratton, S.; Royer, CW; Vicente, LN; Zhang, Z., Direct search based on probabilistic feasible descent for bound and linearly constrained problems, Comput. Optim. Appl., 72, 3, 525-559 (2019) · Zbl 1420.90083
[35] Hock, W., Schittkowski, K.: Test Examples for Nonlinear Programming Codes. Lecture Notes in Economics and Mathematical Systems, vol. 187. Springer (1981) · Zbl 0452.90038
[36] Jahn, J.: Introduction to the Theory of Nonlinear Optimization. Springer (1994) · Zbl 0814.49001
[37] Kitayama, S.; Arakawa, M.; Yamazaki, K., Sequential approximate optimization using radial basis function network for engineering optimization, Optim. Eng., 12, 4, 535-557 (2011) · Zbl 1284.65077
[38] Klassen, KJ; Yoogalingam, R., Improving performance in outpatient appointment services with a simulation optimization approach, Prod. Oper. Manag., 18, 4, 447-458 (2009)
[39] Lacksonen, T., Empirical comparison of search algorithms for discrete event simulation, Comput. Ind. Eng., 40, 1-2, 133-148 (2001)
[40] Larson, J.; Billups, SC, Stochastic derivative-free optimization using a trust region framework, Comput. Optim. Appl., 64, 3, 619-645 (2016) · Zbl 1381.90098
[41] Le Digabel, S., Wild, S.M.: A Taxonomy of Constraints in Simulation-Based Optimization. Technical Report G-2015-57, Les cahiers du GERAD (2015)
[42] Letham, B.; Karrer, B.; Ottoni, G.; Bakshy, E., Constrained Bayesian optimization with noisy experiments, Bayesian Anal., 14, 2, 495-519 (2019) · Zbl 1416.62156
[43] Lukšan, L., Vlček, J.: Test problems for nonsmooth unconstrained and linearly constrained optimization. Technical Report V-798, ICS AS CR (2000)
[44] Mezura-Montes, E., Coello, C.A.: Useful Infeasible Solutions in Engineering Optimization with Evolutionary Algorithms. In: Proceedings of the 4th Mexican International Conference on Advances in Artificial Intelligence, MICAI’05, pp. 652-662, Springer (2005)
[45] Mockus, J.: Bayesian approach to global optimization: theory and applications, volume 37 of Mathematics and Its Applications. Springer (2012)
[46] Moré, JJ; Wild, SM, Benchmarking derivative-free optimization algorithms, SIAM J. Optim., 20, 1, 172-191 (2009) · Zbl 1187.90319
[47] Nelder, JA; Mead, R., A simplex method for function minimization, Comput. J., 7, 4, 308-313 (1965) · Zbl 0229.65053
[48] Paquette, C.; Scheinberg, K., A stochastic line search method with expected complexity analysis, SIAM J. Optim., 30, 1, 349-376 (2020) · Zbl 1431.90153
[49] Robbins, H.; Monro, S., A stochastic approximation method, Ann. Math. Stat., 22, 3, 400-407 (1951) · Zbl 0054.05901
[50] Rockafellar, RT, Generalized directional derivatives and subgradients of nonconvex functions, Canad. J. Math., 32, 2, 257-280 (1980) · Zbl 0447.49009
[51] Rodríguez, JF; Renaud, JE; Watson, LT, Trust region augmented lagrangian methods for sequential response surface approximation and optimization, J. Mech. Des., 120, 1, 58-66 (1998)
[52] 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
[53] Tao, J.; Wang, N., DNA double helix based hybrid GA for the gasoline blending recipe optimization problem, Chem. Eng. Technol., 31, 3, 440-451 (2008)
[54] Wang, Z.; Ierapetritou, M., Constrained optimization of black-box stochastic systems using a novel feasibility enhanced Kriging-based method, Comput. Chem. Eng., 118, 210-223 (2018)
[55] Zhao, J.; Wang, N., A bio-inspired algorithm based on membrane computing and its application to gasoline blending scheduling, Comput. Chem. Eng., 35, 2, 272-283 (2011)
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.