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 {\displaystyle f_{1}} is the most important, objective f 2 {\displaystyle 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 {\displaystyle f_{1}} , to even a very large increase in f 2 , f 3 , f 4 , {\displaystyle f_{2},f_{3},f_{4},} etc. Similarly, the decision-maker prefers even a very small increase in f 2 {\displaystyle f_{2}} , to even a very large increase in f 3 , f 4 , {\displaystyle 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. Lexicographic optimization is sometimes called preemptive optimization, since a small increase in one objective value preempts a much larger increase in less important objective values. As an example, consider a firm which puts safety above all. 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 {\displaystyle f_{1}} denotes safety and f 2 {\displaystyle f_{2}} denotes profits. As another example, in project management, when analyzing PERT networks, one often wants to minimize the mean completion time, and subject to this, minimize the variance of the completion time.
Notation A lexicographic maximization problem is often written as: lex max f 1 ( x ) , f 2 ( x ) , … , f n ( x ) subject to x ∈ X {\displaystyle {\begin{aligned}\operatorname {lex} \max &&f_{1}(x),f_{2}(x),\ldots ,f_{n}(x)\\{\text{subject to}}&&x\in X\end{aligned}}} where f 1 , … , f n {\displaystyle f_{1},\ldots ,f_{n}} are the functions to maximize, ordered from the most to the least important; x {\displaystyle x} is the vector of decision variables; and X {\displaystyle X} is the feasible set - the set of possible values of x {\displaystyle x} . A lexicographic minimization problem can be defined analogously.
Algorithms There are several algorithms for solving lexicographic optimization problems.
Sequential algorithm for general objectives A leximin optimization problem with n {\displaystyle n} objectives can be solved using a sequence of n {\displaystyle n} single-objective optimization problems, as follows:
… excerpt ends here. Continue reading the full article.
