Algebraic Solution of Tropical Polynomial Optimization Problems

Nikolai Krivulin
Additional contact information
Nikolai Krivulin: Faculty of Mthematics and Mechanics, St. Petersburg State University, Universitetskaya Emb. 7/9, 199034 St. Petersburg, Russia

Mathematics, 2021, vol. 9, issue 19, 1-18

Abstract: 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.

Keywords: tropical algebra; idempotent semifield; tropical Puiseux polynomial; constrained polynomial optimization problem; box constraint; variable elimination (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/9/19/2472/pdf (application/pdf)
https://www.mdpi.com/2227-7390/9/19/2472/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:9:y:2021:i:19:p:2472-:d:649581

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().