Exact and approximate results for convex envelopes of special structured functions over simplices

M. Locatelli ()
Additional contact information
M. Locatelli: Università di Parma Parco Area delle Scienze

Journal of Global Optimization, 2022, vol. 83, issue 2, No 2, 220 pages

Abstract: Abstract In this paper we describe how to derive the convex envelope of a function f over the n-dimensional unit simplex $$\Delta _n$$ Δ n at different levels of detail, depending on the properties of function f, by starting from its definition as the supremum of all the affine underestimators of f over $$\Delta _n$$ Δ n . At the first level we are able to derive the closed-form formula of the convex envelope. At the second level we are able to derive the exact value of the convex envelope at some point $${\mathbf{x}}\in \Delta _n$$ x ∈ Δ n , and a supporting hyperplane of the convex envelope itself at the same point, by solving a suitable convex optimization problem. Finally, at the third level we are able to derive an underestimating value which differs from the exact value of the convex envelope at some point $${\mathbf{x}}\in \Delta _n$$ x ∈ Δ n by at most a given threshold $$\delta $$ δ . The underestimation is obtained by solving a suitable LP problem and may lead also to a convex piecewise linear underestimator of f.

Keywords: Non-convex optimization; Convex envelope; Piecewise linear underestimator (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10898-021-01112-0 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:83:y:2022:i:2:d:10.1007_s10898-021-01112-0

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

DOI: 10.1007/s10898-021-01112-0

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