Lexicographic max-min optimization

The Saturation Algorithm works when the feasible set is a convex set, and the objectives are concave functions. Variants of these algorithm appear in many papers. The earliest appearance is attributed to Alexander Kopelowitz^[1] by Elkind and Pasechnik.^[6] Other variants appear in.^{[7]: 20–27 [8][9][5]: Alg.2 [10][11][12][13][14][15]}

The algorithm keeps a set of objectives that are considered saturated (also called: blocking). This means that their value cannot be improved without harming lower-valued objectives. The other objectives are called free. Initially, all objectives are free. In general, the algorithm works as follows:

• While some objective is free:
  • (P1) Solve the following single-objective problem, where ${\displaystyle z_{k}}$ is the saturation value of objective ${\displaystyle f_{k}}$:$${\displaystyle {\begin{aligned}\max ~~~z\\{\text{subject to}}~~~&x\in X,\\&f_{k}(x)=z_{k}{\text{ for all saturated objectives }}k,\\&f_{k}(x)\geq z{\text{ for all free objectives }}k\end{aligned}}}$$
  • If the problem is infeasible or unbounded, stop and declare that there is no solution.
  • Otherwise, let ${\displaystyle z_{\max }}$ be the maximum value of the first problem.
  • Look for free objectives whose value cannot increase above ${\displaystyle z_{\max }}$ without decreasing some other objective below ${\displaystyle z_{\max }}$. In any lexmaxmin solution, the value of any such objective must be exactly ${\displaystyle z_{\max }}$. Add all such objectives to the set of saturated objectives, set their saturation value to ${\displaystyle z_{\max }}$, and go back to (P1).

It remains to explain how we can find new saturated objectives in each iteration.

Method 1: interior optimizers.^[1][6] An interior optimizer of a linear program is an optimal solution in which the smallest possible number of constraints are tight. In other words, it is a solution in the interior of the optimal face. An interior optimizer of (P1) can be found by solving (P1) using the ellipsoid method or interior point methods.

The set of tight constraints in an interior optimizer is unique. Proof: Suppose by contradiction that there are two interior-optimizers, x1 and x2, with different sets of tight constraints. Since the feasible set is convex, the average solution x3 = (x1+x2)/2 is also an optimizer. Every constraint that is not tight in either x1 or x2, is not tight in x3. Therefore, the number of tight constraints in x3 is smaller than in x1 and x2, contradicting the definition of an interior optimizer.

Therefore, the set of tight constraints in the interior optimizer corresponds to the set of free objectives that become saturated. Using this method, the leximin solution can be computed using at most n iterations.

Method 2: iterating over all objectives.^[7] It is possible to find at least one saturated objective using the following algorithm.

• For every free objective ${\displaystyle f_{j}}$:
  • (P2) Solve the following single-objective problem:$${\displaystyle {\begin{aligned}\max ~~~f_{j}(x)\\{\text{subject to}}~~~&x\in X,\\&f_{k}(x)\geq z_{k}{\text{ for all saturated objectives }}k,\\&f_{k}(x)\geq z_{\max }{\text{ for all free objectives }}k\end{aligned}}}$$
  • If the optimal value equals ${\displaystyle z_{\max }}$, then objective j becomes saturated from now on.
  • Otherwise, the optimal value must be larger than ${\displaystyle z_{\max }}$; objective j remains free for now.
• End for

At each step, at least one free objective must become saturated. This is because, if no objective were saturated, then the mean of all optimal solutions to (P2) would be a feasible solution in which all objective values are larger than ${\displaystyle z_{\max }}$ - contradicting the optimality of solution to (P1). For example, suppose ${\displaystyle z_{\max }=1}$, objective 1 is not saturated because there is a solution with value-vector (3,1), and objective 2 is not saturated because there exists a solution with value-vector and (1,3). Then, there exists a solution with value-vector at least (2,2), but ${\displaystyle z_{\max }}$ should have been at least 2.

Therefore, after at most n iterations, all variables are saturated and a leximin-optimal solution is found. In each iteration t, the algorithm solves at most n-t+1 linear programs; therefore, the run-time of the algorithm is at most ${\displaystyle (n+2)(n+1)/2\in O(n^{2})}$ times the run-time of the LP solver.

In some cases, the run-time of the saturation algorithm can be improved. Instead of finding all saturated objectives, we can break out of the inner loop after finding one saturated objective; the algorithm still stops after at most n iterations, and may reduce the number of linear programs (P2) we need to solve.^[5]: Alg.3

