(119c) Convexification of Nonconvex Compositions with Norms

Nonconvex optimization problems involving compositions of functions with norms arise in diverse settings such as facility location [1], molecular energy minimization [2], and object packing [3]. These problems present a challenge for global optimization algorithms based on spatial branch-and-bound since they exhibit a high degree of symmetry, and factorable relaxations of reverse convex constraints and compositions of functions with norms are generally weak [4,5]. Global minima have been found for small instances [6], but many problems remain open.

In this work, we introduce novel convex envelopes for common functions composed with norms based on the characterization of their generating sets. The theoretical development exploits the fact that the generating set of these functions is a finite collection of compact convex sets [7]. We implement our envelopes in the global optimization solver BARON and demonstrate their impact using open problems from the literature as a benchmark.

[1] P. Kalczynski and Z. Drezner. Extremely non-convex optimization problems: the case of the multiple obnoxious facilities location. Optimization Letters, 16:1153–1166, 2022.

[2] M. R. Hoare and P. Pal. Physical cluster mechanics: statics and energy surfaces for monatomic systems. Advances in Physics, 20:161–196, 1971.

[3] A. Wang, C. L. Hanselman, and C. E. Gounaris. A customized branch-and-bound approach for irregular shape nesting. Journal of Global Optimization, 71:935–955, 2018.

[4] A. Khajavirad. Packing circles in a square: a theoretical comparison of various convexification techniques. Technical report, Optimization Online, 2017

[5] A. Wang and C. E. Gounaris. On tackling reverse convex constraints for non-overlapping of unequal circles. Journal of Global Optimization, 80:357-385, 2021.

[6] M. C. Markót and T. Csendes. A New Verified Optimization Technique for the "Packing Circles in a Unit Square" Problems. SIAM Journal on Optimization, 16, 193– 219.

[7] A. Khajavirad and N. V. Sahinidis. Convex envelopes generated from finitely many compact convex sets. Mathematical Programming, 137:371–408, 2013.