About one recursive way to construct an effective solution to an $N$-criteria problem

V. I. Zhukovskii ; L. V. Zhukovskaya ; L. V. Smirnova

Taurida Journal of Computer Science Theory and Mathematics, no. 2 (2024), pp. 7-13

Résumé

Often in publications on game and multicriteria problems, all criteria are quadratic forms. It is for such problems that a recursive method for constructing a Pareto-maximal (effective) alternative is proposed. The article considers the $N$-criteria problem \begin{equation*} \Gamma = \left\langle \mathbb{R}^{nN}, \left\{J_i (u)\right\}_{i\in \mathbb{N}}\right\rangle. \end{equation*} Here, the solutions (alternatives) $u = (u_1, \ldots, u_N)$ are a column vector from the set $\mathbb{R}^{nN}$, $i$ criterion is \begin{equation*} J_i (u) = \sum_{j=1}^{N} u_j'D_{ij} u_j + 2 \sum_{j=1}^{N} d_{ij}' u_j \quad (i\in \mathbb{N}), \end{equation*} the constant $n\times n$-matrices $D_{ij}$ are symmetric, the stroke on top means the transposition operation ($u_i'$ — $n$-vector-string), $d_{ij}'$ — constant $n$-vector-string. It is assumed that the quadratic form $u_i'D_{ii} u_i$ is definitely positive ($D_{ii} > 0$), and the quadratic form $u_i'D_{ij} u_i$ is definitely negative $(D_{ij} 0$, $j \neq i)$. Problem $\Gamma$ can be considered as a mathematical model of an industrial cluster which includes $N$ productions. Moreover, each production $i$ seeks to increase its own profit ($D_{ii} > 0$), focusing on the opposition of all others ($D_{ij} 0$, $j \neq i$). The possibility of jointly choosing an effective alternative is being considered. Definition. The alternative $u^n = (u_1^n, \ldots, u_N^n) \in \mathbb{R}^{nN}$ is called the Pareto-maximal (effective) for problem $\Gamma$ if, under $\forall u\in \mathbb{R}^{nN}$, the system of inequalities \begin{equation*} J_i(u) \geqslant J_i(u^n) \quad (i\in \mathbb{N}) \end{equation*} is incompatible, of which at least one is strict. As a result of the transformation of the linear convolution of criteria $q(u, \alpha) = \sum\limits_{j=1}^N \alpha_j J_j (u)$ ($\alpha_i = \mathrm{const} > 0$), of a recursive search for the values of numbers $\alpha^* = (1, \alpha_2^*, \ldots, \alpha_N^*)$ and of using Karlin's lemma: An alternative $u^n$ that satisfies the condition \begin{equation*} \max\limits_{u \in \mathbb{R}^{nN}} \sum\limits_{i=1}^N \alpha_i J_i (u) = \sum\limits_{i=1}^N \alpha_i J_i (u^n), \end{equation*} for some $\alpha_1, \ldots, \alpha_N$ is Pareto-maximal for problem $\Gamma$, the validity of the following statement has been established. Statement. Let the $n\times n$-matrices in the problem $\Gamma$ be \begin{equation*} D_{ii} > 0, \;\; D_{ij} 0 \quad (i, j = 1, \ldots, N; i\neq j) \end{equation*} and the largest roots of the characteristic equations $\text{det} [D_{ij} - \lambda E_n] = 0 $ satisfy the condition $\Lambda_{11} \Lambda_{22} \lambda_{12} \lambda_{21}$, then the effective solution of the problem $\Gamma$ has the form \begin{equation*} u^n_j = - D^{-1}_{j} (\alpha^*) d_{j} (\alpha^*) \quad (j \in \mathbb{N}). \end{equation*}

Détail

Mots-clés : multicriteria problem
Keywords: alternative, Pareto optimality, efficiency, recursion.