Title: Complete algebraic solution of multidimensional optimization problems in tropical semifield,
Abstract: We consider multidimensional optimization problems that are formulated in the
framework of tropical mathematics to minimize functions defined on vectors over
a tropical semifield (a semiring with idempotent addition and invertible
multiplication). The functions, given by a matrix and calculated through
multiplicative conjugate transposition, are nonlinear in the tropical
mathematics sense. We start with known results on the solution of the problems
with irreducible matrices. To solve the problems in the case of arbitrary
(reducible) matrices, we first derive the minimum value of the objective
function, and find a set of solutions. We show that all solutions of the
problem satisfy a system of vector inequalities, and then use these
inequalities to establish characteristic properties of the solution set.
Furthermore, all solutions of the problem are represented as a family of
subsets, each defined by a matrix that is obtained by using a matrix
sparsification technique. We describe a backtracking procedure that allows one
to reduce the brute-force generation of sparsified matrices by skipping those,
which cannot provide solutions, and thus offers an economical way to obtain all
subsets in the family. Finally, the characteristic properties of the solution
set are used to provide complete solutions in a closed form. We illustrate the
results obtained with simple numerical examples.