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$.

Lexicographic min-max optimization

In lexicographic min-max optimization (also called leximin optimization or leximax optimization), all objectives are equally important. The goal is to maximize the smallest objective; subject to that, maximize the next-smallest objective, and so on. In other words, the decision-maker ranks the possible solutions according to a leximin order of their objective function values. Many algorithms for lexicographic optimization can be adapted to leximin optimization.