arxiv: 2605.01493 · v1 · submitted 2026-05-02 · 🧮 math.OC

Recognition: unknown

On the convex hull of the graph of a simple monomial

Jon Lee , Daphne Skipper , Emily Speakman

Authors on Pith no claims yet

Pith reviewed 2026-05-09 14:27 UTC · model grok-4.3

classification 🧮 math.OC

keywords convex hullmonomialgraph of functionvolume formulalinear inequalitiesbox domainglobal optimizationspatial branch-and-bound

0 comments

The pith

The convex hull of the graph of a simple monomial over a nonnegative box is fully described by linear inequalities when at most one lower bound is positive.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper examines the convex hull of the graph of a monomial like the product of powers of variables over a box domain in the nonnegative orthant. It supplies an explicit description of this hull using linear inequalities along with a closed-form volume formula, restricted to the case where at most one variable has a positive lower bound. The motivation comes from improving how monomials are handled inside spatial branch-and-bound procedures for global optimization. A sympathetic reader would care because tighter, exact convex relaxations for common nonlinear terms can reduce the computational effort needed to solve nonconvex problems to proven optimality.

Core claim

We give a description via linear inequalities, and a formula for the volume, of the convex hull of the graph of a simple monomial on a nonnegative box domain in arbitrary dimension, where at most one of the variable lower bounds is positive.

What carries the argument

The convex hull of the monomial graph, cut out exactly by a finite collection of linear inequalities that incorporate the monomial exponents and the box bounds.

If this is right

Exact convex envelopes become available for monomials inside spatial branch-and-bound solvers.
The volume formula quantifies the relaxation gap and can guide branching decisions.
The inequality description applies uniformly in any dimension.
The zero-lower-bound case is recovered as a special instance of the given formulas.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The same style of derivation could be attempted for other elementary nonlinearities provided the domain restriction is kept.
Implementing the inequalities directly in a solver might eliminate the need for dynamic cut generation on monomial terms.
Low-dimensional numerical checks of the volume formula against sampled points would provide quick confirmation before scaling to higher dimensions.

Load-bearing premise

The domain is a nonnegative box in which at most one variable has a positive lower bound.

What would settle it

Take a concrete monomial with two positive lower bounds, compute its true convex hull by vertex enumeration or convex-hull software, and check whether the inequalities claimed in the paper still describe it exactly.

read the original abstract

Motivated by previous efforts toward mathematically analyzing the treatment of monomials in spatial branch-and-bound, we study the convex hull of the graph of a simple monomial on a nonnegative box domain in arbitrary dimension, where at most one of the variable lower bounds is positive. We give: (i) a description via linear inequalities, and (ii) a formula for the volume.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

This paper gives an explicit linear-inequality description and volume formula for the convex hull of a monomial graph over a nonnegative box with at most one positive lower bound.

read the letter

The paper gives a linear inequality description and volume formula for the convex hull of the graph of a simple monomial on a nonnegative box domain in arbitrary dimension, where at most one of the variable lower bounds is positive. That is the core contribution they deliver. They build on prior work analyzing monomials in spatial branch-and-bound and turn the restricted case into something that can be written down and used directly in a relaxation. The inequalities are linear, which matters for solvers, and the volume formula is closed-form rather than left as an integral or numerical quantity. If the proofs are complete, this is the kind of concrete polyhedral result that can tighten bounds in global optimization without extra overhead at runtime. The paper does well by stating the domain restriction clearly and staying inside it instead of claiming a general result it cannot support. The construction appears tailored to the case where all variables are nonnegative and at most one lower bound is positive, which matches the stress-test note that no unstated extension is required. The main soft spot is exactly that restriction. When two or more variables have positive lower bounds the hull description becomes more involved, and this work does not address it. That is not a flaw in the paper, just a limit on how far the result travels. I see no circularity or reliance on fitted quantities; the claim is presented as a direct characterization. This is for researchers who build or analyze relaxations inside spatial branch-and-bound or who need explicit convex hulls for monomial terms in low-dimensional boxes. A reader working on solver implementation or polyhedral methods will get usable inequalities and a volume expression they can check. It is not a broad theoretical leap, but the setting is practical and the output is verifiable. I would send it to peer review so the inequalities and volume formula can be examined in detail.

