9.1.1.2 Multiobjective optimization

Suppose that there is a collection of cost functions, each of which evaluates an action. This leads to a generalization of Formulation 9.1 to multiobjective optimization.

Formulation 9..2 (Multiobjective Optimization)  

1. A nonempty set $U$ called the action space. Each $u \in U$ is referred to as an action.
2. A vector-valued cost function of the form $L: U \rightarrow {\mathbb{R}}^d$ for some integer $d$. If desired, $\infty$ may also be allowed for any of the cost components.

A version of this problem was considered in Section 7.7.2, which involved the optimal coordination of multiple robots. Two actions, $u$ and $u'$, are called equivalent if $L(u) = L(u')$. An action $u$ is said to dominate an action $u'$ if they are not equivalent and $L_i(u) \leq L_i(u')$ for all $i$ such that $1 \leq i \leq d$. This defines a partial ordering, $\leq$, on the set of actions. Note that many actions may be incomparable. An action is called Pareto optimal if it is not dominated by any others. This means that it is minimal with respect to the partial ordering.

Example 9..1 (Simple Example of Pareto Optimality)   Suppose that $U = \{1,2,3,4,5\}$ and $d = 2$. The costs are assigned as $L(1) = (4,0)$, $L(2) = (3,3)$, $L(3) = (2,2)$, $L(4) = (5,7)$, and $L(5) = (9,0)$. The actions $2$, $4$, and $5$ can be eliminated because they are dominated by other actions. For example, $(3,3)$ is dominated by $(2,2)$; hence, action $u = 3$ is preferable to $u=2$. The remaining two actions, $u=1$ and $u = 3$, are Pareto optimal. $\blacksquare$

Based on this simple example, the notion of Pareto optimality seems mostly aimed at discarding dominated actions. Although there may be multiple Pareto-optimal solutions, it at least narrows down $U$ to a collection of the best alternatives.

Example 9..2 (Pennsylvania Turnpike)   Imagine driving across the state of Pennsylvania and being confronted with the Pennsylvania Turnpike, which is a toll highway that once posted threatening signs about speed limits and the according fines for speeding. Let $U = \{50,51,\ldots,100\}$ represent possible integer speeds, expressed in miles per hour (mph). A posted sign indicates that the speeding fines are 1) $50 for being caught driving between 56 and 65 mph, 2) $100 for being caught between 66 and 75, 3) $200 between 76 and 85, and 4) $500 between 86 and 100. Beyond 100 mph, it is assumed that the penalty includes jail time, which is so severe that it will not be considered.

The two criteria for a driver are 1) the time to cross the state, and 2) the amount of money spent on tickets. It is assumed that you will be caught violating the speed limit. The goal is to minimize both. What are the resulting Pareto-optimal driving speeds? Compare driving 56 mph to driving 57 mph. Both cost the same amount of money, but driving 57 mph takes less time. Therefore, 57 mph dominates 56 mph. In fact, 65 mph dominates all speeds down to 56 mph because the cost is the same, and it reduces the time the most. Based on this argument, the Pareto-optimal driving speeds are 55, 65, 75, 85, and 100. It is up to the individual drivers to decide on the particular best action for them; however, it is clear that no speeds outside of the Pareto-optimal set are sensible. $\blacksquare$

The following example illustrates the main frustration with Pareto optimality. Removing nondominated solutions may not be useful enough. In come cases, there may even be a continuum of Pareto-optimal solutions. Therefore, the Pareto-optimal concept is not always useful. Its value depends on the particular application.

Example 9..3 (A Continuum of Pareto-Optimal Solutions)   Let $U = [0,1]$ and $d = 2$. Let $L(u) = (u,1-u)$. In this case, every element of $U$ is Pareto optimal. This can be seen by noting that a slight reduction in one criterion causes an increase in the other. Thus, any two actions are incomparable. $\blacksquare$