Solving a tropical optimization problem with linear constraints

Authors

  • Nikolay K. Krivulin St. Petersburg State University, Universitetskaya nab., 7-9, St. Petersburg, 199034, Russian Federation;
  • Vladimir N. Sorokin St. Petersburg State University, Universitetskaya nab., 7-9, St. Petersburg, 199034, Russian Federation;

Abstract

An optimization problem is considered in terms of tropical (idempotent) mathematics to minimize a nonlinear function subject to linear inequality constraints on the feasible solution set. The objective function is defined on a vector set over an idempotent semifield by using a matrix through multiplicative conjugate transposition. The considered problem is a further generalization of some known problems, involving the evaluation of the spectral radius of a matrix. The generalization implies the use of a more complicated objective function and the imposition of additional constraints. To solve the new problem, an auxiliary variable is introduced, which represents the minimum value of the objective function. Then, the problem is reduced to the solving of an inequality, where the auxiliary variable plays the role of a parameter. Necessary and sufficient conditions for the existence of the solution are used to calculate the parameter, and the general solution of the inequality is then taken as a solution of the initial optimization problem. Numerical examples of the solution of problems on two-dimensional vectors are provided. Refs 20.

Keywords:

tropical mathematics, idempotent semifield, spectral radius, linear inequality, optimization problem, complete solution

Downloads

Download data is not yet available.

Published

2015-11-01

How to Cite

Krivulin, N. K., & Sorokin, V. N. (2015). Solving a tropical optimization problem with linear constraints. Vestnik of Saint Petersburg University. Mathematics. Mechanics. Astronomy, 2(4), 541–552. Retrieved from https://math-mech-astr-journal.spbu.ru/article/view/11191

Issue

Section

Mathematics