Optimization problems over tropical semifields: Algebraic solutions and application examples

Research output: Contribution to conferenceAbstractpeer-review


We consider multidimensional optimization problems, formulated in the framework of tropical (idempotent) mathematics to minimize or maximize functions defined on vectors over idempotent semifields. The objective functions can be linear or nonlinear in the tropical mathematics sense; the problems can have constraints in the form of tropical linear vector equalities and inequalities. We start with a brief overview of known optimization problems and existing solution methods. Some of the problems are solved directly in an explicit form under fairly general assumptions, whereas other problems have only algorithmic solutions in the form of iterative computational procedures, which produce a particular solution, or indicate that no solution exist. Furthermore, we examine new unconstrained and constrained problems with nonlinear objective functions, which are defined using multiplicative conjugate transposition of vectors. Examples include problems of Chebyshev approximation, problems of minimizing the span seminorm, and problems with evaluating the tropical spectral radius of a matrix. To solve the problems, we propose new techniques based on the reduction of the problem to parametrized systems of inequalities, the derivation sharp bounds for the objective function, and the application of extremal properties of the spectral radius. By using these techniques, we offer direct exact solutions of the problems in a compact vector form, which is ready for further analysis and practical implementation. For some problems, the solutions obtained are complete solutions. Finally, applications of the results to problems in Chebyshev approximation, project scheduling, location analysis and decision making are discussed.
Original languageEnglish
StatePublished - Jul 2016
Event7th European Congress of Mathematics - Technische Universität Berlin, Berlin, Germany
Duration: 18 Jul 201622 Jul 2016


Conference7th European Congress of Mathematics
Abbreviated title7ECM
Internet address

Scopus subject areas

  • Control and Optimization
  • Algebra and Number Theory
  • Management Science and Operations Research

Fingerprint Dive into the research topics of 'Optimization problems over tropical semifields: Algebraic solutions and application examples'. Together they form a unique fingerprint.

Cite this