Multi-objective Optimization: Pareto Optimal Solutions, Properties

Article Outline

Keywords

See also

References

The multi-objective optimization ( multiple criteria decision making ) problem is the problem of choosing a most preferred solution when two or more incommensurate, conflicting objective functions (criteria) are to be simultaneously maximized. A central difficulty in such problems is that, unlike in single objective maximization problems, there is no obvious or simple way to define the concept of a most preferred solution. Nevertheless, because the applications of multi-objective optimization abound, there has been great interest during the past 30 years in seeking appropriate definitions for a most preferred solution and in developing algorithms that aid the decision maker (DM) to find such a solution. These applications are in a wide variety of areas, including, for example, production planning, finance, environmental conservation, academic planning, nutrition planning, advertising, facility location, auditing, blending techniques, transportation planning, and scheduling, to name just a few.

There are several alternate mathematical formulations of the multi-objective optimization problem [13]. For purposes of modeling the deterministic multiple objective optimization problems found in management science/operations research, however, the most popular form of the problem is denoted

$$ \mathrm{(V)} \quad \begin{cases} \operatorname{VMAX} & [ f_{1}(x) ,\ldots, f_{p}(x) ] \\ \text{s.t.} & x\in X. \end{cases} $$

Here, p ≥ 2, X is a nonempty subset of R ⁿ, each f _j , j = 1, …, p, is a real-valued function defined on X or on a suitable set containing X, and VMAX indicates that we are to, in some as-yet unspecified sense, ‘vector maximize’ the vector

$$ f(x) = [ f_{1}(x) ,\ldots, f_{p}(x) ] $$

of objective functions ( criteria ) over X. The set X is called the set of alternatives or the decision set .

Of all of the solution concepts proposed for helping the DM find a most preferred solution for problem (V), the concept of efficiency has proven to be of overriding importance. An efficient ( Pareto optimal , noninferior , nondominated ) solution for problem (V) is a point $\overline{x}\in X$ such that there exists no other point x ∊ X that satisfies $f(x) \ge f(\overline{x})$ and $f(x) \neq f(\overline{x})$. Letting X _E denote the set of all efficient points for problem (V), we see that whenever $\overline{x}\in X_{E}$, there is no other feasible point that does at least as well as $\overline{x}$ in all of the criteria for problem (V) and strictly better in at least one criterion. A point $\overline{x}\in X$ is called dominated when for some other point x ∊ X, $f(x) \ge f(\overline{x})$ and, for at least one j = 1, …, p, $f_{j}(x) > f_{j}(\overline{x})$. Thus, we have the alternate definition for efficiency that states that a point $\overline{x}$ is an efficient solution for problem (V) when $\overline{x}\in X$ and there are no other points in X that dominate $\overline{x}$.

One of the reasons for the fundamental importance of the efficiency concept is that it has proven to be highly useful in a variety of algorithms for problem (V). Among these algorithms are the satisficing methods, compromise programming , most interactive methods , and the vector maximization method . The latter method, for instance, seeks to generate either all of X _E or key parts of X _E . The generated set is shown to the DM. Then, based upon the DM's internal utility (or value) function, the DM chooses from the generated set a most preferred solution. For details concerning these methods for problem (V), see [7,10,12,13,14].

In some cases, it is useful to consider a slightly relaxed concept of efficiency called weak efficiency. A point $\overline{x}\in X$ is called a  weakly efficient ( weakly Pareto optimal , weakly noninferior , weakly nondominated ) solution for problem (V) when there is no other point x ∊ X such that $f(x) > f(\overline{x})$. Let X _WE denote the set of all weakly efficient points for problem (V). Notice that X _E is a subset of X _WE . In some cases of problem (V), such as when the objective functions are ratios of linear functions, it is easier to analyze and generate points in X _WE than points in X _E .

Let U represent a utility function defined on the space R ^p of the objective functions of problem (V). Suppose that U is coordinatewise increasing , i. e., that whenever $\overline{z}, z\in \mathbb{R}^{p}$ satisfy $\overline{z}\ge z$ and $\overline{z}_{j}> z_{j}$ for some j = 1, …, p, then $U(\overline{z}) > U(z)$. Suppose that x ^∗ is an optimal solution to the single objective problem

$$ \mathrm{(S)} \quad \max_{x\in X} U[ f_{1}(x) ,\ldots, f_{p}(x)]. $$

Then x ^∗ must be an efficient solution for problem (V) (cf. [11]).

