Can we measure the difficulty of an optimization problem?

Date

2014-11

Authors

Alpcan, Tansu
Everitt, Tom
Hutter, Marcus

Journal Title

Journal ISSN

Volume Title

Publisher

IEEE

Abstract

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 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.

Description

Keywords

Citation

Source

2014 IEEE Information Theory Workshop (ITW), Hobart, TAS., 2-5 Nov. 2014

Type

Conference paper

Book Title

Entity type

Access Statement

License Rights

DOI

10.1109/ITW.2014.6970853

Restricted until