×

zbMATH — the first resource for mathematics

Filter-based stochastic algorithm for global optimization. (English) Zbl 1447.90042
Summary: We propose the general Filter-based Stochastic Algorithm (FbSA) for the global optimization of nonconvex and nonsmooth constrained problems. Under certain conditions on the probability distributions that generate the sample points, almost sure convergence is proved. In order to optimize problems with computationally expensive black-box objective functions, we develop the FbSA-RBF algorithm based on the general FbSA and assisted by Radial Basis Function (RBF) surrogate models to approximate the objective function. At each iteration, the resulting algorithm constructs/updates a surrogate model of the objective function and generates trial points using a dynamic coordinate search strategy similar to the one used in the Dynamically Dimensioned Search method. To identify a promising best trial point, a non-dominance concept based on the values of the surrogate model and the constraint violation at the trial points is used. Theoretical results concerning the sufficient conditions for the almost surely convergence of the algorithm are presented. Preliminary numerical experiments show that the FbSA-RBF is competitive when compared with other known methods in the literature.
MSC:
90C26 Nonconvex programming, global optimization
Software:
DIRECT; ipfilter; MLMSRBF
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Aguirre, AH; Rionda, SB; Coello Coello, CA; Lizrraga, GL; Montes, EM, Handling constraints using multiobjective optimization concepts, Int. J. Numer. Methods Eng., 59, 15, 1989-2017 (2004) · Zbl 1060.74581
[2] Ali, MM; Golalikhani, M., An electromagnetism-like method for nonlinearly constrained global optimization, Comput. Math. Appl., 60, 8, 2279-2285 (2010) · Zbl 1205.90270
[3] Ali, MM; Zhu, WX, A penalty function-based differential evolution algorithm for constrained global optimization, Comput. Optim. Appl., 54, 1, 707-739 (2013) · Zbl 1295.90050
[4] 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
[5] Barbosa, HJC; Lemonge, ACC; Iba, H., An adaptive penalty method for genetic algorithms in constrained optimization problems, Frontiers in Evolutionary Robotics, Chapter 2 (2008), Rijeka: IntechOpen, Rijeka
[6] Birgin, EG; Floudas, CA; Martínez, JM, Global minimization using an augmented Lagrangian method with variable lower-level constraints, Math. Program., 125, 139-162 (2010) · Zbl 1198.90322
[7] Booker, AJ; Dennis, JE; Frank, PD; Serafini, DB; Torczon, V.; Trosset, MW, A rigorous framework for optimization of expensive functions by surrogates, Struct. Multidisc. Optim., 17, 1-19 (1999)
[8] Chin, CM; Fletcher, R., On the global convergence of an SLP-filter algorithm that takes EQP steps, Math. Program., 96, 1, 161-177 (2003) · Zbl 1023.90060
[9] Coello, CAC, Theoretical and numerical constraint-handling techniques used with evolutionary algorithms: a survey of the state of the art, Comput. Method. Appl. Mech. Eng., 191, 11, 1245-1287 (2002) · Zbl 1026.74056
[10] Costa, MFP; Fernandes, FP; Rocha, AMAC, Multiple solutions of mixed variable optimization by multistart Hooke and Jeeves filter method, Appl. Math. Sci., 8, 2163-2179 (2014)
[11] Costa, MFP; Rocha, AMAC; Fernandes, EMGP, Filter-based direct method for constrained global optimization, J. Glob. Optim., 71, 3, 517-536 (2018) · Zbl 1402.90127
[12] Di Pillo, G.; Lucidi, S.; Rinaldi, F., An approach to constrained global optimization based on exact penalty functions, J. Glob. Optim., 54, 251-260 (2012) · Zbl 1259.90099
[13] Dolan, ED; Moré, J., Benchmarking optimization software with performance profiles, Math. Program., 91, 2, 201-213 (2002) · Zbl 1049.90004
[14] Echebest, N.; Shuverdt, ML; Vignau, RP, An inexact restoration derivative-free filter method for nonlinear programming, Comput. Appl. Math., 36, 1, 693-718 (2017) · Zbl 1359.65092
[15] Ferreira, PS; Karas, EW; Sachine, M.; Sobral, FN, Global convergence of a derivative-free inexact restoration filter algorithm for nonlinear programming, Optimization, 66, 271-292 (2017) · Zbl 1365.90237
[16] Fletcher, R.; Gould, NIM; Leyffer, S.; Toint, PL; Wachter, A., Global convergence of trust-region SQP-filter algorithm for general nonlinear programming, SIAM J. Optim., 13, 635-659 (2002) · Zbl 1038.90076
[17] Fletcher, R.; Leyffer, S., Nonlinear programming without a penalty function, Math. Program., 91, 239-269 (2002) · Zbl 1049.90088
[18] Gablonsky, J.: DIRECT Version 2.0 User Guide. Technical Report CRSC-TR01-08, Center for Research in Scientific Computation, North Carolina State University (2001)
[19] Gonçalves, MLN; Melo, JG; Prudente, LF, Augmented Lagrangian methods for nonlinear programming with possible infeasibility, J. Glob. Optim., 63, 297-318 (2015) · Zbl 1353.90117
[20] Gonzaga, CC; Karas, EW; Vanti, M., A globally convergent filter method for nonlinear programming, SIAM J. Optim., 14, 3, 646-669 (2003) · Zbl 1079.90129
[21] Gould, NIM; Leyffer, S.; Toint, PL, A multidimensional filter algorithm for nonlinear equations and nonlinear least-squares, SIAM J. Optim., 15, 1, 17-38 (2004) · Zbl 1075.65075
[22] Greenwood, GW; Shu, QJ, Convergence in evolutionary programs with self-adaptation, Evol. Comput., 9, 2, 147-157 (2001)
[23] He, Q.; Wang, L., A hybrid particle swarm optimization with a feasibility-based rule for constrained optimization, Appl. Math. Comput., 186, 2, 1407-1422 (2007) · Zbl 1117.65088
[24] Hedar, A-R; Fukushima, M., Derivative-free filter simulated annealing method for constrained continuous global optimization, J. Glob. Optim., 35, 4, 521-549 (2006) · Zbl 1133.90421
[25] Karas, EW; Oening, AP; Ribeiro, AA, Global convergence of slanting filter methods for nonlinear programming, Appl. Math. Comput., 200, 486-500 (2008) · Zbl 1149.65042
[26] Liang, J.J., Runarsson, T.P., Mezura-Montes, E., Clerc, M., Suganthan, P.N., Coello, C.A.C., Deb, K.: Problem Definitions and Evaluation Criteria for the CEC 2006 Special Session on Constrained Real-Parameter Optimization. Technical Report, Nanyang Technological University, Singapore (2006)
[27] Long, J.; Zeng, S., A new Filter-Levenberg-Marquart method with disturbance for solving nonlinear complementarity problems, Appl. Math. Comput., 216, 2, 677-688 (2010) · Zbl 1197.65065
[28] Macêdo, M.J.F.G., Costa, M.F.P., Rocha, A.M.A.C., Karas, E.W.: Combining filter method and dynamically dimensioned search for constrained global optimization. In: Gervasi, O., Murgante, B., Misra, S., Borruso, G., Torre, C., Rocha, A., Taniar, D., Apduhan, B., Stankova, E., Cuzzocrea, A. (eds.) Computational Science and Its Applications—ICCSA 2017: 17th International Conference, Trieste, Italy, July 3-6, 2017, Proceedings, Part III, pp. 119-134. Springer International Publishing (2017)
[29] Mallipeddi, R., Suganthan, P.N.: Problem Definitions and Evaluation Criteria for the CEC 2010 Competition on Constrained Real-Parameter Optimization. Technical Report, Nanyang Technological University, Singapore (2010)
[30] Nuñez, L.; Regis, RG; Varela, K., Accelerated random search for constrained global optimization assisted by radial basis function surrogates, J. Comput. Appl. Math., 340, 276-295 (2018) · Zbl 1433.90127
[31] Periçaro, GA; Ribeiro, AA; Karas, EW, Global convergence of a general filter algorithm based on an efficiency condition of the step, Appl. Math. Comput., 219, 9581-9597 (2013) · Zbl 1291.90246
[32] Petalas, YG; Parsopoulos, KE; Vrahatis, MN, Memetic particle swarm optimization, Ann. Oper. Res., 156, 1, 99-127 (2007) · Zbl 1145.90108
[33] Powell, MJD; Light, W., The theory of radial basis function approximation in 1990, Advances in Numerical Analysis. Vol. 2. Wavelets, Subdivision Algorithms and Radial Basis Functions, 105-210 (1992), Oxford: Oxford University Press, Oxford · Zbl 0787.65005
[34] Price, CJ; Reale, M.; Robertson, BL, Stochastic filter methods for generally constrained global optimization, J. Glob. Optim., 65, 3, 441-456 (2016) · Zbl 1342.90152
[35] Regis, RG, Convergence guarantees for generalized adaptive stochastic search methods for continuous global optimization, Eur. J. Oper. Res., 207, 1187-1202 (2010) · Zbl 1209.90295
[36] Regis, RG, Stochastic radial basis function algorithms for large-scale optimization involving expensive black-box objective and constraint functions, Comput. Oper. Res., 38, 837-853 (2011) · Zbl 1434.90109
[37] Regis, RG, Constrained optimization by radial basis function interpolation for high-dimensional expensive black-box problems with infeasible initial points, Eng. Optim., 46, 218-243 (2014)
[38] Regis, RG; Shoemaker, CA, A stochastic radial basis function method for the global optimization of expensive functions, INFORMS J. Comput., 19, 4, 497-509 (2007) · Zbl 1241.90192
[39] Regis, RG; Shoemaker, CA, Combining radial basis function surrogates and dynamic coordinate search in high-dimensional expensive black-box optimization, Eng. Optim., 45, 529-555 (2013)
[40] Resnick, SI, A Probablity Path (1999), Boston: Birkhauser, Boston
[41] Ribeiro, AA; Karas, EW; Gonzaga, CC, Global convergence of filter methods for nonlinear programming, SIAM J. Optim., 19, 3, 1231-1249 (2008) · Zbl 1169.49034
[42] Rocha, AMAC; Costa, MFP; Fernandes, EMGP, A filter-based artificial fish swarm algorithm for constrained global optimization: theoretical and practical issues, J. Glob. Optim., 60, 239-263 (2014) · Zbl 1312.90066
[43] Rocha, AMAC; Fernandes, EMGP, Hybridizing the electromagnetism-like algorithm with descent search for solving engineering design problems, Int. J. Comput. Math., 86, 1932-1946 (2009) · Zbl 1177.65089
[44] Tolson, BA; Asadzadeh, M.; Maier, HR; Zecchin, A., Hybrid discrete dynamically dimensioned search (HD-DDS)algorithm for water distribution system design optimization, Water Resour. Res., 45, W12416 (2009)
[45] Tolson, BA; Shoemaker, CA, Dynamically dimensioned search algorithm for computationally efficient watershed model calibration, Water Resour. Res., 43, W01413 (2007)
[46] Ulbrich, M.; Ulbrich, S.; Vicente, LN, A globally convergent primal-dual interior-point filter method for nonlinear programming, Math. Program., 100, 2, 379-410 (2004) · Zbl 1070.90110
[47] Wang, C-Y; Li, D., Unified theory of augmented lagrangian methods for constrained global optimization, J. Glob. Optim., 44, 3, 433-458 (2008) · Zbl 1192.90149
[48] Wang, X.; Zhu, Z.; Zuo, S.; Huang, Q., An SQP-filter method for inequality constrained optimization and its global convergence, Appl. Math. Comput., 217, 24, 10224-10230 (2011) · Zbl 1236.65071
[49] Ye, KQ; Li, W.; Sudjianto, A., Algorithmic construction of optimal symmetric latin hypercube designs, J. Stat. Plan. Infer., 90, 1, 145-159 (2000) · Zbl 1109.62329
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.