A direct solution of tropical polynomial optimization problems

Nikolai Krivulin

Published 2020-02-08Version 1

We consider polynomial optimization problems formulated in the framework of tropical algebra, where the objective function to minimize and constraints are given by tropical analogues of Puiseux polynomials defined on linearly ordered, algebraically complete (radicable) idempotent semifield (i.e., semiring with idempotent addition and invertible multiplication). To solve the problems, we apply a technique that introduces a parameter to represent the minimum of the objective function, and then reduces the problem to a system of parametrized inequalities. The existence conditions for solutions of the system are used to evaluate the minimum, and the corresponding solutions of the system are taken as a complete solution of the polynomial optimization problem. With this technique, we derive a complete solution of the problems in one variable in a direct analytical form, and show how the solution can be obtained in the case of polynomials in more than one variables. Computational complexity of the solution is estimated, and applications of the results to solve real-world problems are briefly discussed.