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

Relative Entropy Methods in Constrained Polynomial and Signomial Optimization

  • Chapter
  • First Online:
Polynomial Optimization, Moments, and Applications

Part of the book series: Springer Optimization and Its Applications ((SOIA,volume 206))

  • 369 Accesses

Abstract

Relative entropy programs belong to the class of convex optimization problems. Within techniques based on the arithmetic-geometric mean inequality, they facilitate to compute nonnegativity certificates of polynomials and of signomials.

While the initial focus was mostly on unconstrained certificates and unconstrained optimization, recently, Murray, Chandrasekaran and Wierman developed conditional techniques, which provide a natural extension to the case of convex constrained sets. This expository article gives an introduction into these concepts and explains the geometry of the resulting conditional SAGE cone. To this end, we deal with the sublinear circuits of a finite point set in \(\mathbb {R}^n\), which generalize the simplicial circuits of the affine-linear matroid induced by a finite point set to a constrained setting.

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

Access this chapter

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

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 109.00
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Hardcover Book
USD 139.99
Price excludes VAT (USA)
  • Durable hardcover edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

References

  1. Ahmadi, A.A., Majumdar, A.: DSOS and SDSOS optimization: more tractable alternatives to sum of squares and semidefinite optimization. SIAM J. Appl. Algebra Geom. 3(2), 193–230 (2019)

    Article  MathSciNet  Google Scholar 

  2. Averkov, G.: Optimal size of linear matrix inequalities in semidefinite approaches to polynomial optimization. SIAM J. Appl. Algebra Geom. 3(1), 128–151 (2019). https://doi.org/10.1137/18M1201342

    Article  MathSciNet  Google Scholar 

  3. Boyd, S., Kim, S.J., Vandenberghe, L., Hassibi, A.: A tutorial on geometric programming. Optim. Eng. 8, 67–127 (2007)

    Article  MathSciNet  Google Scholar 

  4. Chandrasekaran, V., Shah, P.: Relative entropy relaxations for signomial optimization. SIAM J. Optim. 26(2), 1147–1173 (2016). https://doi.org/10.1137/140988978

    Article  MathSciNet  Google Scholar 

  5. Chandrasekaran, V., Shah, P.: Relative entropy optimization and its applications. Math. Program. A 161(1–2), 1–32 (2017). https://doi.org/10.1007/s10107-016-0998-2

    Article  MathSciNet  Google Scholar 

  6. Chares, R.: Cones and interior-point algorithms for structured convex optimization involving powers and exponentials. Ph.D. thesis, Université Catholique de Louvain (2009)

    Google Scholar 

  7. Diamond, S., Boyd, S.: CVXPY: a Python-embedded modeling language for convex optimization. J. Mach. Learn. Res. 17(83), 1–5 (2016)

    MathSciNet  Google Scholar 

  8. Domahidi, A., Chu, E., Boyd, S.: ECOS: an SOCP solver for embedded systems. In: Proceedings of European Control Conference 2013, Zürich, pp. 3071–3076. IEEE (2013)

    Google Scholar 

  9. Dressler, M., Murray, R.: Algebraic perspectives on signomial optimization. SIAM J. Appl. Algebra Geom. 6(4), 650–684 (2022)

    Article  MathSciNet  Google Scholar 

  10. Dressler, M., Iliman, S., de Wolff, T.: A Positivstellensatz for sums of nonnegative circuit polynomials. SIAM J. Appl. Algebra Geom. 1(1), 536–555 (2017)

    Article  MathSciNet  Google Scholar 

  11. Dressler, M., Naumann, H., Theobald, T.: The dual cone of sums of non-negative circuit polynomials. Adv. Geom. 21(2), 227–236 (2021)

    Article  MathSciNet  Google Scholar 

  12. Forsgård, J., de Wolff, T.: The algebraic boundary of the SONC cone. SIAM J. Appl. Algebra Geom. 6, 468–502 (2022)

    Article  MathSciNet  Google Scholar 

  13. Handelman, D.: Representing polynomials by positive linear functions on compact convex polyhedra. Pacific J. Math. 132(1), 35–62 (1988). http://projecteuclid.org/getRecord?id=euclid.pjm/1102689794

    Article  MathSciNet  Google Scholar 

  14. Iliman, S., de Wolff, T.: Amoebas, nonnegative polynomials and sums of squares supported on circuits. Res. Math. Sci. 3(paper no. 9) (2016). https://doi.org/10.1186/s40687-016-0052-2

  15. Karaca, O., Darivianakis, G., Beuchat, P., Georghiou, A., Lygeros, J.: The REPOP toolbox: tackling polynomial optimization using relative entropy relaxations. In: 20th IFAC World Congress, IFAC PapersOnLine, vol. 50(1), pp. 11652–11657. Elsevier (2017). https://doi.org/10.1016/j.ifacol.2017.08.1669

  16. Katthän, L., Naumann, H., Theobald, T.: A unified framework of SAGE and SONC polynomials and its duality theory. Math. Comput. 90, 1297–1322 (2021)

    Article  MathSciNet  Google Scholar 

  17. Lasserre, J.: Moments, Positive Polynomials and Their Applications. Imperial College Press, London (2010). https://doi.org/10.1142/p665

  18. Magron, V., Wang, J.: SONC optimization and exact nonnegativity certificates via second-order cone programming. J. Symb. Comput. 115, 346–370 (2023)

    Article  MathSciNet  Google Scholar 

  19. Magron, V., Wang, J.: Sparse Polynomial Optimization: Theory and Practice. World Scientific, Singapore (2023)

    Book  Google Scholar 

  20. MOSEK: MOSEK Modeling Cookbook 3.3.0. Online (2022). https://docs.mosek.com/modeling-cookbook/index.html

  21. Moustrou, P., Naumann, H., Riener, C., Theobald, T., Verdure, H.: Symmetry reduction in AM/GM-based optimization. SIAM J. Optim. 32, 765–785 (2022)

    Article  MathSciNet  Google Scholar 

  22. Müller, S., Feliu, E., Regensburger, G., Conradi, C., Shiu, A., Dickenstein, A.: Sign conditions for injectivity of generalized polynomial maps with applications to chemical reaction networks and real algebraic geometry. Found. Comp. Math. 16(1), 69–97 (2015). https://doi.org/10.1007/s10208-014-9239-3

    Article  MathSciNet  Google Scholar 

  23. Murray, R.: Sageopt 0.5.3 (2020). https://doi.org/10.5281/ZENODO.4017991

  24. Murray, R., Chandrasekaran, V., Wierman, A.: Newton polytopes and relative entropy optimization. Found. Comput. Math. 21, 1703–1737 (2021)

    Article  MathSciNet  Google Scholar 

  25. Murray, R., Chandrasekaran, V., Wierman, A.: Signomial and polynomial optimization via relative entropy and partial dualization. Math. Program. Comput. 13, 257–295 (2021). https://doi.org/10.1007/s12532-020-00193-4

    Article  MathSciNet  Google Scholar 

  26. Murray, R., Naumann, H., Theobald, T.: Sublinear circuits and the constrained signomial nonnegativity problem. Math. Program. 198, 471–505 (2023)

    Article  MathSciNet  Google Scholar 

  27. Naumann, H., Theobald, T.: The \(\mathcal {S}\)-cone and a primal-dual view on second-order representability. Beiträge Algebra Geom. (Special issue on the 50th anniversary of the journal) 62, 229–249 (2021)

    Google Scholar 

  28. Naumann, H., Theobald, T.: Sublinear circuits for polyhedral sets. Vietnam J. Math. (Special issue on the honor of Bernd Sturmfels) 50, 447–468 (2022)

    Google Scholar 

  29. Nesterov, Y.: Constructing self-concordant barriers for convex cones. CORE discussion paper no. 2006/30 (2006)

    Google Scholar 

  30. Nesterov, Y.: Lectures on Convex Optimization, 2nd edn. Springer, Berlin (2018)

    Book  Google Scholar 

  31. Nowzari, C., Preciado, V.M., Pappas, G.J.: Optimal resource allocation for control of networked epidemic models. IEEE Trans. Control Netw. Syst. 4(2), 159–169 (2017)

    Article  MathSciNet  Google Scholar 

  32. Pantea, C., Koeppl, H., Craciun, G.: Global injectivity and multiple equilibria in uni- and bi-molecular reaction networks. Discrete Contin. Dyn. Syst. B 17(6), 2153–2170 (2012). https://doi.org/10.3934/dcdsb.2012.17.2153

    Article  MathSciNet  Google Scholar 

  33. Papp, D.: Duality of sum of nonnegative circuit polynomials and optimal SONC bounds. J. Symb. Comput. 114, 246–266 (2023)

    Article  MathSciNet  Google Scholar 

  34. Reznick, B.: Forms derived from the arithmetic-geometric inequality. Math. Annalen 283(3), 431–464 (1989)

    Article  MathSciNet  Google Scholar 

  35. Wang, J.: Nonnegative polynomials and circuit polynomials. SIAM J. Appl. Algebra Geom. 6(2), 111–133 (2022)

    Article  MathSciNet  Google Scholar 

  36. Wang, A.H., Jaini, P., Yu, Y., Poupart, P.: A Positivstellensatz for conditional SAGE signomials (2020). Preprint, arXiv:2003.03731

    Google Scholar 

  37. Wang, J., Magron, V., Lasserre, J.B., Mai, N.H.A.: CS-TSSOS: correlative and term sparsity for large-scale polynomial optimization. ACM Trans. Math. Softw. 48(4), 1–26 (2022)

    Article  MathSciNet  Google Scholar 

  38. York, M., Hoburg, W., Drela, M.: Turbofan engine sizing and tradeoff analysis via signomial programming. J. Aircraft 55(3), 988–1003 (2018). https://doi.org/10.2514/1.c034463

    Article  Google Scholar 

