×

Filter-based DIRECT method for constrained global optimization. (English) Zbl 1402.90127

Summary: This paper presents a DIRECT-type method that uses a filter methodology to assure convergence to a feasible and optimal solution of nonsmooth and nonconvex constrained global optimization problems. The filter methodology aims to give priority to the selection of hyperrectangles with feasible center points, followed by those with infeasible and non-dominated center points and finally by those that have infeasible and dominated center points. The convergence properties of the algorithm are analyzed. Preliminary numerical experiments show that the proposed filter-based DIRECT algorithm gives competitive results when compared with other DIRECT-type methods.

MSC:

90C26 Nonconvex programming, global optimization
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Audet, C; Dennis, JE, A pattern search filter method for nonlinear programming without derivatives, SIAM J. Optim., 14, 980-1010, (2004) · Zbl 1073.90066 · doi:10.1137/S105262340138983X
[2] Bertsekas, D.P.: Nonlinear Programming, 2nd edn. Athena Scientific, Belmont (1999) · Zbl 1015.90077
[3] Birgin, E.G., Floudas, C.A., Martínez, J.M.: Global minimization using an Augmented Lagrangian method with variable lower-level constraints. Technical Report MCDO121206, January 22, 2007, http://www.ime.usp.br/ egbirgin/ · Zbl 1180.65081
[4] Birgin, EG; Floudas, CA; Martínez, JM, Global minimization using an augmented Lagrangian method with variable lower-level constraints, Math. Program. Ser. A, 125, 139-162, (2010) · Zbl 1198.90322 · doi:10.1007/s10107-009-0264-y
[5] Birgin, EG; Martínez, JM, Augmented Lagrangian method with nonmonotone penalty parameters for constrained optimization, Comput. Optim. Appl., 51, 941-965, (2012) · Zbl 1244.90216 · doi:10.1007/s10589-011-9396-0
[6] Chin, CM; Fletcher, R, On the global convergence of an SLP-filter algorithm that takes EQP steps, Math. Program., 96, 161-177, (2003) · Zbl 1023.90060 · doi:10.1007/s10107-003-0378-6
[7] Costa, MFP; Fernandes, FP; Fernandes, EMGP; Rocha, AMAC, Multiple solutions of mixed variable optimization by multistart Hooke and jeeves filter method, Appl. Math. Sci., 8, 2163-2179, (2014)
[8] Dennis, JE; Price, CJ; Coope, ID, Direct search methods for nonlinear constrained optimization using filters and frames, Optim. Eng., 5, 123-144, (2004) · Zbl 1085.90054 · doi:10.1023/B:OPTE.0000033371.04406.e0
[9] Di Pillo, G., Liuzzi, G., Lucidi, S., Piccialli, V., Rinaldi, F.: A DIRECT-type approach for derivative-free constrained global optimization. Technical Report, July 4, 2014, http://www.math.unipd.it/ rinaldi/papers/glob_con.pdf · Zbl 1370.90189
[10] Pillo, G; Liuzzi, G; Lucidi, S; Piccialli, V; Rinaldi, F, A DIRECT-type approach for derivative-free constrained global optimization, Comput. Optim. Appl., 65, 361-397, (2016) · Zbl 1370.90189 · doi:10.1007/s10589-016-9876-3
[11] 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 · doi:10.1007/s10898-010-9582-0
[12] Pillo, G; Lucidi, S; Rinaldi, F, A derivative-free algorithm for constrained global optimization based on exact penalty functions, J. Optim. Theory Appl., 164, 862-882, (2015) · Zbl 1330.90085 · doi:10.1007/s10957-013-0487-1
[13] Dolan, ED; Moré, JJ, Benchmarking optimization software with performance profiles, Math. Program. Ser. A, 91, 201-213, (2002) · Zbl 1049.90004 · doi:10.1007/s101070100263
[14] Fasano, G; Liuzzi, G; Lucidi, S; Rinaldi, F, A linesearch-based derivative-free approach for nonsmooth constrained optimization, SIAM J. Optim., 24, 959-992, (2014) · Zbl 1302.90207 · doi:10.1137/130940037
[15] Ferreira, PS; Karas, EW; Sachine, M; Sobral, FNC, Global convergence of a derivative-free inexact restoration filter algorithm for nonlinear programming, Optimization, 66, 271-292, (2017) · Zbl 1365.90237 · doi:10.1080/02331934.2016.1263629
[16] Finkel, D.E.: DIRECT Optimization Algorithm User Guide. Center for Research in Scientific Computation. North Carolina State University, Raleigh (2003)
[17] Finkel D.E., Kelley C.T.: Convergence Analysis of the DIRECT Algorithm. Technical Report CRSC-TR04-28, Center for Research in Scientific Computation, North Carolina State University (2004)
[18] Finkel, DE; Kelley, CT, Additive scaling and the DIRECT algorithm, J. Glob. Optim., 36, 597-608, (2006) · Zbl 1142.90488 · doi:10.1007/s10898-006-9029-9
[19] Fletcher, R; Leyffer, S, Nonlinear programming without a penalty function, Math. Program. Ser. A, 91, 239-269, (2002) · Zbl 1049.90088 · doi:10.1007/s101070100244
[20] Gablonsky J.M.: DIRECT version 2.0 user guide. Technical Report CRSC-TR-01-08, Center for Research in Scientific Computation, North Carolina State University (2001)
[21] Gablonsky, JM; Kelley, CT, A locally-biased form of the DIRECT algorithm, J. Glob. Optim., 21, 27-37, (2001) · Zbl 1039.90049 · doi:10.1023/A:1017930332101
[22] Gould, NIM; Leyffer, S; Toint, PhL, A multidimensional filter algorithm for nonlinear equations and nonlinear least squares, SIAM J. Optim., 15, 17-38, (2004) · Zbl 1075.65075 · doi:10.1137/S1052623403422637
[23] He, J., Watson, L.T., Sosonkina M.: Algorithm 897: VTDIRECT95: serial and parallel Codes for the global optimization algorithm DIRECT. ACM Trans. Math. Softw., 36(3), Article no. 17 (2009) · Zbl 1364.65127
[24] Hedar, A-R; Fahim, A, Filter-based genetic algorithm for mixed variable programming, Numer. Algebra Control Optim., 1, 99-116, (2011) · Zbl 1219.90107 · doi:10.3934/naco.2011.1.99
[25] Horst, R., Pardalos, P.M., Thoai, N.V.: Introduction to Global Optimization. Kluwer, Dordrecht (2000) · Zbl 0966.90073 · doi:10.1007/978-1-4615-0015-5
[26] Jones, DR; Floudas, C (ed.); Pardalos, P (ed.), The DIRECT global optimization algorithm, 431-440, (2001), Boston · doi:10.1007/0-306-48332-7_93
[27] Jones, DR; Perttunen, CD; Stuckman, BE, Lipschitzian optimization without the Lipschitz constant, J. Optim. Theory Appl., 79, 157-181, (1993) · Zbl 0796.49032 · doi:10.1007/BF00941892
[28] Karas, E; Ribeiro, A; Sagastizábal, C; Solodov, M, A bundle-filter method for nonsmooth convex constrained optimization, Math. Program. Ser. B, 116, 297-320, (2009) · Zbl 1165.90024 · doi:10.1007/s10107-007-0123-7
[29] Liu, M., Li, X., Wu, Q.: A filter algorithm with inexact line search. Math. Probl. Eng., Article ID 349178 20 pages (2012) · Zbl 1264.90161
[30] Liu, Q, Linear scaling and the DIRECT algorithm, J. Glob. Optim., 56, 1233-1245, (2013) · Zbl 1272.90060 · doi:10.1007/s10898-012-9952-x
[31] Liu, Q; Cheng, W, A modified DIRECT algorithm with bilevel partition, J. Glob. Optim., 60, 483-499, (2014) · Zbl 1303.90083 · doi:10.1007/s10898-013-0119-1
[32] Liu, Q; Zeng, J, Global optimization by multilevel partition, J. Glob. Optim., 61, 47-69, (2015) · Zbl 1312.90062 · doi:10.1007/s10898-014-0152-8
[33] Liu, Q; Zeng, J; Yang, G, Mrdirect: a multilevel robust DIRECT algorithm for global optimization problems, J. Glob. Optim., 62, 205-227, (2015) · Zbl 1326.90065
[34] Liuzzi, G; Lucidi, S; Piccialli, V, A partition-based global optimization algorithm, J. Glob. Optim., 48, 113-128, (2010) · Zbl 1230.90153 · doi:10.1007/s10898-009-9515-y
[35] Liuzzi, G; Lucidi, S; Piccialli, V, Exploiting derivative-free local searches in DIRECT-type algorithms for global optimization, Comput. Optim. Appl., 65, 449-475, (2016) · Zbl 1370.90194 · doi:10.1007/s10589-015-9741-9
[36] Peng, Y; Liu, Z, A derivative-free filter algorithm for nonlineat complementarity problem, Appl. Math. Comput., 182, 846-853, (2006) · Zbl 1111.65054
[37] Price, CJ; Reale, M; Robertson, BL, Stochastic filter methods for generally constrained global optimization, J. Glob. Optim., 65, 441-456, (2016) · Zbl 1342.90152 · doi:10.1007/s10898-015-0388-y
[38] Ribeiro, AA; Karas, EW; Gonzaga, CC, Global convergence of filter methods for nonlinear programming, SIAM J. Optim., 19, 1231-1249, (2008) · Zbl 1169.49034 · doi:10.1137/060672285
[39] 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 · doi:10.1007/s10898-014-0157-3
[40] Sergeyev, YD; Kvasov, DE, Global search based on efficient diagonal partitions and a set of Lipschitz constants, SIAM J. Optim., 16, 910-937, (2006) · Zbl 1097.65068 · doi:10.1137/040621132
[41] Shcherbina, O; Neumaier, A; Sam-Haroud, D; Vu, X-H; Nguyen, T-V; Bliek, C (ed.); Jermann, C (ed.); Neumaier, A (ed.), Benchmarking global optimization and constraint satisfaction codes, 211-222, (2003), Berlin · Zbl 1296.90004 · doi:10.1007/978-3-540-39901-8_16
[42] Shen, C; Leyffer, S; Fletcher, R, A nonmonotone filter method for nonlinear optimization, Comput. Optim. Appl., 52, 583-607, (2012) · Zbl 1259.90140 · doi:10.1007/s10589-011-9430-2
[43] Su, K; Pu, D, A nonmonotone filter trust region method for nonlinear constrained optimization, J. Comput. Appl. Math., 223, 230-239, (2009) · Zbl 1180.65081 · doi:10.1016/j.cam.2008.01.013
[44] Su, K., Lu, X., Liu, W.: An improved filter method for nonlinear complementarity problem. Math. Probl. Eng., 2013, Article ID 450829 7 pages (2013) · Zbl 1299.90350
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.