Furthermore, instead of looping over all objectives to find a saturated one, the algorithm can find a saturated objective using the dual problem of (P1). In some cases, the dual variables are given as a byproduct of solving (P1), for example, when the objectives and constraints are linear and the solver is the simplex algorithm. In this case, (P2) is not needed at all, and the run-time of the algorithm is at most ${\displaystyle n}$ times the run-time of the solver of (P1).^[5]: Alg.4

All these variants work only for convex problems. For non-convex problems, there might be no saturated objective, so the algorithm might not stop.

The Ordered Outcomes Algorithm works in arbitrary domains (not necessarily convex). It was developed by Ogryczak and Śliwiński^[16] and also presented in the context of telecommunication networks by Ogryczak, Pioro and Tomaszewski,^[5] and in the context of location problems by Ogryczak.^[17] The algorithm reduces lexmaxmin optimization to the easier problem of lexicographic optimization. Lexicographic optimization can be done with a simple sequential algorithm, which solves at most n linear programs. The reduction starts with the following presentation of lexmaxmin:$${\displaystyle {\begin{aligned}(L1)\\\operatorname {lex} \max &&f_{[1]}(x),\ldots ,f_{[n]}(x)\\{\text{subject to}}&&x\in X\end{aligned}}}$$

This problem cannot be solved as-is, because ${\displaystyle f_{[t]}(x)}$ (the t-th smallest value in ${\displaystyle \mathbf {f} (x)}$) is not a simple function of x. The problem (L1) is equivalent to the following problem, where ${\displaystyle f_{[1..t]}(x):=\sum _{i=1}^{t}f_{[i]}(x)=}$ the sum of the t smallest values in ${\displaystyle \mathbf {f} (x)}$:$${\displaystyle {\begin{aligned}(L2)\\\operatorname {lex} \max &&f_{[1..1]}(x),f_{[1..2]}(x),\ldots ,f_{[1..n]}(x)\\{\text{subject to}}&&x\in X\end{aligned}}}$$

This problem can be solved iteratively using lexicographic optimization, but the number of constraints in each iteration t is C(n,t) -- the number of subsets of size t. This grows exponentially with n. It is possible to reduce the problem to a different problem, in which the number of constraints is polynomial in n.

For every t, the sum ${\displaystyle f_{[1..t]}(x)}$ can be computed as the optimal value to the following problem, with n+1 auxiliary variables (an unbounded variable ${\displaystyle r_{t}}$, and non-negative variables ${\displaystyle d_{t,j}}$ for all j in 1,...,n), and n additional constraints:^{[5]: Thm.8 [18]}$${\displaystyle {\begin{aligned}(L3)\\\max(t\cdot r_{t}-\sum _{j=1}^{n}d_{t,j})\\{\text{subject to}}~~~&x\in X,\\&r_{t}-f_{j}(x)\leq d_{t,j}{\text{ for all }}j\in [n],\\&d_{t,j}\geq 0{\text{ for all }}j\in [n].\end{aligned}}}$$

Proof. Let us compute the values of the auxiliary variables in the optimal solution.

• For all j, ${\displaystyle d_{t,j}}$ should be at least as large as both 0 and ${\displaystyle r_{t}-f_{j}(x)}$, and subject to this, it should be minimized, since it appears in the objective with a minus sign. Therefore, ${\displaystyle d_{t,j}=\max(0,r_{t}-f_{j}(x))}$. So the objective can be written as: ${\displaystyle t\cdot r_{t}-\sum _{j=1}^{n}\max(0,r_{t}-f_{j}(x))}$.
• For any k between 0 and n, if ${\displaystyle r_{t}}$ is larger than the smallest k objective values (that is, ${\displaystyle r_{t}\geq f_{[k]}(x)}$), then the sum at the right-hand side contains exactly k positive elements: ${\displaystyle \sum _{j=1}^{k}(r_{t}-f_{[j]}(x))=k\cdot r_{t}-f_{[1..k]}(x)}$. In that case, the objective can be written as: ${\displaystyle (t-k)\cdot r_{t}+f_{[1..k]}(x)}$. Note that ${\displaystyle (t-k)\cdot r_{t}}$ is increasing with ${\displaystyle r_{t}}$ when k<t, and decreasing with ${\displaystyle r_{t}}$ when k>t. Therefore, the maximum value is attained when k=t, that is, ${\displaystyle r_{t}}$ is larger than the smallest t objective values; in that case, the objective exactly equals ${\displaystyle f_{[1..t]}(x)}$, as claimed.

