Multi-objective optimization

Multi-objective optimization (also multi-objective programming or multi-criteria optimization) is a field of mathematical optimization that studies problems involving the simultaneous optimization of two or more objective functions (criteria), which are typically conflicting. Formally, the problem is defined as the minimization of a vector objective function over a set of feasible solutions.

Definition and Terminology

A multi-objective optimization problem is generally formulated as follows: $\underset{x\in S}{min}\{f_1(x),f_2(x),\dots ,f_k(x)\}$ where $S\subseteq {ℝ}^n$ is the non-empty set of feasible solutions, and $f_i:S\to ℝ$ are the objective functions ($k\ge 2$). The vector $f(x)=(f_1(x),\dots ,f_k(x))$ is called the objective vector.

Unlike in scalar optimization, in a multi-objective setting, there is usually no single solution that improves the values of all criteria simultaneously. Therefore, the classical concept of an optimum is generalized using the concept of Pareto optimality.

• Pareto solution (Pareto optimal or efficient solution): a feasible solution $x^{\ast }\in S$ for which there is no other solution $x\in S$ such that $f_i(x)\le f_i(x^{\ast })$ for all $i=1,\dots ,k$, and $f_j(x)<f_j(x^{\ast })$ for at least one index $j$. In other words, a solution is Pareto optimal if no objective value can be improved without worsening at least one other objective.
• Pareto front (or Pareto set): the set of all objective vectors corresponding to Pareto optimal solutions.
• Weakly Pareto optimal solution: a solution $x^{\ast }\in S$ for which there is no other solution $x\in S$ such that $f_i(x)<f_i(x^{\ast })$ for all $i$.

Key Properties and Theorems

• Weighted Sum Theorem: In convex problems (where all functions $f_i(x)$ and the set $S$ are convex), any Pareto optimal solution $x^{\ast }$ is a solution to the scalar problem of minimizing the weighted sum of the criteria $\underset{x\in S}{min}\sum _{i=1}^k{w}_i{f}_i(x)$ for some set of non-negative weights $w_i\ge 0$. However, in non-convex problems, this method may fail to find certain parts of the Pareto front.

• Karush-Kuhn-Tucker (KKT) Optimality Conditions: The necessary optimality conditions for smooth problems are generalized to the multi-objective case. At a Pareto optimal point, there exists a non-zero set of non-negative multipliers (weights) for which the gradients of the objective functions and the active constraints are linearly dependent.

• Properties of the Solution Set: The Pareto front has several important qualitative characteristics. Its boundary is bounded by the ideal point (composed of the component-wise minima of all criteria) and the nadir point (composed of the component-wise maxima on the front).

Examples

• Linear Problem: Minimize $f_1(x)=-x_1$ and $f_2(x)=-x_2$ subject to the constraint $x_1+x_2\le 1$, $x_1,x_2\ge 0$. Here, improving one objective (e.g., increasing $x_1$) inevitably leads to the worsening of the other (decreasing $x_2$). The set of Pareto optimal solutions is the line segment $x_1+x_2=1$.
• Non-convex Problem: Minimize $f_1(x)=x^2$ and $f_2(x)=(x-2{)}^2$ on the interval $[0,2]$. The Pareto front is non-convex. The weighted sum method with positive weights cannot find solutions inside this interval (e.g., at the point $x=1$), because the linear combination of the criteria will only reach its minimum at the extreme points $x=0$ or $x=2$.

Related Concepts and Applications

Multi-objective optimization is closely related to multi-criteria decision-making (MCDM), which studies the selection of the best alternative considering the preferences of a decision-maker. The main methods for transforming a multi-objective problem into a scalar one (scalarization) include:

• Weighted Sum Method.
• $\epsilon$-constraint Method: One objective is optimized, while the others are converted into constraints of the form $f_i(x)\le {\epsilon }_i$. This method is capable of finding solutions on non-convex parts of the front.

Multi-objective optimization is widely used in engineering design, economics (e.g., portfolio optimization), management, and ecology.

External links

• Multi-objective optimization — Wikipedia

See also

• Optimal solution (optimization)
• Decision theory
• Decision-making
• Operations research