Sequential algorithm for general objectives

A leximin optimization problem with n objectives can be solved using a sequence of n single-objective optimization problems, as follows:^{[1][3]: Alg.1}

• For t = 1,...,n do
  • Solve the following single-objective problem:
    $${\displaystyle {\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}}}$$

    
  • If the problem is infeasible or unbounded, stop and declare that there is no solution.
  • Otherwise, put the value of the optimal solution in ${\displaystyle z_{t}}$ and continue.
• End for

So, in the first iteration, we find the maximum feasible value of the most important objective ${\displaystyle f_{1}(x)}$, and put this maximum value in ${\displaystyle z_{1}}$. In the second iteration, we find the maximum feasible value of the second-most important objective ${\displaystyle f_{2}(x)}$, with the additional constraint that the most imporant objective must keep its maximum value of ${\displaystyle 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 objectives

Linear lexicographic optimization^[2] 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:

$${\displaystyle {\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 ${\displaystyle c_{1},\ldots ,c_{n}}$ are vectors representing the linear objectives to maximize, ordered from the most to the least important; ${\displaystyle x}$ is the vector of decision variables; and the feasible set is determined by the matrix ${\displaystyle A}$ and the vector ${\displaystyle b}$.

Isermann^[2] 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.

Weighted average for linear objectives

Sherali and Soyster^[1] prove that, for any linear lexicographic optimization problem, there exist a set of weights ${\displaystyle w_{1}>w_{2}>\cdots >w_{n}}$ such that the set of lexicographically-optimal solutions is identical to the set of solutions to the following single-objective problem:

$${\displaystyle {\begin{aligned}\max &&w_{1}f_{1}(x)+\cdots +w_{n}f_{n}(x)\\{\text{subject to}}&&x\in X\end{aligned}}}$$

One way to compute the weights is given by Yager.^[4] He assumes that all objective values are real numbers between 0 and 1, and the smallest difference between any two possible values is some constant d < 1 (so that values with difference smaller than d are considered equal). Then, the weight ${\displaystyle w_{t}}$ of ${\displaystyle f_{t}(x)}$ is set to approximately ${\displaystyle d^{t}}$. This guarantees that maximizing the weighted sum ${\displaystyle \sum _{t}w_{t}f_{t}(x)}$ is equivalent to lexicographic maximization.

Cococcioni, Pappalardo and Sergeyev^[5] show that, given a computer that can make numeric computations with infinitesimals, it is possible to choose weights that are infinitesimals (specifically: ${\displaystyle w_{1}=1}$; ${\displaystyle w_{2}}$ is infinitesimal; ${\displaystyle w_{3}}$ is infinitesimal-squared; etc.), and thus reduce linear lexicographic optimization to single-objective linear programming with infinitesimals. They present an adaptation of the simplex algorithm to infinitesimals, and present some running examples.