Flat lower envelopes solve bounded monomial convexification on two-variable cones
Bounded monomial sets are basic relaxable objects in deterministic global optimization. Belotti's 2025 Mathematical Programming article established the upper envelope for two-variable cones and the lower envelope in dimension two, while leaving the lower envelope open in dimensions greater than two. We close this gap by proving that, in every dimension of at least three, the lower convex envelope over the bounded monomial set intersected with a two-variable cone is flat: after convexifying the restricted epigraph, the only lower constraint on the graph variable is the imposed lower value bound. The formula is independent of the upper value bound and the total homogeneity degree. The proof is based on a level-set convexification identity: every point in the monomial superlevel set inside the cone is either on the target level or an explicit convex combination of two points on that level. A single coordinate outside the constrained pair supplies the required compensation, which also explains why the result fails sharply in dimension two. Combining this lower-envelope formula with Belotti's known upper envelope yields the complete convex hull of the bounded graph for all homogeneity regimes in dimensions of at least three. We also give constructive certificates, separation conditions, a notation summary in the back matter, and reproducible numerical diagnostics showing that the two-point certificates are recovered to roundoff-level reconstruction accuracy over representative regimes.
1. Belotti P. Convex envelopes of bounded monomials on two-variable cones. Math Program. 2025;211(1–2):93–123. https://doi.org/10.1007/s10107-025-02212-5
2. McCormick GP. Computability of global solutions to factorable nonconvex programs: Part I–Convex underestimating problems. Math Program. 1976;10(1):147–175. https://doi.org/10.1007/BF01580665
3. Al-Khayyal FA, Falk JE. Jointly constrained biconvex programming. Math Oper Res. 1983;8(2):273–286. https://doi.org/10.1287/moor.8.2.273
4. Rikun AD. A convex envelope formula for multilinear functions. J Glob Optim. 1997;10(4):425–437. https://doi.org/10.1023/A:1008217604285
5. Meyer CA, Floudas CA. Trilinear monomials with mixed sign domains: Facets of the convex and concave envelopes. J Glob Optim. 2004;29(2):125–155. https://doi.org/10.1023/B:JOGO.0000042112.72379.e6
6. Anstreicher KM, Burer S, Park K. Convex hull representations for bounded products of variables. J Glob Optim. 2021;80:757–778. https://doi.org/10.1007/s10898-021-01046-7
7. Nguyen TT, Richard J-PP, Tawarmalani M. Deriving convex hulls through lifting and projection. Math Program. 2018;169(2):377–415. https://doi.org/10.1007/s10107-017-1138-3
8. Tawarmalani M, Sahinidis NV. Convexification and Global Optimization in Continuous and Mixed-Integer Nonlinear Programming. Kluwer Academic Publishers; 2002. https://doi.org/10.1007/978-1-4757-3532-1
9. He T, Tawarmalani M. A new framework to relax composite functions in nonlinear programs. Math Program. 2021;190:427–466. https://doi.org/10.1007/s10107-020-01541-x
10. Kim J, Richard J-PP, Tawarmalani M. Piecewise polyhedral relaxations of multilinear optimization. SIAM J Optim. 2024;34(4):3167–3193. https://doi.org/10.1137/22M1507486
11. Horst R, Tuy H. Global Optimization: Deterministic Approachesn, 3rd rev. and enl. ed. Springer; 1996. https://doi.org/10.1007/978-3-662-03199-5
12. Sherali HD, Adams WP. A Reformulation-Linearization Technique for Solving Discrete and Continuous Nonconvex Problems. Kluwer Academic Publishers; 1999. https://doi.org/10.1007/978-1-4757-4388-3
13. Belotti P, Lee J, Liberti L, Margot F, Wächter A. Branching and bounds tightening techniques for non-convex MINLP. Optim Methods Softw. 2009;24(4–5):597–634. https://doi.org/10.1080/10556780903087124
14. Smith EMB, Pantelides CC. A symbolic reformulation/spatial branch-and-bound algorithm for the global optimisation of nonconvex MINLPs. Comput Chem Eng. 1999;23(4–5):457–478. https://doi.org/10.1016/S0098-1354(98)00286-5
15. Sahinidis NV. BARON: A general purpose global optimization software package. J Glob Optim. 1996;8(2):201–205. https://doi.org/10.1007/BF00138693
16. Misener R, Floudas CA. ANTIGONE: Algorithms for continuous/integer global optimization of nonlinear equations. J Glob Optim. 2014;59(2–3):503–526. https://doi.org/10.1007/s10898-014-0166-2
17. Bestuzheva K, Besançon M, Chen W-K, et al. The SCIP Optimization Suite 8.0. arXiv. Published 2021. https://arxiv.org/abs/2112.08872
18. Irkıl N, Pişkin E, Agarwal P. Global existence and decay of solutions for a system of viscoelastic wave equations of Kirchhoff type with logarithmic nonlinearity. Math Methods Appl Sci. 2022;45(5):2921–2948. https://doi.org/10.1002/mma.7964
19. Rajchakit G, Sriraman R, Boonsatit N, Hammachukiattikul P, Lim CP, Agarwal P. Global exponential stability of Clifford-valued neural networks with time-varying delays and impulsive effects. Adv Differ Equ. 2021;2021:208. https://doi.org/10.1186/s13662-021-03367-z
20. Zhang Y, Agarwal P, Bhatnagar V, Balochian S, Yan J. Swarm intelligence and its applications. Sci World J. 2013;2013:528069. https://doi.org/10.1155/2013/528069
21. Zhang Y, Agarwal P, Bhatnagar V, Balochian S, Zhang X. Swarm Intelligence and Its Applications 2014. Sci World J. 2014;2014:204294. https://doi.org/10.1155/2014/204294
22. Saber S. Solution to ∂-problem with support conditions in weakly q-convex domains. Commun Korean Math Soc. 2018;33(2):409–421. https://doi.org/10.4134/CKMS.c170022
23. Saber S. Compactness of commutators of Toeplitz operators on q-pseudoconvex domains. Electron J Differ Equ. 2018;2018(111):1–17. Accessed June 10, 2026. https://hdl.handle.net/10877/15302
24. Saber S. Compactness of the complex Green operator in a Stein manifold. UPB Sci Bull Ser A. 2019;81(2):185–200. Accessed June 10, 2026. https://www.scientificbulletin.upb.ro/static/pdfs/rez625_100458.pdf
25. Boyd S, Kim S-J, Vandenberghe L, Hassibi A. A tutorial on geometric programming. Optim Eng. 2007;8(1):67–127. https://doi.org/10.1007/s11081-007-9001-7
26. Ecker JG. Geometric programming: Methods, computations and applications. SIAM Rev. 1980;22(3):338–362. https://doi.org/10.1137/1022058
27. Duffin RJ, Peterson EL, Zener C. Geometric Programming: Theory and Application. Wiley; 1967.
28. Boyd SP, Kim S-J, Patil DD, Horowitz MA. Digital circuit optimization via geometric programming. Oper Res. 2005;53(6):899–932. https://doi.org/10.1287/opre.1050.0254
29. Hershenson MDM, Boyd SP, Lee TH. Optimal design of a CMOS op-amp via geometric programming. IEEE Trans Comput-Aided Des Integr Circuits Syst. 2001;20(1):1–21. https://doi.org/10.1109/43.905671
30. Hoburg W, Abbeel P. Geometric programming for aircraft design optimization. AIAA J. 2014;52(11):2414–2426. https://doi.org/10.2514/1.J052732
31. Ogura M, Kishida M, Lam J. Geometric programming for optimal positive linear systems. IEEE Trans Autom Control. 2020;65(11):4648–4663. https://doi.org/10.1109/TAC.2019.2960697
32. Lu H-C, Li H-L, Gounaris CE, Floudas CA. Convex relaxation for solving posynomial programs. J Glob Optim. 2010;46(1):147–154. https://doi.org/10.1007/s10898-009-9414-2
33. Tsai J-F, Lin M-H. An efficient global approach for posynomial geometric programming problems. INFORMS J Comput. 2011;23(3):483–492. https://doi.org/10.1287/ijoc.1100.0403
34. Neumaier A. Interval Methods for Systems of Equations. Cambridge University Press; 1990. https:///doi.org/10.1017/CBO9780511526473
35. Lee J, Skipper D, Speakman E. Algorithmic and modeling insights via volumetric comparison of polyhedral relaxations. Math Program. 2018;170(1):121–140. https://doi.org/10.1007/s10107-018-1272-6
36. Speakman E, Lee J. Quantifying double McCormick. Math Oper Res. 2017;42(4):1230–1253. https://doi.org/10.1287/moor.2017.0846
37. Speakman E, Lee J. On branching-point selection for trilinear monomials in spatial branch-and-bound: The hull relaxation. J Glob Optim. 2018;72(2):129–153. https://doi.org/10.1007/s10898-018-0620-7
38. Lee J, Skipper D, Speakman E. Gaining or losing perspective. J Glob Optim. 2022;82:835–862. https://doi.org/10.1007/s10898-021-01055-6
39. Rockafellar RT. Convex Analysis. Princeton University Press; 1970. https://www.jstor.org/stable/j.ctt14bs1ff
40. Hiriart-Urruty J-B, Lemaréchal C. Convex Analysis and Minimization Algorithms I: Fundamentals. Springer; 1993. https://doi.org/10.1007/978-3-662-02796-7
41. Boyd S, Vandenberghe L. Convex Optimization. Cambridge University Press; 2004. https://doi.org/10.1017/CBO9780511804441
42. Ben-Tal A, Nemirovski A. Lectures on Modern Convex Optimization. SIAM; 2001. https://doi.org/10.1137/1.9780898718829
43. Bénichou M, Gauthier JM, Girodet P, Hentges G, Ribière G, Vincent O. Experiments in mixed-integer linear programming. Math Program. 1971;1(1):76–94. https://doi.org/10.1007/BF01584074
44. Belotti P, Gőz JC, Pólik I, Ralphs TK, Terlaky T. A complete characterization of disjunctive conic cuts for mixed integer second order cone optimization. Discret Optim. 2017;24:3–31. https://doi.org/10.1016/j.disopt.2016.10.001
45. Speakman E, Yu H, Lee J. Experimental validation of volume-based comparison for double-McCormick relaxations. In: Salvagnin D, Lombardi M, editors. Integration of AI and OR Techniques in Constraint Programming. CPAIOR 2017. Lecture Notes in Computer Science, vol 10335. Springer; 2017:229–243. https://doi.org/10.1007/978-3-319-59776-8_19