An edge-concave underestimator for the global optimization of twice-differentiable nonconvex problems

M. M. Faruque Hasan ()
Additional contact information
M. M. Faruque Hasan: Texas A&M University

Journal of Global Optimization, 2018, vol. 71, issue 4, No 5, 735-752

Abstract: Abstract We present a new relaxation method for the deterministic global optimization of general nonconvex and $${\mathscr {C}}^2$$ C 2 -continuous problems. Instead of using a convex underestimator, the method uses an edge-concave (componentwise concave) underestimator to relax a nonconvex function. The underestimator is constructed by subtracting a positive quadratic expression such that all nonedge-concavities in the original function is overpowered by the added expression. While the edge-concave underestimator is nonlinear, the linear facets of its vertex polyhedral convex envelope leads to a linear programming (LP)-based relaxation of the original nonconvex problem. We present some theoretical results on this new class of underestimators and compare the performance of the LP relaxation with relaxations obtained by convex underestimators such as $$\alpha \hbox {BB}$$ α BB and its variants for several test problems. We also discuss the potential of a hybrid relaxation, relying on the dynamic selection of convex and edge-concave underestimators using criteria such as maximum separation distance.

Keywords: Global optimization; Edge-concave underestimator; Relaxation; Nonconvex NLP (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-0646-x 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-0646-x

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

DOI: 10.1007/s10898-018-0646-x

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