Application of tropical optimization for solving multicriteria problems of pairwise comparisons using log-Chebyshev approximation^††thanks: Internat. J. Approx. Reason. 169, 109168 (2024)

The heuristic methods are mainly based on aggregating columns of the pairwise comparison matrix to obtain a solution by calculating a weighted sum of these columns [8]. In the most widely used method of principal eigenvector [47, 48, 49], the solution vector $\bm{x}$ is defined as the sum of columns taken with weights assumed proportional to the components of $\bm{x}$. Under this assumption, the vector $\bm{x}$ must satisfy the equation $\bm{C}\bm{x}=\lambda\bm{x}$ where $1/\lambda$ is a coefficient of proportionality, and it is found as the principal (Perron) eigenvector of the matrix $\bm{C}$ corresponding to the maximum eigenvalue.

The approximation methods reduce the problem to finding a consistent matrix $\bm{X}$ that approximates a given matrix $\bm{C}$ in the sense of some distance function as approximation error [8]. Then, a positive vector $\bm{x}$ that determines the approximating consistent matrix is taken as a vector of absolute ratings of alternatives. The approximation problem is solved as an optimization problem of minimizing the distance between the matrices $\bm{C}$ and $\bm{X}$, which provides a formal justification of the solution obtained.

If the approximation error is measured on the standard linear scale, the approach normally leads to complex multiextremal optimization problems that are very hard to solve [50]. On the contrary, the application of the logarithmic scale (with logarithm to a base greater than $1$) makes the approximation problem more tractable and even allows the solution to be derived analytically in an exact explicit form.

A widespread approximation technique to solve the pairwise comparison problem measures the error between the matrices $\bm{C}=(c_{ij})$ and $\bm{X}=(x_{i}/x_{j})$ by using the Euclidean metric in logarithmic scale [43, 9, 1]. This technique known as the method of geometric mean, involves finding a positive vector $\bm{x}=(x_{j})$ that solves the problem

The standard solution approach, which applies the first derivative test to find the roots of the partial derivatives of the objective function with respect to all $x_{i}$, yields a solution vector $\bm{x}$ with the components given in the parametric form

After normalization (e.g. by dividing by the sum of components), this vector is taken as the optimal solution of the pairwise comparison problem.

As another approximation technique, a method of minimizing the Chebyshev distance in logarithmic scale (a log-Chebyshev approximation method) is proposed in [29, 30, 34]. The method aims to find positive vectors $\bm{x}$ that solve the problem

We observe that the methods of principal eigenvector and geometric mean lead to unique solutions and offer efficient computational procedures of calculating the result. At the same time, the solution provided by log-Chebyshev approximation can be nonunique and thus require further analysis. Considering an approximate character of the pairwise comparison model which usually leads to inconsistent results of pairwise comparisons, multiple solutions of the problem look quite reasonable and even allow to select a solution satisfying additional constraints.

Let us consider the problem of unconstrained log-Chebyshev approximation at (1). Observing that the logarithm to a base greater than $1$ monotonically increases, the objective function is rewritten as (see, e.g. [34])

Since the logarithmic function on the right-hand side attains its maximum there where its argument is maximal, we remove the logarithm from the objective function. Moreover, it is not difficult to verify (see [14, 15, 34]) that the obtained objective function is connected with the standard relative approximation error by the equality

This means that the log-Chebyshev approximation of the matrix $\bm{C}$ is equivalent to the approximation in the sense of relative error as well.

Consider an extension of the pairwise comparison problem where the ratings of alternatives are to be evaluated subject to some predefined constraints. Suppose the constraints imposed on the ratings are in the form of two-sided bounds on ratios between the ratings. These constraints can reflect prior knowledge about the relationship between ratings, which can be obtained by different assessment techniques or resulted from the nature of alternatives.

Given a nonnegative matrix $\bm{B}=(b_{ij})$ where $b_{ij}>0$ shows that alternative $i$ must be considered not less than $b_{ij}$ times better than $j$, and $b_{ij}=0$ indicates that no constraint is imposed on $i$ with respect to $j$. The constraints are given by the inequalities $b_{ij}x_{j}\leq x_{i}$ for all $i,j=1,\ldots,n$, or equivalently by the double inequality $b_{ij}\leq x_{i}/x_{j}\leq 1/b_{ji}$ when $b_{ji}>0$. Combining the former inequalities for all $j$ yields the system of inequalities

