Lexicographic optimization

Lexicographic optimization is a kind of Multi-objective optimization. In general, multi-objective optimization deals with optimization problems with two or more objective functions to be optimized simultaneously. Often, the different objectives can be ranked in order of importance to the decision-maker, so that objective $f_{1}$ is the most important, objective $f_{2}$ is the next most important, and so on. Lexicographic optimization presumes that the decision-maker prefers even a very small increase in $f_{1}$, to even a very large increase in $f_{2},f_{3},f_{4},$ etc. Similarly, the decision-maker prefers even a very small increase in $f_{2}$, to even a very large increase in $f_{3},f_{4},$ etc. In other words, the decision-maker has lexicographic preferences, ranking the possible solutions according to a lexicographic order of their objective function values.

As an example, consider a firm who puts safety above all. So it wants to maximize the safety of its workers and customers. Subject to attaining the maximum possible safety, it wants to maximize profits. This firm performs lexicographic optimization, where $f_{1}$ denots safety and $f_{2}$ denotes profits.

Algorithms

One algorithm for lexicographic optimization consists of solving a sequence of single-objective optimization problems of the form

${\begin{aligned}\min &f_{l}(\mathbf {x} )\\{\text{s.t. }}&f_{j}(\mathbf {x} )\leq \mathbf {y} _{j}^{*},\;j=1,\dotsc ,l-1,\\&\mathbf {x} \in X,\end{aligned}}$

where $\mathbf {y} _{j}^{*}$ is the optimal value of the above problem with $l=j$. Thus, $\mathbf {y} _{1}^{*}:=\min\{f_{1}(\mathbf {x} )\mid \mathbf {x} \in X\}$ and each new problem of the form in the above problem in the sequence adds one new constraint as $l$ goes from $1$ to $k$.

See also

• Leximin order