Direct algebraic solutions to tropical optimization problems

Research output: Contribution to conferenceAbstractpeer-review


Multidimensional optimization problems are considered within the framework of tropical (idempotent) algebra. The problems consist of minimizing or maximizing functions defined on vectors of a finite-dimensional semimodule over an idempotent semifield, and may have constraints in the form of linear equations and inequalities. The objective function can be either a linear function or a nonlinear function that is given by the vector operator of multiplicative conjugate transposition. We start with an overview of known optimization problems and related solution methods. Certain problems that were originally stated in different terms, but can readily be reformulated in the tropical algebra setting, are also included.

First, we present problems that have linear objective functions and thus are idempotent analogues of those in conventional linear programming. Then, problems with nonlinear objective functions are examined, including Chebyshev and Chebyshev-like approximation problems, problems with minimization and maximization of span seminorm, and problems that involve the evaluation of the spectral radius of a matrix. Some of these problems admit complete direct solutions given in an explicit vector form. The known solutions to other problems are obtained in an indirect form of iterative algorithms that produce a particular solution if any or show that there is no solution.

Furthermore, we consider new optimization problems that extend certain known problems to take into account more general objective functions and more complicated systems of constraints. To obtain direct, explicit solutions to the new problems, we propose algebraic approaches, which offer the results in a compact vector form that is suitable for both further analysis and practical implementation, and guarantees low computational complexity of the solutions. For many problems, the approaches yield complete solutions to the problems of interest. The solution of certain problems without constraints involves obtaining sharp lower or upper bounds for the objective function. We use the bound in an equation for the function, which is solved to find all vectors that yield the bound. To extend the solution to problems with linear equation and inequality constraints, we first obtain a general solution to the equation or inequality, and then substitute it into the function to arrive at one of the unconstrained problems with known solution. To solve other problems, with and without constraints, we introduce an auxiliary variable to indicate the minimum value of the objective function. The problem is reduced to the solving of a linear inequality with a parameterized matrix, where the auxiliary variable plays the role of a parameter. We exploit the existence condition for solutions of the inequality to evaluate the parameter, and then take the general solution of the inequality as a complete solution to the initial optimization problem. We conclude with a brief discussion of application of the result to solve real-world problems in job scheduling, location analysis, decision making and other fields.
Original languageEnglish
StatePublished - 2014
EventThe 19th International Linear Algebra Society (ILAS) Conference - Seoul, Korea, Republic of
Duration: 6 Aug 20149 Aug 2014


ConferenceThe 19th International Linear Algebra Society (ILAS) Conference
CountryKorea, Republic of
Internet address

Scopus subject areas

  • Mathematics(all)


  • tropical algebra
  • idempotent semifield
  • optimization problem
  • nonlinear objective function
  • linear constraint

Fingerprint Dive into the research topics of 'Direct algebraic solutions to tropical optimization problems'. Together they form a unique fingerprint.

Cite this