## Tropical Optimization Problems ∗

## Nikolai Krivulin † ‡

## Abstract

We consider optimization problems that are formulated and solved in the framework of tropical mathematics. The problems consist in minimizing or maximizing functionals defined on vectors of finite-dimensional semimodules over idempotent semifields, and may involve constraints in the form of linear equations and inequalities. The objective function can be either a linear function or nonlinear function calculated by means of multiplicative conjugate transposition of vectors. We start with an overview of known tropical optimization problems and solution methods. Then, we formulate certain new problems and present direct solutions to the problems in a closed compact vector form suitable for further analysis and applications. For many problems, the results obtained are complete solutions.

Key-Words: idempotent semifield, tropical optimization, nonlinear objective function, linear constraints, Chebyshev approximation.

MSC (2010): 65K10, 15A80, 65K05, 90C48, 41A50

## 1 Introduction

Tropical (idempotent) mathematics presents an area of applied mathematics that focuses on the theory and applications of semirings with idempotent addition. Among the first works, which laid the foundation for the area, were the pioneering papers by Pandit [1], Cuninghame-Green [2], Giffler [3] and Hoffman [4], dating back to the early 1960s.

The classical works published at the same time or somewhat earlier by Kleene [5], Bellman [6], and Bellman and Karush [7, 8] also served as an essential prerequisite. Specifically, a significant effect was exerted on the

∗ Advances in Economics and Optimization: Collected Scientific Studies Dedicated to the Memory of L. V. Kantorovich (L. A. Petrosyan, J. V. Romanovsky, D. W. K. Yeung, eds), pp. 195-214, Nova Science Publishers, New York, 2014.

† Faculty of Mathematics and Mechanics, Saint Petersburg State University, 28 Universitetsky Ave., Saint Petersburg, 198504, Russia, nkk@math.spbu.ru.

‡ The work was supported in part by the Russian Foundation for Humanities under Grant #13-02-00338.

area by the Bellman-Karush maximum transform. This transform, which was initially introduced in [7] in a multiplicative form, has taken an additive form in [8] and in many later publications. The additive form of the transform is in direct connection with the theory of support functions in convex optimization [9]. Note that this additive form was also proposed by Romanovsky [10].

A notable contribution to the development of the area was made by the Leningrad (St. Petersburg) researchers N. N. Vorob'ev, J. V. Romanovsky and A. A. Korbut. In the paper [11] published in 1963, Vorob'ev provided a groundwork for the theory of linear operators on extremal spaces, which were defined as vector spaces over idempotent semifields with the operations of maximum and minimum in the role of addition.

Then came the works [12, 13, 14, 15], in which Romanovsky studied asymptotic properties of solutions in dynamic programming problems and obtained an idempotent analogue for the Gelfand spectral radius theorem for bounded linear operators in Banach spaces. These results have proved to be conceptually close to the theory of the extremal spaces, which was further developed by Vorob'ev [16, 17] and Korbut [18, 19].

An extensive advancement in the theory and applications of tropical mathematics was achieved by V. P. Maslov and his colleagues, who have introduced idempotent functional analysis as a new important field within the area. The results obtained by the Maslov scientific school and published in the monographs by Maslov and Samborski˘ ı [20], Maslov and Kolokoltsov [21], Kolokoltsov and Maslov [22], as well as in many research papers, have provided a strong analytical framework for the contemporary tropical mathematics.

In the last few decades, tropical mathematics has received considerable attention as both a powerful mathematics apparatus and a flexible application tool. Advances in the theory and applications have resulted in a great many publications, including the monographs by Cuninghame-Green [23], Carr´ e [24], U. Zimmermann [25], Baccelli et al. [26], Golan [27], Heidergott, Olsder and van der Woude [28], Gondran and Minoux [29], Krivulin [30], Butkoviˇ c [31], McEneaney [32], and in a large amount of contributed papers.

Optimization problems, which can be formulated and solved in terms of tropical mathematics, form an important research domain within the area. These problems arise in many real-world applications in job scheduling, location analysis, transportation networks, decision making, discrete event dynamic systems, and in other fields.

Optimization problems have been examined even in the early publications [2, 4]. Since that time a number of studies that investigate optimization problems in the context of tropical mathematics has been published, which includes the monographs [23, 25, 30, 31].

Tropical optimization problems are commonly formulated to minimize or maximize functionals defined on vectors of a finite-dimensional semimodule

over an idempotent semifield, and may include additional constraints in the form of equations and inequalities. Some problems have both the objective function and constraints that are linear in the sense of tropical mathematics. These problems, which can be considered as direct analogues to linear programming problems, were examined in [4, 33, 25].

In another class of problems [34, 23, 25], the constraints are linear, but the objective functions are not. In these problems, the objective function can usually be written by means of a multiplicative conjugate transposition operator, which does not preserve linearity.

To solve the problems considered, a variety of methods were proposed. Some problems in a rather general setting can be completely solved in an explicit form [4, 34, 33, 25]. For other problems, only algorithmic solutions are known in the form of iterative numerical procedures that produce a particular solution or indicate that no solution exists [35, 36].

In this chapter, we offer a brief overview of known tropical optimization problems and solution methods. We formulate certain new problems and present direct solutions to the problems in a closed compact vector form suitable for further analysis and applications. For many problems, the results obtained are complete solutions.

The chapter is organized as follows. In Section 2, we briefly outline the definitions, notation, and key facts of tropical mathematics to be used in the subsequent sections. Section 3 is devoted to known optimization problems. We present new tropical optimization problems and describe obtained solutions in Section 4. The chapter concludes with an extensive list of references on the topic considered.

## 2 Preliminary Definitions, Notation and Results

We start with a brief overview of the basic elements of tropical (idempotent) mathematics to provide a formal unifying framework for formulating tropical optimization problems and representing the solutions to the problems in the subsequent sections. The overview mainly follows the notation system and results developed by Krivulin [37, 38, 39, 30], which underlie the solutions presented.

The literature on the topic offers a wide range of publications written in varied styles and available on both the introductory and advanced levels. Specifically, the recent monographs: Kolokoltsov and Maslov [22], Golan [27], Heidergott, Olsder and van der Woude [28], Gondran and Minoux [29, 31], Butkoviˇ [31]; and overview papers: Kolokoltsov [40], Litvinov [41], c Akian, Bapat and Gaubert [42], provide a broad source for further reading.

## 2.1 Idempotent Semifield

An idempotent semifield is an algebraic system ( X , ⊕ ⊗ , , 0 1 , ), where X is a nonempty set closed under addition ⊕ and multiplication ⊗ , and equipped with zero 0 and one 1 , such that ( X , ⊕ , 0 ) is a commutative idempotent monoid, ( X , ⊗ , 1 ) is an abelian group, multiplication distributes over addition, and 0 is absorbing for multiplication.

