Pith. sign in

REVIEW 4 major objections 5 minor 24 references

A novel exact approach to polynomial optimization

T0 review · 4 major / 5 minor · reviewed 2026-08-06 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The paper claims every polynomial on the unit box decomposes into linear box-constraint factors times convex quadratics, and the tightest such split, from one SDP, gives exact global optimization that beats SOS and BARON.

desk verdict The paper's advertised arbitrary-degree SLC existence theorem is false, but the degree-3/4 core and the best-decomposition SDP are genuine contributions that deserve referee attention after major revision. read the letter →

arxiv 2507.02120 v1 pith:4XYZ4DIN submitted 2025-07-02 math.OC

Dimitris Bertsimas , Dick den Hertog , Thodoris Koukouvinos This is my paper · ORCID
classification math.OC MSC 90C2690C2290C30
keywords polynomialoptimizationSLCdecompositionconvexrelaxationsemidefiniteprogrammingbranchandboundglobalsumoflineartimesnonconvex
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

This paper proposes a convex-relaxation route to global polynomial optimization that avoids large sum-of-squares lifts. The idea is to decompose the objective polynomial as a sum of linear times convex (SLC) terms: products of at most $d-2$ box-constraint factors (variables or one-minus-variables) multiplied by convex quadratics. The paper claims to prove that such decompositions always exist for polynomials of any degree on $[0,1]^n$, and then to select the decomposition that gives the tightest lower bound by solving a single semidefinite program whose largest linear-matrix-inequality block is $(n+1)\times(n+1)$. If the claims hold, the resulting bounds are strong enough that spatial branch-and-bound often closes the gap at the root node, and the paper reports solving degree-3 instances with 40 variables and degree-4 instances with 20 variables in under an hour.

What carries the argument

The load-bearing object is the SLC decomposition with box-constraint factors: $p_d=\sum f_{I,J}q_{I,J}$, where $f_{I,J}$ are products of distinct $x_i$ and $(1-x_j)$ factors of total degree at most $d-2$ and $q_{I,J}$ are convex quadratics. The argument has three parts: coefficient matching that assigns each monomial of $p_d$ to one quadratic via the tensor of polynomial coefficients; convexity certification by making each quadratic's Hessian diagonally dominant through a global $\alpha\|x\|^2$ shift and invoking the Gershgorin circle theorem; and bound-tightening by treating the decomposition coefficients as uncertain parameters in a robust optimization problem, then dualizing the inner maximization into the SDP formulation whose LMIs have $(n+1)\times(n+1)$ blocks.

What would settle it

Take $p(x)=x_1^4$ on $[0,1]^1$ and try to write it as in Theorem 6. The allowed factors $f_{I,J}$ for $d=4$ are products of distinct box factors of degree at most 2: $1$, $x$, $1-x$, and $x(1-x)$. Each times a convex quadratic can contribute at most one factor of $x$ or $1-x$, so no term can produce the $x^4$ monomial unless a factor such as $x^2$ is allowed, which the distinctness condition forbids. A direct coefficient match on this one-variable quartic therefore contradicts the universal existence claim as stated.

Watch

Extended reading notes

Core claim

The central discovery is the SLC decomposition theorem: any polynomial $p_d$ of degree $d$ over the unit box can be written as $p_d(x)=\sum_{I,J,\,I\cap J=\emptyset,\,|I\cup J|\le d-2} f_{I,J}(x)q_{I,J}(x)$, where $f_{I,J}(x)=\prod_{i\in I}x_i\prod_{j\in J}(1-x_j)$ and every $q_{I,J}$ is a convex quadratic. The paper further shows that the infinite family of valid decompositions can be parametrized by coefficient sets $Z$ (or $V$), and that maximizing the resulting lower bound over all valid decompositions is a robust convex problem whose dual is a single SDP with $(n+1)\times(n+1)$ LMI blocks. This yields both a convex relaxation of the original polynomial problem and, when embedded in branch-and-bound, a certified global optimum.

Load-bearing premise

The existence proof assumes every monomial can be matched by multiplying a convex quadratic with a product of distinct variables or one-minus-variables, so a monomial in which the same variable appears more than once has no direct match in the construction.

Editorial extensions