We incorporate the constraints into (1) to formulate the following problem of constrained log-Chebyshev approximation. Given a positive $(n\times n)$-matrix $\bm{C}=(c_{ij})$ of pairwise comparisons and nonnegative $(n\times n)$-matrix $\bm{B}=(b_{ij})$ of constraints, the problem is to find positive $n$-vectors $\bm{x}=(x_{j})$ that achieve

Note that multiplying all components of the vector $\bm{x}$ by a common positive factor does not change both objective function and inequality constraints in problem (2), and hence the solutions of the problem are scale-invariant.

Finally, we observe that the methods of principal eigenvector and geometric mean cannot accommodate the above constraints in a straightforward way without considerable modification and complication of the solution. As it is shown later, the constrained problem of log-Chebyshev approximation at (2) can be directly solved to give the result in a compact vector form.

If problem (2) has a unique solution up to a positive factor, this solution is taken as the vector of absolute ratings of alternatives in question.

Suppose that the solution of (2) is not unique and denote the set of obtained solution vectors $\bm{x}$ by

A nonunique solution vector of the pairwise comparison problem may make it difficult to derive an optimal decision, and thus further analysis is needed to characterize the result by one or two vectors that are reasonably representative of the solution. An approach developed in [34] suggests to reduce the entire set of solutions to two vectors that provide the “best” and “worst” answers to the questions of which alternative has the highest rating and how much this rating differs from the ratings of other alternatives. As the best solution, the approach takes a vector that maximally differentiates the alternatives with the highest and lowest ratings, and as the worst a vector that minimally differentiates all alternatives. The difference between alternatives is measured by the ratio in the form of a multiplicative version of the Hilbert (span, range) seminorm of the vector $\bm{x}$, which is given by

The best and worst differentiating solutions are then obtained by maximizing and minimizing the Hilbert seminorm over all vectors $\bm{x}\in X$, which leads to the optimization problems

As examples show (see, e.g. [34]), one of the shortcomings of this approach is that the best (worst) differentiating solution found in this way may not be unique. To overcome this possible issue, we now propose a new improved procedure of finding the best and worst differentiating solutions, which provides a reduced set of the best solutions and a unique worst solution.

Since the solutions of problem (2) are invariant under multiplication by a positive factor, we can restrict ourselves to vectors that are normalized by dividing by the maximum component. Adding the normalization condition transforms the last two problems into the problems

Furthermore, we note that both problems can have nonunique normalized solutions. Under this circumstance, it is reasonable to concentrate only on the minimal normalized solution to the maximization problem and the maximal normalized solution to the minimization problem. As usual, a solution $\bm{x}_{0}$ is called minimal (maximal) if the componentwise inequality $\bm{x}_{0}\leq\bm{x}$ ($\bm{x}_{0}\geq\bm{x}$) holds for any solution $\bm{x}$.

Indeed, all normalized vectors that maximize or minimize the ratio between the highest and lowest ratings have two common components whose ratio is fixed: the maximum component equal to 1, and the minimum component less or equal to 1. In this case, the lower (higher) the ratings of the other alternatives, the better (worse) the alternative with the maximum rating is distinguishable from the others.

The max-ordering optimization aims at minimizing the worst value of the scalar objective functions in the multiobjective problem. For each $\bm{x}$, the approach considers that function which takes the maximal (worst) value. This leads to the replacement of the vector objective function by a scalar function given by the maximum component of the vector function, which is known as the Chebyshev scalarization approach in multiobjective optimization [42].

The solution of the constrained problem at (5) starts with the introduction of the feasible solution set $X_{0}$ given by the constraints as

We apply the Chebyshev scalarization and use the associativity of the maximum operation to form the scalar objective function

Then, the problem reduces to the minimization problem

which is solved to obtain the max-ordering solution in the form of the set

Note that the solution obtained by the max-ordering optimization is known to be week Pareto-optimal and become Pareto-optimal if unique [42].

If the solution is not unique (up to a positive factor), we further reduce the solution set by extracting the best and worst differentiating vectors of ratings given by the minimal and maximal normalized solutions of problems (4) over the set $X_{1}$.

