Arbitrarily tight $$\alpha $$ α BB underestimators of general non-linear functions over sub-optimal domains

N. Kazazakis and C. S. Adjiman ()
Additional contact information
N. Kazazakis: Imperial College London
C. S. Adjiman: Imperial College London

Journal of Global Optimization, 2018, vol. 71, issue 4, No 7, 815-844

Abstract: Abstract In this paper we explore the construction of arbitrarily tight $$\alpha $$ α BB relaxations of $$C^2$$ C 2 general non-linear non-convex functions. We illustrate the theoretical challenges of building such relaxations by deriving conditions under which it is possible for an $$ \alpha $$ α BB underestimator to provide exact bounds. We subsequently propose a methodology to build $$ \alpha $$ α BB underestimators which may be arbitrarily tight (i.e., the maximum separation distance between the original function and its underestimator is arbitrarily close to 0) in some domains that do not include the global solution (defined in the text as “sub-optimal”), assuming exact eigenvalue calculations are possible. This is achieved using a transformation of the original function into a $$\mu $$ μ -subenergy function and the derivation of $$\alpha $$ α BB underestimators for the new function. We prove that this transformation results in a number of desirable bounding properties in certain domains. These theoretical results are validated in computational test cases where approximations of the tightest possible $$\mu $$ μ -subenergy underestimators, derived using sampling, are compared to similarly derived approximations of the tightest possible classical $$\alpha $$ α BB underestimators. Our tests show that $$\mu $$ μ -subenergy underestimators produce much tighter bounds, and succeed in fathoming nodes which are impossible to fathom using classical $$ \alpha $$ α BB.

Keywords: $$\alpha $$ α BB; Subenergy; Underestimator; Eigenvalue (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10898-018-0632-3 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:71:y:2018:i:4:d:10.1007_s10898-018-0632-3

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

DOI: 10.1007/s10898-018-0632-3

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