Referee Report

0 major / 2 minor

Summary. The manuscript derives an explicit linear-inequality description of the convex hull of the graph of the monomial function x ↦ ∏_{i=1}^n x_i over a box domain [l,u] ⊂ R_+^n in which at most one coordinate of l is positive, together with a closed-form expression for the volume of this convex hull. The domain restriction is stated at the outset and the derivations are carried out inside it.

Significance. If the claimed inequality description and volume formula are correct, the work supplies a concrete, finitely generated convex relaxation for a common nonconvex term that appears in spatial branch-and-bound. The explicit volume formula additionally permits quantitative comparison of relaxation strength across different box geometries. Both contributions are directly usable in the analysis of global optimization algorithms.

minor comments (2)

The abstract and introduction refer to a “simple monomial” without a precise definition in the opening paragraphs; a one-sentence clarification of the term would improve readability.
Notation for the lower-bound vector l is introduced in the abstract but the subsequent sections occasionally switch between component-wise and vector notation without explicit reminder; a short notational table or consistent use of boldface would help.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive summary, assessment of significance, and recommendation of minor revision. No specific major comments were listed in the report, so we interpret this as an indication that the core contributions are acceptable as presented.

Circularity Check

0 steps flagged

No significant circularity in derivation chain

full rationale

The paper states its domain restriction (nonnegative box with at most one positive lower bound) explicitly up front and derives both the linear-inequality description and volume formula directly for that case. No step reduces a claimed prediction or uniqueness result to a fitted input, self-citation chain, or ansatz smuggled from prior work by the same authors; the central claims are presented as exact characterizations obtained inside the stated assumptions without external load-bearing citations or redefinitions that collapse to the inputs.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract-only review supplies no explicit free parameters, axioms, or invented entities; the result is presented as a direct geometric characterization.

pith-pipeline@v0.9.0 · 5346 in / 1072 out tokens · 24663 ms · 2026-05-09T14:27:23.067551+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

18 extracted references · 10 canonical work pages

[1]

Lee, J., Skipper, D., Speakman, E.: On the convex hull of the graph of a simple monomial, STOGO 2025, Proceedings of the XVI Workshop on Global Optimization, 167–171 (2025)

2025
[2]

Comput- ers & Chemical Engineering23(4), 457–478 (1999)

Smith, E.M.B., Pantelides, C.C.: A symbolic reformulation/spatial branch-and- bound algorithm for the global optimisation of nonconvex minlps. Comput- ers & Chemical Engineering23(4), 457–478 (1999). https://doi.org/10.1016/ S0098-1354(98)00286-5

1999
[3]

Graduate Texts in Mathematics, 152

Ziegler, G.M.: Lectures on Polytopes. Graduate Texts in Mathematics, 152. Springer, New York (1995). https://doi.org/10.1007/978-1-4613-8431-1

work page doi:10.1007/978-1-4613-8431-1 1995
[4]

Jour- nal of Automated Reasoning26(2), 107–137 (2001) https://doi.org/10.1023/A: 1026518331905

Rikun, A.D.: A convex envelope formula for multilinear functions. Jour- nal of Global Optimization10, 425–437 (1997). https://doi.org/10.1023/A: 1008217604285

work page doi:10.1023/a: 1997
[5]

Mathematical Programming170, 121–140 (2018)

Lee, J., Skipper, D., Speakman, E.: Algorithmic and modeling insights via vol- umetric comparison of polyhedral relaxations. Mathematical Programming170, 121–140 (2018). https://doi.org/10.1007/s10107-018-1272-6

work page doi:10.1007/s10107-018-1272-6 2018
[6]

Discrete Applied Mathematics275, 79–94 (2020)

Lee, J., Skipper, D.: Volume computation for sparse boolean quadric relaxations. Discrete Applied Mathematics275, 79–94 (2020). https://doi.org/10.1016/j.dam. 2018.10.038

work page doi:10.1016/j.dam 2020
[7]

