Arbitrarily tight aBB underestimators of general non-linear functions over sub-optimal domains
File(s)
Author(s)
Kazazakis, N
Adjiman, CSJ
Type
Journal Article
Abstract
In this paper we explore the construction of arbitrarily tight αBB relaxations of C2 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 αBB underestimator to provide exact bounds. We subsequently propose a methodology to build α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 μ-subenergy function and the derivation of α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 μ-subenergy underestimators, derived using sampling, are compared to similarly derived approximations of the tightest possible classical αBB underestimators. Our tests show that μ-subenergy underestimators produce much tighter bounds, and succeed in fathoming nodes which are impossible to fathom using classical αBB.
Date Issued
2018-08-01
Date Acceptance
2018-02-24
Citation
Journal of Global Optimization, 2018, 71 (4), pp.815-844
ISSN
0925-5001
Publisher
Springer Verlag
Start Page
815
End Page
844
Journal / Book Title
Journal of Global Optimization
Volume
71
Issue
4
Copyright Statement
© The Author(s) 2018. This article is distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made.
Sponsor
Engineering & Physical Science Research Council (EPSRC)
Grant Number
EP/J003840/1
Subjects
Science & Technology
Technology
Physical Sciences
Operations Research & Management Science
Mathematics, Applied
Mathematics
alpha BB
Subenergy
Underestimator
Eigenvalue
DIFFERENTIABLE CONSTRAINED NLPS
GLOBAL OPTIMIZATION METHOD
ALPHA-BB
CONVEX UNDERESTIMATORS
TUNNELING ALGORITHM
AUTOMATIC METHOD
CLUSTER PROBLEM
NONCONVEX
SATISFACTION
RELAXATIONS
0102 Applied Mathematics
0103 Numerical And Computational Mathematics
0802 Computation Theory And Mathematics
Operations Research
Publication Status
Published
Date Publish Online
2018-03-29