Convexification of a Separable Function over a Polyhedral Ground Set
Preprint
Abstract
In this paper, we study the set $\mathcal{S}^κ= \{ (x,y)\in\mathcal{G}\times\mathbb{R}^n : y_j = x_j^κ, j=1,\dots,n\}$, where $κ> 1$ and the ground set $\mathcal{G}$ is a nonempty polytope contained in $[0,1]^n$. This nonconvex set is closely related to separable standard quadratic programming and appears as a substructure in potential-based network flow problems from gas and water networks. Our aim is to obtain the convex hull of $\mathcal{S}^κ$ or its tight outer-approximation for the special case when the ground set $\mathcal{G}$ is the standard simplex. We propose power cone, second-order cone and semidefinite programming relaxations for this purpose, which are further strengthened by the Reformulation-Linearization Technique and the Reformulation-Perspectification Technique. For $κ=2$, we obtain the convex hull of $\mathcal{S}^κ$ in the low-dimensional setting. For general $κ$, we give approximation guarantees for the power cone representable relaxation, the weakest relaxation we consider. We prove that this weakest relaxation is tight with probability one as $n\to\infty$ when a uniformly generated linear objective is optimized over it. Finally, we provide the results of our extensive computational experiments comparing the empirical strength of several conic programming relaxations that we propose.
Keywords
All Related Versions
This publication has 22 references indexed in Scilit:
- Solving continuous and discrete nonlinear programs with BARONComputational Optimization and Applications, 2024
- Gaining or losing perspective for convex multivariate functions on box domainsMathematical Programming, 2024
- Global solutions of nonconvex standard quadratic programs via mixed integer linear programming reformulationsJournal of Global Optimization, 2021
- On standard quadratic programs with exact and inexact doubly nonnegative relaxationsMathematical Programming, 2021
- Algorithmic results for potential‐based flows: Easy and hard casesNetworks, 2018
- Error bounds for monomial convexification in polynomial optimizationMathematical Programming, 2018
- On the copositive representation of binary and continuous nonconvex quadratic programsMathematical Programming, 2008
- Convex envelopes for edge-concave functionsMathematical Programming, 2005
- Concave envelopes of monomial functions over rectanglesNaval Research Logistics (NRL), 2004
- A Reformulation-Linearization Technique for Solving Discrete and Continuous Nonconvex Problems1999