The lexicographic optimization examines the scalar objective functions in a hierarchical order based on certain ranking of objectives. Suppose the objectives are numbered in such a way that objective $1$ has the highest rank, objective $2$ has the second highest and so on until objective $m$ having the lowest rank. The lexicographic approach first solves the problem of minimizing function $1$ and examines the set of optimal solutions obtained. If the solution is unique, it is taken as the solution of the overall multiobjective problem. Otherwise function $2$ is minimized over all solutions of the first problem, and the procedure continues until a unique solution is obtained or the problem with function $m$ is solved.

To apply this approach to problem (5), we first take the set $X_{0}$ given by (6), and then successively obtain the solution sets $X_{s}$ for each problem

The solution procedure stops at step $s<m$ if the set $X_{s}$ consists of a single solution vector, or at step $s=m$ otherwise. The last found set $X_{s}$ is taken as the lexicographic solution for the entire problem. In the same way as before, if the solution given by $X_{s}$ is not unique, it is reduced to the minimal and maximal solutions of respective problems at (4) over $X_{s}$.

This approach combines the lexicographic ordering and max-ordering into one procedure that improves the accuracy of the assessment provided by the max-ordering approach. The procedure consists of several steps, each of which finds the max-ordering solution of a reduced problem that has a lower multiplicity of objectives and smaller feasible set. The first solution step coincides with the above described max-ordering solution of the constrained problem with $m$ objectives and the feasible solution set given by the constraints. Each subsequent step takes the solution from the previous step as the current feasible set and selects objectives that can be further minimized over this set, to incorporate into a current vector objective function. A scalar objective function is included if it has its minimum value over the current feasible set below the minimum of the objective function at the previous step.

We denote by $I_{s}$ the set of indices of scalar objective functions that form components of the vector objective function, and by $X_{s}$ the solution set obtained at step $s$. We initially set $I_{0}=\{1,\ldots,m\}$ and define $X_{0}$ as in (6).

We find a solution set $X_{s}$ by solving the problem

With the minimum value of the objective function at step $s$ denoted by $\theta_{s}$, we define the index set

The procedure is completed at step $s<m$ if either the set $X_{s}$ reduces to a single solution vector or the condition $I_{s}=\emptyset$ holds. We additionally solve optimization problems (4) if the final set $X_{s}$ provides a nonunique solution.

Below we show how the solutions offered by the above three approaches can be directly represented in explicit analytical form using methods and result of tropical mathematics.

Consider the set $\mathbb{R}_{+}$ of nonnegative reals with two binary operations: addition denoted by $\oplus$ and defined as maximum, and multiplication denoted and defined as usual. Both operations are associative and commutative, and multiplication distributes over addition. Addition is idempotent since $x\oplus x=\max(x,x)=x$ for all $x\in\mathbb{R}_{+}$, and thus not invertible. It induces a partial order by the rule: $x\leq y$ if and only if $x\oplus y=y$, which is in agreement with the natural linear order on $\mathbb{R}_{+}$. With these properties, the system $\langle\mathbb{R}_{+},0,\oplus\rangle$ forms an idempotent Abelian semigroup with identity.

With usual multiplication, the system $\langle\mathbb{R}_{+},1,\times\rangle$ has the structure of an Abelian group where powers with rational (and even real) exponents are well defined, which means that this system is radicable (algebraically complete). In what follows, the multiplication sign $\times$ is omitted as in the standard algebra to save writing. Under the above properties, the system $\langle\mathbb{R}_{+},0,1,\oplus,\times\rangle$ is commonly classified as a linearly ordered idempotent radicable semifield and referred to as max-algebra.

Both addition and multiplication are monotone in each argument: if the inequality $x\leq y$ holds for some $x,y\in\mathbb{R}_{+}$, then the inequalities $x\oplus z\leq y\oplus z$ and $xz\leq yz$ are valid for any $z\in\mathbb{R}_{+}$ as well. Furthermore, it results from the inequality $x\leq y$ with $x,y\neq 0$ that $x^{q}\geq y^{q}$ if $q\leq 0$ and $x^{q}\leq y^{q}$ if $q>0$.

Matrices over max-algebra are introduced in the usual way; addition and multiplication of compatible matrices as well as multiplication of matrices by scalars follow the standard entrywise rules where the arithmetic addition $+$ is replaced by $\oplus=\max$ (whereas the multiplication does not change). The monotonicity of scalar operations extends to the matrix operations, where the inequalities are understood entrywise.