Download references

Acknowledgements

This expository article took its origin in the presentation material developed for a minicourse held at the Second POEMA (Polynomial Optimization, Efficiency Through Moments and Algebra) Learning Week, September 2021, Toulouse/hybrid. Thanks to Constantin Ickstadt, Nadine Defoßa as well as the anonymous reviewers for helpful comments.

Author information

Authors and Affiliations

  1. FB 12 – Institut für Mathematik, Goethe-Universität, Frankfurt am Main, Germany

    Thorsten Theobald

Authors
  1. Thorsten Theobald
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Thorsten Theobald .

Editor information

Editors and Affiliations

  1. University of Birmingham, Birmingham, UK

    Michal Kočvara

  2. Aromath, Inria at Université Côte d’Azur, Sophia Antipolis, France

    Bernard Mourrain

  3. UiT The Arctic University of Norway, Tromsø, Norway

    Cordian Riener

Rights and permissions

Reprints and permissions

Copyright information

© 2023 The Author(s), under exclusive license to Springer Nature Switzerland AG

About this chapter

Check for updates. Verify currency and authenticity via CrossMark

Cite this chapter

Theobald, T. (2023). Relative Entropy Methods in Constrained Polynomial and Signomial Optimization. In: Kočvara, M., Mourrain, B., Riener, C. (eds) Polynomial Optimization, Moments, and Applications. Springer Optimization and Its Applications, vol 206. Springer, Cham. https://doi.org/10.1007/978-3-031-38659-6_2

Download citation

Publish with us

Policies and ethics

Search

Navigation