Namespaces
Variants
Actions

Difference between revisions of "Multi-criterion problem"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
(TeX)
 
Line 1: Line 1:
 +
{{TEX|done}}
 
A mathematical model for making an optimal decision with respect to several criteria simultaneously. These criteria may reflect evaluations of various qualities of the objects (or processes) about which a decision is to be made, or may be evaluations of some single characteristic from various points of view. The theory of multi-criterion problems belongs to [[Operations research|operations research]].
 
A mathematical model for making an optimal decision with respect to several criteria simultaneously. These criteria may reflect evaluations of various qualities of the objects (or processes) about which a decision is to be made, or may be evaluations of some single characteristic from various points of view. The theory of multi-criterion problems belongs to [[Operations research|operations research]].
  
Formally a multi-criterion problem is given by a set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m065/m065110/m0651101.png" /> of  "feasible decisions"  and a set of objective functions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m065/m065110/m0651102.png" /> on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m065/m065110/m0651103.png" />, taking real values. The essence of a multi-criterion problem is finding an optimal decision, that is, an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m065/m065110/m0651104.png" /> which, in some sense, maximizes the values of all the functions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m065/m065110/m0651105.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m065/m065110/m0651106.png" />. The existence of a decision maximizing all objective functions is a rare exception. Therefore in the theory of multi-criterion problems the notion of optimality has various and, moreover, non-trivial interpretations. The content of the theory of multi-criterion problems is the development of such concepts of optimality, the proof of their realizability (that is, the existence of decisions which are optimal in the corresponding sense), and the search for these realizations (that is, the actual solution of the problem).
+
Formally a multi-criterion problem is given by a set $X$ of  "feasible decisions"  and a set of objective functions $f_1,\dots,f_n$ on $X$, taking real values. The essence of a multi-criterion problem is finding an optimal decision, that is, an $x\in X$ which, in some sense, maximizes the values of all the functions $f_i$, $i=1,\dots,n$. The existence of a decision maximizing all objective functions is a rare exception. Therefore in the theory of multi-criterion problems the notion of optimality has various and, moreover, non-trivial interpretations. The content of the theory of multi-criterion problems is the development of such concepts of optimality, the proof of their realizability (that is, the existence of decisions which are optimal in the corresponding sense), and the search for these realizations (that is, the actual solution of the problem).
  
The most direct approach to solving a multi-criterion problem consists in reducing it to an ordinary ( "single-criterion" ) problem of [[Mathematical programming|mathematical programming]] by replacing the system of objective functions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m065/m065110/m0651107.png" /> by an aggregate function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m065/m065110/m0651108.png" />. In this role there may appear weighted sums <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m065/m065110/m0651109.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m065/m065110/m06511010.png" />, weighted maxima <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m065/m065110/m06511011.png" />, and other combinations of the initial objective functions. This approach is conceptually and technically convenient. Its fundamental shortcoming is the difficulty in satisfying the need for a meaningful comparability of the values of the various objective functions and also the uncertainty (and not infrequent arbitrariness) in the choice of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m065/m065110/m06511012.png" /> and, in particular, in the weights <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m065/m065110/m06511013.png" />. To establish these one is often advised to resort to expert evaluations.
+
The most direct approach to solving a multi-criterion problem consists in reducing it to an ordinary ("single-criterion") problem of [[Mathematical programming|mathematical programming]] by replacing the system of objective functions $f_1,\dots,f_n$ by an aggregate function $F(f_1,\dots,f_n)$. In this role there may appear weighted sums $\sum_{i=1}^n\lambda_if_i$, $\lambda_i\geq0$, weighted maxima $\max_i\lambda_if_i$, and other combinations of the initial objective functions. This approach is conceptually and technically convenient. Its fundamental shortcoming is the difficulty in satisfying the need for a meaningful comparability of the values of the various objective functions and also the uncertainty (and not infrequent arbitrariness) in the choice of $F$ and, in particular, in the weights $\lambda_i$. To establish these one is often advised to resort to expert evaluations.
  
