Numerical and Computational Challenges
in Science and Engineering Program
Lecture
June 24, 10:00 am
Gregory Litvinov, International Sophus Lie Centre
Idempotent Interval Analysis and Optimization Problems
G.L. Litvinov and A.N. Sobolevskii
Many problems in the optimization theory are strongly nonlinear in
the traditional sense but possess a hidden linear structure over suitable
idempotent semirings. In the talk interval analysis over idempotent
semirings is developed with an emphasis on the matrix theory. 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 linear algebra but in the idempotent
case it is polynomial.
Back to Thematic
Year Index
