Contraction methods for continuous optimization
From MaRDI portal
Publication:6324595
arXiv1909.01123MaRDI QIDQ6324595
Author name not available (Why is that?)
Publication date: 3 September 2019
Abstract: Motivated by the grid search method and Bayesian optimization, we introduce the concept of contractibility and its applications in model-based optimization. First, a basic framework of contraction methods is established to construct a nonempty closed set sequence that contracts from the initial domain to the set of global minimizers. Then, from the perspective of whether the contraction can be carried out effectively, relevant conditions are introduced to divide all continuous optimization problems into three categories: (i) logarithmic time contractible, (ii) polynomial time contractible, or (iii) noncontractible. For every problem from the first two categories, there exists a contraction sequence that converges to the set of all global minimizers with linear convergence; for any problem from the last category, we discuss possible troubles caused by contraction. Finally, a practical algorithm is proposed with high probability bounds for convergence rate and complexity. It is shown that the contractibility contributes to practical applications and can also be seen as a complement to smoothness for distinguishing the optimization problems that are easy to solve.
Has companion code repository: https://github.com/xiaopengluo/contropt
No records found.
This page was built for publication: Contraction methods for continuous optimization
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6324595)