In addition, we assume the semifield to admit a linear order, which is consistent with the partial order induced by idempotent addition to define x ≤ y if and only if x ⊕ y = y . Moreover, the semifield is assumed to be algebraically complete (radicable), which implies that the equation x p = a has a root for all a ∈ X and every natural p .

Examples of the linearly ordered and algebraically complete idempotent semifield include R max + , = ( R ∪ {-∞} , max + , , -∞ , 0), R min + , = ( R ∪{ + ∞} , min + + , , ∞ , 0), R max , × = ( R + ∪{ } 0 , max , × , 0 1) and , R min , × = ( R + ∪{ + ∞} , min , × , + ∞ , 1), where R is the set of real numbers and R + = { x ∈ R | x &gt; 0 } .

Below, we drop the multiplication sign ⊗ for the brevity sake. The relation symbols and the optimization problems are thought of in terms of the linear order on the semifield.

## 2.2 Algebra of Matrices and Vectors

The set of matrices with m rows and n columns over X is denoted by X m n × . A matrix with all entries equal to 0 is the zero matrix. A matrix is column-regular (row-regular) if it has no zero columns (rows). A matrix that has no zero rows nor zero columns is called regular.

Addition and multiplication of conforming matrices and scalar multiplication are performed component-wise in the usual way, except that the ordinary scalar addition is replaced by ⊕ and the multiplication by ⊗ .

/negationslash

The multiplicative conjugate transpose of any nonzero matrix A = ( a ij ) ∈ X m n × is the matrix A -= ( a -ij ) ∈ X n × m , where a -ij = a -1 ji if a ji = 0 , and a -ij = 0 otherwise.

A matrix with only one column (row) is a column (row) vector. The set of column vectors of size n forms an idempotent semimodule over X and is denoted X n . A vector with all elements equal to 0 is the zero vector. A vector that has no zero elements is regular.

/negationslash

The multiplicative conjugate transpose of any nonzero vector x = ( x i ) ∈ X n is the row vector x -= ( x -i ), where x -i = x -1 i if x i = 0 , and x -i = 0 otherwise.

For any vector x ∈ X n and matrix A ∈ X m n × , idempotent analogues of the vector and matrix norms are given by

$$\| x \| = \bigoplus _ { i = 1 } ^ { n } x _ { i }, \quad \| \mathcal { A } \| = \bigoplus _ { i = 1 } ^ { m } \bigoplus _ { j = 1 } ^ { n } a _ { i j }.$$

With the vector 1 = ( 1 , . . . , 1 ) T , which has all components equal to 1 , we write

$$\| x \| = \mathbb { 1 } ^ { T } x, \quad \| A \| = \mathbb { 1 } ^ { T } A \mathbb { 1 }.$$

Consider square matrices of order n in X n × n . A matrix with 1 's on the diagonal and 0 's elsewhere is the identity matrix denoted I .

The trace of any matrix A = ( a ij ) is given by tr A = a 11 ⊕··· ⊕ a nn . To represent solutions to optimization problems below, we use a function that takes any matrix A to the scalar

$$\text{Tr} ( A ) = \text{tr} \, A \oplus \cdots \oplus \text{tr} \, A ^ { n }.$$

If the condition Tr( A ) ≤ 1 holds, we apply the asterate operator, which produces the matrix (sometimes called the Kleene star)

$$A ^ { * } = I \oplus A \oplus \cdots \oplus A ^ { n - 1 }.$$

If Tr( A ) = 1 , we form the matrix A + , which holds those columns of the matrix A × = AA ∗ that have 1 on the diagonal.

## 2.3 Linear Operators and Their Spectral Properties

Every matrix A ∈ X n × n defines a linear operator on X n , which is endowed with certain spectral properties. A scalar λ ∈ X and a nonzero vector x ∈ X n are corresponding eigenvalue and eigenvector of A if they satisfy the equation

$$A x = \lambda x.$$

The matrix A always possesses an eigenvalue that is calculated by the formula

$$\lambda = \bigoplus _ { m = 1 } ^ { n } \text{tr} ^ { 1 / m } ( A ^ { m } ).$$

Any other eigenvalue of A , if it exists, is not greater (in the sense of the order on X ) than λ , which is called the spectral radius of A .

All eigenvectors of the matrix A , which correspond to the spectral radius λ , are given by

$$x = ( \lambda ^ { - 1 } A ) ^ { + } u,$$

where u is any regular vector of appropriate size.

## 3 An Overview of Known Problems and Solution Methods

Multidimensional optimization problems form an important research domain in tropical mathematics, dating back to the early works by CuninghameGreen [2] and Hoffman [4]. These problems appear in various application

areas, including job scheduling [2, 34, 23, 25, 36, 43, 44, 45, 46, 47], location analysis [48, 49, 50], transportation networks [25, 43], decision making [51, 52, 53], and discrete event dynamic systems [54, 55, 56, 37].

In this section, we offer a brief overview of known tropical optimization problems and discuss existing solution methods. We consider problems of minimizing or maximizing both linear and nonlinear functionals defined on vectors in finite-dimensional semimodules over idempotent semifields, subject to constraints expressed as linear equations and inequalities. The overview covers the problems with nonlinear objective functions that are, or can be, written by means of multiplicative conjugate transposition of vectors. Our analysis of the literature shows that many problems, which are relevant to tropical optimization, have objective functions that admit this form.

Note that the problems with nonlinear objective functions are usually considered in a different way; these problems are formulated and solved either in the usual setting within the framework of ordinary mathematics [57, 36, 58, 59, 43], or in terms of two dual semifields R max + , and R min + , at once [34, 23, 45, 46].

In the description of the problems below, we use the capital letters A , B and C for known matrices and the lower case letters b , d , p and q for known vectors. The symbol x represents the unknown vector. The matrix and vector operations are thought of as defined in terms of an idempotent semifield. The minus sign in the exponent indicates multiplicative conjugate transposition of vectors and matrices.

Specifically, in terms of the real semifield R max + , , vector addition, matrixvector multiplication and scalar multiplication follow the standard rules, where the operations max and + play the respective roles of addition and multiplication. Multiplicative conjugate transposition of a vector implies replacing each element of the vector by its inverse (which coincides with its opposite in ordinary arithmetic), and transposition.

## 3.1 Problems with Linear Objective Functions

One of the first optimization problems defined and solved in terms of tropical mathematics is a formal analogue of linear programming problems, which takes the form

$$\minimize & \quad p ^ { T } x, \\ \text{subject to } & \ A x \geq d.$$

Exact general solutions to the problem are obtained under various assumptions concerning the idempotent semiring, in which context the problem is examined. Specifically, Hoffman [4] considered a rather general idempotent semiring and proposed a solution based on abstract extension of the duality principle in linear programming. Another general solution was established by U. Zimmermann [25] by means of a residual-based solution tech-

