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 ${\displaystyle f_{1}}$ is the most important, objective ${\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 ${\displaystyle f_{1}}$, to even a very large increase in ${\displaystyle f_{2},f_{3},f_{4},}$ etc. Similarly, the decision-maker prefers even a very small increase in ${\displaystyle f_{2}}$, to even a very large increase in ${\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,^[1] 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 ${\displaystyle f_{1}}$ denotes safety and ${\displaystyle f_{2}}$ denotes profits.

As another example,^[2] 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.

A lexicographic maximization problem is often written as:$${\displaystyle {\begin{aligned}\operatorname {lex} \max &&f_{1}(x),f_{2}(x),\ldots ,f_{n}(x)\\{\text{sujeto a}}&&x\in X\end{aligned}}}$$where ${\displaystyle f_{1},\ldots ,f_{n}}$ are the functions to maximize, ordered from the most to the least important; ${\displaystyle x}$ is the vector of decision variables; and ${\displaystyle X}$ is the feasible set - the set of possible values of ${\displaystyle x}$. A lexicographic minimization problem can be defined analogously.

There are several algorithms for solving lexicographic optimization problems.^[3]

(1) Unicidad . En general, un problema de optimización lexicográfica puede tener más de una solución óptima. Sin embargo, si${\displaystyle x^{1}}$y${\displaystyle x^{2}}$son dos soluciones óptimas, entonces su valor debe ser el mismo, es decir,${\displaystyle f_{i}(x^{1})=f_{i}(x^{2})}$a pesar de${\displaystyle i\in [n]}$. ^{[ 3 ] : Teorema 2} Además, si el dominio factible es un conjunto convexo y las funciones objetivo son estrictamente cóncavas , entonces el problema tiene como máximo una solución óptima, ya que si hubiera dos soluciones óptimas diferentes, su media sería otra solución factible en la que las funciones objetivo alcanzaran un valor más alto, contradiciendo la optimalidad de las soluciones originales.

(2) Sumas parciales . Dado un vector${\displaystyle f_{1},\ldots ,f_{n}}$de funciones para optimizar, para todos${\displaystyle t}$en${\displaystyle 1,\dots ,n,}$definir${\displaystyle f_{1..t}:=\sum _{i=1}^{t}f_{i}}$= la suma de todas las funciones desde la más importante hasta la más${\displaystyle t}$-el más importante. Entonces, el problema de optimización lexicográfica original es equivalente al siguiente: ^{[ 3 ] : Teorema 4}$${\displaystyle {\begin{aligned}\operatorname {lex} \max &&f_{1...1}(x),f_{1..2}(x),\ldots ,f_{1..n}(x)\\{\text{subject to}}&&x\in X\end{aligned}}}$$En algunos casos, el segundo problema puede ser más fácil de resolver.

• La optimización lexicográfica max-min es una variante de la optimización lexicográfica en la que todos los objetivos son igualmente importantes, y el objetivo es maximizar el objetivo más pequeño, luego el segundo objetivo más pequeño, y así sucesivamente.
• En teoría de juegos, el nucleolo se define como un conjunto de soluciones lexicográficamente mínimo. ^{[ 6 ]}