pith. sign in

arxiv: 2112.15289 · v2 · submitted 2021-12-31 · 🧮 math.OC

Homogenization for polynomial optimization with unbounded sets

Lei Huang , Jiawang Nie , Ya-Xiang Yuan This is my paper

Pith reviewed 2026-05-24 12:30 UTC · model grok-4.3

classification 🧮 math.OC
keywords polynomial optimizationhomogenizationmoment-SOS relaxationsunbounded setsPositivstellensatzfinite convergenceoptimality conditions
0
0 comments X

The pith

By homogenizing the problem, the Moment-SOS hierarchy attains finite convergence for unbounded polynomial optimization under regularity conditions at all minimizers.

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

The paper develops a homogenization technique for polynomial optimization over unbounded domains. It shows that a hierarchy of moment and sum-of-squares relaxations converges in finitely many steps provided the feasible set is closed at infinity, the homogenized equality ideal is real radical, and standard second-order optimality conditions hold at every minimizer including those at infinity. This extends the reach of SOS methods, which previously required compactness for finite convergence guarantees. The work also establishes extended Positivstellensatz results for nonnegativity on unbounded sets and settles a conjecture regarding the version with denominators.

Core claim

Under the assumptions that the feasible set is closed at infinity and the ideal of homogenized equality constraining polynomials is real radical, the hierarchy of Moment-SOS relaxations has finite convergence if the linear independence constraint qualification, strict complementarity and second order sufficiency conditions hold at every minimizer, including the one at infinity.

What carries the argument

The homogenization formulation that converts the unbounded polynomial optimization problem into an equivalent problem amenable to finite-convergence analysis of the Moment-SOS hierarchy.

If this is right

  • The hierarchy solves the original problem exactly after finitely many relaxations under the stated conditions.
  • Extended Putinar-Vasilescu type Positivstellensatz holds for polynomials nonnegative on such unbounded sets.
  • The classical Moment-SOS hierarchy with denominators also has finite convergence, answering a conjecture positively.
  • Minimizers at infinity are handled correctly within the same framework.

Where Pith is reading between the lines

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

  • Similar homogenization might apply to other relaxation hierarchies beyond Moment-SOS.
  • Numerical checks for closedness at infinity could be developed to apply the method in practice.
  • This suggests that many unbounded problems in applications like portfolio optimization or control theory may now be solvable exactly via SDP hierarchies.

Load-bearing premise

The feasible set must be closed at infinity and the homogenized equality constraining ideal must be real radical.

What would settle it

An explicit polynomial optimization problem where the feasible set is closed at infinity, the ideal is real radical, and KKT conditions hold at all minimizers, yet the Moment-SOS hierarchy fails to converge in finite steps.

read the original abstract

This paper considers polynomial optimization with unbounded sets. We give a homogenization formulation and propose a hierarchy of Moment-SOS relaxations to solve it. Under the assumptions that the feasible set is closed at infinity and the ideal of homogenized equality constraining polynomials is real radical, we show that this hierarchy of Moment-SOS relaxations has finite convergence, if some optimality conditions (i.e., the linear independence constraint qualification, strict complementarity and second order sufficiency conditions) hold at every minimizer, including the one at infinity. Moreover, we prove extended versions of Putinar-Vasilescu type Positivstellensatz for polynomials that are nonnegative on unbounded sets. The classical Moment-SOS hierarchy with denominators is also studied. In particular, we give a positive answer to a conjecture of Mai, Lasserre and Magron in their recent work.

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.

Referee Report

0 major / 3 minor

Summary. The paper introduces a homogenization formulation for polynomial optimization over unbounded feasible sets and proposes a hierarchy of Moment-SOS relaxations. Under the assumptions that the feasible set is closed at infinity and the ideal generated by the homogenized equality constraints is real radical, the hierarchy is shown to have finite convergence whenever the linear independence constraint qualification, strict complementarity, and second-order sufficient optimality conditions hold at every minimizer (including the minimizer at infinity). The paper also proves extended Putinar-Vasilescu-type Positivstellensatz results for polynomials nonnegative on unbounded sets and gives a positive resolution to a conjecture of Mai, Lasserre, and Magron on the classical Moment-SOS hierarchy with denominators.