nique. The common approach in [4] was further developed by Superville [33] to examine the problem in the context of the semifield R max + , . The problem was also solved by Gavalec and K. Zimmermann [60] for the semifields R max + , and R max , × in the framework of max-separable functions.

The results of the theory of max-separable functions were applied by K. Zimmermann [57, 36, 58, 59, 43] to solve the problem with more constraints

$$\minimize & \quad p ^ { T } x, \\ & \text{subject to } \quad A x \leq d, \quad C x \geq b, \\ & \quad g \leq x \leq h. \\. &.$$

Under general conditions, an exact solution was obtained, which was, however, given in ordinary terms rather than in terms of tropical mathematics.

Butkoviˇ c [35], Butkoviˇ and Aminu [44, 47] studied a problem that has c constraints in the form of two-sided equation (with the unknown vector on both left and right sides), and can be written as

$$& \minimize \quad p ^ { T } x, \\ & \text{subject to } \quad A x \oplus b = C x \oplus d.$$

Specifically, a pseudo-polynomial algorithm was proposed in [44], which produces a solution if solutions exist or indicates that the problem has no solutions. The algorithm applies an alternating method proposed in [61] to replace the equality constraints by two opposite inequalities, which are alternately solved to achieve more and more accurate estimates for the solution. An heuristic approach that combines a search scheme providing approximate solutions with iterative procedures of solving low-dimensional problems with one or two unknown variables was developed in [47].

## 3.2 Problems with Nonlinear Objective Functions

The tropical optimization problems with nonlinear objective functions, in which nonlinearity results from the application of multiplicative conjugate transposition, form a rich class of various problems that arise in many applications. We divide the problems into a few groups according to the particular form of the objective function and the principal interpretation of the problems.

## 3.2.1 Chebyshev Approximation

Among the first problems with nonlinear objective functions was the problem, which is formulated in the form

$$\minimize & \quad ( A x ) ^ { - } p, \\ \text{subject to } & \ A x \leq p.$$

The problem was considered by Cuninghame-Green [34] in the context of approximation in the semifield R max + , with the Chebyshev metric. The problem required finding a vector x that gives the best underestimating approximation to a vector p by means of vectors Ax . A general solution in an explicit form was obtained based on the theory of linear operators on vectors over the semifield R max + , . A similar solution was provided by U. Zimmermann [25].

An unconstrained approximation problem formulated in terms of a general idempotent semifield was examined by Krivulin [30] in the form

$$\minimize \ ( A x ) ^ { - } p \oplus p ^ { - } A x.$$

To solve the problem, an approach was proposed, which involves the derivation of a sharp lower bound for the objective function. The form of this bound is exploited to construct vectors that produce the bound. The results obtained were applied to establish existence conditions and to describe all solutions in a closed vector form for the equation Ax = p . In addition, the following problems of both underestimating and overestimating approximation were solved as consequences of the results:

$$\minimize & \quad ( A x ) ^ { - } p, & \quad \minimize & \quad p ^ { - } A x, \\ \text{subject to } & \ A x \leq p ; & \quad \text{subject to } & \ A x \geq p.$$

Certain of the problems, which were originally formulated and solved in a different setting, can be represented in terms of tropical mathematics as problems with nonlinear objective functions and linear constraints and thus are also included in the overview. In particular, a constrained problem of the Chebyshev approximation in the semifield R max + , was examined in [36], where the problem was solved with a polynomial-time threshold-type algorithm. In terms of tropical mathematics, this problem can be written in the form

$$\minimize \quad & ( A x ) ^ { - } p \oplus p ^ { - } A x, \\ \text{subject to} \quad & g \leq x \leq h.$$

## 3.2.2 Problems with Span Seminorm

The problems examined by Butkoviˇ c and Tam [45, 46] in the context of the semifield R max + , had the objective function defined as the span seminorm, which calculates the maximum deviation between elements of a vector. Solutions to both minimization and maximization problems were obtained using a combined technique based on the representation in terms of both the semifield R max + , and its dual R min + , . Note that these problems can be described only in terms of the semifield R max + , as follows

$$\minimize \ 1 ^ { T } A x ( A x ) ^ { - } 1, \quad \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \$$

where 1 = ( 1 , . . . , 1 ) T is a vector of ones in the sense of R max + , .

## 3.2.3 A Problem of 'Linear-fractional' Programming

A minimization problem that has constraints in the form of a two-sided inequality, and that is written in terms of the semifield R max + , as

$$\minimize & \quad p ^ { T } x ( q ^ { T } x ) ^ { - 1 }, \\ \text{subject to } & \ A x \oplus b \leq C x \oplus d,$$

was investigated by Gaubert, Katz and Sergeev [62]. The problem, called a tropical linear-fractional programming problem, was solved by means of an iterative computational scheme that exploits the relationship established by Akian, Gaubert and Guterman [63] between the solutions to two-sided vector equations in the sense of R max + , and mean payoff games.

## 3.2.4 Extremal Property of the Spectral Radius

A problem examined by Cuninghame-Green [2] to minimize a functional defined on vectors over the semifield R max + , was apparently the first optimization problem, which arose in the context of tropical mathematics. With the use of multiplicative conjugate transposition, the problem can be represented in the form

$$\minimize \ x ^ { - } A x.$$

As one of the main result in [2], which gave impetus to further research on the spectral theory of linear operators in tropical mathematics, it was shown that the minimum in the problem is equal to the spectral radius λ of the matrix A and is attained at any eigenvector that corresponds to the radius. Moreover, explicit expressions were obtained to calculate the spectral radius and the eigenvector in terms of standard arithmetic operations. Similar results were provided by Engel and Schneider [64] and by Superville [33].

Furthermore, the above solution was extended and represented in more general terms of tropical mathematics by Cuninghame-Green [23]. Analogues results in a compact vector form using multiplicative conjugate transposition were proposed by Krivulin [37, 38, 30].

To find all vectors that yield the minimum in the problem, a computational approach was proposed in [23]. It consists in solving a linear programming problem and thus does not guarantee a direct solution in an explicit form.

Finally, Elsner and van den Driessche [51, 52] indicated that the solution set includes, in addition to the eigenvectors, all vectors x that satisfy the inequality Ax ≤ λ x . An iterative computational procedure was offered to obtain vectors from this solution set.

## 4 Some New Problems and Recent Results

In this part, we present several new problems [65, 66, 67, 68, 69, 70], which are formulated and solved in terms of a general algebraically complete linearly ordered idempotent semifield. If a complete solution to a problem is obtained, the solution is given below by an expression that represents a general vector describing all vectors in the solution set, and that is referred to as the general solution.

## 4.1 Chebyshev-like Approximation Problems

