Activities per year
Abstract
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 finitedimensional 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 Chebyshevlike 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 realworld problems in job scheduling, location analysis, decision making and other fields.
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 Chebyshevlike 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 realworld problems in job scheduling, location analysis, decision making and other fields.
Original language  English 

Pages  7576 
State  Published  2014 
Event  The 19th International Linear Algebra Society (ILAS) Conference  Seoul, Korea, Republic of Duration: 6 Aug 2014 → 9 Aug 2014 http://siags.siam.org/siagla//meetings/20140806ilas.html 
Conference
Conference  The 19th International Linear Algebra Society (ILAS) Conference 

Country  Korea, Republic of 
City  Seoul 
Period  6/08/14 → 9/08/14 
Internet address 
Scopus subject areas
 Mathematics(all)
Keywords
 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.
Activities

Direct algebraic solutions to tropical optimization problems
Николай Кимович Кривулин (Speaker)
6 Aug 2014Activity: Talk types › Oral presentation

The 19th International Linear Algebra Society (ILAS) Conference
Николай Кимович Кривулин (Participant)
6 Aug 2014 → 9 Aug 2014Activity: Attendance types › Participating in a conference, workshop, ...