Idempotent interval analysis and optimization problems

Abstract

Many problems in optimization theory are strongly nonlinear in the traditional sense but possess a hidden linear structure over suitable idempotent semirings. After an overview of `Idempotent Mathematics' with an emphasis on matrix theory, interval analysis over idempotent semirings is developed. The theory is applied to construction of exact interval solutions to the interval discrete stationary Bellman equation. Solution of an interval system is typically NP-hard in the traditional interval linear algebra; in the idempotent case it is polynomial. A generalization to the case of positive semirings is outlined.

28 pages, no figures; to be published in Reliable Computing

References in corpus (1)

• Exact interval solutions to the discrete Bellman equation and polynomial complexity of problems in interval idempotent linear algebra

Cited by in corpus (6)

• Duality and interval analysis over idempotent semirings
• Universal algorithms for solving the matrix Bellman equations over semirings
• Reachability of eigenspaces for interval circulant matrices in max-algebra
• The Markov chain tree theorem and the state reduction algorithm in commutative semirings
• An interval version of separation by semispaces in max-min convexity
• Idempotent and tropical mathematics. Complexity of algorithms and interval analysis