TY - CONF

T1 - Solving multidimensional optimization problems over tropical semifields

AU - Кривулин, Николай Кимович

PY - 2015

Y1 - 2015

N2 - We consider multidimensional problems that are formulated in the framework of tropical mathematics to minimize or maximize functions defined on vectors of a finite-dimensional semimodule over an idempotent semifield. The objective functions can be linear or nonlinear; in the latter case they are defined using multiplicative conjugate transposition of vectors. Both unconstrained problems and problems with vector equality and inequality constraints are under consideration. We start with a brief overview of known problems and existing solution methods. Some of these problems can be solved directly in an explicit form under fairly general assumptions about the underlying semifield. For other problems, algorithmic solutions are known only in terms of particular semifields to have the form of iterative computational procedures, which produces a particular solution, or indicates that no solution exist. Furthermore, we examine new problems with nonlinear objective functions, including problems of Chebyshev approximation, problems of minimizing the span seminorm, and problems with evaluating the spectral radius of a matrix. To solve the problems, several techniques are proposed based on the reduction of the problem to a parameterized system of inequalities, the derivation sharp bounds for the objective function, and the application of extremal properties of the spectral radius. We use these technique to obtain direct exact solutions of the problems in a compact vector form, which is ready for further analysis and practical implementation. The solutions obtained are applied to solve optimization problems in Chebyshev approximation, project scheduling, location analysis and decision making.

AB - We consider multidimensional problems that are formulated in the framework of tropical mathematics to minimize or maximize functions defined on vectors of a finite-dimensional semimodule over an idempotent semifield. The objective functions can be linear or nonlinear; in the latter case they are defined using multiplicative conjugate transposition of vectors. Both unconstrained problems and problems with vector equality and inequality constraints are under consideration. We start with a brief overview of known problems and existing solution methods. Some of these problems can be solved directly in an explicit form under fairly general assumptions about the underlying semifield. For other problems, algorithmic solutions are known only in terms of particular semifields to have the form of iterative computational procedures, which produces a particular solution, or indicates that no solution exist. Furthermore, we examine new problems with nonlinear objective functions, including problems of Chebyshev approximation, problems of minimizing the span seminorm, and problems with evaluating the spectral radius of a matrix. To solve the problems, several techniques are proposed based on the reduction of the problem to a parameterized system of inequalities, the derivation sharp bounds for the objective function, and the application of extremal properties of the spectral radius. We use these technique to obtain direct exact solutions of the problems in a compact vector form, which is ready for further analysis and practical implementation. The solutions obtained are applied to solve optimization problems in Chebyshev approximation, project scheduling, location analysis and decision making.

M3 - Abstract

SP - 2

T2 - SIAM Conference on Applied Algebraic Geometry

Y2 - 3 August 2015 through 7 August 2015

ER -