The transpose of a matrix $\bm{A}$ is denoted by $\bm{A}^{T}$. The matrices which consist of one column are vectors, and of one row are transposed vectors. The set of matrices of $m$ rows and $n$ columns is denoted by $\mathbb{R}_{+}^{m\times n}$, and the set of column vectors with $n$ entries is by $\mathbb{R}_{+}^{n}$.

The zero matrix denoted by $\bm{0}$ and the identity matrix denoted by $\bm{I}$ are defined in the same way as in conventional algebra. A matrix without zero rows (columns) is called row-regular (column-regular), and a vector without zero entries is called regular. The matrices without zero entries and regular vectors are also called positive.

A vector $\bm{y}$ is collinear to vector $\bm{x}$, if $\bm{y}=c\bm{x}$ for some $c\in\mathbb{R}_{+}$.

For any nonzero matrix $\bm{A}=(a_{ij})$ from the set $\mathbb{R}_{+}^{m\times n}$, its multiplicative conjugate transpose (or simply conjugate) is the matrix $\bm{A}^{-}=(a_{ij}^{-})$ in $\mathbb{R}_{+}^{n\times m}$ where $a_{ij}^{-}=a_{ji}^{-1}$ if $a_{ji}\neq 0$, and $a_{ij}^{-}=0$ otherwise. If a matrix $\bm{A}$ is row-regular, then the following inequality obviously holds:

For any nonzero vector $\bm{x}=(x_{j})$ from $\mathbb{R}_{+}^{n}$, its conjugate is the row vector $\bm{x}^{-}=(x_{j}^{-})$ where $x_{j}^{-}=x_{j}^{-1}$ if $x_{j}\neq 0$, and $x_{j}^{-}=0$ otherwise. If a vector $\bm{x}$ is regular, then the following matrix inequality and scalar equality are valid:

(where the equality holds for any nonzero vector $\bm{x}$).

For any square matrix $\bm{A}=(a_{ij})$ from $\mathbb{R}_{+}^{n\times n}$, the nonnegative integer powers represent repeated multiplication of the matrix by itself, defined by $\bm{A}^{0}=\bm{I}$ and $\bm{A}^{p}=\bm{A}\bm{A}^{p-1}$ for all integer $p>0$. The trace of $\bm{A}$ is given by

For any matrix $\bm{A}\in\mathbb{R}_{+}^{n\times n}$, a trace function is introduced to serve as a tropical analogue of the matrix determinant in the form

If the condition $\mathop{\mathrm{missing}}{Tr}(\bm{A})\leq 1$ holds, then the Kleene star operator is defined to map the matrix $\bm{A}$ into the matrix

Moreover, under the same condition, the inequality

is valid for all integer $p\geq 0$, from which it follows directly that

The spectral radius of a matrix $\bm{A}\in\mathbb{R}_{+}^{n\times n}$ is given by

Consider a matrix $\bm{A}=(a_{ij})$ in $\mathbb{R}_{+}^{m\times n}$ and vector $\bm{x}=(x_{j})$ in $\mathbb{R}_{+}^{n}$. With the notation $\bm{1}=(1,\ldots,1)^{T}$, tropical analogues of the matrix and vector norms are defined as

We conclude the overview with two inequalities that appear in the derivation of the solution of optimization problems in what follows. Suppose $\bm{A}\in\mathbb{R}_{+}^{m\times n}$ is a given matrix and $\bm{d}\in\mathbb{R}_{+}^{m}$ is a given vector, and consider the problem to find all vectors $\bm{x}\in\mathbb{R}_{+}^{n}$ that satisfy the inequality

Solutions of (11) are known under various assumptions in different forms. We use a solution suggested by the following assertion (see, e.g. [27]).

As a consequence of the lemma, the solution of the equation $\bm{A}\bm{x}=\bm{d}$, if exists, can be represented as a family of solutions each defined by the vector inequality $\bm{x}\leq(\bm{d}^{-}\bm{A})^{-}$ where one scalar inequality is replaced by an equality.

Assume that for a given square matrix $\bm{B}\in\mathbb{R}_{+}^{n\times n}$, we need to find all regular solutions $\bm{x}\in\mathbb{R}_{+}^{n}$ to the inequality

A complete solution of (12) can be obtained as follows [27, 28].

