Solution of a tropical optimization problem with linear constraints
Nikolai Krivulin, V. N. Sorokin · Vestnik St Petersburg University Mathematics · 2015
An optimization problem is considered that is formulated in terms of tropical (idempotent) mathematics and consists in the minimization of a nonlinear function in the presence of linear constraints on the domain of admissible values. The objective function is defined on the set of vectors over an idempotent semifield by a matrix with the use of the operation of multiplicative conjugate transposition. The problem considered is a further generalization of several known problems in which the solution involves the calculation of the spectral radius of the matrix. This generalization implies the use of a more complicated objective function compared with that in the above-mentioned problems, and the imposition of additional constraints. To solve the new problem, an auxiliary variable is introduced that describes the minimum value of the objective function. Then the problem reduces to solving an inequality in which the auxiliary variable plays the role of a parameter. Necessary and sufficient conditions for the existence of solutions to the inequality are used to calculate the parameter, and then the general solution of the inequality is taken as a solution to the original optimization problem. Numerical examples of the solution of problems on the set of two-dimensional vectors are presented.