Can we measure the difficulty of an optimization problem?
2014 (English)Conference paper (Other academic)
Can we measure the difficulty of an optimization problem? Although optimization plays a crucial role in modernscience and technology, a formal framework that puts problemsand solution algorithms into a broader context has not beenestablished. This paper presents a conceptual approach which gives a positive answer to the question for a broad class of optimization problems. Adopting an information and computational perspective, the proposed framework builds upon Shannon and algorithmic information theories. As a starting point, a concrete model and definition of optimization problems is provided. Then, a formal definition of optimization difficulty is introduced which builds upon algorithmic information theory. Following an initial analysis, lower and upper bounds on optimization difficulty are established. One of the upper-bounds is closely related to Shannon information theory and black-box optimization. Finally, various computational issues and future research directions are discussed.
Place, publisher, year, edition, pages
2014. 356-360 p.
, Information Theory Workshop (ITW), IEEE, ISSN 1662-9019
Mathematics Computer Science
IdentifiersURN: urn:nbn:se:su:diva-112784DOI: 10.1109/ITW.2014.6970853OAI: oai:DiVA.org:su-112784DiVA: diva2:780780
IEEE Information Theory Workshop (ITW)