Let us consider a problem to minimize a conjugate quadratic (or pseudoquadratic) vector form subject to a linear constraint. Given matrices $\bm{A},\bm{B}\in\mathbb{R}_{+}^{n\times n}$, we find regular vectors $\bm{x}\in\mathbb{R}_{+}^{n}$ that attain the minimum

Complete solutions to the problem and its variations are proposed in [27, 28, 31, 32]. We use a solution in the form of the next statement.

We note that the above solution has a polynomial computational complexity in the dimension $n$. Specifically, it is shown in [31, 32] that this solution can be calculated with at most $O(n^{5})$ scalar operations.

We now formulate an equivalence statement that allows all solutions of problem (13) to be described using solutions of a vector inequality in the form of (12) and vice versa. This new result plays a key role in the development of solutions for the multiobjective optimization problems in subsequent sections.

In this subsection, we concentrate on optimization problems with the objective function in the form of Hilbert seminorm, which appear in the analysis of multiple solutions of the pairwise comparison problem. We consider constrained problems of maximization and minimization of Hilbert seminorm and present results that allow to find all solutions of the problems.

We start with a conventional form given by (3) for the Hilbert seminorm of a vector $\bm{x}=(x_{i})$. After rewriting it in terms of max-algebra, we obtain

We examine optimization problems with $\bm{x}^{-}\bm{1}\bm{1}^{T}\bm{x}$ as the objective function, which we refer to as a tropical representation of the multiplicative Hilbert seminorm or simply as Hilbert seminorm.

First, we suppose that given a matrix $\bm{B}\in\mathbb{R}_{+}^{n\times n}$, we seek for regular solutions $\bm{x}\in\mathbb{R}_{+}^{n}$ of the constrained maximization problem

A solution to problem (16) can be obtained as follows (see [34]).

It is not difficult to see that the most computationally intensive component of the solution is the calculation of the Kleene star matrix $\bm{B}^{\ast}$. This calculation can take no more that $O(n^{4})$ scalar operations, which determines the computational complexity involved in the solution.

Another problem of interest is to find regular vectors $\bm{x}$ that achieve the minimum

The statement below offers a solution to problem (17), obtained by applying Theorem 3 with substitution $\bm{A}=\bm{1}\bm{1}^{T}$ (see [35] for a solution of the problem with an extended system of constraints).

The computational complexity of the solution is shown in [35] to be $O(n^{4})$.

Let us examine problems (16) and (17) under additional conditions to implement an improved technique of evaluating the best and worst differentiating solutions of the pairwise comparison problem. We add to both problems a normalization constraint on the solution vector $\bm{x}$ in the form

We now concentrate on finding extremal (minimal and maximal) normalized solutions of problems (16) and (17). To solve the problems with normalization constraint, one can refine the results of Lemmas 5 and 6 and then find the extremal solutions. Below we offer direct solutions to the problems, which use less specific assumptions and involve less complicated calculations.

Suppose that we need to find the minimal solution of problem (16) with the normalization constraint added. The problem takes the following form:

The next statement improves the result of Lemma (5) and extends it to matrices that may have zero entries.

We turn to the derivation of the maximal solution to the following minimization problem obtained from (17) by adding the normalization constraint:

A complete solution of the problem is given by the next statement.

Let us verify that the solution $(\bm{1}^{T}\bm{B}^{\ast})^{-}$ of the minimization problem (19) is greater or equal to any solution of the maximization problem (18). Indeed, with the equality $(\bm{1}^{T}\bm{B}^{\ast})^{-}=\bm{B}^{\ast}(\bm{1}^{T}\bm{B}^{\ast})^{-}$, we have for each $k=1,\ldots,n$ that

which shows that all normalized columns of the matrix $\bm{B}^{\ast}$, including the solution vectors of problem (18), are less or equal to the solution of (19).

To conclude this section, we note that the obtained solutions to both maximization and minimization problems involve the calculation of the Kleene star matrix $\bm{B}^{\ast}$ as the main component, and thus have the complexity $O(n^{4})$.

We start with the max-ordering solution technique, which leads to the solution of problem (7) over the feasible set $X_{0}$ given by (6).

In terms of max-algebra, the set $X_{0}$ is the set of regular vectors $\bm{x}$ that solve the inequality $\bm{B}\bm{x}\leq\bm{x}$. The objective function at (7) takes the form

Combining the objective function with the constraint leads to the problem