×

Criteria and dimension reduction of linear multiple criteria optimization problems. (English) Zbl 1245.90118

Summary: Two of the main approaches in multiple criteria optimization are optimization over the efficient set and utility function program. These are nonconvex optimization problems in which local optima can be different from global optima. Existing global optimization methods for solving such problems can only work well for problems of moderate dimensions. In this article, we propose some ways to reduce the number of criteria and the dimension of a linear multiple criteria optimization problem. By the concept of so-called representative and extreme criteria, which is motivated by the concept of redundant (or nonessential) objective functions of Gal and Leberling, we can reduce the number of criteria without altering the set of efficient solutions. Furthermore, by using linear independent criteria, the linear multiple criteria optimization problem under consideration can be transformed into an equivalent linear multiple criteria optimization problem in the space of linear independent criteria. This equivalence is understood in a sense that efficient solutions of each problem can be derived from efficient solutions of the other by some affine transformation. As a result, such criteria and dimension reduction techniques could help to increase the efficiency of existing algorithms and to develop new methods for handling global optimization problems arisen from multiple objective optimization.

MSC:

90C29 Multi-objective and goal programming
90C26 Nonconvex programming, global optimization
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Agrell P.J.: On redundancy in multi criteria decision making. Eur. J. Oper. Res. 98, 571–586 (1997) · Zbl 0917.90207 · doi:10.1016/0377-2217(95)00340-1
[2] Amador F., Romero C.: Redundancy in lexicographic goal programming: an empirical approach. Eur. J. Oper. Res. 41, 347–354 (1989) · doi:10.1016/0377-2217(89)90255-5
[3] Benson H.P.: Optimization over the efficient set. J. Math. Anal. Appl. 98, 562–580 (1984) · Zbl 0534.90077 · doi:10.1016/0022-247X(84)90269-5
[4] Benson H.P.: An all-linear programming relaxation algorithm for optimizing over the efficient set. J. Glob. Optim. 1, 83–104 (1991) · Zbl 0739.90056 · doi:10.1007/BF00120667
[5] Benson H.P.: A geometrical analysis of the outcome set in multiple objective convex programs with linear criterion functions. J. Glob. Optim. 6, 231–251 (1995) · Zbl 0835.90082 · doi:10.1007/BF01099463
[6] Benson H.P.: An outer approximation algorithm for generating all efficient extreme points in the outcome set of a multiple objective linear programming problems. J. Glob. Optim. 13, 1–24 (1998) · Zbl 0908.90223 · doi:10.1023/A:1008215702611
[7] Benson H.P., Lee D.: Outcome–based algorithm for ptimizing over the efficient set of a bicriteria linear programming problem. J. Optim. Theory Appl. 88, 77–105 (1996) · Zbl 0842.90099 · doi:10.1007/BF02192023
[8] Benson H.P., Sun E.: Outcome space partition of weight set in multiobjective linear programming. J. Optim. Theory Appl. 105, 17–36 (2000) · Zbl 1028.90051 · doi:10.1023/A:1004605810296
[9] Brockhoff, D., Zitzler, E.: Dimensionality reduction in multiobjective optimization: the minimum objective subset problem, In: Waldmann K.H., Stocker U.M. (eds.) Operations Research Proceedings 2006, 423–429 (2007) · Zbl 1209.90311
[10] Dauer J.P., Fosnaugh T.A.: Optimization over the efficient set. J. Glob. Optim. 7, 261–277 (1995) · Zbl 0841.90107 · doi:10.1007/BF01279451
[11] Deb, K., Saxena, D.: On finding pareto-optimal solutions through dimensionality reduction for certain large-dimensional multi-objective optimization problems, KanGal Report 2005011, Department of Mechanical Engineering, IIT Kanpur, India, (2005)
[12] Ehrgott M.: Multicriteria Optimization. Springer, Berlin (2005) · Zbl 1132.90001
[13] Fülöp, J.: A cutting plane algorithm for linear optimization over the efficient set, generalized convexity. In: Komlösi S., Rapcsàk T., Schaible S. (eds.) Lecture Notes in Economics and Mathematical Systems, vol. 405, 374–385, Springer, Berlin, Germany, (1994) · Zbl 0802.90088
[14] Gal, T.: A note on size reduction of the objective functions matrix in vector maximum problems. In: Multiple Criteria Decision Making Theory and Application, Proceedings of Third Conference, Hagen/Königswinter, 1979. Lecture Notes in Economics and Mathematical Systems, vol. 177, pp. 74–84. Springer, Berlin (1980)
[15] Gal T., Hanne T.: Consequences of dropping nonessential objectives for the application of MCDM methods. Eur. J. Oper. Res. 119, 373–378 (1999) · Zbl 0933.90054 · doi:10.1016/S0377-2217(99)00139-3
[16] Gal T., Hanne T.: Nonessential objectives within network approaches for MCDM. Eur. J. Oper. Res. 168, 584–592 (2006) · Zbl 1101.90037 · doi:10.1016/j.ejor.2004.04.045
[17] Gal T., Leberling H.: Redundant objective functions in linear vector maximum problems and their determination. Eur. J. Oper. Res. 1, 176–184 (1977) · Zbl 0374.90043 · doi:10.1016/0377-2217(77)90025-X
[18] Hanne, T.: Nonessential objectives and network-based multicriteria decision making. In: Ferreira M., Menezes A.M.R., Catanas F. (eds.), Temas em metodos quantitativos, 4, 153–168 (2004)
[19] Horst R., Pardalos P.M., Thoai N.V.: Introduction to Global Optimization, 2nd edn. Kluwer, Dordrecht, The Netherlands (2000) · Zbl 0966.90073
[20] Horst R., Thoai N.V.: Utility function programs and optimization over the efficient set in multiple objective decision making. J. Optim. Theory Appl. 92, 469–486 (1997) · Zbl 0871.90072 · doi:10.1023/A:1022659523991
[21] Horst R., Thoai N.V.: Maximizing a concave function over the efficient or weakly–efficient set. Eur. J. Oper. Res. 117, 239–252 (1999) · Zbl 0998.90074 · doi:10.1016/S0377-2217(98)00230-6
[22] Horst R., Thoai N.V., Yamamoto Y., Zenke D.: On optimization over the efficient set in linear multicriteria programming. J. Optim. Theory Appl. 134, 433–443 (2007) · Zbl 1146.90062 · doi:10.1007/s10957-007-9219-8
[23] Horst R., Tuy H.: Global Optimization: Deterministic Approaches, 2nd edn. Springer, Berlin (1993) · Zbl 0704.90057
[24] Keeney R.L., Raiffa H.: Decisions with Multiple Objectives: Preferences and Value Tradeoffs. Wiley, New York (1976) · Zbl 0488.90001
[25] Le-Thi H.A., Pham D.T., Muu L.D.: Numerical solution for optimization over the efficient set by D.C. optimization algorithms. Oper. Res. Lett. 19, 117–128 (1996) · Zbl 0871.90074 · doi:10.1016/0167-6377(96)00022-3
[26] Lindroth P., Patriksson M., Stömberg A.B.: Approximating the pareto optimal set using a reduced set of objective functions. Eur. J. Oper. Res. 207, 1519–1534 (2010) · Zbl 1205.90263 · doi:10.1016/j.ejor.2010.07.004
[27] Malinowska A.B.: Changes of the set of efficient solutions by extending the number of objectives and its evaluation. Control Cybern. 31, 964–974 (2002) · Zbl 1180.90293
[28] Malinowska A.B.: Nonessential objective functions in linear multiobjective optimization problems. Control Cybern. 35, 873–880 (2006) · Zbl 1170.90422
[29] Malinowska A.B.: Weakly and properly nonessential objectives in multiobjective optimization problems. Oper. Res. Lett. 36, 647–650 (2008) · Zbl 1210.90157 · doi:10.1016/j.orl.2008.02.005
[30] Malinowska A.B., Torres D.F.M.: Computational approach to essential and nonessential objective functions in linear multicriteria optimization. J. Optim. Theory Appl. 139, 577–590 (2008) · Zbl 1163.90734 · doi:10.1007/s10957-008-9397-z
[31] Muu L.D., Luc L.T.: On equivalence between convex maximization and optimization over the efficient set. Vietnam J. Math. 24, 439–444 (1996)
[32] Pardalos, P., Siskos, Y., Zopounidis, C. (eds): Advances in Multicriteria Analysis. Kluwer, (1995) · Zbl 0847.00021
[33] Pareto V.: Manual d’économie polytique. F. Rouge, Lausan (1896)
[34] Philip J.: Algorithms for the vector maximization problem. Math. Program. 2, 207–229 (1972) · Zbl 0288.90052 · doi:10.1007/BF01584543
[35] Roy B.: Multicriteria Methodology for Decision Aiding. Kluwer, (1996) · Zbl 0893.90108
[36] Steuer R.E.: Multiple Criteria Optimization: Theory, Computation, Applications. Wiley, New York (1985)
[37] Thoai N.V.: Conical algorithm in global optimization for optimizing over efficient sets. J. Glob. Optim. 18, 321–336 (2000) · Zbl 1026.90081 · doi:10.1023/A:1026544116333
[38] Thoai N.V.: Convergence and application of a decomposition method using duality bounds for nonconvex global optimization. J. Optim. Theory Appl. 113, 165–193 (2002) · Zbl 1009.90092 · doi:10.1023/A:1014865432210
[39] Thoai N.V.: Decomposition branch and bound algorithm for optimization problems over efficient sets. J. Ind. Manag. Optim. 4, 647–660 (2008) · Zbl 1160.90654 · doi:10.3934/jimo.2008.4.647
[40] Thoai N.V.: Reverse convex programming approach in the space of extreme criteria for optimization over the efficient sets. J. Optim. Theory Appl. 147, 263–277 (2010) · Zbl 1213.90204 · doi:10.1007/s10957-010-9721-2
[41] Yamamoto Y.: Optimization over the efficient set: overview. J. Glob. Optim. 22, 285–317 (2002) · Zbl 1045.90061 · doi:10.1023/A:1013875600711
[42] Yu P.L.: Multiple Criteria Decision Making: Concepts, Techniques and Extensions. Plenum, New York (1985) · Zbl 0643.90045
[43] Yu P.L.: Multiple criteria decision making: five basic concepts. In: Nemhauser, G.L., Rinnooy Kan, A.H.G., Todd, M.J. (eds) Optimization, pp. 663–699. Amsterdam, North-Holland (1989)
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.