PreprintarXiv licencearXiv
On the convexification of a bilinearly constrained set with a common variable
Abstract
We study the convexification of sets defined by box constraints and bilinear inequality constraints in which all bilinear terms share a common variable. For this structured class of nonconvex sets, we provide a complete characterization of the extreme points of the convex hull and derive an explicit description of all facet-defining inequalities, thereby obtaining a full polyhedral description of the convex hull. In addition, we develop a polynomial-time separation algorithm for the facet-defining inequalities and illustrate its effectiveness through examples. These results offer both structural insight into the geometry of the convex hull and algorithmic tools for identifying violated inequalities.
Related
- NomadBBO: A direct-search framework for constrained mixed-variable blackbox optimization in Python
- Finite convexification by Minkowski summation
- On the partial convexification for low-rank spectral optimization: rank bounds and algorithms
- Fuel-optimal Boost-Back Guidance via Successive Convexification with a Terminal Constraint for ReusableLaunch Vehicles
- A constructive solution to Talagrand's Gaussian convexification problem
BibTeX
@misc{oh2026convexification,
title = {{On the convexification of a bilinearly constrained set with a common variable}},
author = {Hyun-Ju Oh and Boshi Yang},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.16116},
eprint = {2610.16116},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.16116},
}
RIS
TY - UNPB
TI - On the convexification of a bilinearly constrained set with a common variable
AU - Hyun-Ju Oh
AU - Boshi Yang
PY - 2026
DA - 2026/10/12
PB - arXiv
DO - 10.48550/arxiv.2610.16116
UR - https://arxiv.org/abs/2610.16116
AB - We study the convexification of sets defined by box constraints and bilinear inequality constraints in which all bilinear terms share a common variable. For this structured class of nonconvex sets, we provide a complete characterization of the extreme points of the convex hull and derive an explicit description of all facet-defining inequalities, thereby obtaining a full polyhedral description of the convex hull. In addition, we develop a polynomial-time separation algorithm for the facet-defining inequalities and illustrate its effectiveness through examples. These results offer both structural insight into the geometry of the convex hull and algorithmic tools for identifying violated inequalities.
ER -