We start with constrained optimization problems with nonlinear objective functions that have the form similar to that in the Chebyshev approximation problems (1) and (2). One of the application areas for these problems is the single facility location problems in multidimensional spaces with Chebyshev distance under various constraints in the form of linear equalities and inequalities (see, e. g., [50, 68, 67]).

To solve the next two problems with simple boundary constraints, we apply a general approach which was proposed and developed in [37, 38, 30]. The approach involves the derivation of a sharp lower bound on the objective function and the use of this bound to obtain solution vectors.

First, consider the following problem: given vectors p q g h , , , ∈ X n , find regular vectors x ∈ X n such that

$$\minimize & \quad q ^ { - } x \oplus x ^ { - } p, \\ \text{subject to } & \quad g \leq x \leq h.$$

Theorem 1 ([68]) . Let x be the general regular solution to problem (5) , where p and q are regular vectors, g and h are vectors such that g ≤ h , and let ∆ = √ q -p .

Then, the minimum in (5) is equal to

$$\mu = \Delta \oplus q ^ { - } g \oplus h ^ { - } p,$$

and the general solution is given by

$$\mu ^ { - 1 } p \oplus g \leq x \leq ( \mu ^ { - 1 } q ^ { - } \oplus h ^ { - } ) ^ { - }.$$

Suppose that, given a matrix A ∈ X m n × and vectors p q , ∈ X m , g ∈ X n , the problem is to find regular vectors x ∈ X n that

$$\minimize \quad & q ^ { - } A x \oplus ( A x ) ^ { - } p, \\ \text{subject to} \quad & x \geq g.$$

Theorem 2 ([68]) . Let x be a regular solution to problem (6) , where A is a regular matrix, p and q are regular vectors, and let ∆ = √ ( A q ( -A ) - -) p .

Then, the minimum in (6) is equal to

$$\mu = \Delta \oplus q ^ { - } A g,$$

and attained at

$$x = \mu ( q ^ { - } A ) ^ { - }.$$

We now consider another problem with conditions that include a linear inequality with a matrix. Given vectors p q g h , , , ∈ X n and a matrix B ∈ X n × n , find regular vectors x ∈ X n that solve the problem

$$\minimize & \quad x ^ { - } p \oplus q ^ { - } x, \\ \text{subject to } & \ B x \oplus g \leq x, \\ & \quad x \leq h.$$

Note that the conditions in the problem can be represented in the equivalent form

$$B x & \leq x, \\ g & \leq x \leq h.$$

The solution of the problem follows an approach that is based on the general solution of linear inequalities obtained in [39, 30] and refined in [71]. We introduce an additional parameter, which indicates the minimum value of the objective function. The problem is then reduced to the solving of a linear inequality with a matrix that depends on the parameter. We exploit the existence condition for solutions of the inequality to evaluate the parameter, and then take the general solution to the inequality as the solution to the initial problem.

Theorem 3 ([67]) . Let x be the general regular solution to problem (7) , where B is a matrix such that Tr( B ) ≤ 1 , p is a nonzero vector, q and h are regular vectors, and g is a vector such that h B g -∗ ≤ 1 . Then, the minimum in (7) is equal to

$$\theta = ( q ^ { - } B ^ { * } p ) ^ { 1 / 2 } \oplus h ^ { - } B ^ { * } p \oplus q ^ { - } B ^ { * } g,$$

and the general solution is given by

$$x = B ^ { * } u, \quad g \oplus \theta ^ { - 1 } p \leq u \leq ( ( h ^ { - } \oplus \theta ^ { - 1 } q ^ { - } ) B ^ { * } ) ^ { - }.$$

As a consequence, we obtain a complete solution to the problem, which was partially solved in [50]. Consider a variant of problem (7) without the boundary constraints,

$$\minimize & \quad x ^ { - } p \oplus q ^ { - } x, \\ \text{subject to } \ B x \leq x.$$

Corollary 4 ([67]) . Let x be the general regular solution to problem (8) , where B is a matrix such that Tr( B ) ≤ 1 , p is a nonzero vector and q is a regular vector.

Then, the minimum in (8) is equal to

$$\theta = ( q ^ { - } B ^ { * } p ) ^ { 1 / 2 },$$

and the general solution is given by

$$x = B ^ { * } u, \quad \theta ^ { - 1 } p \leq u \leq \theta ( q ^ { - } B ^ { * } ) ^ { - }.$$

## 4.2 Problems with Span Seminorm

The problems, in which the objective function is defined through the span seminorm, appeared in the context of job scheduling [45, 46]. Minimization of the span seminorm solves scheduling problems in the just-in-time manufacturing. Maximization problems arise when the optimal schedule aims to spread the initiation or completion time of the jobs over the maximum possible time interval.

The solution to the problem without constraints uses the evaluation of lower or upper bounds on the objective function. To solve the problems with linear equation and inequality constraints, we first obtain a general solution to the equation or inequality, and then substitute it into the objective function to get an unconstrained problem with known solution.

## 4.2.1 Minimization Problems

We start with an unconstrained problem that presents a rather extended version of minimization problem (3). Given matrices A B , ∈ X m n × and vectors p q , ∈ X m , the problem is to find regular vectors x ∈ X n that

$$\minimize \ q ^ { - } B x ( A x ) ^ { - } p.$$

Theorem 5 ([69]) . Let x be a regular solution to problem (9) , where A is a row-regular matrix, B is a column-regular matrix, p is nonzero vector and q is regular vector.

Then, the minimum in (9) is equal to

$$\Delta = ( A ( q ^ { - } B ) ^ { - } ) ^ { - } p,$$

and attained at

$$x = \alpha ( q ^ { - } B ) ^ { - }, \quad \alpha > 0.$$

We now examine particular cases of problem (9). Suppose that B = A = I and p = q = 1 , where 1 denotes the vector having all elements equal to 1 , and consider the problem

$$\minimize \ 1 ^ { T } x x ^ { - 1 }.$$

Application of Theorem 5 shows that the problem has the minimum ∆ = 1 , which is attained at any vector x = α 1 , α &gt; 0 .

If we assume that A = B and p = q = 1 , then we arrive at problem (3). Theorem 5 allows us to obtain the solution to the last problem in a new compact vector form.

Corollary 6. Let x be a regular solution to problem (3) , where A is a regular matrix.

Then, the minimum in (3) is equal to

$$\Delta = ( A ( \mathbb { 1 } ^ { T } A ) ^ { - } ) ^ { - } \mathbb { 1 },$$

and attained at

$$x = \alpha ( 1 ^ { T } A ) ^ { - }, \quad \alpha > 0.$$

Consider a constrained problem: given matrices B C , ∈ X n × n , find regular vectors x ∈ X n such that

$$\minimize & \quad \mathbb { 1 } ^ { T } y y ^ { - 1 }, \\ \text{subject to} & \quad C x = y, \\ & \quad D x \leq x.$$

