Convexification of a Separable Function over a Polyhedral Ground Set

2025/10/18 by Santanu S. Dey, Dey, Santanu S., Burak Kocuk +1
Computer Science · Mathematics · #Advanced Optimization Algorithms Research #Complexity and Algorithms in Graphs #FOS: Mathematics #Optimization and Control (math.OC) #Optimization and Variational Analysis

paper · pdf · doi:10.48550/arxiv.2510.16595

openalex publication_date 2025/10/18 · openalex created_date 2025/10/22 · openalex updated_date 2026/07/28

Abstract

In this paper, we study the set S^κ= \ (x,y)\inG×ℝⁿ : y_j = x_j^κ, j=1,…,n\, where κ> 1 and the ground set G is a nonempty polytope contained in [0,1]ⁿ. 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 S^κ or its tight outer-approximation for the special case when the ground set 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 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→∞ 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.

Citations

• A second-order cone representable class of nonconvex quadratic programs
• Valid Cuts for the Design of Potential-based Flow Networks
• Global Optimization of Gas Transportation and Storage: Convex Hull Characterizations and Relaxations
• Solving continuous and discrete nonlinear programs with BARON
• Gaining or losing perspective for convex multivariate functions on box domains
• Convexification Techniques for Fractional Programs
• A reformulation-enumeration MINLP algorithm for gas network design
• On Standard Quadratic Programs with Exact and Inexact Doubly Nonnegative Relaxations
• Global Solutions of Nonconvex Standard Quadratic Programs via Mixed Integer Linear Programming Reformulations

Related

• Strengthened SDP Relaxation for an Extended Trust Region Subproblem with an Application to Optimal Power Flow
• Relaxations for Non-Separable Cardinality/Rank Penalties
• The convex hull of a quadratic constraint over a polytope
• A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
• Separable Concave Optimization Approximately Equals Piecewise-Linear Optimization