A particular case of this approach is the selection of a  "main criterion" , that is, all weights except a single <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m065/m065110/m06511014.png" /> are put equal to zero. Then the multi-criterion problem becomes an ordinary problem of mathematical programming, and the set of optimal solutions of it can be considered as the set of feasible solutions for a new multi-criterion problem with objective functions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m065/m065110/m06511015.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m065/m065110/m06511016.png" />.
+
A particular case of this approach is the selection of a  "main criterion", that is, all weights except a single $\lambda_{i_0}$ are put equal to zero. Then the multi-criterion problem becomes an ordinary problem of mathematical programming, and the set of optimal solutions of it can be considered as the set of feasible solutions for a new multi-criterion problem with objective functions $f_i$, $i\neq i_0$.
  
As the solutions of a multi-criterion problem one can consider solutions which are Pareto optimal, that is, solutions which do not allow an improvement with respect to any one criterion, except at the expense of detoriation in another criterion (in other words, an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m065/m065110/m06511017.png" /> such that for any <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m065/m065110/m06511018.png" />, if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m065/m065110/m06511019.png" /> then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m065/m065110/m06511020.png" /> for some <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m065/m065110/m06511021.png" />). The shortcoming of this approach is the plurality of Pareto-optimal solutions. This defect was overcome, following a suggestion of J. Nash, by the method of  "bargaining schemes" , which essentially limits the number of selected solutions among the Pareto-optimal solutions. It consists in establishing, on the basis of informal considerations, certain minimal feasible values <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m065/m065110/m06511022.png" /> and subsequently finding a feasible <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m065/m065110/m06511023.png" /> maximizing <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m065/m065110/m06511024.png" /> (see also [[Arbitration scheme|Arbitration scheme]]).
+
As the solutions of a multi-criterion problem one can consider solutions which are Pareto optimal, that is, solutions which do not allow an improvement with respect to any one criterion, except at the expense of detoriation in another criterion (in other words, an $x\in X$ such that for any $y\in X$, if $f_i(x)<f_i(y)$ then $f_j(y)<f_j(x)$ for some $j$). The shortcoming of this approach is the plurality of Pareto-optimal solutions. This defect was overcome, following a suggestion of J. Nash, by the method of  "bargaining schemes", which essentially limits the number of selected solutions among the Pareto-optimal solutions. It consists in establishing, on the basis of informal considerations, certain minimal feasible values $f_i^0$ and subsequently finding a feasible $x$ maximizing $\prod_{i=1}^n(f_i(x)-f_i^0)$ (see also [[Arbitration scheme|Arbitration scheme]]).
  
A multi-criterion problem can also be considered as a game (see [[Games, theory of|Games, theory of]]) and its solution can be treated on the basis of various game-theoretic methods. For example, if a feasible solution <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m065/m065110/m06511025.png" /> is chosen with the aim of maximizing one of the objective functions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m065/m065110/m06511026.png" />, and if it is unknown which one has to be maximized, then it is possible to use a weighted sum of these functions, taking as weights the components of a mixed strategy of  "nature" . A multi-criterion problem can be treated as a [[Non-cooperative game|non-cooperative game]], or can include the point of view of cooperative game theory (see [[Cooperative game|Cooperative game]]) as well as the application of related optimality principles.
+
A multi-criterion problem can also be considered as a game (see [[Games, theory of|Games, theory of]]) and its solution can be treated on the basis of various game-theoretic methods. For example, if a feasible solution $x$ is chosen with the aim of maximizing one of the objective functions $f_1,\dots,f_n$, and if it is unknown which one has to be maximized, then it is possible to use a weighted sum of these functions, taking as weights the components of a mixed strategy of  "nature". A multi-criterion problem can be treated as a [[Non-cooperative game|non-cooperative game]], or can include the point of view of cooperative game theory (see [[Cooperative game|Cooperative game]]) as well as the application of related optimality principles.
  
 
====References====
 
====References====

Latest revision as of 14:01, 14 September 2014

A mathematical model for making an optimal decision with respect to several criteria simultaneously. These criteria may reflect evaluations of various qualities of the objects (or processes) about which a decision is to be made, or may be evaluations of some single characteristic from various points of view. The theory of multi-criterion problems belongs to operations research.

Formally a multi-criterion problem is given by a set $X$ of "feasible decisions" and a set of objective functions $f_1,\dots,f_n$ on $X$, taking real values. The essence of a multi-criterion problem is finding an optimal decision, that is, an $x\in X$ which, in some sense, maximizes the values of all the functions $f_i$, $i=1,\dots,n$. The existence of a decision maximizing all objective functions is a rare exception. Therefore in the theory of multi-criterion problems the notion of optimality has various and, moreover, non-trivial interpretations. The content of the theory of multi-criterion problems is the development of such concepts of optimality, the proof of their realizability (that is, the existence of decisions which are optimal in the corresponding sense), and the search for these realizations (that is, the actual solution of the problem).

The most direct approach to solving a multi-criterion problem consists in reducing it to an ordinary ("single-criterion") problem of mathematical programming by replacing the system of objective functions $f_1,\dots,f_n$ by an aggregate function $F(f_1,\dots,f_n)$. In this role there may appear weighted sums $\sum_{i=1}^n\lambda_if_i$, $\lambda_i\geq0$, weighted maxima $\max_i\lambda_if_i$, and other combinations of the initial objective functions. This approach is conceptually and technically convenient. Its fundamental shortcoming is the difficulty in satisfying the need for a meaningful comparability of the values of the various objective functions and also the uncertainty (and not infrequent arbitrariness) in the choice of $F$ and, in particular, in the weights $\lambda_i$. To establish these one is often advised to resort to expert evaluations.

A particular case of this approach is the selection of a "main criterion", that is, all weights except a single $\lambda_{i_0}$ are put equal to zero. Then the multi-criterion problem becomes an ordinary problem of mathematical programming, and the set of optimal solutions of it can be considered as the set of feasible solutions for a new multi-criterion problem with objective functions $f_i$, $i\neq i_0$.

As the solutions of a multi-criterion problem one can consider solutions which are Pareto optimal, that is, solutions which do not allow an improvement with respect to any one criterion, except at the expense of detoriation in another criterion (in other words, an $x\in X$ such that for any $y\in X$, if $f_i(x)<f_i(y)$ then $f_j(y)<f_j(x)$ for some $j$). The shortcoming of this approach is the plurality of Pareto-optimal solutions. This defect was overcome, following a suggestion of J. Nash, by the method of "bargaining schemes", which essentially limits the number of selected solutions among the Pareto-optimal solutions. It consists in establishing, on the basis of informal considerations, certain minimal feasible values $f_i^0$ and subsequently finding a feasible $x$ maximizing $\prod_{i=1}^n(f_i(x)-f_i^0)$ (see also Arbitration scheme).

A multi-criterion problem can also be considered as a game (see Games, theory of) and its solution can be treated on the basis of various game-theoretic methods. For example, if a feasible solution $x$ is chosen with the aim of maximizing one of the objective functions $f_1,\dots,f_n$, and if it is unknown which one has to be maximized, then it is possible to use a weighted sum of these functions, taking as weights the components of a mixed strategy of "nature". A multi-criterion problem can be treated as a non-cooperative game, or can include the point of view of cooperative game theory (see Cooperative game) as well as the application of related optimality principles.

References

[1] R.D. Luce, H. Raiffa, "Games and decisions. Introduction and critical survey" , Wiley (1957)


Comments

The method described for selecting a Pareto-optimal solution is also known as Nash' solution of the bargaining problem.

Sometimes the terms vector-valued optimization or multiple objective decision problem are used for multi-criterion problem.

References

[a1] B.D. Graven, "Vector valued optimization" S. Schaible (ed.) W.T. Ziemba (ed.) , Generalized Concavity in Optimization and Economics , Acad. Press (1981) pp. 661–688
[a2] V. Chankong, Y.Y. Haimes, "Multiobjective decision making: theory and methodology" , North-Holland (1983)
[a3] G. Leitmann, "Cooperative and non-cooperative many players differential games" , Internat. Center Mech. Sci. , 190 , Springer (1974)
How to Cite This Entry:
Multi-criterion problem. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Multi-criterion_problem&oldid=33287
This article was adapted from an original article by N.N. Vorob'ev (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article