TY - CHAP

T1 - Solving a tropical optimization problem via matrix sparsification

AU - Krivulin, Nikolai

N1 - Conference code: 15

PY - 2015

Y1 - 2015

N2 - An optimization problem, which arises in various applications as that of minimizing the span seminorm, is considered in the framework of tropical mathematics. The problem is to minimize a nonlinear function defined on vectors over an idempotent semifield, and calculated by means of multiplicative conjugate transposition. We find the minimum of the function, and give a partial solution which explicitly represents a subset of solution vectors. We characterize all solutions by a system of simultaneous equation and inequality, and exploit this characterization to investigate properties of the solutions. A matrix sparsification technique is developed to extend the partial solution to a wider solution subset, and then to a complete solution described as a family of subsets. We offer a backtracking procedure that generates all members of the family, and derive an explicit representation for the complete solution. Numerical examples and graphical illustrations of the results are presented.

AB - An optimization problem, which arises in various applications as that of minimizing the span seminorm, is considered in the framework of tropical mathematics. The problem is to minimize a nonlinear function defined on vectors over an idempotent semifield, and calculated by means of multiplicative conjugate transposition. We find the minimum of the function, and give a partial solution which explicitly represents a subset of solution vectors. We characterize all solutions by a system of simultaneous equation and inequality, and exploit this characterization to investigate properties of the solutions. A matrix sparsification technique is developed to extend the partial solution to a wider solution subset, and then to a complete solution described as a family of subsets. We offer a backtracking procedure that generates all members of the family, and derive an explicit representation for the complete solution. Numerical examples and graphical illustrations of the results are presented.

KW - tropical algebra

KW - idempotent semifield

KW - optimization problem

KW - span seminorm

KW - sparse matrix

KW - backtracking

KW - complete solution

U2 - 10.1007/978-3-319-24704-5_20

DO - 10.1007/978-3-319-24704-5_20

M3 - Chapter

SN - 978-3-319-24703-8

T3 - Lecture Notes in Computer Science

SP - 326

EP - 343

BT - Relational and Algebraic Methods in Computer Science

A2 - Kahl, Wolfram

A2 - Winter, Michael

A2 - Oliveira, José N.

PB - Springer Nature

CY - Cham

T2 - 15th International Conference on Relational and Algebraic Methods in Computer Science

Y2 - 28 September 2015 through 1 October 2015

ER -