[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

Tight relaxations for polynomial optimization and Lagrange multiplier expressions

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

Abstract

This paper proposes tight semidefinite relaxations for polynomial optimization. The optimality conditions are investigated. We show that generally Lagrange multipliers can be expressed as polynomial functions in decision variables over the set of critical points. The polynomial expressions are determined by linear equations. Based on these expressions, new Lasserre type semidefinite relaxations are constructed for solving the polynomial optimization. We show that the hierarchy of new relaxations has finite convergence, or equivalently, the new relaxations are tight for a finite relaxation order.

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
£29.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 includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

Notes

  1. It is the preordering of the polynomial tuple \((c_{in},\psi )\); see Sect. 7.1.

  2. Note that \(1-x^Tx =(1-e^Tx)(1+x^Tx)+\sum _{i=1}^n x_i(1-x_i)^2+\sum _{i\ne j}x_i^2x_j \in \hbox {IQ}(c_{eq},c_{in}).\)

  3. This is because \(-c_1^2p_1^2 \in \hbox {Ideal}(\phi ) \subseteq \hbox {IQ}(\phi ,\psi )\) and the set \(\{-c_1(x)^2p_1(x)^2 \ge 0 \}\) is compact.

  4. This is because \(1-x_1^2-x_2^2\) belongs to the quadratic module of \((x_1, x_2,1-x_1-x_2)\) and \(1-x_3^2-x_4^2\) belongs to the quadratic module of \((x_3, x_4,1-x_3-x_4)\). See the footnote in Example 6.1.

  5. Note that \(4-{\sum }_{i=1}^4 x_i^2 = {\sum }_{i=1}^4 \Big ( x_i (1-x_i)^2 + (1-x_i) (1+x_i^2) \Big ) \in \hbox {IQ}(c_{eq}, c_{in}).\)

References

  1. Bertsekas, D.: Nonlinear Programming, 2nd edn. Athena Scientific, Cambridge (1995)

    MATH  Google Scholar 

  2. Bochnak, J., Coste, M., Roy, M.-F.: Real Algebraic Geometry. Springer, New York (1998)

    Book  Google Scholar 

  3. Bugarin, F., Henrion, D., Lasserre, J.: Minimizing the sum of many rational functions. Math. Programm. Comput. 8, 83–111 (2016)

    Article  MathSciNet  Google Scholar 

  4. Cox, D., Little, J., O’Shea, D.: Ideals, Varieties, and Algorithms. An Introduction to Computational Algebraic Geometry and Commutative Algebra, 3rd edn. Undergraduate Texts in Mathematics. Springer, New York (1997)

    Google Scholar 

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

    MathSciNet  MATH  Google Scholar 

  6. 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)

    Article  MathSciNet  Google Scholar 

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

    Article  MathSciNet  Google Scholar 

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

    Article  MathSciNet  Google Scholar 

  9. de Klerk, E., Laurent, M., Sun, Z.: Convergence analysis for Lasserre’s measure-based hierarchy of upper bounds for polynomial optimization. Math. Programm. 162, 363–392 (2017)

    Article  MathSciNet  Google Scholar 

  10. de Klerk, E., Hess, R., Laurent, M.: Improved convergence rates for Lasserre-type hierarchies of upper bounds for box-constrained polynomial optimization. Preprint (2016). arXiv:1603.03329 [math.OC]

  11. Greuel, G.-M., Pfister, G.: A Singular Introduction to Commutative Algebra. Springer, New York (2002)

    Book  Google Scholar 

  12. He, S., Luo, Z., Nie, J., Zhang, S.: Semidefinite relaxation bounds for indefinite homogeneous quadratic optimization. SIAM J. Optim. 19(2), 503–523 (2008)

    Article  MathSciNet  Google Scholar 

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

    Article  MathSciNet  Google Scholar 

  14. Henrion, D., Lasserre, J.B.: Detecting global optimality and extracting solutions in GloptiPoly. Positive polynomials in control, 293–310. Lecture Notes in Control and Information Science 312. Springer, Berlin (2005)

    Chapter  Google Scholar 

  15. Jibetean, D., de Klerk, E.: Global optimization of rational functions: a semidefinite programming approach. Math. Program. 106(1), 93–109 (2006)

    Article  MathSciNet  Google Scholar 

  16. Kollár, J.: Sharp effective Nullstellensatz. J. Am. Math. Soc. 1(4), 963–975 (1988)

    Article  MathSciNet  Google Scholar 

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

    Article  MathSciNet  Google Scholar 

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

    Article  MathSciNet  Google Scholar 

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

    Article  MathSciNet  Google Scholar 

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

    Article  Google Scholar 

  21. Lasserre, J.B.: Moments, Positive Polynomials and Their Applications. Imperial College Press, London (2009)

    Book  Google Scholar 

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

    Book  Google Scholar 

  23. Lasserre, J.B., Toh, K.C., Yang, S.: A bounded degree SOS hierarchy for polynomial optimization. EURO J. Comput. Optim. 5, 87–117 (2017)

    Article  MathSciNet  Google Scholar 

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

    Article  MathSciNet  Google Scholar 

  25. Laurent, M.: Sums of squares, moment matrices and optimization over polynomials. In: Putinar, M., Sullivant, S. (eds.) Emerging Applications of Algebraic Geometry, vol. 149 of IMA Volumes in Mathematics and its Applications, pp. 157–270. Springer, New York (2009)

    Google Scholar 

  26. Laurent, M.: Optimization over polynomials: Selected topics. In: Proceedings of the International Congress of Mathematicians (2014)

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

    Article  MathSciNet  Google Scholar 

  28. Nie, J., Demmel, J., Gu, M.: Global minimization of rational functions and the nearest GCDs. J. Global Optim. 40(4), 697–718 (2008)

    Article  MathSciNet  Google Scholar 

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

    Article  MathSciNet  Google Scholar 

  30. Nie, J.: An exact Jacobian SDP relaxation for polynomial optimization. Math. Programm. Ser. A 137, 225–255 (2013)

    Article  MathSciNet  Google Scholar 

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

    Article  MathSciNet  Google Scholar 

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

    Article  MathSciNet  Google Scholar 

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

    Article  MathSciNet  Google Scholar 

  34. Nie, J.: Linear optimization with cones of moments and nonnegative polynomials. Math. Programm. Ser. B 153(1), 247–274 (2015)

    Article  MathSciNet  Google Scholar 

  35. Parrilo, P.A., Sturmfels, B.: Minimizing polynomial functions. In: Basu, S., Gonzalez-Vega, L. (eds.) Algorithmic and Quantitative Aspects of Real Algebraic Geometry in Mathematics and Computer Science, volume 60 of DIMACS Series in Discrete Mathematics and Computer Science, pp. 83–99. AMS (2003)

    Chapter  Google Scholar 

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

    Article  MathSciNet  Google Scholar 

  37. Reznick, B.: Some concrete aspects of Hilbert’s 17th problem. In: Contemporary Mathematics, vol 253, pp. 251–272. American Mathematical Society (2000)

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

    Article  MathSciNet  Google Scholar 

  39. Scheiderer, C.: Positivity and sums of squares: A guide to recent results. In: Putinar, M., Sullivant, S. (eds.) Emerging Applications of Algebraic Geometry, IMA Volumes Math. Appl. 149. Springer, pp. 271–324 (2009)

  40. Sturm, J.F.: SeDuMi 1.02: a MATLAB toolbox for optimization over symmetric cones. Optim. Methods Softw. 11–12, 625–653 (1999)

    Article  MathSciNet  Google Scholar 

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

    Book  Google Scholar 

  42. Vui, H.H., Són, P.T.: Global optimization of polynomials using the truncated tangency variety and sums of squares. SIAM J. Optim. 19(2), 941–951 (2008)

    Article  MathSciNet  Google Scholar 

Download references

Acknowledgements

The author was partially supported by the NSF grants DMS-1417985 and DMS-1619973. He would like to thank the anonymous referees for valuable comments on improving the paper.

Author information

Authors and Affiliations

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

    Jiawang Nie

Authors
  1. Jiawang Nie
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Jiawang Nie.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Nie, J. Tight relaxations for polynomial optimization and Lagrange multiplier expressions. Math. Program. 178, 1–37 (2019). https://doi.org/10.1007/s10107-018-1276-2

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10107-018-1276-2

Keywords

Mathematics Subject Classification

Search

Navigation