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.
Original languageEnglish
Title of host publication Relational and Algebraic Methods in Computer Science
Subtitle of host publication15th International Conference, RAMiCS 2015, Braga, Portugal, September 28 - October 1, 2015, Proceedings
EditorsWolfram Kahl, Michael Winter, José N. Oliveira
Place of PublicationCham
PublisherSpringer Nature
Pages326-343
ISBN (Electronic)978-3-319-24704-5
ISBN (Print)978-3-319-24703-8
DOIs
StatePublished - 2015
Event15th International Conference on Relational and Algebraic Methods in Computer Science - Braga, Portugal
Duration: 28 Sep 2015 → 1 Oct 2015
Conference number: 15
http://ramics2015.di.uminho.pt/

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume9348
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference15th International Conference on Relational and Algebraic Methods in Computer Science
Abbreviated titleRAMiCS 2015
Country/TerritoryPortugal
CityBraga
Period28/09/15 → 1/10/15
Internet address

    Scopus subject areas

  • Control and Optimization
  • Algebra and Number Theory

    Research areas

  • tropical algebra, idempotent semifield, optimization problem, span seminorm, sparse matrix, backtracking, complete solution

ID: 32915553