TY - JOUR

T1 - Complete algebraic solution of multidimensional optimization problems in tropical semifield

AU - Кривулин, Николай Кимович

N1 - Conference code: 16

PY - 2018/10

Y1 - 2018/10

N2 - 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.

AB - 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.

KW - tropical semifield

KW - tropical optimization

KW - matrix sparsification

KW - complete solution

KW - backtracking

KW - Backtracking

KW - Tropical semifield

KW - Complete solution

KW - LINEAR CONSTRAINTS

KW - Tropical optimization

KW - Matrix sparsification

U2 - 10.1016/j.jlamp.2018.05.002

DO - 10.1016/j.jlamp.2018.05.002

M3 - Article

VL - 99

SP - 26

EP - 40

JO - Journal of Logical and Algebraic Methods in Programming

JF - Journal of Logical and Algebraic Methods in Programming

SN - 2352-2208

T2 - The 16th International Conference on Relational and Algebraic Methods in Computer Science

Y2 - 15 May 2017 through 18 May 2017

ER -