Skip navigation
Skip navigation

Can we measure the difficulty of an optimization problem?

Alpcan, Tansu; Everitt, Tom; Hutter, Marcus

Description

an we measure the difficulty of an optimization problem? Although optimization plays a crucial role in modern science and technology, a formal framework that puts problems and solution algorithms into a broader context has not been established. 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...[Show more]

dc.contributor.authorAlpcan, Tansu
dc.contributor.authorEveritt, Tom
dc.contributor.authorHutter, Marcus
dc.date.accessioned2015-08-12T06:19:25Z
dc.date.available2015-08-12T06:19:25Z
dc.identifier.isbn978-1-4799-5999-0
dc.identifier.issn1662-9019
dc.identifier.urihttp://hdl.handle.net/1885/14703
dc.description.abstractan we measure the difficulty of an optimization problem? Although optimization plays a crucial role in modern science and technology, a formal framework that puts problems and solution algorithms into a broader context has not been established. 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.
dc.publisherIEEE
dc.rights© 2014 IEEE
dc.source2014 IEEE Information Theory Workshop (ITW), Hobart, TAS., 2-5 Nov. 2014
dc.titleCan we measure the difficulty of an optimization problem?
dc.typeConference paper
dc.date.issued2014-11
local.type.statusPublished Version
local.contributor.affiliationHutter, M., Research School of Computer Science, The Australian National University
dc.relationhttp://purl.org/au-research/grants/arc/DP140100819
local.bibliographicCitation.startpage356
local.bibliographicCitation.lastpage360
local.identifier.doi10.1109/ITW.2014.6970853
CollectionsANU Research Publications

Download

There are no files associated with this item.


Items in Open Research are protected by copyright, with all rights reserved, unless otherwise indicated.

Updated:  19 May 2020/ Responsible Officer:  University Librarian/ Page Contact:  Library Systems & Web Coordinator