Optimization problems over tropical semifields: Algebraic solutions and application examples

Результат исследований: Материалы конференцийтезисы


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.
Язык оригиналаанглийский
СостояниеОпубликовано - июл 2016
Событие7th European Congress of Mathematics - Technische Universität Berlin, Berlin, Германия
Продолжительность: 18 июл 201622 июл 2016


Конференция7th European Congress of Mathematics
Сокращенный заголовок7ECM
Адрес в сети Интернет


Предметные области Scopus

  • Теория оптимизации
  • Алгебра и теория чисел
  • Теория управления и исследование операций


Кривулин, Н. К. (2016). Optimization problems over tropical semifields: Algebraic solutions and application examples. 616. Выдержка из 7th European Congress of Mathematics, Berlin, Германия.