Therefore, the problem (L2) is equivalent to the following lexicographic maximization problem:^[5]: (32)$${\displaystyle {\begin{aligned}(L4)\\\operatorname {lex} \max(t\cdot r_{t}-\sum _{j=1}^{n}d_{t,j})_{t=1}^{n}\\{\text{subject to}}~~~&x\in X,\\&r_{t}-f_{j}(x)\leq d_{t,j}{\text{ for all }}j\in [n],\\&d_{t,j}\geq 0{\text{ for all }}j\in [n].\end{aligned}}}$$

This problem (L4) has ${\displaystyle n^{2}+n}$ additional variables, and ${\displaystyle n^{2}}$ additional constraints. It can be solved by every algorithm for solving lexicographic maximization, for example: the sequential algorithm using n linear programs, or the lexicographic simplex algorithm (if the objectives and constraints are linear).

One advantage of the Ordered Outcomes Algorithm is that it can be used even when the single-problem solver is inaccurate, and returns only approximate solutions. Specifically, if the single-problem solver approximates the optimal single-problem solution with multiplicative factor α ∈ (0,1] and additive factor ϵ ≥ 0, then the algorithm returns a solution that approximates the leximin-optimal solution with multiplicative factor α²/(1 − α + α²) and additive factor ϵ/(1 − α + α²).^[19]

The Ordered Values Algorithm works in any domain in which the set of possible values of the objective functions is finite. It was developed by Ogryczak and Śliwiński.^[16] Let ${\displaystyle V=\{v_{1},\ldots ,v_{r}\}}$ be the set of all values that can be returned by the functions ${\displaystyle f_{1},\ldots ,f_{n}}$, such that ${\displaystyle v_{1}<\cdots <v_{r}}$. Given a solution x, and an integer k in {1,..,r}, define ${\displaystyle h_{k}(x)}$ as the number of occurrences of the value v_r in the vector ${\displaystyle f_{1}(x),\ldots ,f_{n}(x)}$. Then, the lexmaxmin problem can be stated as the following lexicographic minimization problem:$${\displaystyle {\begin{aligned}(H1)\\\operatorname {lex} \min &&h_{1}(x),\ldots ,h_{r-1}(x)\\{\text{subject to}}&&x\in X\end{aligned}}}$$since we want to have as few as possible functions attaining the smallest value; subject to this, as few as possible functions attaining the next-smallest value; and so on. Ogryczak and Śliwiński^[16] show how to transform this non-linear program into a linear program with auxiliary variables. In their computational experiments, the Ordered Values algorithm runs much faster than the Saturation algorithm and the Ordered Outcomes algorithm.

Behringer^[4] presented a sequential algorithm for lexmaxmin optimization^{[clarification needed]} when the objectives are quasiconvex functions, and the feasible set X is a convex set.

Yager^[20] presented a way to represent the leximin ordering analytically using the Ordered weighted averaging aggregation operator. 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). 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 lexmaxmin.

If the set of vectors is discrete, and the domain is sufficiently small, then it is possible to use one of the functions representing the leximin order, and maximize it subject to the constraints, using a solver for constraint-satisfaction problems.

But if the domain is large, the above approach becomes unfeasible due to the large number of possible values that this function can have: ${\displaystyle {m+n-1 \choose n}}$, where m is the number of different values in the domain, and n is the number of variables.^[21]

Bouveret and Lemaître present five different algorithms for finding leximin-optimal solutions to discrete constraint-satisfaction problems:^[21]

1. Branch and bound based on the LEXIMIN constraint - a constraint on two vectors x and y, saying that y is leximin-larger than x.
2. Branching on saturated subsets - finding subsets of variables that must be fixed at the minimum value, and finding the maximum-minimum value for the other variables.
3. Using the SORT constraint - a constraint on two vectors x and y, saying that y contains the same elements as x sorted in ascending order. This constraint can be computed efficiently by several algorithms.^[22][23]
4. Using the ATLEAST constraint.
5. Using max-min transformations.

In their experiments, the best-performing approach was 4 (ATLEAST), followed by 3 (SORT) followed by 1 (LEXIMIN).

Dall'aglio^[24] presents an algorithm for computing a leximin-optimal resource allocation.