.. _multi_objective_optimization:

Multi-objective optimization
==========================================================================================


:Driver: :ref:`ActiveLearning`


:Download script: :download:`multi_objective_optimization.py`


Many optimization task do not consist of only a single objective :math:`f(\mathbf{x})` to be minimized in some domain :math:`\mathbf{x}\in \mathcal{X}\subset \mathbb{R}^d`, but rather in a set of objectives :math:`\mathbf{f}(\mathbf{x}) = [f_1(\mathbf{x}), f_2(\mathbf{x}),\dots,f_k(\mathbf{x})]^{\rm T}` to be minimized together.

A solution :math:`\mathbf{a} = \mathbf{f}(\mathbf{x}_1)` is said to *dominate* another solution :math:`\mathbf{b} = \mathbf{f}(\mathbf{x}_2)` if :math:`a_i \le b_i` for all :math:`i \in [1, \dots, k]`
and there exists at least on entry :math:`j \in [1, \dots, k]` such that :math:`a_j < b_j`.

A solution is called Pareto optimal if it is not dominated by any other solution. The set of Pareto optimal solutions is called the *Pareto front*. The aim of a multi-objective optimization is to find the Pareto front for the set of objectives :math:`\mathbf{f}(\mathbf{x})`.

We consider an analytic multi-objective optimization problem with :math:`k=2` objectives:

.. math::

   \text{Minimize } f_1(x_1,x_2) &=& x_1
   
   \text{Minimize } f_2(x_1,x_2) &=& \frac{g(x_2)}{x_1}

It can be shown, that the problem has Pareto-optimal solutions :math:`(x_1, x_2^*)`, where :math:`x_2^*` is the globally minimum solution of :math:`g(x_2)` and :math:`x_1` can take any value [DEB1999]_.

As an example, we consider the multi-modal function

.. math::

   g(x_2) = 20 + (x_2^2 - 10\cos(2\pi x_2))

with local minima approximately located at integer values of :math:`x_2` and the global minimum at :math:`g(x_2^* = 0)=10`. That is, the Pareto front is defined as :math:`f_2 = \frac{10}{f_1}`.

.. [DEB1999] Deb, K., "Multi-objective genetic algorithms: Problem difficulties and construction of test problems". *Evolutionary computation*, 7(3), pp.205-230 (1999)



.. literalinclude:: ./multi_objective_optimization.py
   :language: python
   :linenos:


 

.. figure:: images/multi_objective_optimization/multi_objective_minimization.svg
   :alt: Multi-objective minimization

   Result of the multi-objective minimization in the :math:`(f_1, f_2)`-plane.

   The blue dots show all observations, whereas the orange dots show
   nondominated solution, i.e. an estimate of the Pareto front. The dashed line
   shows the true analytic Pareto front within the domain of :math:`(x_1, x_2)`.

   The progress of the study is shown in terms of the nondominated hypervolume
   (blue shaded area) that is defined by the nondominating observations as
   well as a lower and upper reference point (red and blue cross).