Theorem 7 ([69]) . Let x be a regular solution to problem (10) , where C is a regular matrix and D is a matrix such that Tr( D ) ≤ 1 . Then, the minimum in (10) is equal to

$$\Delta = ( C D ^ { * } ( 1 ^ { T } C D ^ { * } ) ^ { - } ) ^ { - } 1,$$

and attained at

$$x = \alpha D ^ { * } ( \mathbb { 1 } ^ { T } C D ^ { * } ) ^ { - }, \quad \alpha > 0.$$

## 4.2.2 Maximization Problems

We begin with an unconstrained problem. Given matrices A ∈ X m n × , B ∈ X l × n , and vectors p ∈ X m , q ∈ X l , we need to find regular vectors x ∈ X n that solve the problem

$$\maximize \ q ^ { - } B x ( A x ) ^ { - } p.$$

The following result offers a complete solution to (11) under fairly general conditions.

Theorem 8 ([66]) . Let x be the general regular solution to problem (11) , where A is a matrix with regular columns, B is a column-regular matrix, p and q are regular vectors. Then, the minimum in (11) is equal to

$$\Delta = q ^ { - } B A ^ { - } p,$$

and the general solution x = ( x i ) has components that are given by

/negationslash

$$x _ { k } & = \alpha a _ { k } ^ { - } p, \\ x _ { j } & \leq \alpha a _ { s j } ^ { - 1 } p _ { s }, \quad j \neq k,$$

where α &gt; 0 , and the indices k and s are defined by the conditions

$$k = \arg \max _ { 1 \leq i \leq n } q ^ { - } b _ { i } a _ { i } ^ { - } p, \quad s = \arg \max _ { 1 \leq i \leq m } a _ { i k } ^ { - 1 } p _ { i }.$$

Consider a special case of the problem. Assume that p = q = 1 . Then, we have

$$\mathbb { 1 } ^ { T } B x ( A x ) ^ { - } \mathbb { 1 } = \| B x \| \| ( A x ) ^ { - } \|, \quad \mathbb { 1 } ^ { T } B A ^ { - } \mathbb { 1 } = \| B A ^ { - } \|.$$

Under this assumption, problem (11) becomes

$$\maximize \ \| B x \| \| ( A x ) ^ { - } \|.$$

Application of Theorem 8 leads to the following result.

Corollary 9 ([66]) . Let x be the general regular solution to problem (12) , where A is a matrix with regular columns and B is a column-regular matrix. Then, the minimum in (12) is equal to

$$\Delta = \| B A ^ { - } \|,$$

and the general solution x = ( x i ) has components that are given by

/negationslash

$$x _ { k } & = \alpha \| a _ { k } ^ { - } \|, \\ x _ { j } & \leq \alpha a _ { s j } ^ { - 1 }, \quad j \neq k,$$

where α &gt; 0 , and the indices k and s are defined by the conditions

$$k = \arg \max _ { 1 \leq i \leq n } \| b _ { i } \| \| a _ { i } ^ { - } \|, \quad s = \arg \max _ { 1 \leq i \leq m } a _ { i k } ^ { - 1 }.$$

We now discuss the solution to constrained problems. Suppose that, given a matrix C ∈ X n × n , we need to solve the problem

$$\maximize & \quad q ^ { - } B x ( A x ) ^ { - } p, \\ \text{subject to } & \ C x \leq x.$$

It is known (see, e.g., [30]) that the inequality constraints have regular solutions if and only if Tr( C ) ≤ 1 . Under this condition, the general solution takes the form x = C u ∗ , where u is any regular vector. Problem (13) then reduces to the unconstrained problem

$$\maximize \ q ^ { - } B C ^ { * } u ( A C ^ { * } u ) ^ { - } p.$$

The last problem takes the form of (11), and thus is completely solved by Theorem 8.

In a similar way, we obtain the solution to the problem with equality constraints

$$\maximize \quad & q ^ { - } B x ( A x ) ^ { - } p, \\ \text{subject to } \quad C x = x.$$

Indeed, if the condition Tr( C ) = 1 holds, then the equation Cx = x has the general solution x = C u + , where u is any regular vector [30]. Substitution of the solution into the objective function again leads to a problem in the form of (11),

$$\maximize \ q ^ { - } B C ^ { + } u ( A C ^ { + } u ) ^ { - } p.$$

## 4.3 Problems with Evaluation of Spectral Radius

First, we return to problem (4), which admits a solution based on the extremal property of the spectral radius. A complete solution to the problem was given in [71] as a consequence of solution to a more general optimization problem. A direct complete solution to problem (4) is obtained in [70] in the following form.

Lemma 10. Let x be the general regular solution to problem (4) , where A is a matrix with spectral radius λ &gt; 0 .

Then, the minimum in (4) is equal to λ , and the general solution is given by

$$x = ( \lambda ^ { - 1 } A ) ^ { * } u, \quad u \in \mathcal { K } ^ { n }.$$

The proof of the statement is based on the derivation of a sharp lower bound for the objective function, accompanied by the development of the equation, which specifies the solution set for the problem. We then reduce the equation to an inequality and take the general solution to the inequality as a complete solution to the optimization problem.

Extensions of problem (4), which differ from (4) by more general form of the objective function and constraints, were examined in [72, 65], where general solutions were obtained under various assumptions.

Below, we offer complete direct solutions to certain new problems, which present further extensions of problem (4).

## 4.3.1 An Unconstrained Problem

Suppose that a matrix A ∈ X n × n , vectors p q , ∈ X n , and a scalar c ∈ X are given. Consider the problem of finding regular vectors x ∈ X n that

$$\minimize \ x ^ { - } A x \oplus x ^ { - } p \oplus q ^ { - } x \oplus c.$$

The problem is completely solved as follows.

Theorem 11 ([70]) . Let x be the general regular solution to problem (15) , where A is a matrix with spectral radius λ &gt; 0 and q is a regular vector. Denote

$$\mu = \lambda \oplus \bigoplus _ { m = 1 } ^ { n } ( q ^ { - } A ^ { m - 1 } p ) ^ { 1 / ( m + 1 ) } \oplus c.$$

Then, the minimum in (15) is equal to µ and the general solution is given by

$$x = ( \mu ^ { - 1 } A ) ^ { * } u, \quad \mu ^ { - 1 } p \leq u \leq \mu ( q ^ { - } ( \mu ^ { - 1 } A ) ^ { * } ) ^ { - }.$$

## 4.3.2 Problems with Constraints

Given matrices A B , ∈ X n × n , C ∈ X m n × , and vectors g ∈ X n , h ∈ X m , consider the problem to find regular vectors x ∈ X n that

$$\minimize & \quad x ^ { - } A x, \\ \text{subject to } & \ B x \oplus g \leq x, \\ & C x \leq h.$$

