Abstract
In this paper, we propose a computationally efficient approach for solving complex multicriteria lexicographic optimization problems, which can be complicated by the multiextremal nature of the efficiency criteria and extensive volume of computations required to calculate the criteria values. The formulation of problems is assumed to be the subject to change as well, which, in turn, may require solving dynamically defined sets of multicriteria optimization problems. The proposed approach is based on reducing multidimensional problems to one-dimensional global optimization problems, utilizing efficient global search algorithms, and reusing the search information obtained in the process of calculations. The results of numerical experiments confirm that the proposed approach demonstrates high computational efficiency of solving multicriteria global optimization problems.
Similar content being viewed by others
Notes
From a general point of view, the MCOlex problem can be considered as a special case of the MMCOlex problem for \(t=1\).
Data ordering is reflected by using a subscript.
If \(M=m+1\), then \(z_M^*\) is the minimum value of the function \(\varphi (x)\).
This method is also known as the index method—see [29].
The values \(r_{\nu } > 1\), \(1 \le \nu \le m+1\), are the AGCS reliability parameters used for computing the interval characteristics in (25).
References
Miettinen, K.: Nonlinear Multiobjective Optimization. Springer, New York (1999)
Ehrgott, M.: Multicriteria Optimization, 2nd edn. Springer, New York (2010)
Collette, Y., Siarry, P.: Multiobjective Optimization: Principles and Case Studies (Decision Engineering). Springer, New York (2011)
Marler, R.T., Arora, J.S.: Multi-Objective Optimization: Concepts and Methods for Engineering. VDM Verlag, Germany (2009)
Pardalos, P.M., Žilinskas, A., Žilinskas, J.: Non-Convex Multi-Objective Optimization. Springer, New York (2017)
Marler, R., Arora, J.: Survey of multi-objective optimization methods for engineering. Struct. Multidisc. Optim. 26, 369–395 (2004)
Figueira, J., Greco, S., Ehrgott, M. (eds.): Multiple Criteria Decision Analysis: State of the Art Surveys. Springer, New York (NY) (2005)
Zavadskas, E.K., Turskis, Z., Kildienė, S.: State of art surveys of overviews on MCDM/MADM methods. Technol. Econ. Dev. Econ. 20, 165–179 (2014)
Hillermeier, C., Jahn, J.: Multiobjective optimization: survey of methods and industrial applications. Surv. Math. Ind. 11, 1–42 (2005)
Eichfelder, G.: Scalarizations for adaptively solving multi-objective optimization problems. Comput. Optim. Appl. 44, 249–273 (2009)
Branke, J., Deb, K., Miettinen, K., Slowinski, R. (eds.): Multi-Objective Optimization-Interactive and Evolutionary Approaches. Springer, Berlin (2008)
Deb, K.: Multi-Objective Optimization using Evolutionary Algorithms. Wiley, Chichester (2001)
Yang, X.-S.: Nature-Inspired Metaheuristic Algorithms. Luniver Press, Frome (2008)
Tan, K.C., Khor, E.F., Lee, T.H.: Multi-Objective Evolutionary Algorithms and Applications. Springer-Verlag, London (2005)
Cococcioni, M., Cudazzo, A., Pappalardo, M., Sergeyev, Y.D.: Solving the lexicographic multi-objective mixed-integer linear programming problem using branch-and-bound and grossone methodology. Commun. Nonlinear Sci. Numer. Simul. 84, 105177 (2020)
Cococcioni, M., Pappalardo, M., Sergeyev, Y.D.: Lexicographic multi-objective linear programming using Grossone methodology: theory and algorithm. Appl. Math. Comput. 318, 298–311 (2018)
Lai, L., Fiaschi, L., Cococcioni, M.: Solving mixed Pareto-lexicographic multi-objective optimization problems: the case of priority chains. Swarm Evol. Comput. 55, 100687 (2020). https://doi.org/10.1016/j.swevo.2020.100687
Zarepisheh, M., Khorram, E.: On the transformation of lexicographic nonlinear multiobjective programs to single objective programs. Math. Methods Oper. Res. 74, 217–231 (2011)
Haimes, Y.Y., Lasdon, L., Wismer, D.: On a bicriterion formulation of the problem of integrated systems identification and system optimization. IEEE Trans. Syst. Man Cybern. 1, 296–297 (1971)
Chankong, V., Haimes, Y.Y.: Multiobjective Decision Making: Theory and Methodology. North-Holland Series in System Science and Engineering. Elsevier, New York (NY) (1983)
Ehrgott, M., Ruzika, S.: Improved \(\varepsilon \)-constraint method for multiobjective programming. J. Optim. Theory Appl. 138, 375–396 (2008)
Rastegar, N., Khorram, E.: Relaxation of constraints in lexicographic multiobjective programming problems. J. Math. Progr. Oper. Res. 64, 2111–2129 (2015)
Castro-Gutierrez, J., Landa-Silva, D., Pérez, J.M.: Improved dynamic lexicographic ordering for multi-objective optimisation. Lect. Notes Comput. Sci. 6239, 31–40 (2010)
Gergel, V.P., Kozinov, E.A.: Efficient multicriterial optimization based on intensive reuse of search information. J. Glob. Optim. 71(1), 73–90 (2018). https://doi.org/10.1007/s10898-018-0624-3
Audet, C., Savard, G., Zghal, W.: Multiobjective optimization through a series of single-objective formulations. SIAM J. Optim. 19(1), 188–210 (2008)
Jones, D.R.: A taxonomy of global optimization methods based on response surfaces. J. Glob. Optim. 21, 345–383 (2001)
Voutchkov, I., Keane, A.: Multi-objective optimization using surrogates. Comput. Intell. Optim. Adapt. Learn. Optim. 7, 155–175 (2010)
Strongin, R.G.: Numerical Methods in Multiextremal Problems: Information-statistical Algorithms. Nauka, Moscow (1978). (in Russian)
Strongin, R.G., Sergeyev, Y.D.: Global Optimization with Non-convex Constraints. Sequential and Parallel Algorithms, 2nd edn. Kluwer Academic Publishers, Dordrecht (2013). 3 rd ed. (2014)
Törn, A., Žilinskas, A.: Global Optimization. Lecture Notes in Computer Science, vol. 350. Springer-Verlag, Berlin (1989)
Horst, R., Tuy, H.: Global Optimization: Deterministic Approaches. Springer-Verlag, Berlin (1990)
Zhigljavsky, A.A.: Theory of Global Random Search. Kluwer Academic Publishers, Dordrecht (1991)
Pintér, J.D.: Global Optimization in Action (Continuous and Lipschitz Optimization: Algorithms, Implementations and Applications). Kluwer Academic Publishers, Dortrecht (1996)
Sergeyev, Y.D., Strongin, R.G., Lera, D.: Introduction to Global Optimization Exploiting Space-filling Curves. Springer, Berlin (2013)
Locatelli, M., Schoen, F.: Global Optimization: Theory, Algorithms, and Applications. SIAM, India (2013)
Floudas, C.A., Pardalos, M.P.: Recent Advances in Global Optimization. Princeton University Press, Princeton (2016)
Sergeyev, Y.D., Kvasov, D.E.: Deterministic Global Optimization: An Introduction to the Diagonal Approach (Springer Briefs in Optimization). Springer, Berlin (2017)
Carr, C.R., Howe, C.W.: Quantitative Decision Procedures in Management and Economic: Deterministic Theory and Applications. McGraw-Hill, New York (1964)
Dam, E.R., Husslage, B., Hertog, D.: One-dimensional nested maximin designs. J. Glob. Optim. 46(2), 287–306 (2010)
Gergel, V.P., Grishagin, V.A., Israfilov, R.A.: Adaptive dimensionality reduction in multiobjective optimization with multiextremal criteria. Lect. Notes Comput. Sci. 11331, 129–140 (2019)
Grishagin, V.A., Israfilov, R.A.: Global search acceleration in the nested optimization scheme. AIP Conf. Proc. 1738, 400010 (2016). https://doi.org/10.1063/1.4952198
Grishagin, V.A., Israfilov, R.A., Sergeyev, Y.D.: Comparative efficiency of dimensionality reduction schemes in global optimization. AIP Conf. Proc. 1776, 060011 (2016). https://doi.org/10.1063/1.4965345
Lera, D., Sergeyev, Y.D.: Deterministic global optimization using space-filling curves and multiple estimates of Lipschitz and Holder constants. Commun. Nonlinear Sci. 23(1–3), 328–342 (2015)
Gergel, V.: A unified approach to use of coprocessors of various types for solving global optimization problems. In: 2nd International Conference on MACSI. 13–18 (2015). https://doi.org/10.1109/MCSI.2015.18
Arora, R.K.: Optimization: Algorithms and Applications. CRC Press, Boca Raton (2015)
Bazaraa, M.S., Sherali, H.D., Shetty, C.M.: Nonlinear Programming: Theory and Algorithms. Wiley, Amsterdam (2006)
Strongin, R.G., Gergel, V.P., Grishagin, V.A., Barkalov, K.A.: Parallel Computing in Global Optimization Problems. MSU Press, Moscow (2013). (in Russian)
Sergeyev, Y.D., Pugliese, P., Famularo, D.: Index information algorithm with local tuning for solving multidimensional global optimization problems with multiextremal constraints. Math. Progr. Ser. A 96, 489–512 (2003)
Gergel, V.P., Kozinov, E.A.: Accelerating multicriterial optimization by the intensive exploitation of accumulated search data. AIP Conf. Proc. 1776, 090003 (2016). https://doi.org/10.1063/1.4965367
Sysoyev, A., Barkalov, K., Gergel, V.: Globalizer: a novel supercomputer software system for solving time-consuming global optimization problems. Numer. Algebra Control. Optim. 8(1), 47–62 (2018)
Martĺ, L., Garcĺa, J., Berlanga, A., Molina, J.M.: A stopping criterion for multi-objective optimization evolutionary algorithms. Inf. Sci. 367–368, 700–718 (2016)
Dilettoso, E., Rizzo, S.A., Salerno, N.: A weakly Pareto compliant quality indicator. Math. Comput. Appl. 22(1), 25 (2017)
Wu, J., Azarm, S.: Metrics for quality assessment of a multiobjective design optimization solution set. J. Mech. Des. 123(1), 18–25 (2001)
Audet, C., Bigeon, J., Cartier, D., Le Digabel, S., Salomon, L.: Performance indicators in multiobjective optimization. Technical Report G-2018-90, Les cahiers du GERAD. (2018)
Evtushenko, YuG, Posypkin, M.A.: A deterministic algorithm for global multi-objective optimization. Optim. Methods Softw. 29(5), 1005–1019 (2014)
Žilinskas, A., Žilinskas, J.: Adaptation of a one-step worst-case optimal univariate algorithm of bi-objective Lipschitz optimization to multidimensional problems. Commun. Nonlinear Sci. Numer. Simul. 21(1–3), 89–98 (2015)
Huband, S., Hingston, P., Barone, L., While, L.: A review of multiobjective test problems and a scalable test problem toolkit. IEEE Trans. Evolut. Comput. 10(5), 477–506 (2006)
Hansen, N., Auger, A., Finck, S., Ros, R.: Real-parameter black-box optimization benchmarking 2009: experimental setup. INRIA Research Report RR-6829, INRIA Saclay-Ile-de-France. updated February 2010 (2009)
Custódio, A.L., Madeira, J.F.A., Vaz, A.I.F., Vicente, L.N.: Direct multisearch for multiobjective optimization. SIAM J. Optim. 21(3), 1109–1140 (2011)
Brockhoff, D., Tusar, T., Auger, A., Hansen, N.: Using well-understood single-objective functions in multiobjective black-box optimization test suites. (2019) arXiv:1604.00359
Gaviano, M., Kvasov, D.E., Lera, D., Sergeyev, Y.D.: Software for generation of classes of test functions with known local and global minima for global optimization. ACM Trans. Math. Softw. 29(4), 469–480 (2003)
Kvasov, D.E., Sergeyev, Y.D.: Deterministic approaches for solving practical black-box global optimization problems. Adv. Eng. Softw. 80, 58–66 (2015)
Modorskii, V., Gaynutdinova, D., Gergel, V., Barkalov, K.: Optimization in design of scientfic products for purposes of cavitation problems. AIP Conf. Proc. 1738, 400013 (2016)
Acknowledgements
The work was supported by the Ministry of Science and Higher Education of the Russian Federation, agreement No 075-15-2020-808.
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
About this article
Cite this article
Gergel, V., Kozinov, E. & Barkalov, K. Computationally efficient approach for solving lexicographic multicriteria optimization problems. Optim Lett 15, 2469–2495 (2021). https://doi.org/10.1007/s11590-020-01668-y
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11590-020-01668-y