Idempotent interval analysis and optimization problems
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2001
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911217188077568 |
|---|---|
| author | Litvinov, Grigori Sobolevskii, Andrei |
| author_facet | Litvinov, Grigori Sobolevskii, Andrei |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_math_0101080 |
| institution | arXiv |
| publishDate | 2001 |
| record_format | arxiv |
| spellingShingle | Idempotent interval analysis and optimization problems Litvinov, Grigori Sobolevskii, Andrei Numerical Analysis Optimization and Control 65G30, 06F05, 16Y60, 12K10, 65K10, 08A70 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. |
| title | Idempotent interval analysis and optimization problems |
| topic | Numerical Analysis Optimization and Control 65G30, 06F05, 16Y60, 12K10, 65K10, 08A70 |
| url | https://arxiv.org/abs/math/0101080 |