Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Homogenization for polynomial optimization with unbounded sets

  • Full Length Paper
  • Series A
  • Published:
Mathematical Programming Submit manuscript

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 sufficient 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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

Notes

  1. Throughout the paper, for convenience, a minimizer means a global minimizer, unless it is otherwise specified for the meaning.

References

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

    MathSciNet  MATH  Google Scholar 

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

    MathSciNet  MATH  Google Scholar 

  3. Bertsekas, D.: Nonlinear Programming, 2nd edn. Athena Scientific, Belmont (1995)

    MATH  Google Scholar 

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

    MathSciNet  MATH  Google Scholar 

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

    MathSciNet  MATH  Google Scholar 

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

    MathSciNet  MATH  Google Scholar 

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

    MathSciNet  MATH  Google Scholar 

  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)

    MathSciNet  MATH  Google Scholar 

  9. Gelfand, I., Kapranov, M., Zelevinsky, A.: Discriminants, resultants, and multidimensional determinants. Theory & applications, Birkhäuser, Mathematics (1994)

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

    MathSciNet  MATH  Google Scholar 

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

    MathSciNet  MATH  Google Scholar 

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

    MathSciNet  MATH  Google Scholar 

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

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

    MathSciNet  MATH  Google Scholar 

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

    MathSciNet  MATH  Google Scholar 

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

    MathSciNet  MATH  Google Scholar 

  17. De Klerk E., Laurent M., Parrilo P.: On the equivalence of 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)

  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)

    MathSciNet  MATH  Google Scholar 

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

  20. De Klerk, E., Pasechnik, D.: Approximation of the stability number of a graph via copositive programming. SIAM J. Optim. 12(4), 875–892 (2002)

    MathSciNet  MATH  Google Scholar 

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

    MathSciNet  MATH  Google Scholar 

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

    MathSciNet  MATH  Google Scholar 

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

    MATH  Google Scholar 

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

    MathSciNet  MATH  Google Scholar 

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

    MATH  Google Scholar 

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

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

    MathSciNet  MATH  Google Scholar 

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

    MathSciNet  MATH  Google Scholar 

  29. Laurent, M.: Sums of squares, moment matrices and optimization over polynomials. In: Emerging applications of algebraic geometry of IMA Volumes in Mathematics and its Applications, 149: 157–270. Springer (2009)

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

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

  32. Mai, N., Lasserre, J., Magron, V.: Positivity certificates and polynomial optimization on non-compact semialgebraic sets. Math. Program. 194, 443–485 (2021)

    MathSciNet  MATH  Google Scholar 

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

    MathSciNet  MATH  Google Scholar 

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

    MATH  Google Scholar 

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

    MATH  Google Scholar 

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

    MathSciNet  MATH  Google Scholar 

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

    MathSciNet  MATH  Google Scholar 

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

    MathSciNet  MATH  Google Scholar 

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

    MathSciNet  MATH  Google Scholar 

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

    MathSciNet  MATH  Google Scholar 

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

    MathSciNet  MATH  Google Scholar 

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

    MathSciNet  MATH  Google Scholar 

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

    MathSciNet  MATH  Google Scholar 

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

    MathSciNet  MATH  Google Scholar 

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

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

    MathSciNet  MATH  Google Scholar 

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

    MathSciNet  MATH  Google Scholar 

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

    MathSciNet  MATH  Google Scholar 

  49. Reznick, B.: Some concrete aspects of Hilbert’s 17th problem. Contemp. Math. 253, 251–272 (2000)

    MathSciNet  MATH  Google Scholar 

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

    MathSciNet  MATH  Google Scholar 

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

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

    MathSciNet  MATH  Google Scholar 

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

    MathSciNet  MATH  Google Scholar 

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

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

    MATH  Google Scholar 

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

    MathSciNet  MATH  Google Scholar 

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

  58. Yu, J.: Do most polynomials generate a prime ideal? J. Algebra 459, 468–474 (2016)

    MathSciNet  MATH  Google Scholar 

Download references

Acknowledgements

The authors would like to thank the editors and anonymous referees for fruitful comments and suggestions. Lei Huang and Ya-Xiang Yuan are partially supported by the National Natural Science Foundation of China (No. 12288201).

Author information

Authors and Affiliations

  1. Institute of Computational Mathematics and Scientific/Engineering Computing, Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing, 100190, China

    Lei Huang & Ya-Xiang Yuan

  2. School of Mathematical Sciences, University of Chinese Academy of Sciences, Beijing, 100049, China

    Lei Huang

  3. Department of Mathematics, University of California San Diego, 9500 Gilman Drive, La Jolla, CA, 92093, USA

    Jiawang Nie

Authors
  1. Lei Huang
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Jiawang Nie
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Ya-Xiang Yuan
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Lei Huang.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Springer Nature or its licensor holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Springer Nature or its licensor holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Huang, L., Nie, J. & Yuan, YX. Homogenization for polynomial optimization with unbounded sets. Math. Program. 200, 105–145 (2023). https://doi.org/10.1007/s10107-022-01878-5

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10107-022-01878-5

Keywords

Mathematics Subject Classification

Search

Navigation