{"ID":2853473,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2510.16595","arxiv_id":"2510.16595","title":"Convexification of a Separable Function over a Polyhedral Ground Set","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 $κ\u003e 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.","short_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 $κ\u003e 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 substruc...","url_abs":"https://arxiv.org/abs/2510.16595","url_pdf":"https://arxiv.org/pdf/2510.16595v1","authors":"[\"Santanu S. Dey\",\"Burak Kocuk\"]","published":"2025-10-18T17:49:36Z","proceeding":"math.OC","tasks":"[\"math.OC\"]","methods":"[]","has_code":false}