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.

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:$${\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},\ldots ,f_{n}$ are the functions to maximize, ordered from the most to the least important; $x$ is the vector of decision variables; and $X$ is the feasible set - the set of possible values of $x$. A lexicographic minimization problem can be defined analogously.

Algorithms

There are several algorithms for solving lexicographic optimization problems.

Sequential algorithm for general functions

A leximin optimization problem witn n objectives can be solved using a sequence of n single-objective optimization problems, as follows.

• For t = 1,...,n do
  • Solve the following single-objective problem:$${\begin{aligned}\max ~~~f_{t}(x)\\{\text{subject to}}~~~&x\in X,\\&f_{k}(x)\geq z_{k}{\text{ for all }}k{\text{ in }}1,\ldots ,t-1.\end{aligned}}$$
  • Put the value of the optimal solution in $z_{t}$.
• End for

So, in the first iteration, we find the maximum feasible value of the most important objective $f_{1}(x)$, and put this maximum value in $z_{1}$. In the second iteration, we find the maximum feasible value of the second-most important objective $f_{2}(x)$, with the additional constraint that the most imporant objective must keep its maximum value of $z_{1}$; and so on.

The sequential algorithm is general - it can be applied whenever we have a solver for the single-objective functions.

Lexicographic simplex algorithm for linear functions

Linear lexicographic optimization is a special case of lexicographic optimization in which the objectives are linear, and the feasible set is described by linear inequalities. It can be written as:$${\begin{aligned}\operatorname {lex} \max &&c_{1}\cdot x,c_{2}\cdot x,\ldots ,c_{n}\cdot x\\{\text{subject to}}&&A\cdot x\leq b,x\geq 0\end{aligned}}$$where $c_{1},\ldots ,c_{n}$ are vectors representing the linear objectives to maximize, ordered from the most to the least important; $x$ is the vector of decision variables; and the feasible set is determined by the matrix $A$ and the vector $b$.

Isermann extended the theory of linear programming duality to lexicographic linear programs, and developed a lexicographic simplex algorithm. In contrast to the sequential algorithm, this simplex algorithm considers all objective functions simultaneously.

Lexicographic max-min optimization

In lexicographic max-min optimization (also called lexmaxmin or leximin or leximax or lexicographic max-ordering 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. The problem can be written as:$${\begin{aligned}\operatorname {lex} \max \min &&f_{1}(x),f_{2}(x),\ldots ,f_{n}(x)\\{\text{subject to}}&&x\in X\end{aligned}}$$ Alternatively, denote by $f_{[1]}(x):=\min(f_{1}(x),\ldots ,f_{n}(x))=$ the smallest objective value in x. Similarly, denote by $f_{[2]}x):=$ the second-smallest objective value in x, and so on. Then, the lexmaxmin optimization problem can be written as a lexicographic maximization problem:$${\begin{aligned}\operatorname {lex} \max &&f_{[1]},\ldots ,f_{[n]}\\{\text{subject to}}&&x\in X\end{aligned}}$$As an example, consider egalitarian social planners, who want to decide on a policy such that the welfare of the poorest person will be as high as possible; subject to this, they want to maximize the welfare of the second-poorest person; and so on. This planner solves a lexmaxmin problem, where $f_{i}$ denotes the welfare of agent i.

An early application of lexmaxmin (not using this name) was presented by Dersher in his book on game theory, in the context of taking maximum advantage of the opponent's mistakes in a zero-sum game. Behringer cites many other examples in game theory as well as decision theory.

Behringer's algorithm for quasiconcave functions

Behringer presented a sequential algorithm for lexmaxmin optimization when the objectives are quasiconvex functions, and the feasible set X is a convex set.

Reduction to lexicographic maximization

Many algorithms for lexicographic optimization can be adapted to leximin optimization.