Mathematical P rogramming 10, 147–175 (1976) https://doi.org/10.1007/BF01580665

McCormick, G.P.: Computability of global solutions to factorable nonconvex pro- grams: Part I -— convex underestimating problems. Mathematical Programming, Series B10(1), 147–175 (1976). https://doi.org/10.1007/BF01580665

work page doi:10.1007/bf01580665 1976
[9]

Journal of Global Optimization29, 125–155 (2004) https://doi.org/10.1023/B:JOGO.0000042112.72379.e6

Meyer, C.A., Floudas, C.A.: Trilinear monomials with mixed sign domains: Facets of the convex and concave envelopes. Journal of Global Optimization29, 125–155 (2004) https://doi.org/10.1023/B:JOGO.0000042112.72379.e6

work page doi:10.1023/b:jogo.0000042112.72379.e6 2004
[10]

Speakman, E.: Volumetric guidance for handling triple products in spatial branch- and-bound. Ph.D. Dissertation, University of Michigan (April 2017). https:// deepblue.lib.umich.edu/items/17bbe5ef-d264-4575-beb9-9581d4b239f7

2017
[11]

Mathematics of Oper- ations Research42(4), 1230–1253 (2017)

Speakman, E., Lee, J.: Quantifying double McCormick. Mathematics of Oper- ations Research42(4), 1230–1253 (2017). https://doi.org/10.1287/moor.2017. 0846

work page doi:10.1287/moor.2017 2017
[12]

Discrete Appllied Mathematics308, 36–45 (2022)

Speakman, E., Averkov, G.: Computing the volume of the convex hull of the graph of a trilinear monomial using mixed volumes. Discrete Appllied Mathematics308, 36–45 (2022). https://doi.org/10.1016/j.dam.2019.09.007

work page doi:10.1016/j.dam.2019.09.007 2022
[13]

https://arxiv.org/abs/2512.13964 (2025)

Makhoul, L., Speakman, E.: Volume formulae for the convex hull of the graph of a trilinear monomial: A complete characterization for general box domains. https://arxiv.org/abs/2512.13964 (2025)

work page arXiv 2025
[14]

Journal of Global Optimization 72, 129–153 (2018)

Speakman, E., Lee, J.: On branching-point selection for trilinear monomials in spatial branch-and-bound: the hull relaxation. Journal of Global Optimization 72, 129–153 (2018). https://doi.org/10.1007/s10898-018-0620-7

work page doi:10.1007/s10898-018-0620-7 2018
[15]

In: Salvagnin, D., Lombardi, M

Speakman, E., Yu, H., Lee, J.: Experimental validation of volume-based compar- ison for double-McCormick relaxations. In: Salvagnin, D., Lombardi, M. (eds.) CPAIOR 2017, pp. 229–243. Springer, Cham (2017). https://doi.org/10.1007/ 978-3-319-59776-8 19

2017
[16]

Journal of Global Optimization47(4), 661–685 (2010)

Cafieri, S., Lee, J., Liberti, L.: On convex relaxations of quadrilinear terms. Journal of Global Optimization47(4), 661–685 (2010). https://doi.org/10.1007/ s10898-009-9484-1

2010
[17]

Jr.: Geometric comparison of combinatorial polytopes

Lee, J., Morris, W.D. Jr.: Geometric comparison of combinatorial polytopes. Discrete Applied Mathematics55, 163–182 (1994). https://doi.org/10.1016/ 0166-218X(94)90006-X

1994
[18]

Discrete Mathematics163(1), 293–298 (1997)

Ko, C.-W., Lee, J., Steingr´ ımsson, E.: The volume of relaxed boolean-quadric and cut polytopes. Discrete Mathematics163(1), 293–298 (1997). https://doi.org/10. 1016/0012-365X(95)00343-U

1997
[19]

Dis- crete & Computational Geometry12(4), 465–479 (1994)

Steingr´ ımsson, E.: A decomposition of 2-weak vertex-packing polytopes. Dis- crete & Computational Geometry12(4), 465–479 (1994). https://doi.org/10. 1007/BF02574393 30

1994