Pareto set

From DDWiki

Revision as of 16:24, 25 January 2007 by IanTseng (Talk | contribs)

(diff) ←Older revision | Current revision (diff) | Newer revision→ (diff)

In Multi-Objective Optimization, the Pareto set, or Pareto Frontier, is a subset of the set of feasible points of solutions that contains all points that have at least one objective optimized while holding all other objectives constant. These points are called Pareto optimal points.

The term is named after Vilfredo Pareto, an Italian economist.

Definition

Given a multiobjective optimization problem:

minimize $\mathbf f(\mathbf x)=\{f_{1}(\mathbf x), f_{2}(\mathbf x), f_{3}(\mathbf x),..., f_{n}(\mathbf x)\}$
subject to $h(\mathbf x)=0, g(\mathbf x)\leq 0$

The feasible domain $\mathcal A$ is defined as:
$\mathcal A=\{\mathbf x\colon h(\mathbf x)=0, g(\mathbf x)\leq 0\}$

A point $\mathbf x_{0}$ in the feasible domain $\mathcal A$ is Pareto optimal if and only if there is not another $\mathbf x$ in $\mathcal A$ such that $f_{i}(\mathbf x)\leq f_{i}(\mathbf x_{0})$ for all $i = {1,2,3,..., n}$ and $f_{i}(\mathbf x)<f_{i}(\mathbf x_{0})$ for at least one $i$ .

Use in Optimization

In multi-objective optimization tradeoffs commonly have to be made. These tradeoffs occur when improvement of one objective comes at the expense of another objective. For instance, in the optimization of a bar for minimum weight and maximum strength, reducing the diameter of the bar would see an improvement in weight but at a reduction in strength. A Pareto point in this problem is one where no feasible points exist that yield a lower weight or higher strength while keeping the other objective fixed. The set of all Pareto points in this system form the Pareto set or Pareto Frontier. To an engineer or designer, the optimal design is likely to be one of the points in this set since the Pareto set contains all potentially optimal solutions or designs given all possible tradeoff situations. Reducing the design space to only the Pareto set allows the engineer to focus on important tradeoffs without considering the full range of all possible parameters. Also, it is can be helpful to optimize along the line defined by the Pareto Frontier to achieve the optimal balance between tradeoffs.

The first figure shows a hypothetical plot of feasible points. The second figure shows the Pareto set of of the feasible points in the first figure.

Plots taken from http://www-sop.inria.fr/sinus/personnel/Nathalie.Marco/resmulti-crit.html.