Convexification of a Separable Function over a Polyhedral Ground Set

Abstract

In this paper, we study the set ${\mathcal{S}}^{\kappa }=\{(x,y)\in \mathcal{G}\times {\mathbb{R}}^n:y_j=x_j^{\kappa },j=1,\dots ,n\}$, where $\kappa >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}}^{\kappa }$ 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 $\kappa =2$, we obtain the convex hull of ${\mathcal{S}}^{\kappa }$ in the low-dimensional setting. For general $\kappa$, 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.