Theorem 12 ([65]) . Let x be the general regular solution to problem (16) , where A is a matrix with spectral radius λ &gt; 0 , B is a matrix such that Tr( B ) ≤ 1 . Suppose that C is a column-regular matrix and h is a regular vector such that h CB g -∗ ≤ 1 .

Then, the minimum in (16) is equal to

$$\theta = \bigoplus _ { k = 1 } ^ { n } \bigoplus _ { 0 \leq i _ { 0 } + i _ { 1 } + \cdots + i _ { k } \leq n - k } \text{tr} ^ { 1 / k } ( B ^ { i _ { 0 } } ( A B ^ { i _ { 1 } } \cdots A B ^ { i _ { k } } ) ( I \oplus g h ^ { - } C ) ),$$

and the general solution is given by

$$x = ( \theta ^ { - 1 } A \oplus B ) ^ { * } u, \quad g \leq u \leq ( h ^ { - } C ( \theta ^ { - 1 } A \oplus B ) ^ { * } ) ^ { - }.$$

In the case when C = 0 , problem (16) takes the form

$$\text{minimize} \quad & x ^ { - } A x, \\ \text{subject to} \quad & B x \oplus g \leq x.$$

Corollary 13 ([71, 65]) . Let x be the general regular solution to problem (17) , where A is a matrix with spectral radius λ &gt; 0 . Then, the minimum in (17) is equal to

$$\theta = \lambda \oplus \bigoplus _ { k = 1 } ^ { n - 1 } \bigoplus _ { 1 \leq i _ { 1 } + \dots + i _ { k } \leq n - k } \text{tr} ^ { 1 / k } ( A B ^ { i _ { 1 } } \cdots A B ^ { i _ { k } } ),$$

and the general solution is given by

$$x = ( \theta ^ { - 1 } A \oplus B ) ^ { * } u, \quad u \geq g.$$

Suppose that B = 0 and C = I . In this case, problem (16) becomes

$$\minimize & \quad x ^ { - } A x, \\ \text{subject to } & \quad g \leq x \leq h.$$

Corollary 14 ([65]) . Let x be the general regular solution to problem (18) , where A is a matrix with spectral radius λ &gt; 0 , g is a vector and h is a regular vector such that h g -≤ 1 . Then, the minimum in (18) is equal to

$$\theta = \lambda \oplus \bigoplus _ { k = 1 } ^ { n } ( h ^ { - } A ^ { k } g ) ^ { 1 / k },$$

and the general solution is given by

$$x = ( \theta ^ { - 1 } A ) ^ { * } u, \quad g \leq u \leq ( h ^ { - } ( \theta ^ { - 1 } A ) ^ { * } ) ^ { - }.$$

The next problem combines a special case of the objective function of problem (15) with the constraints of problem (17). Given matrices A B , ∈ X n × n and vectors p g , ∈ X n , we find regular vectors x ∈ X n that provide solutions to the problem

$$\minimize & \quad x ^ { - } A x \oplus x ^ { - } p, \\ \text{subject to } & \ B x \oplus g \leq x.$$

Theorem 15 ([70]) . Let x be the general regular solution to problem (19) , where A is a matrix with spectral radius λ &gt; 0 and B is a matrix such that Tr( B ) ≤ 1 .

Then, the minimum in (19) is equal to

$$\theta = \lambda \oplus \bigoplus _ { k = 1 } ^ { n - 1 } \bigoplus _ { 1 \leq i _ { 1 } + \dots + i _ { k } \leq n - k } \text{tr} ^ { 1 / k } ( A B ^ { i _ { 1 } } \cdots A B ^ { i _ { k } } ),$$

and the general solution is given by

$$x = ( \theta ^ { - 1 } A \oplus B ) ^ { * } u, \quad u \geq \theta ^ { - 1 } p \oplus g.$$

## Acknowledgments

The author thanks an editor for helpful comments and suggestions on earlier drafts of the manuscript.

## References

$$\begin{smallmatrix} [ 1 ] & S. \, N. \, N. \, P a n d i t, \, \text{``A new matrix calculus}, \end{smallmatrix} \\ & J. \, S I A M \, 9 \, \text{no. } 4, \, ( 1 9 6 1 ) \, 6 3 2 - 6 3 9.$$

- [2] R. A. Cuninghame-Green, 'Describing industrial processes with interference and approximating their steady-state behaviour,' Oper. Res. Quart. 13 no. 1, (1962) 95-100.
- [3] B. Giffler, 'Scheduling general production systems using schedule algebra,' Naval Res. Logist. Quart. 10 no. 1, (1963) 237-255.
- [4] A. J. Hoffman, 'On abstract dual linear programs,' Naval Res. Logist. Quart. 10 no. 1, (1963) 369-373.
- [5] S. C. Kleene, 'Representation of events in nerve nets and finite automata,' in Automata Studies , C. E. Shannon and J. McCarthy, eds., vol. 34 of Annals of Mathematics Studies , pp. 3-41. Princeton University Press, 1956.
- [6] R. Bellman, 'On a quasi-linear equation,' Canad. J. Math. 8 (1956) 198-202.
- [7] R. Bellman and W. Karush, 'On a new functional transform in analysis: The maximum transform,' Bull. Amer. Math. Soc. 67 (1961) 501-503.
- [8] R. Bellman and W. Karush, 'Mathematical programming and the maximum transform,' Journal of the Society for Industrial and Applied Mathematics 10 no. 3, (1962) 550-567. http://www.jstor.org/stable/2098751 .
- [9] R. T. Rockafellar, Convex Analysis . Princeton University Press, Princeton, NJ, 1970.
- [10] I. V. Romanovsky, 'Some remarks on the functional transformation of Bellman-Karush,' Vestnik Leningrad Univ. 17 no. 18, (1962) 148-150. (in Russian).
- [11] N. N. Vorob'ev, 'The extremal matrix algebra,' Soviet Math. Dokl. 4 no. 5, (1963) 1220-1223.
- [12] I. V. Romanovski˘ ı, 'Asymptotic behavior of dynamic programming processes with a continuous set of states,' Soviet Math. Dokl. 5 no. 6, (1964) 1684-1687.
- [13] I. V. Romanovskii, 'Asymptotic representation of recurrence relations in dynamic programming,' Soviet Phys. Dokl. 9 no. 8, (1965) 633-635.
- [14] I. V. Romanovskii, 'Optimization of stationary control of a discrete deterministic process,' Cybernetics 3 (April, 1967) 52-62.
- [15] I. V. Romanovskiy, 'Deterministic processes of dynamic programming with additional constraints,' J. Cybernet. 2 no. 1, (1972) 79-84.

