Convex envelopes generated from finitely many compact convex sets
type: Item
instance of: scholarly article
title: Convex envelopes generated from finitely many compact convex sets
zbMATH Open document ID: 1284.90055
author: Aida Khajavirad
author: Nikolaos V. Sahinidis
published in: Mathematical Programming. Series A. Series B
publication date: 2013-03-18T00:00:00Z
review text: The authors focus on the problem of constructing the convex envelope of a lower semicontinuous function \(\phi\) defined over a compact convex subset \(C\) of \(\mathbb{R}^n\). The convex envelope of \(\phi\) on \(C\) can be fully characterized by the set of extreme points of the convex hull of \(\mathrm{epi}_C\phi\); the projection of this set on \(C\) is the generating set of the convex envelope of \(\phi\) over \(C\). The authors present a convex NLP formula for the problem of constructing the convex envelope of an lsc function whose generating set is representable as the union of a finite number of compact convex sets; in this case, the envelope representation problem is significantly simplified. Their convexification argument is based on the concept of perspective transformation. The authors focus on functions of the form \(\phi(x,y)= f(x)g(y)\) (\(x\in \mathbb{R}^m,\) \(y\in \mathbb{R}^n\)) over a box, where \(f\) is nonnegative and convex and \(g\) is nonnegative and componentwise concave. In Section 3, they study the case where \(f\) is assumed to be a power, or to have exponential form, and they provide a characterization of the convex envelope of \(\phi\). In Section 4, analytical expressions for the convex envelopes of functions of the form \(\phi(x,y)= f(x)g(y)\), where \(f\) is nonnegative convex and \(g\) is componenwise concave are presented, under the additional assumption that \(g\) is univariate and bivariate in turn.
Mathematics Subject Classification ID: 90C26
Mathematics Subject Classification ID: 90C30
zbMATH DE Number: 6145974
zbMATH Keywords: convex envelope
zbMATH Keywords: global optimization
zbMATH Keywords: factorable relaxations
zbMATH Keywords: perspective transformation
zbMATH Keywords: submodular functions
reviewed by: Rita Pini
describes a project that uses: BARON
describes a project that uses: MINLPLib
MaRDI profile type: Publication
full work available at URL: s10107-011-0496-5
OpenAlex ID: W2001451578
cites work: Jointly Constrained Biconvex Programming
cites work: Disjunctive Programming
cites work: Disjunctive Programming and a Hierarchy of Relaxations for Discrete Optimization Problems
cites work: Multiterm polyhedral relaxations for nonconvex, quadratically constrained quadratic programs
cites work: Q3102800
cites work: MINLPLib -- a collection of test models for mixed-integer nonlinear programming
cites work: Convex programming for disjunctive convex optimization
cites work: Perspective cuts for a class of convex 0-1 mixed integer programs
cites work: Generalized convex disjunctive programming: Nonlinear convex hull relaxation
cites work: Perspective Relaxation of Mixed Integer Nonlinear Programs with Indicator Variables
cites work: The Convex Envelope of (n–1)-Convex Functions
cites work: Convex envelopes of products of convex and component-wise concave functions
cites work: Computability of global solutions to factorable nonconvex programs: Part I — Convex underestimating problems
cites work: Trilinear monomials with mixed sign domains: Facets of the convex and concave envelopes
cites work: Convex envelopes for edge-concave functions
cites work: Q4040221
cites work: A convex envelope formula for multilinear functions
cites work: Convex Analysis
cites work: Variational Analysis
cites work: BARON: A general purpose global optimization software package
cites work: Convex envelopes of multilinear functions over a unit hypercube and over special discrete sets
cites work: A branch-and-cut method for 0-1 mixed convex programming
cites work: Existence and sum decomposition of vertex polyhedral convex envelopes
cites work: Strong valid inequalities for orthogonal disjunctions and bilinear covering sets
cites work: Explicit convex and concave envelopes through polyhedral subdivisions
cites work: Semidefinite relaxations of fractional programs via novel convexification techniques
cites work: Convex extensions and envelopes of lower semi-continuous functions
cites work: Global optimization of mixed-integer nonlinear programs: a theoretical and computational study
cites work: A polyhedral branch-and-cut approach to global optimization
DOI: 10.1007/S10107-011-0496-5
description: scientific article; zbMATH DE number 6145974