Multi-objective optimization

In the real world one often encounters optimization problems with more than one (usually conflicting) objective function, such as the cost and the performance index of an industrial product. Such optimization problems are called multi-objective, or vector, optimization problems.

A multi-objective optimization problem with $ p $ objective functions can be formulated as follows:

$$ \textrm{ (P) } \left \{ \begin{array}{l} {\textrm{ minimize } \ f ( x ) = ( f _ {1} ( x ) \dots f _ {p} ( x ) ) ^ {T} , } \\ {\textrm{ subject } roman ^ { \ } x \in X, } \end{array} \right . $$

where $ X $ is a constraint set in a certain space. One may consider a more general infinite-dimensional objective function. If the set $ X $ is specified by inequality (and/or equality) constraints in a finite-dimensional Euclidean space, i.e.,

$$ X = \left \{ {x \in \mathbf R ^ {n} } : {g _ {j} ( x ) \leq 0, j = 1 \dots m } \right \} , $$

then the problem is called the multi-objective programming problem.

Since the objective space $ \mathbf R ^ {p} $ is only partially ordered, first of all one has to make clear the concept of a solution of the problem (P).

1) A point $ x ^ {*} \in X $ is a completely optimal solution of (P) if

$$ f _ {i} ( x ^ {*} ) \leq f _ {i} ( x ) , \forall i = 1 \dots p, \forall x \in X. $$

Unfortunately, a completely optimal solution rarely exists.

2) A point $ x ^ {*} \in X $ is a Pareto optimal (or efficient) solution of (P) if there exists no $ x \in X $ such that

$$ f _ {i} ( x ) \leq f _ {i} ( x ^ {*} ) , \forall i = 1 \dots p, $$

$$ f _ {i} ( x ) < f _ {i} ( x ^ {*} ) , \exists i \in \{ 1 \dots p \} . $$

Slightly strengthened and weakened solution concepts of Pareto optimality are called proper Pareto optimality and weak Pareto optimality, respectively. By introducing a more general preference structure (preference ordering) in the objective space, one may obtain a more general solution concept.

Several mathematical notions from ordinary scalar optimization, such as optimality conditions, stability, sensitivity, and duality, have been extended to multi-objective optimization. The details can be found in [a1], [a2], [a3].

For the multi-objective programming problem the following extended Kuhn–Tucker condition has been obtained: If $ x ^ {*} $ is a Pareto optimal solution and the Kuhn–Tucker constraint qualification is satisfied at $ x ^ {*} $, then there exist non-negative vectors $ \mu ^ {*} \neq 0 \in \mathbf R ^ {p} $ and $ \lambda ^ {*} \in \mathbf R ^ {m} $ such that

$$ \sum _ {i = 1 } ^ { p } \mu _ {i} ^ {*} \nabla f _ {i} ( x ^ {*} ) + \sum _ {j = 1 } ^ { m } \lambda _ {j} ^ {*} \nabla g _ {j} ( x ^ {*} ) = 0, $$

$$ \lambda _ {j} ^ {*} g _ {j} ( x ^ {*} ) = 0, j = 1 \dots m. $$

In order to consider stability and sensitivity, the following parametric multi-objective optimization problem is considered:

$$ \textrm{ (P } {} _ {u} \textrm{ ) } \left \{ \begin{array}{l} {\textrm{ minimize } \ f ( x,u ) , } \\ {\textrm{ subject } roman ^ { \ } x \in X ( u ) , } \end{array} \right . $$

where $ u $ is a parameter vector. Let $ W ( u ) $ be the set of all Pareto optimal values in the objective space to ( $ \textrm{ P } _ {u} $). The set-valued mapping $ W $ is considered to be a generalization of the marginal (optimal-value) function in ordinary scalar optimization. The behaviour of $ W $ has been analyzed both qualitatively and quantitatively.

Several types of duality, such as Lagrange duality, Wolfe duality, and conjugate duality, are investigated in optimization. Each of these duality theories has been extended to multi-objective optimization. For details see [a1], [a2], [a3].

In order to obtain a Pareto optimal solution of (P) one usually solves a scalarized optimization problem. Typical examples of the scalarization methods are as follows.

1) The weighted sum minimization method:

$$ \left \{ \begin{array}{l} {\textrm{ minimize } \ \sum _ {i = 1 } ^ { p } w _ {i} f _ {i} ( x ) , } \\ {\textrm{ subject } roman ^ { \ } x \in X, } \end{array} \right . $$

where $ w _ {i} $ denotes the relative importance of each $ f _ {i} $;

2) The $ \epsilon $- constraint method:

$$ \left \{ \begin{array}{l} {\textrm{ minimize } \ f _ {p} ( x ) , } \\ {\textrm{ subject } roman ^ { \ } f _ {i} ( x ) \leq \epsilon _ {i} , i = 1 \dots p - 1, x \in X, } \end{array} \right . $$

where $ \epsilon _ {i} $ denotes the admissible worst level of $ f _ {i} $;

3) The norm minimization method:

$$ \left \{ \begin{array}{l} {\textrm{ minimize } \ \left \| {f ( x ) - y ^ {*} } \right \| , } \\ {\textrm{ subject } roman ^ { \ } x \in X, } \end{array} \right . $$

where $ y ^ {*} $ is the ideal (or reference) point in $ \mathbf R ^ {p} $. One often uses the (augmented) Chebyshev norm.

From the viewpoint of decision making, one Pareto optimal solution should be chosen as a final decision according to the preference structure of the decision maker. Roughly speaking, to this end there are three approaches:

1) generate all or sufficiently many Pareto optimal solutions and leave it to the decision maker to choose the preferred solution;

2) find the value (utility) function which represents the preference structure of the decision maker and maximize this scalar function (this approach is usually called multi-attribute utility theory);

3) find a Pareto optimal solution and extract local (partial) information about the preference structure from the decision maker. Based on this information, compute another Pareto optimal solution. This process is repeated until the decision maker is satisfied by the current solution. This approach is called an interactive method. Several interesting methods have been proposed [a4].

References

[a1]	Y. Sawaragi, H. Nakayama, T. Tanino, "Theory of multiobjective optimization" , Acad. Press (1985)
[a2]	J. Jahn, "Mathematical vector optimization in partially ordered linear spaces" , Peter Lang (1986)
[a3]	D.T. Luc, "Theory of vector optimization" , Springer (1989)
[a4]	R. Steuer, "Multiple criteria optimization: theory, computation and application" , Wiley (1986)