| [16]   | N. N. Vorob'ev, 'Extremal algebra of positive matrices,' Elektron. Informationsverarbeit. Kybernetik 3 no. 1, (1967) 39-71. (in Russian).                                                                      |
|--------|----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|
| [17]   | N. N. Vorob'ev, 'Extremal algebra of non-negative matrices,' Elektron. Informationsverarbeit. Kybernetik 6 no. 4/5, (1970) 303-311. (in Russian).                                                              |
| [18]   | A. A. Korbut, 'Extremal spaces,' Soviet Math. Dokl. 6 no. 5, (1965) 1358-1361.                                                                                                                                 |
| [19]   | A. A. Korbut, 'Extremal vector spaces and their properties,' Elektron. Informationsverarbeit. Kybernetik 8 no. 8/9, (1972) 525-536. (in Russian).                                                              |
| [20]   | V. P. Maslov and S. N. Samborski˘, ı vol. 13 of Advances in Soviet Mathematics . AMS, Providence, RI, 1992.                                                                                                    |
| [21]   | V. Maslov and V. Kolokoltsov, Idempotent Analysis and Its Applications to Optimal Control Theory . Nauka, Moscow, 1994. (in Russian).                                                                          |
| [22]   | V. N. Kolokoltsov and V. P. Maslov, Idempotent Analysis and Its Applications , vol. 401 of Mathematics and Its Applications . Kluwer Academic Publishers, Dordrecht, 1997.                                     |
| [23]   | R. Cuninghame-Green, Minimax Algebra , vol. 166 of Lecture Notes in Economics and Mathematical Systems . Springer, Berlin, 1979.                                                                               |
| [24]   | B. Carr´, e Graphs and Networks . Oxford Applied Mathematics and Computing Science Series. Clarendon Press, Oxford, 1979.                                                                                      |
| [25]   | U. Zimmermann, Linear and Combinatorial Optimization in Ordered Algebraic Structures , vol. 10 of Annals of Discrete Mathematics . Elsevier, Amsterdam, 1981.                                                  |
| [26]   | F. L. Baccelli, G. Cohen, G. J. Olsder, and J.-P. Quadrat, Synchronization and Linearity: An Algebra for Discrete Event Systems . Wiley Series in Probability and Statistics. Wiley, Chichester, 1993.         |
| [27]   | J. S. Golan, Semirings and Affine Equations Over Them: Theory and Applications , vol. 556 of Mathematics and Its Applications . Kluwer Academic Publishers, Dordrecht, 2003.                                   |
| [28]   | B. Heidergott, G. J. Olsder, and J. van der Woude, Max-plus at Work: Modeling and Analysis of Synchronized Systems . Princeton Series in Applied Mathematics. Princeton University Press, Princeton, NJ, 2006. |

| [29]   | M. Gondran and M. Minoux, Graphs, Dioids and Semirings: New Models and Algorithms , vol. 41 of Operations Research / Computer Science Interfaces . Springer, New York, 2008.                                                                                                                      |
|--------|---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|
| [30]   | N. K. Krivulin, Methods of Idempotent Algebra for Problems in Modeling and Analysis of Complex Systems . Saint Petersburg University Press, Saint Petersburg, 2009. (in Russian).                                                                                                                 |
| [31]   | P. Butkoviˇ, c Max-linear Systems: Theory and Algorithms . Springer Monographs in Mathematics. Springer, London, 2010.                                                                                                                                                                            |
| [32]   | W. M. McEneaney, Max-Plus Methods for Nonlinear Control and Estimation . Systems and Control: Foundations and Applications. Birkh¨user, a Boston, 2006.                                                                                                                                           |
| [33]   | L. Superville, Various Aspects of Max-Algebra . PhD thesis, The City University of New York, New York, 1978.                                                                                                                                                                                      |
| [34]   | R. A. Cuninghame-Green, 'Projections in minimax algebra,' Math. Program. 10 (1976) 111-123.                                                                                                                                                                                                       |
| [35]   | P. Butkoviˇ, c 'On properties of solution sets of extremal linear programs,' in Algebraic and Combinatorial Methods in Operations Research , R. E. Burkard, R. A. Cuninghame-Green, and U. Zimmermann, eds., vol. 95 of North-Holland Mathematics Studies , pp. 41-54. Elsevier, Amsterdam, 1984. |
| [36]   | K. Zimmermann, 'Some optimization problems with extremal operations,' in Mathematical Programming at Oberwolfach II , B. Korte and K. Ritter, eds., vol. 22 of Mathematical Programming Studies , pp. 237-251. Springer, Berlin, 1984.                                                            |
| [37]   | N. K. Krivulin, 'Evaluation of bounds on the mean rate of growth of the state vector of a linear dynamical stochastic system in idempotent algebra,' Vestnik St. Petersburg Univ. Math. 38 no. 2, (2005) 42-51.                                                                                   |
| [38]   | N. K. Krivulin, 'Eigenvalues and eigenvectors of matrices in idempotent algebra,' Vestnik St. Petersburg Univ. Math. 39 no. 2, (2006) 72-83.                                                                                                                                                      |
| [39]   | N. K. Krivulin, 'Solution of generalized linear vector equations in idempotent algebra,' Vestnik St. Petersburg Univ. Math. 39 no. 1, (2006) 16-26.                                                                                                                                               |

| [40]   | V. N. Kolokol'tsov, 'Idempotent structures in optimization,' J. Math. Sci. (NY) 104 no. 1, (2001) 847-880.                                                                                                                                                  |
|--------|-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|
| [41]   | G. Litvinov, 'Maslov dequantization, idempotent and tropical mathematics: A brief introduction,' J. Math. Sci. (NY) 140 no. 3, (2007) 426-444, arXiv:math/0507014 [math.GM] .                                                                               |
| [42]   | M. Akian, R. Bapat, and S. Gaubert, 'Max-plus algebra,' in Handbook of Linear Algebra , L. Hogben, ed., Discrete Mathematics and Its Applications, pp. 25-1-25-17. Taylor and Francis, Boca Raton, FL, 2007.                                                |
| [43]   | K. Zimmermann, 'Interval linear systems and optimization problems over max-algebras,' in Linear Optimization Problems with Inexact Data , pp. 165-193. Springer, New York, 2006.                                                                            |
| [44]   | P. Butkoviˇ c and A. Aminu, 'Introduction to max-linear programming,' IMA J. Manag. Math. 20 no. 3, (2009) 233-249.                                                                                                                                         |
| [45]   | P. Butkoviˇ c and K. P. Tam, 'On some properties of the image set of a max-linear mapping,' in Tropical and Idempotent Mathematics , G. L. Litvinov and S. N. Sergeev, eds., vol. 495 of Contemp. Math. , pp. 115-126. American Mathematical Society, 2009. |
| [46]   | K. P. Tam, Optimizing and Approximating Eigenvectors in Max-Algebra . PhD thesis, The University of Birmingham, Birmingham, 2010.                                                                                                                           |
| [47]   | A. Aminu and P. Butkoviˇ, c 'Non-linear programs with max-linear constraints: A heuristic approach,' IMA J. Manag. Math. 23 no. 1, (2012) 41-66.                                                                                                            |
| [48]   | R. A. Cuninghame-Green, 'Minimax algebra and applications,' Fuzzy Sets and Systems 41 no. 3, (1991) 251-267.                                                                                                                                                |
| [49]   | N. K. Krivulin, 'An extremal property of the eigenvalue for irreducible matrices in idempotent algebra and an algebraic solution to a Rawls location problem,' Vestnik St. Petersburg Univ. Math. 44 no. 4, (2011) 272-281.                                 |
| [50]   | N. Krivulin, 'A new algebraic solution to multidimensional minimax location problems with Chebyshev distance,' WSEAS Trans. Math. 11 no. 7, (2012) 605-614, arXiv:1210.4770 [math.OC] .                                                                     |