The property in the previous paragraph explains to a great extent why the concept of efficiency is of such fundamental value. The assumption that the utility function U in the above paragraph is coordinatewise increasing implies that in problem (S), for each j = 1, …, p, more of f _j is preferred to less of f _j . Thus, if we imagine that U is the utility (or value) function of the DM over the objective function space of problem (V), then the previous paragraph implies that whenever the DM prefers more to less in each objective function of problem (V), any point that maximizes the DM's utility for f(x) over X must be an efficient point in problem (V). In short, as long as we know that the DM prefers more to less, we can confine the search for a most preferred solution to X _E . Although the utility function of the DM is generally not actually available, in virtually all applications the DM does, indeed, prefer more to less in each objective function of problem (V). Thus, in essentially all cases, any most preferred solution for problem (V) will be found in X _E .

Because of the central importance of efficiency, a great deal of effort has been made by researchers to delineate the properties of the efficient points and of the efficient set for problem (V). In what follows, we shall briefly highlight some of the most important of these properties.

Consider the single-objective optimization problem

$$ \mathrm{(W)} \quad \begin{cases} \displaystyle \max & \displaystyle \sum_{j = 1}^{p} w_{j}f_{j}(x), \\ \text{s.t.} & x\in X. \end{cases} $$

Here, w _j , j = 1, …, p, are parameters, which are often thought of as weights associated with the objective functions f _j , j = 1, …, p, of problem (V). A number of so-called scalarization properties for efficient points of problem (V) are expressed in terms of problem (W). To present some of these, another efficiency concept, called proper efficiency, is needed. A point x ° is said to be a  properly efficient solution for problem (V) when x ° ∊ X _E and, for some sufficiently large number M, whenever f _i (x) > f _i (x °) for some i = 1, …, p and some x ∊ X, there exists some j = 1, …, p such that f _j (x) < f _j (x °) and

$$ \frac{f_{i}(x) - f_{i}(x^{\circ})}{f_{j}(x^{\circ}) - f_{j}(x)} \le M. $$

In words, for each properly efficient solution of problem (V), for each criterion, the possible marginal gains in that criterion relative to the losses in the criteria that have losses cannot all be unbounded from above. Let X _PRE denote the set of properly efficient solutions for problem (V), and let w ^⊺ = (w ₁, …, w _p ). Then some key scalarization properties are as follows.

• 1) If $\overline{x}$ is the unique optimal solution to problem (W) for some w ≥ 0, w ≠ 0, then $\overline{x}\in X_{E}$.

• 2) If $\overline{x}$ is an optimal solution to problem (W) for some w ≥ 0, w ≠ 0, then $\overline{x}\in X_{WE}$.

• 3) Assume that for each j = 1, …, p, f _j is a concave function on the convex set X. Then $\overline{x}\in X_{PRE}$ if and only if $\overline{x}$ is an optimal solution to problem (W) for some w > 0.

• 4) Under the assumptions in property 3), $\overline{x}\in X_{WE}$ if and only if $\overline{x}$ is an optimal solution to problem (W) for some w ≥ 0, w ≠ 0.

• 5) Under the assumptions of property 3), if $\overline{x}\in X_{E}$ but $\overline{x}\notin X_{PRE}$, then there exists a w ≥ 0, w ≠ 0 with w _j = 0 for at least one j = 1, …, p such that $\overline{x}$ is an optimal solution to problem (W).

• 6) If each f _j , j = 1, …, p, is a linear function and X is a polyhedron, X _PRE = X _E .

The scalarization properties can be used for various purposes, including the generation of points in X _E , X _WE and X _PRE . For instance, when each f _j , j = 1, …, p, is a linear function and X is a polyhedron, from properties 3) and 6), points in X _E , including, at least potentially, all of X _E , can be generated by solving problem (W) as the parameter w > 0 is varied. Under the assumptions of property 3), the same process will generate points in X _PRE , including, at least potentially, all of X _PRE . However, from properties 3)–5), it is apparent that no such simple process for generating X _E exists, even under the assumptions of property 3). This is another motivation for the proper efficiency concept.

Another important issue in efficiency concerns testing. One may want to test a given point for efficiency in problem (V), and one may want to test whether X _E and X _PRE are empty or not. We will present several of the properties of efficiency that provide some of the theory for these tests. These properties all utilize the single-objective problem

$$ \mathrm{(T)} \quad \begin{cases} \displaystyle \max & \displaystyle \sum_{j = 1}^{p} f_{j}(x), \\ \text{s.t.} & f_{j}(x) \ge f_{j}(x^{\circ}), \\ & j = 1,\ldots, p, \\ & x\in X. \end{cases} $$

