On the extension of the direct algorithm to multiple objectives. (English) Zbl 1465.90094

Lovison, Alberto; Miettinen, Kaisa

J. Glob. Optim. 79, No. 2, 387-412 (2021).

Summary: Deterministic global optimization algorithms like Piyavskii-Shubert, direct, ego and many more, have a recognized standing, for problems with many local optima. Although many single objective optimization algorithms have been extended to multiple objectives, completely deterministic algorithms for nonlinear problems with guarantees of convergence to global Pareto optimality are still missing. For instance, deterministic algorithms usually make use of some form of scalarization, which may lead to incomplete representations of the Pareto optimal set. Thus, all global Pareto optima may not be obtained, especially in nonconvex cases. On the other hand, algorithms attempting to produce representations of the globally Pareto optimal set are usually based on heuristics. We analyze the concept of global convergence for multiobjective optimization algorithms and propose a convergence criterion based on the Hausdorff distance in the decision space. Under this light, we consider the well-known global optimization algorithm direct, analyze the available algorithms in the literature that extend direct to multiple objectives and discuss possible alternatives. In particular, we propose a novel definition for the notion of potential Pareto optimality extending the notion of potential optimality defined in direct. We also discuss its advantages and disadvantages when compared with algorithms existing in the literature.

MSC:

90C29	Multi-objective and goal programming
90C26	Nonconvex programming, global optimization
90C30	Nonlinear programming

Keywords:

global convergence; multiobjective optimization; multiple criteria optimization; direct algorithm; deterministic optimization algorithms

Software:

ParEGO; MultiGLODS; MODIR; PAINT; NBI

References:

[1]	Al-Dujaili, A., Suresh, S.: Dividing rectangles attack multi-objective optimization. In: 2016 IEEE Congress on Evolutionary Computation (CEC), pp. 3606-3613 (2016)
[2]	Allgower, EL; Schmidt, PH, An algorithm for piecewise-linear approximation of an implicitly defined manifold, SIAM J. Numer. Anal., 22, 322-346 (1985) · Zbl 0567.65029
[3]	Audet, C.; Savard, G.; Zghal, W., A mesh adaptive direct search algorithm for multiobjective optimization, Eur. J. Oper. Res., 204, 3, 545-556 (2010) · Zbl 1181.90137
[4]	Campana, EF; Diez, M.; Liuzzi, G.; Lucidi, S.; Pellegrini, R.; Piccialli, V.; Rinaldi, F.; Serani, A., A multi-objective direct algorithm for ship hull optimization, Comput. Optim. Appl., 71, 1, 53-72 (2018) · Zbl 1405.90114
[5]	Cao, P.; Qi, S.; Tang, J., Structural damage identification using piezoelectric impedance measurement with sparse inverse analysis, Smart Mater. Struct., 27, 3, 035020 (2018)
[6]	Cao, P.; Shuai, Q.; Tang, J., A multi-objective DIRECT algorithm toward structural damage identification with limited dynamic response information, J. Nondestruct. Eval. Diagn. Prognos. Eng. Syst., 1, 2, 021004-021004-12 (2017)
[7]	Custódio, AL; Madeira, JFA; Vaz, A.; Vicente, L., Direct multisearch for multiobjective optimization, SIAM J. Optim., 21, 1109-1140 (2011) · Zbl 1230.90167
[8]	Custódio, AL; Madeira, JFA, GLODS: global and local optimization using direct search, J. Global Optim., 62, 1-28 (2015) · Zbl 1328.90161
[9]	Custódio, AL; Madeira, JFA, MultiGLODS: global and local multiobjective optimization using direct search, J. Global Optim., 72, 2, 323-345 (2018) · Zbl 1404.90122
[10]	Das, I.; Dennis, JE, Normal-Boundary Intersection: a new method for generating the Pareto surface in nonlinear multicriteria optimization problems, SIAM J. Optim., 8, 631-657 (1998) · Zbl 0911.90287
[11]	Deb, K., Multi-Objective Optimization Using Evolutionary Algorithms (2001), Chichester: Wiley, Chichester · Zbl 0970.90091
[12]	Dellnitz, M.; Schütze, O.; Hestermeyer, T., Covering Pareto sets by multilevel subdivision techniques, J. Optim. Theory Appl., 124, 113-136 (2005) · Zbl 1137.90015
[13]	Emmerich, M.; Beume, N.; Coello Coello, CA; Hernández Aguirre, A.; Zitzler, E., An EMO algorithm using the hypervolume measure as selection criterion, Evolutionary Multi-Criterion Optimization, 62-75 (2005), Berlin, Heidelberg: Springer, Berlin, Heidelberg · Zbl 1109.68595
[14]	Evtushenko, Y.; Potapov, M.; Demyanov, VF; Pallaschke, D., A nondifferentiable approach to multicriteria optimization, Nondifferentiable Optimization: Motivations and Applications, 97-102 (1985), Berlin, Heidelberg: Springer, Berlin, Heidelberg
[15]	Evtushenko, YG; Posypkin, MA, A deterministic algorithm for global multi-objective optimization, Optim Methods Softw., 29, 5, 1005-1019 (2014) · Zbl 1305.90364
[16]	Gergel, V.; Kozinov, E., Efficient multicriterial optimization based on intensive reuse of search information, J. Global Optim., 71, 1, 1-18 (2018) · Zbl 1402.90166
[17]	Guillemin, V.; Pollack, A., Differential Topology (1974), Englewood Cliffs, N.J.: Prentice-Hall Inc., Englewood Cliffs, N.J. · Zbl 0361.57001
[18]	Hartikainen, M.; Miettinen, K.; Wiecek, MM, PAINT: Pareto front interpolation for nonlinear multiobjective optimization, Comput. Optim. Appl., 52, 845-867 (2012) · Zbl 1259.90119
[19]	Hartikainen, ME; Lovison, A., PAINT-SiCon: constructing consistent parametric representations of Pareto sets in nonconvex multiobjective optimization, J. Global Optim., 62, 2, 243-261 (2015) · Zbl 1325.90082
[20]	Jones, DR; Perttunen, CD; Stuckman, BE, Lipschitzian optimization without the Lipschitz constant, J. Optim. Theory Appl., 79, 157-181 (1993) · Zbl 0796.49032
[21]	Knowles, J., ParEGO: a hybrid algorithm with on-line landscape approximation for expensive multiobjective optimization problems, IEEE Trans. Evol. Comput., 10, 50-66 (2006)
[22]	Lera, D.; Sergeyev, YD, GOSH: derivative-free global optimization using multi-dimensional space-filling curves, J. Global Optim., 71, 1, 193-211 (2018) · Zbl 1402.90133
[23]	Lovison, A., Singular Continuation: generating piecewise linear approximations to Pareto sets via global analysis, SIAM J. Optim., 21, 463-490 (2011) · Zbl 1226.90094
[24]	Lovison, A., Global search perspectives for multiobjective optimization, J. Global Optim., 57, 385-398 (2013) · Zbl 1274.90274
[25]	Lovison, A.; Hartikainen, ME; Gaspar-Cunha, A.; Henggeler Antunes, C.; Coello, CC, On generalizing Lipschitz global methods for multiobjective optimization, Evolutionary Multi-Criterion Optimization, 264-278 (2015), Cham: Springer, Cham
[26]	Lovison, A.; Miettinen, K., Exact extension of the DIRECT algorithm to multiple objectives, AIP Conf. Proc., 2070, 1, 020053 (2019)
[27]	Lovison, A., Pecci, F.: Hierarchical stratification of Pareto sets (2014). arXiv:1407.1755 Accessed 15 June 2020
[28]	de Melo, W., On the structure of the Pareto set of generic mappings, Boletim da Sociedade Brasileira de Matemática, 7, 121-126 (1976) · Zbl 0414.58014
[29]	Miettinen, K., Nonlinear Multiobjective Optimization (1999), Boston: Kluwer Academic Publishers, Boston · Zbl 0949.90082
[30]	Neumaier, A., Complete search in continuous global optimization and constraint satisfaction, Acta Numerica, 13, 271-369 (2004) · Zbl 1113.90124
[31]	Pardalos, PM; Žilinskas, A.; Žilinskas, J., Non-Convex Multi-Objective Optimization (2017), Cham: Springer, Cham · Zbl 1372.90004
[32]	Paulavičius, R.; Sergeyev, YD; Kvasov, DE; Žilinskas, J., Globally-biased BIRECT algorithm with local accelerators for expensive global optimization, Expert Syst. Appl., 144, 113052-27 (2020)
[33]	Piyavskii, S., An algorithm for finding the absolute extremum of a function, USSR Comput. Math. Math. Phys., 12, 57-67 (1972) · Zbl 0282.65052
[34]	Schütze, O., Dell’Aere, A., Dellnitz, M.: On continuation methods for the numerical treatment of multi-objective optimization problems. In: Practical Approaches to Multi-Objective Optimization. IBFI, Schloss Dagstuhl, Germany (2005)
[35]	Sergeyev, YD; Kvasov, DE, Global search based on efficient diagonal partitions and a set of Lipschitz constants, SIAM J. Optim., 16, 3, 910-937 (2006) · Zbl 1097.65068
[36]	Sergeyev, YD, On convergence of “divide the best” global optimization algorithms, Optimization, 44, 3, 303-325 (2007) · Zbl 0986.90058
[37]	Shubert, B., A sequential method seeking the global maximum of a function, SIAM J. Numer. Anal., 9, 379-388 (1972) · Zbl 0251.65052
[38]	Smale, S.: Global analysis and economics I: Pareto optimum and a generalization of Morse theory. In: Peixoto, M.M. (ed.) Dynamical Systems, pp. 531-544. Academic Press, (1973) · Zbl 0269.58009
[39]	Srinivas, N., Deb, K.: Muiltiobjective optimization using nondominated sorting in genetic algorithms. Evol. Comput. 2(3), 221-248 (1994)
[40]	Stephens, C.; Baritompa, W., Global optimization requires global information, J. Optim. Theory Appl., 96, 575-588 (1998) · Zbl 0907.90250
[41]	Strongin, RG; Sergeyev, YD, Global Optimization with Non-Convex Constraints (2000), US: Springer, US
[42]	Wang, L., Ishida, H., Hiroyasu, T., Miki, M.: Examination of multi-objective optimization method for global search using DIRECT and GA. In: Proceedings of the IEEE Congress on Evolutionary Computation, pp. 2446-2451. IEEE (2008)
[43]	Wierzbicki, AP, A mathematical basis for satisficing decision making, Math. Model., 3, 391-405 (1982) · Zbl 0521.90097
[44]	Wierzbicki, AP, On the completeness and constructiveness of parametric characterizations to vector optimization problems, OR Spectrum, 8, 73-87 (1986) · Zbl 0592.90084
[45]	Wong, C.S.Y., Al-Dujaili, A., Sundaram, S.: Hypervolume-based DIRECT for multi-objective optimisation. In: Proceedings of the 2016 on Genetic and Evolutionary Computation Conference Companion, GECCO ’16 Companion, pp. 1201-1208. ACM, New York (2016)
[46]	Žilinskas, A., A one-step worst-case optimal algorithm for bi-objective univariate optimization, Optim. Lett., 8, 7, 1945-1960 (2013) · Zbl 1302.90204
[47]	Žilinskas, A.; Gimbutienė, G., On one-step worst-case optimal trisection in univariate bi-objective Lipschitz optimization, Commun. Nonlinear Sci. Numer. Simul., 35, 123-136 (2016) · Zbl 1510.90255