If this is right

  • If the existence result holds, every polynomial optimization over box-type constraints has an SDP relaxation with $(n+1)\times(n+1)$ LMI blocks, avoiding the $O(n^d)$ block dimension of SOS hierarchies.
  • The best-decomposition SDP supplies lower bounds that are often tight at the root; when not, spatial branch-and-bound with these bounds provides a certificate of global optimality.
  • The convex-relaxation step also handles non-polynomial convex constraints such as log-sum-exp, which SOS cannot process directly.
  • The reported numerics show degree-3 problems with 40 variables and degree-4 problems with 20 variables solved to optimality within one hour, beating BARON and SOS on those instances.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • A sharp test of the universal claim is to apply the construction to monomials with repeated variables, such as $x_1^4$; if the distinctness restriction on $f_{I,J}$ cannot be lifted, the theorem as stated needs a degree or sparsity qualification even though the numerical instances may still admit valid decompositions.
  • The robust-optimization formulation suggests a cutting-set variant that generates only the worst-case decomposition coefficients on demand, trading a larger iteration count for smaller LMI stacks; the paper notes this adversarial option but does not implement it.
  • Since polynomial constraints can be decomposed the same way (per the paper's Remark 3), the method could be extended to polynomial-constrained conic programs, where the same SLC bound would apply inside the feasible set rather than only on the objective.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

4 major / 5 minor

Summary. The paper proposes an SLC (sum of linear times convex) decomposition approach to polynomial optimization on the unit box. For a polynomial p_d, the authors claim that p_d can always be written as a sum over products f_{I,J}(x) q_{I,J}(x), where f_{I,J} is a product of distinct variables and (1-x_j) box factors and each q_{I,J} is a convex quadratic. They then formulate the selection of the tightest such decomposition as a robust optimization problem, derive an SDP reformulation using duality, and report numerical results for degree-3 and degree-4 polynomials on box, polynomial-constraint, and log-sum-exp constraint sets. The degree-3 construction is concrete, but the paper's central advertised claim is the arbitrary-degree existence theorem stated in the abstract and in Theorem 6.

Significance. If the arbitrary-degree existence theorem were correct, the approach would be an interesting alternative to SOS/Lasserre hierarchies, and the robust-SDP selection of the best decomposition is a genuinely appealing idea. The degree-3 construction using Gershgorin-based diagonal dominance is explicit and likely correct, and the numerical comparisons on degree-3 and degree-4 instances are informative. However, the central existence claim is false as stated: monomials with repeated variables cannot be represented by products of disjoint box factors and convex quadratics. Since the arbitrary-degree claim is the headline contribution and is used to motivate the SDP formulation and the numerical scaling claims, the manuscript cannot be accepted in its current form. The paper does not include machine-checked proofs or reproducible code; the numerical results alone do not compensate for an invalid central theorem.

major comments (4)
  1. [Theorem 6 (Section 4.1)] The theorem is false as stated. For n=1 and d=4, take p_4(x)=x^4 on [0,1]. The only admissible factors f_{I,J}(x) with I∩J=∅ and |I∪J|≤2 are 1, x, and 1-x. Each q_{I,J} is a convex quadratic, so every summand 1·q(x), x·q(x), or (1-x)·q(x) has degree at most 3. No finite sum of such terms can equal x^4. The proof constructs I={σ(1),...,σ(d-2)} for a monomial c x_{σ(1)}···x_{σ(d)}, which requires the d-2 variables in I to be distinct and available as a subset of {1,...,n}. This fails for monomials with fewer than d-2 distinct variables, e.g. x_1^4 or x_1^2 x_2^2. The disjointness condition explicitly rules out repeated factors such as x_1^2. Thus the abstract's claim that SLC decompositions always exist for arbitrary degree is internally inconsistent with the definition of the decomposition class.
  2. [Theorem 4 (Section 3.1)] The degree-4 existence proof is incomplete. The definition F^{ij}_{kl}=c^4_{ijkl} is ambiguous: c^4 is indexed by unordered multisets i≤j≤k≤l, while F^{ij} must be a symmetric matrix in its k,l indices for x^T F^{ij} x to be a well-defined quadratic. If c is extended symmetrically, a monomial such as x_1x_2x_3x_4 is counted in multiple F^{ij} blocks, and the displayed equality after adding α∥x∥² to every quadratic is asserted rather than verified. The sentence 'we can add additional linear terms in the quadratics ... in order to cancel out the extra terms' does not provide the coefficient-wise cancellation argument needed to establish that the sum equals p_4(x). The proof needs a complete algebra check, including the constants in the subtraction term -(1+n+n(n+1)/2)αx_i.
  3. [Theorems 2 and 5 (Sections 2.2 and 3.2)] The strong-duality reformulations are not justified. The proofs cite Theorem 13.1 of Bertsimas and den Hertog, but they do not verify the hypotheses needed for strong duality: Slater's condition for the uncertainty sets Z and V, compactness, or dual attainment. The inner maximization problems are linear in the SLC coefficients over a set described by equality constraints and PSD constraints; without a Slater point, the dual may have a gap. In addition, the reformulation divides by x_i, 1-x_i, u_{ij}, and similar expressions, but the stated constraints (4j)-(4l) and (8m)-(8o) do not enforce strict positivity of these quantities at the solution. At boundary points, the equivalence asserted by the 'if and only if' statements is not established.
  4. [Numerical claims (Section 6)] The abstract states that degree-3 problems with 40 variables and degree-4 problems with 20 variables are solved to optimality in less than an hour. This is supported for the X1 rows in Tables 2 and 3, but Table 2 shows that for X3 with n=30 both 'Ours' and BARON time out at 3600 seconds; Table 3 does not report a 20-variable degree-4 run on X3. The general claim 'we can solve polynomial optimization problems to optimality ... in less than an hour' should be qualified to the tested feasible regions and dimensions.
minor comments (5)
  1. [Section 4.1] The sentence defining f_{I,J} says 'such that |I∪J| is the degree of the polynomial'; it should say the degree of the monomial or, more precisely, the degree of the factor, which is at most d-2.
  2. [Theorem 6 proof] The notation 'where P^{I,J}=0, and P^{I,J}_{σ(d-1)σ(d)}=c' is self-contradictory; the authors mean that P^{I,J} is the zero matrix except for the specified entry.
  3. [Appendix B, Theorem 8 proof] The Hessian entry H_{ij}(x) is described as a polynomial of degree n-3; this should presumably be d-3 (degree of p^i_{d-1} minus 2). The diagonal-dominance argument is otherwise plausible.
  4. [Throughout] There are several typos and repeated phrases, e.g. 'degree 3 terms in the objective objective' in Section 3.2, 'Gershgorin Theorem' repeated, and 'Lassere' for Lasserre. A careful copyedit is needed.
  5. [References] The companion papers Bertsimas et al. (a) and (b) are cited as Optimization Online preprints; full bibliographic details and, ideally, public availability information should be provided since the RPT method and Theorem 13.1 rely on them.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity found: the SLC derivation is self-contained; the Theorem 6 gap is a correctness issue, not a circular one.

full rationale

The paper's derivation chain is not circular. The existence theorems for SLC decompositions are proved by explicit coefficient matching with the target polynomial and by convexification via Gershgorin's theorem; the target result is not assumed. The 'best SLC decomposition' is obtained by maximizing the relaxation lower bound over the set of all valid decompositions, which is an optimization over free coefficients, not a fit to the reported optima. Prior work by the same authors (RPT and robust duality, Bertsimas et al. (a,b); Bertsimas and den Hertog (2022), Theorem 13.1) is invoked as an external technical toolkit and not as evidence for the existence or tightness claims. The numerical experiments are benchmarked against BARON and SOS with independent solvers, so there is no fitted-input-called-prediction structure. The manuscript's apparent gap in Theorem 6 for monomials with repeated variables (e.g., x^4 on [0,1]) is a mathematical correctness concern, not circularity: the proof attempts a construction and may fail, but it does not define the conclusion into the assumptions. Accordingly, no circular step is identified and the score is 0.

Assumptions & free parameters 1 free parameters · 4 assumptions · 0 invented entities

The method's core relies on the box assumption, Gershgorin-based convexity, conic duality, and the authors' prior RPT and branch-and-bound machinery. No new physical entities. The general existence theorem (Theorem 6) is the main unsupported load-bearing item.

free parameters (1)
  • alpha (convexity shift) = max(0, max_i alpha^i_p, alpha_beta)
    Introduced in Theorems 1, 4, and 6 to make quadratics diagonally dominant and hence convex. Computed deterministically from polynomial coefficients, not fitted to data, and cancels in the telescoping sum.
assumptions (4)
  • domain assumption Feasible region can be assumed contained in [0,1]^n via affine transformation
    Used in Section 2 and Theorem 1 to justify the box assumption. Cited to Burer and Letchford (2009).
  • standard math Gershgorin circle theorem implies a diagonally dominant symmetric matrix is positive semidefinite
    Used in Theorem 1, 4, 6, and Appendix B to establish convexity of quadratics.
  • ad hoc to paper Strong duality holds for the inner maximization problem (max over Z of g3 or g4) with no duality gap
    Theorems 2 and 5 rely on Theorem 13.1 of Bertsimas and den Hertog (2022). Slater conditions for the SDP are not verified, so this is an unproven premise.
  • domain assumption The RPT constraint-multiplication scheme yields valid convex relaxations that link x and U
    Taken from Bertsimas et al. (b); used to derive the feasible set X for U,V and the relaxation g3/g4.

how reviews work

0 comments
Cite this review

Pith. "Pith review of A novel exact approach to polynomial optimization." pith.science (2026). https://pith.science/paper/4XYZ4DIN

@misc{pith2026250702120,
  author       = {Pith},
  title        = {Pith review of: A novel exact approach to polynomial optimization},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/4XYZ4DIN}},
  note         = {Machine review of arXiv:2507.02120}
}
read the original abstract

