Multi-objective optimization

The multi-objective optimization is not a standard problem in the engineering, but is quite common in economics ([14]). While with the mono-dimensional problem the concept of optimum as a minimum is quite clear and defined (the idea of greater or lesser is intuitive with the real number), with multi-objective (also multi-criteria) the concept of minimum is less intuitive. So we must define some relation of order among the points in a multi-dimensional space.

Notation 5.18   Given $\mathbf{x},\mathbf{y}\in \mathbb{R}^n$, define

$$\mathbf{x} = \mathbf{y} \qquad x_k=y_k \, \forall \mathstrut k=1, 2, \dotsc, n$$

$$\mathbf{x} \leqq \mathbf{y} \qquad x_k\leq y_k \,\forall \mathstrut k=1, 2, \dotsc, n$$

$$\mathbf{x} \leq \mathbf{y} \qquad \mathbf{x} \leqq \mathbf{y} \; \; \mathbf{x}\ne \mathbf{y}\; ( \, \exists k\colon x_k < y_k)$$

$$\mathbf{x} < \mathbf{y} \qquad x_k < y_k\, \forall \mathstrut k=1, 2, \dotsc, n$$

Notation 5.19   In the following section, the function $f$ is defined as: $f\colon X \rightarrow Y,\, X\subseteq \mathbb{R}^p, Y\subseteq \mathbb{R}^n$. $X$ is called the decisions space, while Y is called the criteria space.

Given two outcome $\mathbf{y}^1, \mathbf{y}^2$ of the cost functions, $\mathbf{y}^1=f(\mathbf{x}^1)$ and $\mathbf{y}^2=f(\mathbf{x}^2)$, we must define which is better and we indicate that $\mathbf{y}^1$ is better than $\mathbf{y}^2$ with $\mathbf{y}^1\prec\mathbf{y}^2$, that $\mathbf{y}^1$ is worse than $\mathbf{y}^2$ with $\mathbf{y}^1\succ\mathbf{y}^2$, and, finally, that $\mathbf{y}^1$ is indifferent with respect to $\mathbf{y}^2$ with $\mathbf{y}^1\sim\mathbf{y}^2$.

In the optimization theory a great importance has the definition of Pareto point or Pareto preference:

Definition 5.20 (Pareto preference)   Given $\mathbf{y}^1, \mathbf{y}^2\in Y$, the Pareto preference is defined by

$$\mathbf{y}^1\prec\mathbf{y}^2 \qquad \mathbf{y}^1 \leq \mathbf{y}^2.$$

A Pareto preference is intuitively guided by the relation lesser is better.

Definition 5.21 (Non-Dominated and Dominated set)   If $\mathbf{y}^1\prec\mathbf{y}^2$ is a binary preference defined on $Y$, the dominated and the non-dominated set with respect to $\{\prec\}$ are defined as:

$$N(\{\prec\},Y) =\{\mathbf{y}^0\in Y\;\vert\;\nexists\mathbf{y}\in Y\colon \mathbf{y}\prec\mathbf{y}^0\}$$

$$D(\{\prec\},Y) =\{\mathbf{y}^0\in Y\;\vert\;\exists\mathbf{y}\in Y\colon \mathbf{y}\prec\mathbf{y}^0\}$$

If $\mathbf{y}^0\in N(\{\prec\},Y)$, $\mathbf{y}^0$ is a N-point. Similarly, if $\mathbf{y}^0\in D(\{\prec\},Y)$, $\mathbf{y}^0$ is a D-point.

Definition 5.22 (Pareto optimum)   $\mathbf{y}\in Y$ is a Pareto optimum iff it is a N-point with respect to Pareto preference.

We will give now two theorems that are fundamental for the solution of the multi-objective optimization problem; first we introduce the definition of convex cone in $\mathbb{R}^n$:

Notation 5.23 (convex cone)  

$$\Lambda^> = \{ \mathbf{d}\in\mathbb{R}^n\,\vert\, \mathbf{d}>0 \}$$

$$\Lambda^\geq = \{ \mathbf{d}\in\mathbb{R}^n\,\vert\, \mathbf{d}\geq 0 \}$$

$$\Lambda^\geqq = \{ \mathbf{d}\in\mathbb{R}^n\,\vert\, \mathbf{d}\geqq 0 \}$$

Theorem 5.24  

i)

if $\mathbf{y}^0\in Y$ minimizes $\boldsymbol{\lambda}\cdot \mathbf{y}$ over $Y$ for some $\boldsymbol{\lambda}\in\Lambda^>$, then $\mathbf{y}^0$ is a N-point;

ii)

if $\mathbf{y}^0\in Y$ uniquely minimizes $\boldsymbol{\lambda}\cdot \mathbf{y}$ over $Y$ for some $\boldsymbol{\lambda}\in\Lambda^\geq$, then $\mathbf{y}^0$ is a N-point.

Corollary 5.24.1   If $Y$ is $\Lambda^{\geqq}$-convex, i.e. $Y + \Lambda^\geqq$ is a convex set, then a necessary condition for $\mathbf{y}^0\in Y$ to be an N-point is to minimize $\boldsymbol{\lambda}\cdot \mathbf{y}$ over $Y$ for some $\boldsymbol{\lambda}\in\Lambda^>$.

This very important theorem (and its corollary) states that if $\mathbf{y}^0$ minimizes a linear weighted function $\boldsymbol{\lambda}\cdot \mathbf{y}$ (for some $\boldsymbol{\lambda}$), then $\mathbf{y}^0$ is a Pareto optimum. This reduces the problem from a multi-objective one to a mono-objective one, i.e. is sufficient minimizes a linear weighted function of the cost functions.
Note that:

$$\dfrac{\partial y_i}{\partial y_j} = -\dfrac{\lambda_j}{\lambda_i}$$

so the ratio $\tfrac{\lambda_j}{\lambda_i}$ is the trade-off exchanging an unit-gain in the variable $y_j$ with an unit-gain for the variable $y_i$. Finally, note that the theorem is valid for any shape of $Y$.

Theorem 5.25   A necessary and sufficient condition for $\mathbf{y}^0\in Y$ to be an N-point is that $\forall \mathstrut i = 1, 2, \dotsc, n$ there are $n-1$ constants $\vartheta(i) = \{ h_j\, \vert j \neq i,\, \mathstrut j=1, 2, \dotsc, n\}$ so that $\mathbf{y}^0$ uniquely minimizes $y_i$ over $Y(\vartheta(i))=\{\mathbf{y}\in Y \, \vert\, y_j \leq h_j, \, j \neq i, \, \mathstrut j=1, 2, \dotsc, n\}$.

Each constant $h_j$ can be seen as a constraint: so this theorem claims that a necessary and sufficient condition to be a Pareto optimum is to minimize one criterion (the $i$-th objective function), while satisfying the constraints for the remaining criteria. This is equal to say that the multiple criteria problem can be reduced to a single criterion problem (minimize the $y_i$ functions with multiple constraints (ensure that $y_j \leq h_j,\, i\neq j$).