Tight convex underestimators for {{\mathcal C}^2}-continuous problems: I. univariate functions |
| |
Authors: | Chrysanthos E Gounaris Christodoulos A Floudas |
| |
Institution: | (1) Department of Chemical Engineering, Princeton University, Princeton, NJ 08544-5263, USA |
| |
Abstract: | 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 α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 -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. |
| |
Keywords: | Global optimization Convex underestimation α BB Convex envelopes Univariate functions |
本文献已被 SpringerLink 等数据库收录! |
|