Polynomial optimization problems represent a wide class of optimization problems, with a large number of real-world applications. Current approaches for polynomial optimization, such as the sum of squares (SOS) method, rely on large-scale semidefinite programs, and therefore the scale of problems to which they can be applied is limited and an optimality guarantee is not always provided. Moreover, the problem can have other convex nonlinear parts, that cannot be handled by these approaches. In this paper, we propose an alternative approach for polynomial optimization. We obtain a convex relaxation of the original polynomial optimization problem, by deriving a sum of linear times convex (SLC) functions decomposition for the polynomial. We prove that such SLC decompositions always exist for arbitrary degree polynomials. Moreover, we derive the SLC decomposition that results in the tightest lower bound, thus improving significantly the quality of the obtained bounds in each node of the spatial Branch and Bound method. In the numerical experiments, we show that our approach outperforms state-of-the-art methods for polynomial optimization, such as BARON and SOS. We show that with our method, we can solve polynomial optimization problems to optimality with 40 variables and degree 3, as well as 20 variables and degree 4, in less than an hour.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

24 extracted references · 23 canonical work pages

  1. [1]

    Bakonyi and C.R

    M. Bakonyi and C.R. Johnson. The euclidian distance matrix completion problem. SIAM Journal on Matrix Analysis and Applications, 16 0 (2): 0 646--654, 1995

    work page 1995

  2. [2]

    Bertsimas and D

    D. Bertsimas and D. den Hertog. Robust and Adaptive Optimization. Dynamic Ideas LLC, Belmont, 2022

    work page 2022

  3. [3]

    Bertsimas, D

    D. Bertsimas, D. de Moor, D. den Hertog, T. Koukouvinos, and J. Zhen. A novel algorithm for a broad class of nonconvex optimization problems. Optimization Online, 2023a. URL https://optimization-online. org, a

    work page

  4. [4]

    Bertsimas, D

    D. Bertsimas, D. de Moor, D. den Hertog, T. Koukouvinos, and J. Zhen. Cone product reformulation for global optimization. Optimization Online, 2023b. URL https://optimization-online. org, b

    work page

  5. [5]

    Boyd, S.J

    S. Boyd, S.J. Kim, L. Vandenberghe, and A. Hassibi. A tutorial on geometric programming. Optimization and Engineering, 8: 0 67--127, 2007

    work page 2007

  6. [6]

    Burer and A

    S. Burer and A. N. Letchford. On nonconvex quadratic programming with box constraints. SIAM Journal on Optimization, 20 0 (2): 0 1073--1089, 2009

    work page 2009

  7. [7]

    Dalkiran and H.D

    E. Dalkiran and H.D. Sherali. Rlt-pos: Reformulation-linearization technique-based optimization software for solving polynomial programming problems. Mathematical Programming Computation, 8 0 (3): 0 337--375, 2016

    work page 2016

  8. [8]

    Gershgorin

    S.A. Gershgorin. Uber die abgrenzung der eigenwerte einer matrix. Izvestiya Akademii Nauk SSSR, Seriya Matematicheskaya, 1 0 (7): 0 749--754, 1931

    work page 1931

