Cone Product Reformulation for Global Optimization

In this paper, we study nonconvex optimization problems involving sum of linear times convex functions as well as conic constraints belonging to one of the five basic cones, that is, linear cone, second order cone, power cone, exponential cone, and semidefinite cone. By using the reformulation perspectification technique, we can obtain a convex relaxation by forming the perspective of each convex function and linearizing all product terms with newly introduced variables. To further tighten the approximation, we can pairwise multiply parts of the conic constraints. In this paper, we analyze all possibilities of multiplying conic constraints. Particularly noteworthy are the novel results involving the power cone and exponential cone. We delineate methods for deriving new, valid linear and second order cone inequalities for pairwise constraint multiplications involving the power cone and exponential cone, thereby enhancing the strength of the approximation. Numerical experiments on a quadratic optimization problem over exponential cone constraints and on a robust palatable diet problem over power cone constraints demonstrate that including additional inequalities generated from the proposed pairwise multiplications improves the approximation. Moreover, when incorporated in a branch-and-bound procedure, the global optimal solution of the original nonconvex optimization problem can often be obtained faster than by BARON.

History: Accepted by Antonio Frangioni, Area Editor for Design & Analysis of Algorithms–Continuous.

Funding: D. de Moor was supported by the Nederlandse Organisatie voor Wetenschappelijk Onderzoek [Grant 406.18.EB.003]. J. Zhen was supported by the National Natural Science Foundation of China [Grants 72595841, 72595840] and by the Ministry of Education Social Sciences Innovative Group on Complex Systems Modeling in Economic Management in the Era of Digital Intelligence at the University of Chinese Academy of Sciences.

Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information (https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2023.0345) as well as from the IJOC GitHub software repository (https://github.com/INFORMSJoC/2023.0345). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/.