Global search perspectives for multiobjective optimization. (English) Zbl 1274.90274
Summary: Extending the notion of global search to multiobjective optimization is far than straightforward, mainly for the reason that one almost always has to deal with infinite Pareto optima and correspondingly infinite optimal values. Adopting Stephen Smale’s global analysis framework, we highlight the geometrical features of the set of Pareto optima and we are led to consistent notions of global convergence. We formulate then a multiobjective version of a celebrated result by Stephens and Baritompa, about the necessity of generating everywhere dense sample sequences, and describe a globally convergent algorithm in case the Lipschitz constant of the determinant of the Jacobian is known.
MSC:
| 90C26 | Nonconvex programming, global optimization |
| 90C29 | Multi-objective and goal programming |
| 58K05 | Critical points of functions and mappings on manifolds |
Keywords:
multiobjective optimization; global optimization; nonconvexity and multiextremality; stability of mappings; continuation methodsReferences:
| [1] | Allgower E.L., Georg K.: Simplicial and continuation methods for approximating fixed points and solutions to systems of equations. SIAM Rev. 22(1), 28-85 (1980) · Zbl 0432.65027 · doi:10.1137/1022003 |
| [2] | Allgower E.L., Georg K.: Piecewise linear methods for nonlinear equations and optimization. J. Comput. Appl. Math. 124(1-2), 245-261 (2000) · Zbl 0970.65055 · doi:10.1016/S0377-0427(00)00427-1 |
| [3] | Allgower E.L., Gnutzmann S.: An algorithm for piecewise linear approximation of implicitly defined two-dimensional surfaces. SIAM J. Numer. Anal. 24(2), 452-469 (1987) · Zbl 0618.65006 · doi:10.1137/0724033 |
| [4] | Allgower E.L., Sommese A.J.: Piecewise linear approximation of smooth compact fibers. J. Complex. 18(2), 547-556 (2002) · Zbl 1028.65054 · doi:10.1006/jcom.2002.0645 |
| [5] | Arnol′d, V.I.: Singularities of smooth mappings. Russ. Math. Surv. 23(1), 1-43 (1968). http://stacks.iop.org/0036-0279/23/1 · Zbl 0167.21702 |
| [6] | Askar, S., Tiwari, A.: Multi-objective optimisation problems: a symbolic algorithm for performance measurement of evolutionary computing techniques. In: Ehrgott M. (ed.) EMO 2009, Lecture Notes in Computer Science, vol. 5467, pp. 169-182. Springer (2009) · Zbl 1191.90059 |
| [7] | Benson H., Sayin S.: Towards finding global representations of the efficient set in multiple objective mathematical programming. Naval Res Logist 44(1), 47-67 (1997) · Zbl 0882.90116 · doi:10.1002/(SICI)1520-6750(199702)44:1<47::AID-NAV3>3.0.CO;2-M |
| [8] | de Melo W.: On the structure of the Pareto set of generic mappings. Bol. Soc. Brasil. Mat. 7(2), 121-126 (1976) · Zbl 0414.58014 · doi:10.1007/BF02584786 |
| [9] | de Melo W.: Stability and optimization of several functions. Topology 15(1), 1-12 (1976) · Zbl 0327.58008 · doi:10.1016/0040-9383(76)90045-8 |
| [10] | Guillemin V., Pollack A.: Differential topology. Prentice-Hall (1974). http://www.ulb.tu-darmstadt.de/tocs/59605480.pdf · Zbl 0361.57001 |
| [11] | Hartikainen M., Miettinen K., Wiecek M.M.: Constructing a pareto front approximation for decision making. Math. Methods Oper. Res. 73(2), 209-234 (2011). doi:10.1007/s00186-010-0343-0 · Zbl 1216.49002 · doi:10.1007/s00186-010-0343-0 |
| [12] | Hillermeier C.: Generalized homotopy approach to multiobjective optimization. J. Optim. Theory Appl. 110(3), 557-583 (2001) · Zbl 1064.90041 · doi:10.1023/A:1017536311488 |
| [13] | Hillermeier, C.: Nonlinear Multiobjective Optimization. International Series of Numerical Mathematics, vol. 135. Birkhäuser Verlag, Basel (2001). A generalized homotopy approach · Zbl 0966.90069 |
| [14] | Jones D.R.: A taxonomy of global optimization methods based on response surfaces. J. Glob. Optim. 21(4), 345-383 (2001) · Zbl 1172.90492 · doi:10.1023/A:1012771025575 |
| [15] | Jones D.R., Perttunen C.D., Stuckman B.E.: Lipschitzian optimization without the lipschitz constant. J. Optim. Theory Appl. 79(1), 157-181 (1993) · Zbl 0796.49032 · doi:10.1007/BF00941892 |
| [16] | Jones D.R., Schonlau M., Welch W.J.: Efficient global optimization of expensive black-box functions. J. Glob. Optim. 13(4), 455-492 (1998) · Zbl 0917.90270 · doi:10.1023/A:1008306431147 |
| [17] | Khompatraporn C., Pintér J.D., Zabinsky Z.B.: Comparative assessment of algorithms and software for global optimization. J. Glob. Optim. 31(4), 613-633 (2005) · Zbl 1093.90043 · doi:10.1007/s10898-004-9971-3 |
| [18] | Knowles J.: ParEGO: a hybrid algorithm with on-line landscape approximation for expensive multiobjective optimization problems. IEEE Trans. Evol. Comput. 10(1), 50-66 (2006) · doi:10.1109/TEVC.2005.851274 |
| [19] | Levine, H.: Singularities of differentiable mappings. In: C. Wall (ed.) Proceedings of Liverpool Singularities—Symposium I, Lecture Notes in Mathematics, vol. 192, pp. 1-21. Springer, Berlin (1971). doi:10.1007/BFb0066810 · Zbl 0216.45803 |
| [20] | Lovison, A.: Singular continuation: generating piecewise linear approximations to pareto sets via global analysis. SIAM J. Optim. 21(2), 463-490 (2011). doi:10.1137/100784746 · Zbl 1226.90094 |
| [21] | Lovison A., Rigoni E.: Adaptive sampling with a Lipschitz criterion for accurate metamodeling. Commun. Appl. Ind. Math. 1(2), 110-126 (2010) · Zbl 1329.62357 |
| [22] | Miettinen, K.: Nonlinear multiobjective optimization. International Series in Operations Research & Management Science, vol. 12. Kluwer, Boston (1999) · Zbl 0949.90082 |
| [23] | Miglierina E., Molho E.: Scalarization and stability in vector optimization. J. Optim. Theory Appl. 114(3), 657-670 (2002) · Zbl 1026.90080 · doi:10.1023/A:1016031214488 |
| [24] | Miglierina E., Molho E., Rocca M.: Critical points index for vector functions and vector optimization. J. Optim. Theory Appl. 138(3), 479-496 (2008). doi:10.1007/s10957-008-9383-5 · Zbl 1191.90059 · doi:10.1007/s10957-008-9383-5 |
| [25] | Pijavskiĭ, S.A.: An algorithm for finding the absolute minimum of functions. In: Theory of Optimal Solutions (Seminar, Kiev, 1967), No. 2 (Russian), pp. 13-24. Akad. Nauk Ukrain. SSR, Kiev (1967) · Zbl 0917.90270 |
| [26] | Pintér, J.D.: Nonlinear optimization with GAMS/LGO. J. Global Optim. 38(1), 79-101 (2007). doi:10.1007/s10898-006-9084-2 · Zbl 1179.90311 |
| [27] | Schütze, O., Dell’Aere, A., Dellnitz, M.: On continuation methods for the numerical treatment of multi-objective optimization problems. In: Branke, J., Deb, K., Miettinen, K., Steuer, R.E. (eds.) Practical Approaches to Multi-Objective Optimization No. 04461 in Dagstuhl Seminar Proceedings. Internationales Begegnungs- und Forschungszentrum für Informatik (IBFI), Schloss Dagstuhl, Germany, Dagstuhl, Germany (2005). http://drops.dagstuhl.de/opus/volltexte/2005/349 · Zbl 1216.49002 |
| [28] | Sergeyev, Y.D.: An information global optimization algorithm with local tuning. SIAM J. Optim. 5(4), 858-870 (1995). doi:10.1137/0805041. http://dx.doi.org/10.1137/0805041 · Zbl 0847.90128 |
| [29] | Sergeyev Y.D., Kvasov D.E.: Global search based on efficient diagonal partitions and a set of lipschitz constants. SIAM J. Optim. 16(3), 910-937 (2006) · Zbl 1097.65068 · doi:10.1137/040621132 |
| [30] | Shewchuk J.R.: Delaunay refinement algorithms for triangular mesh generation. Comput. Geom. Theory Appl. 22(1-3), 21-74 (2002) · Zbl 1016.68139 · doi:10.1016/S0925-7721(01)00047-5 |
| [31] | Shubert B.O.: A sequential method seeking the global maximum of a function. SIAM J. Numer. Anal. 9, 379-388 (1972) · Zbl 0251.65052 · doi:10.1137/0709036 |
| [32] | Smale S.: What is global analysis?. Am. Math. Month. 76, 4-9 (1969) · Zbl 0169.12604 · doi:10.2307/2316777 |
| [33] | Smale, S.: Global analysis and economics. I. Pareto optimum and a generalization of Morse theory. In: Dynamical Systems (Proc. Sympos., Univ. Bahia, Salvador, 1971), pp. 531-544. Academic Press, New York (1973) · Zbl 1028.65054 |
| [34] | Smale, S.: Optimizing several functions. In: Manifolds-Tokyo 1973 (Proc. Internat. Conf., Tokyo, 1973), pp. 69-75. Univ. Tokyo Press, Tokyo (1975) · Zbl 0349.90086 |
| [35] | Stephens, C., Baritompa, W.: Global optimization requires global information. J. Optim. Theory Appl. 96, 575-588 (1998). doi:10.1023/A:1022612511618. http://dx.doi.org/10.1023/A:1022612511618 · Zbl 0907.90250 |
| [36] | Strongin R.G., Sergeyev Y.D.: Global optimization: fractal approach and non-redundant parallelism. J. Glob. Optim. 27(1), 25-50 (2003) · Zbl 1035.90086 · doi:10.1023/A:1024652720089 |
| [37] | Thom, R.: Les singularités des applications différentiables. Ann. Inst. Fourier (1956) · Zbl 0075.32104 |
| [38] | Wan Y.H.: Morse theory for two functions. Topology 14(3), 217-228 (1975) · Zbl 0305.58007 · doi:10.1016/0040-9383(75)90002-6 |
| [39] | Wan Y.H.: On local Pareto optima. J. Math. Econ. 2(1), 35-42 (1975) · Zbl 0309.90049 · doi:10.1016/0304-4068(75)90012-9 |
| [40] | Whitney, H.: On singularities of mappings of euclidean spaces. I. Mappings of the Plane into the plane. Ann. Math. 62(3), 374-410 (1955). http://www.jstor.org/discover/10.2307/1970070 · Zbl 0068.37101 |
| [41] | Zhang, B., Wood, G.R., Baritompa, W.P.: Multidimensional bisection: the performance and the context. J. Glob. Optim. 3(3), 337-358 (1993). doi:10.1007/BF01096775 · Zbl 0786.90062 |
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.
