Sökning: id:"swepub:oai:DiVA.org:su-112784" >
Can we measure the ...
Can we measure the difficulty of an optimization problem?
-
Alpcan, Tansu (författare)
-
- Everitt, Tom, 1987- (författare)
- Stockholms universitet,Matematiska institutionen
-
Hutter, Marcus (författare)
-
(creator_code:org_t)
- 2014
- 2014
- Engelska.
-
Serie: Information Theory Workshop (ITW), IEEE, 1662-9019
- Relaterad länk:
-
https://urn.kb.se/re...
-
visa fler...
-
https://doi.org/10.1...
-
visa färre...
Abstract
Ämnesord
Stäng
- 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.
Ämnesord
- NATURVETENSKAP -- Matematik (hsv//swe)
- NATURAL SCIENCES -- Mathematics (hsv//eng)
- NATURVETENSKAP -- Data- och informationsvetenskap -- Datavetenskap (hsv//swe)
- NATURAL SCIENCES -- Computer and Information Sciences -- Computer Sciences (hsv//eng)
Publikations- och innehållstyp
- vet (ämneskategori)
- kon (ämneskategori)