Deriving convex hulls through lifting and projection
type: Item
instance of: scholarly article
title: Deriving convex hulls through lifting and projection
zbMATH Open document ID: 1410.90132
author: Trang T. Nguyen
author: Jean-Philippe Richard
author: Mohit Tawarmalani
published in: Mathematical Programming. Series A. Series B
publication date: 2018-06-25T00:00:00Z
review text: The authors focus on the convex hulls of the subsets of a compact hypercube defined by the constraints \(x^{b_1}_1 x^{b_2}_2\geq x_3\) and \(x_1x^{b_2}_2\leq x_3,\) where \(b_1,b_2\geq 1.\) Via a lift-and-project technique, they derive the closed expression for the convex hulls of the sets \[ S^\geq :=\{ (x_1, x_2, x_3)\in [l_1, u_1]\times [l_2, u_2] \times[l_3, u_3]\big| \, x^{b_1}_1 x^{b_2}_2 \geq x_3\} \] \[ S^\leq :=\{ (x_1, x_2, x_3)\in [l_1, u_1]\times [l_2, u_2] \times[l_3, u_3]\big| \, x_1 x^{b_2}_2 \leq x_3\}, \] and \[ S^= :=\{ (x_1, x_2, x_3)\in [l_1, u_1]\times [l_2, u_2] \times[l_3, u_3]\big| \, x_1 x^{b_2}_2 = x_3\}, \] where \(l_1,l_2,l_3\in \mathbb{R}_{++} := \{x \in \mathbb{R}\big| \, x > 0\}\), \(u_1, u_2, u_3\in \mathbb{R}_{++}\), \( l_i\leq u_i\) for \(i = 1, 2, 3\), and \(b_1, b_2\geq 1\). Note that \(b_1\) and \(b_2\) are not restricted to be integers.
Mathematics Subject Classification ID: 90C11
Mathematics Subject Classification ID: 46N10
Mathematics Subject Classification ID: 52A27
Mathematics Subject Classification ID: 90C26
Mathematics Subject Classification ID: 90C57
zbMATH DE Number: 6894014
zbMATH Keywords: convex hull
zbMATH Keywords: nonlinear knapsack sets
zbMATH Keywords: lifting
zbMATH Keywords: projection
zbMATH Keywords: bilinear sets
zbMATH Keywords: explicit descriptions
reviewed by: Rita Pini
MaRDI profile type: Publication
full work available at URL: s10107-017-1138-3
OpenAlex ID: W2606063390
cites work: Jointly Constrained Biconvex Programming
cites work: Computable representations for convex hulls of low-dimensional quadratic forms
cites work: Valid inequalities and convex hulls for multilinear functions
cites work: Optimization Problems with Perturbations: A Guided Tour
cites work: Convex envelopes of multilinear functions over a unit hypercube and over special discrete sets
cites work: Q5812325
cites work: The Convex Envelope of (n–1)-Convex Functions
cites work: Convex envelopes generated from finitely many compact convex sets
cites work: On convex envelopes for bivariate functions over polytopes
cites work: Some results on the strength of relaxations of multilinear 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: Lifting inequalities: a framework for generating strong cuts for nonlinear programs
cites work: Convex Analysis
cites work: A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
cites work: Semidefinite relaxations of fractional programs via novel convexification techniques
cites work: Strong valid inequalities for orthogonal disjunctions and bilinear covering sets
cites work: Explicit convex and concave envelopes through polyhedral subdivisions
DOI: 10.1007/S10107-017-1138-3
description: scientific article; zbMATH DE number 6894014