# zbMATH — the first resource for mathematics

TSSOS: a moment-SOS hierarchy that exploits term sparsity. (English) Zbl 07305921

##### MSC:
 14P10 Semialgebraic sets and related spaces 90C22 Semidefinite programming 12D15 Fields related with sums of squares (formally real fields, Pythagorean fields, etc.) 12Y05 Computational aspects of field theory and polynomials (MSC2010)
##### Software:
GitHub; GloptiPoly; JuMP; Mosek; Robotics; SeDuMi; Sparse-BSOS; SparsePOP; SPOTless; TSSOS; YALMIP
Full Text:
##### References:
 [1] J. Agler, W. Helton, S. McCullough, and L. Rodman, Positive semidefinite matrices with a given sparsity pattern, Linear Algebra. Appl., 107 (1988), pp. 101-149. · Zbl 0655.15016 [2] A. A. Ahmadi and A. Majumdar, DSOS and SDSOS optimization: LP and SOCP-based alternatives to sum of squares optimization, in Proceedings of the 48th Annual Conference on Information Sciences and Systems (CISS), 2014, pp. 1-5. [3] S. Bromberger, J. Fairbanks, et al., JuliaGraphs/LightGraphs.jl: An Optimized Graphs Package for the Julia Programming Language, https://doi.org/10.5281/zenodo.889971, 2017. [4] V. Chandrasekaran and P. Shah, Relative entropy relaxations for signomial optimization, SIAM J. Optim., 26 (2016), pp. 1147-1173, https://doi.org/10.1137/140988978. · Zbl 1345.90066 [5] M. D. Choi, T. Y. Lam, and B. Reznick, Sums of squares of real polynomials, in $$K$$-Theory and Algebraic Geometry: Connections with Quadratic Forms and Division Algebras, Proc. Sympos. Pure Math. 58, AMS, Providence, RI, 1995, pp. 103-126. · Zbl 0821.11028 [6] I. Dunning, J. Huchette, and M. Lubin, JuMP: A modeling language for mathematical optimization, SIAM Rev., 59 (2017), pp. 295-320, https://doi.org/10.1137/15M1020575. · Zbl 1368.90002 [7] M. Fukuda, M. Kojima, K. Murota, and K. Nakata, Exploiting sparsity in semidefinite programming via matrix completion I: General framework, SIAM J. Optim., 11 (2000), pp. 647-674, https://doi.org/10.1137/S1052623400366218. · Zbl 1010.90053 [8] M. Ghasemi and M. Marshall, Lower bounds for polynomials using geometric programming, SIAM J. Optim., 22 (2012), pp. 460-473, https://doi.org/10.1137/110836869. · Zbl 1272.12004 [9] E. J. Hancock and A. Papachristodoulou, Structured sum of squares for networked systems analysis, in Proceedings of the 50th IEEE Conference on Decision and Control and European Control Conference (CDC-ECC). · Zbl 1284.93181 [10] D. Henrion and J. B. Lasserre, GloptiPoly: Global optimization over polynomials with Matlab and SeDuMi, ACM Trans. Math. Software, 29 (2003), pp. 165-194. · Zbl 1070.65549 [11] S. Iliman and T. de Wolff, Amoebas, nonnegative polynomials and sums of squares supported on circuits, Res. Math. Sci., 3 (2016), 9. · Zbl 1415.11071 [12] C. Josz, Application of Polynomial Optimization to Electricity Transmission Networks, Theses, Université Pierre et Marie Curie - Paris VI, Paris, France, 2016. [13] I. Klep, V. Magron, and J. Povh, Sparse Noncommutative Polynomial Optimization, preprint, https://arxiv.org/abs/1909.00569, 2019. [14] M. Kojima, S. Kim, and H. Waki, Sparsity in sums of squares of polynomials, Math. Program., 103 (2005), pp. 45-62. · Zbl 1079.90092 [15] J. B. Lasserre, Global optimization with polynomials and the problem of moments, SIAM J. Optim., 11 (2001), pp. 796-817, https://doi.org/10.1137/S1052623400366802. · Zbl 1010.90061 [16] J. B. Lasserre, Convergent SDP-relaxations in polynomial optimization with sparsity, SIAM J. Optim., 17 (2006), pp. 822-843, https://doi.org/10.1137/05064504X. · Zbl 1119.90036 [17] J.-B. Lasserre, K.-C. Toh, and S. Yang, A bounded degree SOS hierarchy for polynomial optimization, EURO J. Comput. Optim., 5 (2017), pp. 87-117. · Zbl 1368.90132 [18] M. Laurent, Sums of squares, moment matrices and optimization over polynomials, in Emerging Applications of Algebraic Geometry, IMA Vol. Math. Appl. 149, Springer, New York, 2009, pp. 157-270. [19] J. Löfberg, YALMIP: A toolbox for modeling and optimization in MATLAB, in Proceedings of the IEEE International Conference on Robotics and Automation, 2004, pp. 284-289. [20] J. Löfberg, Pre- and post-processing sum-of-squares programs in practice, IEEE Trans. Automat. Control, 54 (2009), pp. 1007-1011. · Zbl 1367.90002 [21] V. Magron, Interval enclosures of upper bounds of roundoff errors using semidefinite programming, ACM Trans. Math. Software, 44 (2018), 41. · Zbl 07003066 [22] V. Magron, G. Constantinides, and A. Donaldson, Certified roundoff error bounds using semidefinite programming, ACM Trans. Math. Software, 43 (2017), 34. · Zbl 1380.65084 [23] A. Majumdar, A. A. Ahmadi, and R. Tedrake, Control and verification of high-dimensional systems with DSOS and SDSOS programming, in Proceedings of the 53rd IEEE Conference on Decision and Control, 2014, pp. 394-401. [24] A. Marandi, E. D. Klerk, and J. Dahl, Solving sparse polynomial optimization problems with chordal structure using the sparse bounded-degree sum-of-squares hierarchy, Discrete Appl. Math., 275 (2020), pp. 95-110. · Zbl 1433.90110 [25] A. Megretski, Systems Polynomial Optimization Tools (SPOT), https://github.com/spot-toolbox/spotless, 2010. [26] J. Miller, Y. Zheng, M. Sznaier, and A. Papachristodoulou, Decomposed Structured Subsets for Semidefinite and Sum-of-Squares Optimization, preprint, https://arxiv.org/abs/1911.12859, 2019. [27] MOSEK ApS, The MOSEK Optimization Toolbox, Version 8.1, https://docs.mosek.com/8.1/toolbox/index.html, 2017. [28] K. Nakata, K. Fujisawa, M. Fukuda, M. Kojima, and K. Murota, Exploiting sparsity in semidefinite programming via matrix completion. II. Implementation and numerical results, Math. Program., 95 (2003), pp. 303-327. · Zbl 1030.90081 [29] P. A. Parrilo, Structured Semidefinite Programs and Semialgebraic Geometry Methods in Robustness and Optimization, Ph.D. thesis, California Institute of Technology, Pasadena, CA, 2000. [30] F. Permenter and P. A. Parrilo, Basis selection for SOS programs via facial reduction and polyhedral approximations, in Proceedings of the 53rd IEEE Conference on Decision and Control, 2014, pp. 6615-6620. [31] F. Permenter and P. A. Parrilo, Finding sparse, equivalent SDPs using minimal coordinate projections, in Proceedings of the 54th IEEE Conference on Decision and Control, 2015, pp. 7274-7279. [32] M. Putinar, Positive polynomials on compact semialgebraic sets, Indiana Univ. Math. J., 42 (1993), pp. 969-984. · Zbl 0796.12002 [33] B. Reznick, Extremal PSD forms with few terms, Duke Math. J., 45 (1978), pp. 363-374. · Zbl 0395.10037 [34] C. Riener, T. Theobald, L. J. Andrén, and J.-B. Lasserre, Exploiting symmetries in SDP-relaxations for polynomial optimization, Math. Oper. Res., 38 (2013), pp. 122-141. · Zbl 1291.90167 [35] J. F. Sturm, Using SeDuMi $$1.02$$, a MATLAB toolbox for optimization over symmetric cones, Optim. Methods Softw., 11 (1999), pp. 625-653. · Zbl 0973.90526 [36] M. Tacchi, T. Weisser, J.-B. Lasserre, and D. Henrion, Exploiting Sparsity for Semi-algebraic Set Volume Computation, preprint, https://arxiv.org/abs/1902.02976, 2019. [37] H. Waki, S. Kim, M. Kojima, and M. Muramatsu, Sums of squares and semidefinite program relaxations for polynomial optimization problems with structured sparsity, SIAM J. Optim., 17 (2006), pp. 218-242, https://doi.org/10.1137/050623802. · Zbl 1109.65058 [38] H. Waki, S. Kim, M. Kojima, M. Muramatsu, and H. Sugimoto, Algorithm 883: SparsePOP-a sparse semidefinite programming relaxation of polynomial optimization problems, ACM Trans. Math. Software, 35 (2009), 15. [39] J. Wang, H. Li, and B. Xia, A new sparse SOS decomposition algorithm based on term sparsity, in Proceedings of the ACM International Symposium on Symbolic and Algebraic Computation, 2019, pp. 347-354. · Zbl 07246266 [40] J. Wang, V. Magron, and J.-B. Lasserre, Chordal-TSSOS: A moment-SOS hierarchy that exploits term sparsity with chordal extension, SIAM J. Optim., to appear. [41] J. Wang, V. Magron, J.-B. Lasserre, and N. H. A. Mai, CS-TSSOS: Correlative and Term Sparsity for Large-Scale Polynomial Optimization, preprint, https://arxiv.org/abs/2005.02828, 2020. [42] T. Weisser, J. B. Lasserre, and K. C. Toh, Sparse-BSOS: A bounded degree SOS hierarchy for large scale polynomial optimization with sparsity, Math. Program. Comput., 10 (2018), pp. 1-32. · Zbl 1402.90136
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.