Lexicographic optimization#Algorithms

A lexicographic maximization problem is often written as:$$$$

\begin{align}

\operatorname{lex}

\max &&

f_1(x), f_2(x), \ldots, f_n(x)

\\

\text{subject to} && x\in X

\end{align}

where $f\_1,\backslash 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.

There are several algorithms for solving lexicographic optimization problems.{{Cite journal |last1=Ogryczak |first1=W. |last2=Pióro |first2=M. |last3=Tomaszewski |first3=A. |date=2005 |title=Telecommunications network design and max-min optimization problem |url=http://yadda.icm.edu.pl/baztech/element/bwmeta1.element.baztech-article-BAT3-0027-0006 |journal=Journal of Telecommunications and Information Technology |language=EN |volume=3 |issue=3 |pages=43–56 |doi=10.26636/jtit.2005.3.326 |issn=1509-4553|doi-access=free }}

A leximin optimization problem with n objectives can be solved using a sequence of n single-objective optimization problems, as follows:{{Rp|location=Alg.1}}

• For t = 1,...,n do
• Solve the following single-objective problem:$$$$

\begin{align}

\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{align}

• If the problem is infeasible or unbounded, stop and declare that there is no solution.
• Otherwise, put the value of the optimal solution in $$

z_t

and continue.

• 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 important 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.

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{align}

\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{align}

where $c\_1,\backslash 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.

Sherali and Soyster prove that, for any linear lexicographic optimization problem, there exist a set of weights $w\_1\; >\; w\_2\; >\; \backslash cdots\; >\; w\_n$ such that the set of lexicographically-optimal solutions is identical to the set of solutions to the following single-objective problem:$$$$

\begin{align}

\max &&

w_1 f_1(x) + \cdots + w_n f_n(x)

\\

\text{subject to} && x\in X

\end{align}

One way to compute the weights is given by Yager.{{Cite journal |last=Yager |first=Ronald R. |date=1997-10-01 |title=On the analytic representation of the Leximin ordering and its application to flexible constraint propagation |url=https://www.sciencedirect.com/science/article/pii/S0377221796002172 |journal=European Journal of Operational Research |language=en |volume=102 |issue=1 |pages=176–192 |doi=10.1016/S0377-2217(96)00217-2 |issn=0377-2217}} 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 $w\_t$ of $f\_t(x)$ is set to approximately $d^t$. This guarantees that maximizing the weighted sum $\backslash sum\_t\; w\_t\; f\_t(x)$ is equivalent to lexicographic maximization.

Cococcioni, Pappalardo and Sergeyev{{Cite journal |last1=Cococcioni |first1=Marco |last2=Pappalardo |first2=Massimo |last3=Sergeyev |first3=Yaroslav D. |date=2018-02-01 |title=Lexicographic multi-objective linear programming using grossone methodology: Theory and algorithm |url=https://www.sciencedirect.com/science/article/pii/S0096300317303703 |journal=Applied Mathematics and Computation |series=Recent Trends in Numerical Computations: Theory and Algorithms |language=en |volume=318 |pages=298–311 |doi=10.1016/j.amc.2017.05.058 |issn=0096-3003|hdl=11568/877746 |hdl-access=free }} show that, given a computer that can make numeric computations with infinitesimals, it is possible to choose weights that are infinitesimals (specifically: $w\_1=1$; $w\_2$ is infinitesimal; $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.

(1) Uniqueness. In general, a lexicographic optimization problem may have more than one optimal solution. However, If $x^1$ and $x^2$ are two optimal solutions, then their value must be the same, that is, $f\_i(x^1)\; =\; f\_i(x^2)$ for all $i\backslash in[n]$.{{Rp|location=Thm.2}} Moreover, if the feasible domain is a convex set, and the objective functions are strictly concave, then the problem has at most one optimal solution, since if there were two different optimal solutions, their mean would be another feasible solution in which the objective functions attain a higher value - contradicting the optimality of the original solutions.

(2) Partial sums. Given a vector $f\_1,\backslash ldots,\; f\_n$ of functions to optimize, for all t in 1,...,n, define $f\_\{1..t\}\; :=\; \backslash sum\_\{i=1\}^t\; f\_i$ = the sum of all functions from the most important to the t-th most important one. Then, the original lexicographic optimization problem is equivalent to the following:{{Rp|location=Thm.4}}$$$$

\begin{align}

\operatorname{lex}

\max &&

f_{1...1}(x), f_{1..2}(x), \ldots, f_{1..n}(x)

\\

\text{subject to} && x\in X

\end{align}

In some cases, the second problem may be easier to solve.

• Lexicographic max-min optimization is a variant of lexicographic optimization in which all objectives are equally important, and the goal is to maximize the smallest objective, then the second-smallest objective, and so on.
• In game theory, the nucleolus is defined as a lexicographically-minimal solution set.{{Cite journal |last=Kohlberg |first=Elon |date=1972-07-01 |title=The Nucleolus as a Solution of a Minimization Problem |url=http://epubs.siam.org/doi/10.1137/0123004 |journal=SIAM Journal on Applied Mathematics |language=en |volume=23 |issue=1 |pages=34–39 |doi=10.1137/0123004 |issn=0036-1399}}

{{reflist}}

Category:Multiple-criteria decision analysis

Category:Optimization algorithms and methods