TY - CONF

T1 - Direct algebraic solutions to tropical optimization problems

AU - Krivulin, Nikolai

N1 - ILAS2014: The 19th Conference of the International Linear Algebra Society, Aug. 6-9, 2014, Sungkyunkwan University, Seoul, Korea, http://www.ilas2014.org

PY - 2014

Y1 - 2014

N2 - 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.

AB - 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.

KW - tropical algebra

KW - idempotent semifield

KW - optimization problem

KW - nonlinear objective function

KW - linear constraint

M3 - Abstract

SP - 75

EP - 76

T2 - The 19th International Linear Algebra Society (ILAS) Conference

Y2 - 6 August 2014 through 9 August 2014

ER -