THEMATIC PROGRAMS

September 15, 2014

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