A general framework for convexity analysis in deterministic global optimization

Ralph Kearfott (), Jessie Castille () and Gaurav Tyagi ()

Journal of Global Optimization, 2013, vol. 56, issue 3, 765-785

Abstract: In previous work, we, and also Epperly and Pistikopoulos, proposed an analysis of general nonlinear programs that identified certain variables as convex, not ever needing subdivision, and non-convex, or possibly needing subdivision in branch and bound algorithms. We proposed a specific algorithm, based on a generated computational graph of the problem, for identifying such variables. In our previous work, we identified only independent variables in the computational graph. Here, we examine alternative sets of non-convex variables consisting not just of independent variables, but of a possibly smaller number of intermediate variables. We do so with examples and theorems. We also apply variants of our proposed analysis to the well-known COCONUT Lib-1 test set. If the number of such non-convex variables is sufficiently small, it may be possible to fully subdivide them before analysis of ranges of objective and constraints, thus dispensing totally with the branch and bound process. Advantages to such a non-adaptive process include higher predictability and easier parallizability. We present an algorithm and exploratory results here, with a more complete empirical study in a subsequent paper. Copyright Springer Science+Business Media, LLC. 2013

Keywords: Automatic verification; Non-convexity; Automatic differentiation; Branch and bound algorithms; Interval analysis; Complete search (search for similar items in EconPapers)
Date: 2013
References: View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://hdl.handle.net/10.1007/s10898-012-9905-4 (text/html)
Access to full text is restricted to subscribers.

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:56:y:2013:i:3:p:765-785

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

DOI: 10.1007/s10898-012-9905-4

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