- [51] L. Elsner and P. van den Driessche, 'Max-algebra and pairwise comparison matrices,' Linear Algebra Appl. 385 no. 1, (2004) 47-62.
- [52] L. Elsner and P. van den Driessche, 'Max-algebra and pairwise comparison matrices, II,' Linear Algebra Appl. 432 no. 4, (2010) 927-935.
- [53] B. B. Gursoy, O. Mason, and S. Sergeev, 'The analytic hierarchy process, max algebra and multi-objective optimisation,' Linear Algebra Appl. 438 no. 7, (2013) 2911-2928.
- [54] S. Gaubert, 'Resource optimization and (min,+) spectral theory,' IEEE Trans. Automat. Control 40 no. 11, (1995) 1931-1934.
- [55] B. De Schutter, Max-Algebraic System Theory for Discrete Event Systems . PhD thesis, Katholieke Universiteit Leuven, Leuven, 1996.
- [56] B. De Schutter and T. van den Boom, 'Model predictive control for max-plus-linear discrete event systems,' Automatica 37 no. 7, (2001) 1049-1056.
- [57] K. Zimmermann, 'On max-separable optimization problems,' in Algebraic and Combinatorial Methods in Operations Research , R. E. Burkard, R. A. Cuninghame-Green, and U. Zimmermann, eds., vol. 95 of North-Holland Mathematics Studies , pp. 357-362. Elsevier, Amsterdam, 1984.
- [58] K. Zimmermann, 'Optimization problems with unimodal functions in max-separable constraints,' Optimization 24 no. 1-2, (1992) 31-41.
- [59] K. Zimmermann, 'Disjunctive optimization, max-separable problems and extremal algebras,'
- Theoret. Comput. Sci. 293 no. 1, (2003) 45-54.
- [60] M. Gavalec and K. Zimmermann, 'Duality for max-separable problems,' Cent. Eur. J. Oper. Res. 20 (2012) 409-419.
- [61] R. A. Cuninghame-Green and P. Butkoviˇ c, 'The equation a ⊕ x = b ⊕ y over (max +),' , Theoret. Comput. Sci. 293 no. 1, (2003) 3-12.
- [62] S. Gaubert, R. D. Katz, and S. Sergeev, 'Tropical linear-fractional programming and parametric mean payoff games,' J. Symbolic Comput. 47 no. 12, (2012) 1447-1478, arXiv:1101.3431 [math.MG] .
- [63] M. Akian, S. Gaubert, and A. Guterman, 'Tropical polyhedra are equivalent to mean payoff games,'

|      | Internat. J. Algebra Comput. 22 no. 1, (2012) 1250001-1-1250001-43, arXiv:0912.2462 [math.CO] .                                                                                                                                                                                                                                                         |
|------|---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|
| [64] | G. M. Engel and H. Schneider, 'Diagonal similarity and equivalence for matrices over groups with 0,' Czechoslovak Math. J. 25 no. 3, (1975) 389-403.                                                                                                                                                                                                    |
| [65] | N. Krivulin, 'A constrained tropical optimization problem: Complete solution and application example,' arXiv:1305.1454 [math.OC] .                                                                                                                                                                                                                      |
| [66] | N. Krivulin, 'A maximization problem in tropical mathematics: A complete solution and application examples,' arXiv:1304.7461 [math.OC] .                                                                                                                                                                                                                |
| [67] | N. Krivulin, 'Complete solution of a constrained tropical optimization problem with application to location in Relational and Algebraic Methods in Computer Science , P. H¨fner, o P. Jipsen, W. Kahl, and M. E. M¨ller, u eds., vol. 8428 of Lecture Notes in Computer Science , pp. 362-378. Springer, Switzerland, 2014. arXiv:1311.2795 [math.OC] . |
| [68] | N. Krivulin and K. Zimmermann, 'Direct solutions to tropical optimization problems with nonlinear objective functions and boundary constraints,' in Mathematical Methods and Optimization Techniques in Engineering , D. Biolek, H. Walter, I. Utu, and C. von Lucken, eds., pp. 86-91. WSEAS Press, 2013. arXiv:1311.2311 [math.OC] .                  |
| [69] | N. Krivulin, 'Explicit solution of a tropical optimization problem with application to project scheduling,' in Mathematical Methods and Optimization Techniques in Engineering , D. Biolek, H. Walter, I. Utu, and C. von Lucken, eds., pp. 39-45. WSEAS Press, 2013. arXiv:1303.5457 [math.OC] .                                                       |
| [70] | N. Krivulin, 'Extremal properties of tropical eigenvalues and solutions to tropical optimization problems,' arXiv:1311.0442 [math.OC] .                                                                                                                                                                                                                 |
| [71] | N. Krivulin, 'A multidimensional tropical optimization problem with nonlinear objective function and linear constraints,' Optimization (2013) , arXiv:1303.0542 [math.OC] .                                                                                                                                                                             |
| [72] | N. Krivulin, 'A complete closed-form solution to a tropical extremal problem,' in Advances in Computer Science , S. Yenuri, ed., vol. 5 of Recent Advances in Computer Engineering Series , pp. 146-151. WSEAS Press, 2012. arXiv:1212.6106 [math.OC] .                                                                                                 |
Nikolai Krivulin
Tropical optimization problems
We consider optimization problems that are formulated and solved in the
framework of tropical mathematics. The problems consist in minimizing or
maximizing functionals defined on vectors of finite-dimensional semimodules
over idempotent semifields, and may involve constraints in the form of linear
equations and inequalities. The objective function can be either a linear
function or nonlinear function calculated by means of multiplicative conjugate
transposition of vectors. We start with an overview of known tropical
optimization problems and solution methods. Then, we formulate certain new
problems and present direct solutions to the problems in a closed compact
vector form suitable for further analysis and applications. For many problems,
the results obtained are complete solutions.