Significance. If the stated conditional finite-convergence result holds, the work meaningfully extends the Moment-SOS framework to non-compact domains, which arise in many applications. The explicit treatment of the minimizer at infinity and the resolution of the cited conjecture are concrete contributions. The extended Positivstellensatz may also be of independent interest in real algebraic geometry.

minor comments (3)
  1. The abstract states that the optimality conditions must hold 'at every minimizer, including the one at infinity,' but the manuscript should clarify in the main text how these conditions are expressed in the homogenized variables and whether they can be checked without first solving the original problem.
  2. Notation for the homogenized polynomials and the 'closed at infinity' property should be introduced with explicit definitions early in the paper (ideally before the statement of the main theorem) to improve readability for readers unfamiliar with homogenization techniques.
  3. The positive answer to the Mai-Lasserre-Magron conjecture is highlighted in the abstract; the manuscript should include a dedicated remark or subsection that isolates exactly which part of their conjecture is settled and how the homogenization approach supplies the missing ingredient.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive assessment of our work on homogenization for polynomial optimization over unbounded sets and for recommending minor revision. The report provides a clear summary of the contributions, including the finite-convergence result under the stated assumptions, the extended Positivstellensatz, and the resolution of the conjecture by Mai, Lasserre, and Magron. No specific major comments are listed in the provided referee report, so we have no point-by-point responses to offer at this stage.

Circularity Check

0 steps flagged

No significant circularity; derivation self-contained under explicit external assumptions

full rationale

The paper states a conditional finite-convergence theorem for the homogenized Moment-SOS hierarchy and an extended Positivstellensatz. Both results are explicitly predicated on the feasible set being closed at infinity, the homogenized equality ideal being real radical, and LICQ/SC/SOS conditions holding at all minimizers (including at infinity). These domain hypotheses are listed as prerequisites in the abstract and are not derived from the paper's own constructions or fitted quantities. The positive resolution of an external conjecture (Mai-Lasserre-Magron) and the classical hierarchy with denominators likewise introduce no self-definitional loops, fitted-input predictions, or load-bearing self-citations. No equation or step reduces the claimed convergence to an input by construction; the development rests on standard real-algebraic-geometry tools and is therefore scored at the default non-circularity level.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claims rest on two domain assumptions stated in the abstract; no free parameters or invented entities appear.

axioms (2)
  • domain assumption The feasible set is closed at infinity
    Invoked as a prerequisite for finite convergence of the hierarchy.
  • domain assumption The ideal of homogenized equality constraining polynomials is real radical
    Required for both the convergence theorem and the Positivstellensatz extension.

pith-pipeline@v0.9.0 · 5666 in / 1336 out tokens · 33902 ms · 2026-05-24T12:30:57.991355+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

