Journal
JOURNAL OF GLOBAL OPTIMIZATION
Volume 42, Issue 1, Pages 51-67Publisher
SPRINGER
DOI: 10.1007/s10898-008-9287-9
Keywords
global optimization; convex underestimation; alpha BB; convex envelopes; univariate functions
Funding
- Div Of Chem, Bioeng, Env, & Transp Sys
- Directorate For Engineering [0827907] Funding Source: National Science Foundation
Ask authors/readers for more resources
A novel method for the convex underestimation of univariate functions is presented in this paper. The method is based on a piecewise application of the well-known alpha BB underestimator, which produces an overall underestimator that is piecewise convex. Subsequently, two algorithms are used to identify the linear segments needed for the construction of its C-1-continuous convex envelope, which is itself a valid convex underestimator of the original function. The resulting convex underestimators are very tight, and their tightness benefits from finer partitioning of the initial domain. It is theoretically proven that there is always some finite level of partitioning for which the method yields the convex envelope of the function of interest. The method was applied on a set of univariate test functions previously presented in the literature, and the results indicate that the method produces convex underestimators of high quality in terms of both lower bound and tightness over the whole domain under consideration.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available