Generalized Ellipsoids

References

• [1] Abramowitz M, Stegun I (1974) Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables (Dover Publications, New York).Google Scholar
• [2] Ahmadi AA, El Khadir B (2021) Time-varying semidefinite programs. Math. Oper. Res. 46(3):1054–1080.Link, Google Scholar
• [3] Ahmadi AA, Günlük O (2025) Robust-to-dynamics optimization. Math. Oper. Res. 50(2):965–992.Link, Google Scholar
• [4] Ahmadi AA, De Klerk E, Hall G (2019) Polynomial norms. SIAM J. Optim. 29(1):399–422.Crossref, Google Scholar
• [5] Ahmadi AA, Chaudhry A, Sindhwani V, Tu S (2024) Safely learning dynamical systems. Preprint, submitted June 8, https://arxiv.org/abs/2305.12284.Google Scholar
• [6] Ahmadi AA, Hall G, Makadia A, Sindhwani V (2017) Geometry of 3D environments and sum of squares polynomials. Srinivasa S, Ayanian N, Amato N, Kuindersma S, eds. Robotics: Science and Systems XIII, RSS 2017 (MIT-Press Journals, Cambridge, MA).Google Scholar
• [7] Ahmadi AA, Jungers RM, Parrilo PA, Roozbehani M (2014) Joint spectral radius and path-complete graph Lyapunov functions. SIAM J. Control Optim. 52(1):687–717.Crossref, Google Scholar
• [8] Ahmadi AA, Olshevsky A, Parrilo PA, Tsitsiklis JN (2013) NP-hardness of deciding convexity of quartic polynomials and related problems. Math. Programming 137(1–2):453–476.Crossref, Google Scholar
• [9] Ando T, Shih M-H (1998) Simultaneous contractibility. SIAM J. Matrix Anal. Appl. 19(2):487–498.Crossref, Google Scholar
• [10] Aylward E, Itani S, Parrilo PA (2007) Explicit SOS decompositions of univariate polynomial matrices and the Kalman–Yakubovich–Popov lemma. Hu T, Khalil HK, eds. Proc. 46th IEEE Conf. Decision Control (IEEE, Piscataway, NJ), 5660–5665.Google Scholar
• [11] Bandeira AS, Maillard A, Mendelson S, Paquette E (2024) Fitting an ellipsoid to a quadratic number of random points. Preprint, submitted October 2, https://arxiv.org/abs/2307.01181.Google Scholar
• [12] Barvinok A (2002) A Course in Convexity, Graduate Studies in Mathematics, vol. 54 (American Mathematical Society, Providence, RI).Crossref, Google Scholar
• [13] Barvinok A (2014) Thrifty approximations of convex bodies by polytopes. Internat. Math. Res. Notices 2014(16):4341–4356.Crossref, Google Scholar
• [14] Ben-Tal A, Nemirovski A (2001) Lectures on Modern Convex Optimization (SIAM, Philadelphia).Crossref, Google Scholar
• [15] Blondel VD, Canterini V (2003) Undecidable problems for probabilistic automata of fixed dimension. Theory Comput. Systems 36(3):231–245.Crossref, Google Scholar
• [16] Blondel VD, Tsitsiklis JN (2000) The boundedness of all products of a pair of matrices is undecidable. Systems Control Lett. 41(2):135–140.Crossref, Google Scholar
• [17] Blondel VD, Nesterov Y, Theys J (2005) On the accuracy of the ellipsoid norm approximation of the joint spectral radius. Linear Algebra Appl. 394:91–107.Crossref, Google Scholar
• [18] Boyd S, Vandenberghe L (2004) Convex Optimization (Cambridge University Press, New York).Crossref, Google Scholar
• [19] Choi MD (1975) Positive semidefinite biquadratic forms. Linear Algebra Appl. 12(2):95–100.Crossref, Google Scholar
• [20] Choi M-D, Lam T-Y, Reznick B (1980) Real zeros of positive semidefinite forms. I. Mathematische Zeitschrift 171(1):1–26.Crossref, Google Scholar
• [21] Choi MD, Lam TY, Reznick B (1995) Sums of squares of real polynomials. Jacob B, Rosenberg A, eds. K-Theory and Algebraic Geometry: Connections with Quadratic Forms and Division Algebras, Proc. Symposia Pure Math., vol. 58 (American Mathematical Society, Providence, RI), 103–126. Google Scholar
• [22] Debreu G (1952) A social equilibrium existence theorem. Proc. Natl. Acad. Sci. USA 38(10):886–893.Crossref, Google Scholar
• [23] Dette H, Studden WJ (2002) Matrix measures, moment spaces and Favard’s theorem for the interval [0, 1] and [0,∞). Linear Algebra Appl. 345(1–3):169–193.Crossref, Google Scholar
• [24] Fawzi H (2019) On representing the positive semidefinite cone using the second-order cone. Math. Programming 175(1):109–118.Crossref, Google Scholar
• [25] Gilbert EG, Johnson DW, Keerthi SS (1988) A fast procedure for computing the distance between complex objects in three-dimensional space. IEEE J. Robotics Automation 4(2):193–203.Crossref, Google Scholar
• [26] Grötschel M, Lovász L, Schrijver A (1988) Geometric Algorithms and Combinatorial Optimization (Springer-Verlag, Berlin).Crossref, Google Scholar
• [27] Harris MT, Parrilo PA (2023) Improved nonnegativity testing in the Bernstein basis via geometric means. Preprint, submitted September 19, https://arxiv.org/abs/2309.10675.Google Scholar
• [28] Helton JW, Nie J (2010) Semidefinite representation of convex sets. Math. Programming 122(1):21–64.Crossref, Google Scholar
• [29] Hespanha JP (2009) Linear Systems Theory (Princeton University Press, Princeton, NJ).Google Scholar
• [30] Hsieh JT, Kothari PK, Potechin A, Xu J (2023) Ellipsoid fitting up to a constant. Etessami K, Feige U, Puppis G, eds. 50th Internat. Colloquium Automata Languages Programming (ICALP 2023), Leibniz International Proceedings in Informatics (LIPIcs), vol. 261 (Schloss Dagstuhl–Leibniz-Zentrum für Informatik, Dagstuhl, Germany), 78:1–78:20.Google Scholar
• [31] Jungers R (2009) The Joint Spectral Radius: Theory and Applications, Lecture Notes in Control and Information Sciences, vol. 385 (Springer-Verlag, Berlin).Crossref, Google Scholar
• [32] Lasserre JB (2009) Convexity in semialgebraic geometry and polynomial optimization. SIAM J. Optim. 19(4):1995–2014.Crossref, Google Scholar
• [33] Legat B, Yuan C, Parrilo PA (2023) Low-rank univariate sum of squares has no spurious local minima. SIAM J. Optim. 33(3):2041–2061.Crossref, Google Scholar
• [34] Löfberg J (2004) YALMIP: A toolbox for modeling and optimization in MATLAB. Proc. 2004 IEEE Internat. Conf. Robotics Automation (ICRA 2004) (IEEE Robotics and Automation Society, IEEE, Piscataway, NJ). Google Scholar
• [35] Löfberg J, Parrilo PA (2004) From coefficients to samples: A new approach to SOS optimization. IEEE Control Systems Society, ed. Proc. 43rd IEEE Conf. Decision Control (CDC 2004) (IEEE, Piscataway, NJ), 3154–3159.Google Scholar
• [36] Nemirovski A, Roos C, Terlaky T (1999) On maximization of quadratic form over intersection of ellipsoids with common center. Math. Programming 86(3):463–473.Crossref, Google Scholar
• [37] Netzer T, Plaumann D (2023) Geometry of Linear Matrix Inequalities (Springer, Cham, Switzerland).Crossref, Google Scholar
• [38] Papp D (2017) Semi-infinite programming using high-degree polynomial interpolants and semidefinite programming. SIAM J. Optim. 27(3):1858–1879.Crossref, Google Scholar
• [39] Papp D, Alizadeh F (2013) Semidefinite characterization of sum-of-squares cones in algebras. SIAM J. Optim. 23(3):1398–1423.Crossref, Google Scholar
• [40] Papp D, Yildiz S (2019) Sum-of-squares optimization without semidefinite programming. SIAM J. Optim. 29(1):822–851.Crossref, Google Scholar
• [41] Parrilo PA (2000) Structured semidefinite programs and semialgebraic geometry methods in robustness and optimization. PhD thesis, California Institute of Technology, Pasadena.Google Scholar
• [42] Raghavendra P, Ryder N, Srivastava N (2017) Real stability testing. Impagliazzo R, Suresh RP, eds. 8th Innovations Theoret. Comput. Sci. Conf. (ITCS 2017), Leibniz International Proceedings in Informatics (LIPIcs), vol. 67 (Schloss Dagstuhl–Leibniz-Zentrum für Informatik, Dagstuhl, Germany), 5:1–5:15.Google Scholar
• [43] Rota G-C, Strang WG (1960) A note on the joint spectral radius. Indagationes Mathematicae Proc. 63:379–381.Crossref, Google Scholar
• [44] Saunderson J, Parrilo PA, Willsky AS (2013) Diagonal and low-rank decompositions and fitting ellipsoids to random points. IEEE Control Systems Society, ed. Proc. 52nd IEEE Conf. Decision Control (CDC 2013) (IEEE, Piscataway, NJ), 6031–6036. Google Scholar
• [45] Saunderson J, Chandrasekaran V, Parrilo PA, Willsky AS (2012) Diagonal and low-rank matrix decompositions, correlation matrices, and ellipsoid fitting. SIAM J. Matrix Anal. Appl. 33(4):1395–1416.Crossref, Google Scholar
• [46] Scherer C, Hol C (2006) Matrix sum-of-squares relaxations for robust semi-definite programs. Math. Programming 107(1–2):189–211.Crossref, Google Scholar
• [47] Todd MJ (2016) Minimum-Volume Ellipsoids: Theory and Algorithms (SIAM, Philadelphia).Crossref, Google Scholar
• [48] Tulsiani M, Wu J (2023) Ellipsoid fitting up to constant via empirical covariance estimation. Preprint, submitted July 23, https://arxiv.org/abs/2307.10941.Google Scholar
• [49] Vandenberghe L, Boyd S (1996) Semidefinite programming. SIAM Rev. 38(1):49–95.Crossref, Google Scholar
• [50] Weisser T, Legat B, Coey C, Kapelevich L, Pablo VJ (2019) Polynomial and moment optimization in Julia and JuMP. Accessed July 29, 2024, https://pretalx.com/juliacon2019/talk/QZBKAU/.Google Scholar
• [51] Yakubovich VA (1970) Factorization of symmetric matrix polynomials. Doklady Akademii Nauk SSSR 194(3):532–535.Google Scholar
• [52] Youla D (1961) On the factorization of rational matrices. IEEE Trans. Inform. Theory 7(3):172–189.Crossref, Google Scholar