Show all 24 references
  1. [9]

    Lasserre

    J.B. Lasserre. Global optimization with polynomials and the problem of moments. SIAM Journal on Optimization, 11 0 (3): 0 796--817, 2001

    2001

  2. [10]

    Lasserre

    J.B. Lasserre. A semidefinite programming approach to the generalized problem of moments. Mathematical Programming, 112: 0 65--92, 2008

    2008

  3. [11]

    Lasserre

    J.B. Lasserre. Moments and sums of squares for polynomial optimization and related problems. Journal of Global Optimization, 45 0 (1): 0 39--61, 2009

    2009

  4. [12]

    Lavaei and S.H

    J. Lavaei and S.H. Low. Zero duality gap in optimal power flow problem. IEEE Transactions on Power systems, 27 0 (1): 0 92--107, 2011

    2011

  5. [13]

    Majumdar, A.A

    A. Majumdar, A.A. Ahmadi, and R. Tedrake. Control and verification of high-dimensional systems with dsos and sdsos programming. In 53rd IEEE Conference on Decision and Control, pages 394--401. IEEE, 2014

    2014

  6. [14]

    The MOSEK optimization toolbox for MATLAB manual

    MOSEK ApS . The MOSEK optimization toolbox for MATLAB manual. Version 10.1., 2024. URL http://docs.mosek.com/10.1/toolbox/index.html

    2024

  7. [15]

    Mutapcic and S

    A. Mutapcic and S. Boyd. Cutting-set methods for robust convex optimization with pessimizing oracles. Optimization Methods & Software, 24 0 (3): 0 381--406, 2009

    2009

  8. [16]

    Niu, Y.J

    Y.S. Niu, Y.J. Wang, H. A. L. Thi, and D. T. Pham. High-order moment portfolio optimization via an accelerated difference-of-convex programming approach and sums-of-squares. arXiv preprint arXiv:1906.01509, 2019

    1906 arXiv

  9. [17]

    P.A. Parrilo. Semidefinite programming relaxations for semialgebraic problems. Mathematical Programming, 96: 0 293--320, 2003

    2003

  10. [18]

    Parrilo and B

    P.A. Parrilo and B. Sturmfels. Minimizing polynomial functions. DIMACS Series in Discrete Mathematices and Theoretical Computer Science, pages 83--99, 2003

    2003

  11. [19]

    Pham and Y.S

    D.T. Pham and Y.S. Niu. An efficient dc programming approach for portfolio decision with higher moments. Computational Optimization and Applications, 50: 0 525--554, 2011

    2011

  12. [20]

    Prajna, A

    S. Prajna, A. Papachristodoulou, and P.A. Parrilo. Introducing sostools: A general purpose sum of squares programming solver. In Proceedings of the 41st IEEE Conference on Decision and Control, 2002., volume 1, pages 741--746. IEEE, 2002

    2002

  13. [21]

    B. Reznick. Some concrete aspects of hilbert's 17th problem. Contemporary mathematics, 253 0 (251-272), 2000

    2000

  14. [22]

    Sahinidis

    N. Sahinidis. Baron: A general purpose global optimization software package. Journal of Global Optimization, 8 0 (2): 0 201--205, 1996

    1996

  15. [23]

    Sherali and W

    H. Sherali and W. Adams. A hierarchy of relaxations between the continuous and convex hull representations for zero-one programming problems. SIAM Journal on Discrete Mathematics, 3 0 (3): 0 411--430, 1990

    1990

  16. [24]

    Sherali and W

    H. Sherali and W. Adams. A Reformulation-Linearization Technique for Solving Discrete and Continuous Nonconvex Problems, volume 31. Springer Science & Business Media, 1999

    1999

Pith tools

Reviewed August 6, 2026 · model on record in the stance chip above.