Here, x ° is an arbitrary element of R ⁿ. The properties are as follows.

• 7) The point x ° ∊ R ⁿ belongs to X _E if and only if x ° is an optimal solution to problem (T).

• 8) Suppose that x ° ∊ X in problem (T), and that problem (T) has no finite maximum value. Then X _PRE = ∅ [1].

• 9) Suppose that the assumptions of property 3) hold, that x ° ∊ X in problem (T), and that problem (T) has no finite maximum value. Then, if the set

  $$ Z = \left\{z\in \mathbb{R}^{p}\colon\ z\le f(x) \ \text{for some}\ x\in X\right\} $$

  is closed, X _E = ∅.

• 10) Assume that each f _j , j = 1, …, p, is a linear function and that X is a polyhedron. Suppose that x ° ∊ X in problem (T), and that problem (T) has no finite maximum value. Then X _E = ∅.

• 11) Any optimal solution to problem (T) belongs to X _E .

Notice from these properties that solving problem (T) is a useful tool for both testing a point for efficiency and for investigating the issues of whether X _E and X _PRE are empty or not. In the case of testing a point x ° for efficiency, property 7) shows that problem (T) can be used to obtain a definitive answer, i. e., using property 7), we will always detect whether or not x ° ∊ X _E . Furthermore, when property 7) shows that x ° ∉ X _E , but problem (T) has an optimal solution x ^∗, then, by property 11), x ^∗ ∊ X _E . Notice also that in this case, x ^∗ dominates x °.

In the case of investigating whether or not X _E and X _PRE are empty, however, definitive answers cannot usually be obtained by using these properties. This is because none of the properties addresses the issue of whether or not X _E and X _PRE are empty when, instead of having an optimal solution or having no finite maximum value, problem (T) has a finite but unattained maximum value. The one case where the properties can be used to definitely detect whether or not X _E and X _PRE are empty is the case where the objective functions of problem (V) are all linear and X is a polyhedron. In that case, problem (T) cannot have a finite but unattained maximum value. Therefore, properties 7), 10) and 11) can be used to detect whether or not X _E = X _PRE is empty in such cases.

One of the main challenges computationally to generating all or parts of X _E or X _WE for the DM to consider is that both X _E and X _WE are, except for trivial cases, nonconvex sets . Although some researchers have suggested ways to mitigate this problem [5], it generally remains a major stumbling block for algorithm development. In many common cases, however, X _E or X _WE possesses a useful, although less valuable, property than convexity upon which algorithms can be based. This property is called connectedness . In particular, a set Z ⊆ R ⁿ is connected if, whenever A and B are nonempty subsets of R ⁿ such that A has no points in common with the closure of B, and B has no points in common with the closure of A, Z ≠ A ∪ B. Some common cases of problem (V) where X _E or X _WE is connected are given in the following properties.

• 12) Assume that for each j = 1, …, p, f _j is a quasiconcave function on X, and that X is a compact convex set. Then X _WE is connected.

• 13) Assume that for each j = 1, …, p, f _j is a concave function on R ⁿ, and that X is a compact convex set. Then X _E is connected.

Recall that a concave function on a convex set is also quasiconcave on the set. Therefore, from property 12), it follows that X _WE is connected when each objective function in problem (V) is a concave function on X, and X is a compact, convex set.

There are a variety of other properties of efficient points and of the efficient set for problem (V). These include, for instance, density properties, stability-related properties, the domination property [2,3,8], and complete efficiency-related properties [4,6]. For further reading, see [5,7,9,10,12,13,14].

See also

Bi-objective Assignment Problem

Decision Support Systems with Multiple Criteria

Estimating Data for Multicriteria Decision Making Problems: Optimization Techniques

Financial Applications of Multicriteria Analysis

Fuzzy Multi-objective Linear Programming

Multicriteria Sorting Methods

Multi-objective Combinatorial Optimization

Multi-objective Integer Linear Programming

Multi-objective Optimization and Decision Support Systems

Multi-objective Optimization: Interaction of Design and Control

Multi-objective Optimization: Interactive Methods for Preference Value Functions

Multi-objective Optimization: Lagrange Duality

Multiple Objective Programming Support

Outranking Methods

Portfolio Selection and Multicriteria Analysis

Preference Disaggregation

Preference Disaggregation Approach: Basic Features, Examples From Financial Decision Making

Preference Modeling