58 extracted references · 58 canonical work pages · 1 internal anchor

  1. [1]

    Ahmadi, A.A., Zhang, J.: On the complexity of testing att ainment of the optimal value in nonlinear optimization. Math. Program. 184, 221–241 (2020)

    work page 2020

  2. [2]

    Bajbar, T., Stein, O.: Coercive polynomials and their ne wton polytopes. SIAM J. Optim. 25(3), 1542–1570 (2015)

    work page 2015

  3. [3]

    Curto, R., Fialkow, L.: Truncated K–moment problems in s everal variables. J. Oper. Theory 54, 189–226 (2005)

    work page 2005

  4. [4]

    Athena S cientific, Belmont (1995)

    Bertsekas, D.: Nonlinear Programming, 2nd edn. Athena S cientific, Belmont (1995)

    work page 1995

  5. [5]

    Demmel, J., Nie, J., Powers, V.: Representations of posi tive polynomials on non-compact semialgebraic sets via KKT ideals. J. Pure Appl. Algebra 209(1), 189–200 (2007)

    work page 2007

  6. [6]

    Dickinson, P., Povh, J.: A new approximation hierarchy f or polynomial conic optimization. Comput. Optim. Appl. 73, 37–67 (2019)

    work page 2019

  7. [7]

    Fan, J., Nie, J., Zhou, A.: Tensor eigenvalue complement arity problems. Math. Program. 170 (2), 507–539 (2018)

    work page 2018

  8. [8]

    Fang, K., Fawzi, H.: The sum-of-squares hierarchy on the sphere and applications in quantum information theory. Math. Program. 190, 331-–360 (2021)

    work page 2021

  9. [9]

    Mathematics: Theory & applications, Birkh¨ auser (1994)

    Gelfand, I., Kapranov, M., Zelevinsky, A.: Discriminan ts, resultants, and multidimensional determinants. Mathematics: Theory & applications, Birkh¨ auser (1994)

    work page 1994

  10. [10]

    Guo, F., W ang, L., Zhou, G.: Minimizing rational functi ons by exact Jacobian SDP relaxation applicable to finite singularities. J. Global Optim. 58(2), 261–284 (2014)

    work page 2014

  11. [11]

    Ha, H., Pham, T.: Solving polynomial optimization prob lems via the truncated tangency variety and sums of squares. J. Pure Appl. Algebra 213(11), 2167–2176 (2009)

    work page 2009

  12. [12]

    Ha, H., Pham, T.: Global optimization of polynomials us ing the truncated tangency variety and sums of squares. SIAM J. Optim. 19(2), 941–951 (2008)

    work page 2008

  13. [13]

    In Positive polynomials in control , 293.C310, Lecture Notes in Control and Inform

    Henrion, D., Lasserre, J.: Detecting global optimalit y and extracting solutions in Gloptipoly. In Positive polynomials in control , 293.C310, Lecture Notes in Control and Inform. Sci., 312, Springer (2005)

    work page 2005

  14. [14]

    Henrion, D., Lasserre, J., Loefberg, J.: Gloptipoly 3: moments, optimization and semidefinite programming. Optim. Methods Softw. 24(4-5), 761–779 (2009)

    work page 2009

  15. [15]

    Jeyakumar, V., Lasserre, J., Li, G.: On polynomial opti mization over non-compact semi- algebraic sets. J. Optim. Theory Appl. 163(3), 707–718 (2014)

    work page 2014

  16. [16]

    De Klerk, E., Laurent, M.: On the Lasserre hierarchy of s emidefinite programming relaxations of convex polynomial optimization problems. SIAM J. Optim. 21, 824–832 (2011)

    work page 2011

  17. [17]

    In: Henrion D., Garulli A

    De Klerk E., Laurent M., Parrilo P.: On the equivalence o f algebraic approaches to the minimization of forms on the simplex. In: Henrion D., Garulli A. (eds) Positive Polynomials in Control. Lecture Notes in Control and Information Science, vol 312. Springer (2005)

    work page 2005

  18. [18]

    De Klerk, E., Lasserre, J., Laurent, M., Sun, Z.: Bound- constrained polynomial optimization using only elementary calculations. Math. Oper. Res. 42(3), 834–853 (2017)

    work page 2017

  19. [19]

    De Klerk, E., Laurent, M.: Convergence analysis of a Las serre hierarchy of upper bounds for polynomial minimization on the sphere. Math. Program. 193(2), 665–685 (2022)

    work page 2022

  20. [20]

    De Klerk, E., Pasechnik, D.: Approximation of the stabi lity number of a graph via copositive programming. SIAM J. Optim. 12(4), 875–892 (2002) HOMOGENIZATION FOR POLYNOMIAL OPTIMIZATION WITH UNBOUNDE D SETS 33

    work page 2002

  21. [21]

    Lasserre, J.: Global optimization with polynomials an d the problem of moments. SIAM J. Optim. 11(3), 796–817 (2001)

    work page 2001

  22. [22]

    Lasserre, J., Laurent, M., Rostalski, P.: Semidefinite characterization and computation of zero-dimensional real radical ideals. Found. Comput. Math. 8, 607–647 (2008)

    work page 2008

  23. [23]

    Lasserre, J.: Convexity in semi-algebraic geometry an d polynomial optimization. SIAM J. Optim. 19, 1995–2014 (2009)

    work page 1995

  24. [24]

    Lasserre, J.: A new look at nonnegativity on closed sets and polynomial optimization. SIAM J. Optim. 21, 864–885 (2011)

    work page 2011

  25. [25]

    Cambridge University Press, Cambridge (2015)

    Lasserre, J.: An Introduction to Polynomial and Semi-a lgebraic Optimization. Cambridge University Press, Cambridge (2015)

    work page 2015

  26. [26]

    In: Sirakov, B ., Ney de Souza., P., Viana, M

    Lasserre,J.: The Moment-SOS hierarchy. In: Sirakov, B ., Ney de Souza., P., Viana, M. (eds.) Proceedings of the International Congress of Mathematicia ns (ICM 2018) , vol 3, pp. 3761–3784, W orld Scientific (2019)

    work page 2018

  27. [27]

    Laurent, M.: Revisiting two theorems of Curto and Fialk ow on moment matrices. Proc. Am. Math. Soc. 133(10), 2965–2976 (2005)

    work page 2005

  28. [28]

    Laurent, M.: Semidefinite representations for finite va rieties. Math. Program. 109, 1–26 (2007)

    work page 2007

  29. [29]

    In: Emerging applications of algebraic geometry of IMA Volumes in Mathematics and its Applica- tions, 149: 157–270

    Laurent, M.: Sums of squares, moment matrices and optim ization over polynomials. In: Emerging applications of algebraic geometry of IMA Volumes in Mathematics and its Applica- tions, 149: 157–270. Springer (2009)

    work page 2009

  30. [30]

    In: Jang, S., Kim, Y., Lee, D.W., Yie, I

    Laurent, M.: Optimization over polynomials: Selected topics. In: Jang, S., Kim, Y., Lee, D.W., Yie, I. (eds.) Proceedings of the International Congress of Mathematicia ns ( ICM 2014) , pp. 843–869 (2014)

    work page 2014

  31. [31]

    arXiv preprint, arXiv:2104.11606 (2021)

    Mai, N., Magron, V.: On the complexity of Putinar-Vasil escu’s Positivstellensatz. arXiv preprint, arXiv:2104.11606 (2021)

    work page arXiv 2021

  32. [32]

    Mai, N., Lasserre, J., Magron, V.: Positivity certifica tes and polynomial optimization on non-compact semialgebraic sets. Math. Program. (2021)

    work page 2021

  33. [33]

    Marshall, M.: Optimization of polynomial functions. Can. Math. Bull. 46(3), 400–418 (2003)

    work page 2003

  34. [34]

    American Mathematical Society, Providence (2008)

    Marshall, M.: Positive Polynomials and Sums of Squares . American Mathematical Society, Providence (2008)

    work page 2008

  35. [35]

    Motzkin, T.S., Straus, E.G.: Maxima for graphs and a new proof of a theorem of Tur´ an. Can. J. Math. 17, 533–540 (1965)

    work page 1965

  36. [36]

    Nie, J., Demmel, J., Sturmfels, B.: Minimizing polynom ials via sum of squares over the gradient ideal. Math. Program. 106(3), 587–606 (2006)

    work page 2006

  37. [37]

    Nie, J.: Discriminants and nonnegative polynomials. J. Symb. Comput. 47(2), 167–191, (2012)

    work page 2012

  38. [38]

    Nie, J.: Certifying convergence of Lasserre’s hierarc hy via flat truncation. Math. Program. 142(1-2), 485–510 (2013)

    work page 2013

  39. [39]

    Nie, J.: An exact Jacobian SDP relaxation for polynomia l optimization. Math. Program. 137(1-2), 225–255 (2013)

    work page 2013

  40. [40]

    Nie, J.: Polynomial optimization with real varieties. SIAM J. Optim. 23(3), 1634–1646 (2013)

    work page 2013

  41. [41]

    Nie, J.: Optimality conditions and finite convergence o f Lasserre’s hierarchy. Math. Program. 146(1-2), 97–121 (2014)

    work page 2014

  42. [42]

    Nie, J.: The hierarchy of local minimums in polynomial o ptimization. Math. Program. 151 (2) 555–583 (2015)

    work page 2015

  43. [43]

    Nie, J.: Tight relaxations for polynomial optimizatio n and Lagrange multiplier expressions. Math. Program. 178(1–2), 1–37 (2019)

    work page 2019

  44. [44]

    Nie, J., Yang, Z., Zhang, X.: A complete semidefinite alg orithm for detecting copositive matrices and tensors. SIAM J. Optim. 28(4), 2902–2921 (2018)

    work page 2018

  45. [45]

    Tangencies and Polynomial Optimization

    Pham, T.: Tangencies and polynomial optimization. arX iv preprint, arXiv:1902.06041 (2019)

    work page internal anchor Pith review Pith/arXiv arXiv 1902

  46. [46]

    Indiana Univ

    Putinar, M.: Positive polynomials on compact semi-alg ebraic sets. Indiana Univ. Math. J. 42(3), 969–984 (1993)

    work page 1993

  47. [47]

    Putinar, M., Vasilescu, F: Positive polynomials on sem i-algebraic sets. C. R. Acad. Sci. Ser. I Math. 328(7), 585–589 (1999)

    work page 1999

  48. [48]

    Putinar, M., Vasilescu, F: Solving moment problems by d imensional extension. C. R. Acad. Sci. Ser. I Math. 328(6), 495–499 (1999)

    work page 1999

  49. [49]

    Reznick, B.: Some concrete aspects of Hilbert’s 17th pr oblem. Contemp. Math. 253, 251–272 (2000) 34 LEI HUANG, JIA W ANG NIE, AND YA-XIANG YUAN

    work page 2000

  50. [50]

    Scheiderer, C.: Sums of squares on real algebraic surfa ces. Manuscr. Math. 119, 395–410 (2006)

    work page 2006

  51. [51]

    In: Emerging applications of algebraic geometry of IMA Volumes in Mathem atics and its Applications , 149, pp

    Scheiderer, C.: Positivity and sums of squares: A guide to recent results. In: Emerging applications of algebraic geometry of IMA Volumes in Mathem atics and its Applications , 149, pp. 271–324. Springer (2009)

    work page 2009

  52. [52]

    Schweighofer, M.: Optimization of polynomials on comp act semialgebraic sets. SIAM J. Optim. 15 (3), 805–825 (2005)

    work page 2005

  53. [53]

    Schweighofer, M.: Global optimization of polynomials using gradient tentacles and sums of squares. SIAM J. Optim. 17(3), 920–942 (2006)

    work page 2006

  54. [54]

    Slot, L., Laurent, M.: Improved convergence analysis o f Lasserre’s measure-based upper bounds for polynomial minimization on compact sets. Math. Program. 193(2), 831–871 (2022)

    work page 2022

  55. [55]

    Springer, New York (2006)

    Sun, W., Yuan, Y.: Optimization Theory and Methods: Non linear Programming. Springer, New York (2006)

    work page 2006

  56. [56]

    Sturm, J.F.: SeDuMi 1.02: a matlab toolbox for optimiza tion over symmetric cones. Optim. Methods Softw. 11(1-4), 625–653 (1999)

    work page 1999

  57. [57]

    In: CBMS Regional Conference Series in Mathematics

    Sturmfels, B.: Solving systems of polynomial equation s. In: CBMS Regional Conference Series in Mathematics. American Mathematical Society, Providence (2002)

    work page 2002

  58. [58]

    Yu, J.: Do most polynomials generate a prime ideal? J. Algebra 459, 468–474 (2016) Lei Huang, Institute of Computational Mathematics and Scien tific/Engineering Com- puting, Academy of Mathematics and Systems Science, Chines e Academy of Sciences, and School of Mathematical Sciences, University of Chinese Acad emy of Sciences, Beijing, China, 100190. Emai...

    work page 2016