TY - JOUR

T1 - Algebraic solution of tropical polynomial optimization problems

AU - Krivulin, Nikolai

N1 - Krivulin N. Algebraic Solution of Tropical Polynomial Optimization Problems. Mathematics. 2021; 9(19):2472. https://doi.org/10.3390/math9192472

PY - 2021/10/3

Y1 - 2021/10/3

N2 - We consider constrained optimization problems defined in the tropical algebra setting on a linearly ordered, algebraically complete (radicable) idempotent semifield (a semiring with idempotent addition and invertible multiplication). The problems are to minimize the objective functions given by tropical analogues of multivariate Puiseux polynomials, subject to box constraints on the variables. A technique for variable elimination is presented that converts the original optimization problem to a new one in which one variable is removed and the box constraint for this variable is modified. The novel approach may be thought of as an extension of the Fourier–Motzkin elimination method for systems of linear inequalities in ordered fields to the issue of polynomial optimization in ordered tropical semifields. We use this technique to develop a procedure to solve the problem in a finite number of iterations. The procedure includes two phases: backward elimination and forward substitution of variables. We describe the main steps of the procedure, discuss its computational complexity and present numerical examples.

AB - We consider constrained optimization problems defined in the tropical algebra setting on a linearly ordered, algebraically complete (radicable) idempotent semifield (a semiring with idempotent addition and invertible multiplication). The problems are to minimize the objective functions given by tropical analogues of multivariate Puiseux polynomials, subject to box constraints on the variables. A technique for variable elimination is presented that converts the original optimization problem to a new one in which one variable is removed and the box constraint for this variable is modified. The novel approach may be thought of as an extension of the Fourier–Motzkin elimination method for systems of linear inequalities in ordered fields to the issue of polynomial optimization in ordered tropical semifields. We use this technique to develop a procedure to solve the problem in a finite number of iterations. The procedure includes two phases: backward elimination and forward substitution of variables. We describe the main steps of the procedure, discuss its computational complexity and present numerical examples.

KW - tropical algebra

KW - idempotent semifield

KW - tropical Puiseux polynomial

KW - constrained polynomial optimization problem

KW - box constraint

KW - variable elimination

KW - tropical algebra

KW - idempotent semifield

KW - tropical Puiseux polynomial

KW - constrained polynomial optimization problem

KW - box constraint

KW - variable elimination

UR - https://arxiv.org/abs/2002.03168

UR - https://www.mdpi.com/2227-7390/9/19/2472

M3 - Article

VL - 9

JO - Mathematics

JF - Mathematics

SN - 2227-7390

IS - 19

M1 - 2472

ER -