An optimal algorithm for Global Optimization and adaptive covering

Serge L. Shishkin () and Alan M. Finn
Additional contact information
Serge L. Shishkin: United Technologies Research Center
Alan M. Finn: United Technologies Research Center

Journal of Global Optimization, 2016, vol. 66, issue 3, No 8, 535-572

Abstract: Abstract The general class of zero-order Global Optimization problems is split into subclasses according to a proposed “Complexity measure” and the computational complexity of each subclass is rigorously estimated. Then, the laboriousness (computational demand) of general Branch-and-Bound (BnB) methods is estimated for each subclass. For conventional “Cubic” BnB based on splitting an n-dimensional cube into $$2^n$$ 2 n sub-cubes, both upper and lower laboriousness estimates are obtained. The value of the Complexity measure for a problem subclass enters linearly into all complexity and laboriousness estimates for that subclass. A new BnB method based on the lattice $$A_n^*$$ A n ∗ is presented with upper laboriousness bound that is, though conservative, smaller by a factor of $$O((4/3)^n)$$ O ( ( 4 / 3 ) n ) than the lower bound of the conventional method. The optimality of the new method is discussed. All results are extended to the class of Adaptive Covering problems—that is, covering of a large n-dimensional set by balls of different size, where the size of each ball is defined by a locally computed criterion.

Keywords: Global Optimization; Branch and Bound; Adaptive covering; Complexity; Optimal algorithms (search for similar items in EconPapers)
Date: 2016
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10898-016-0416-6 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jglopt:v:66:y:2016:i:3:d:10.1007_s10898-016-0416-6

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/10898

DOI: 10.1007/s10898-016-0416-6

Access Statistics for this article

Journal of Global Optimization is currently edited by Sergiy Butenko

More articles in Journal of Global Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().