Lexicographic optimization

Lexicographic optimization is a kind of Multi-objective optimization. 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},$ 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 ranks the possible solutions according to a lexicographic order.

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