Complexity aspects of a semi-infinite optimization problem†

†Dedicated to H.Th. Jongen on the occasion of his 60th birthday

Abstract

This article surveys some of the author's work relating real number complexity and optimization theory. The focus is on the interplay between structural complexity considerations and semi-infinite optimization.

†Dedicated to H.Th. Jongen on the occasion of his 60th birthday

Keywords:

• interval arithmetic
• semi-infinite optimization
• complexity classes

2000 Mathematics Classifications: :

• 65G30
• 90C34
• 68Q15

Acknowledgements

Thanks go to an anonymous referee for some helpful remarks improving the presentation. Partially supported by the IST Programme of the European Community, under the PASCAL Network of Excellence, IST-2002-506778 and by the Danish Agency for Science, Technology and Innovation FNU. This publication only reflects the author's views.

Notes

†Dedicated to H.Th. Jongen on the occasion of his 60th birthday

Note

[1] In the Turing model there is a whole hierarchy of such problems called the polynomial time hierarchy that results from a more and more involved quantifier structure used to describe such problems and introduced by Stockmeyer in 22. An analogous hierarchy is defined straightforwardly for the BSS model.