References

Alizadeh, Farid, Jean-Pierre A Haeberly, and Michael L Overton. 1998. “Primal-Dual Interior-Point Methods for Semidefinite Programming: Convergence Rates, Stability and Numerical Results.” SIAM Journal on Optimization 8 (3): 746–68.

Arnborg, Stefan, Derek G Corneil, and Andrzej Proskurowski. 1987. “Complexity of Finding Embeddings in Ak-Tree.” SIAM Journal on Algebraic Discrete Methods 8 (2): 277–84.

Barvinok, Alexander I. 1995. “Problems of Distance Geometry and Convex Properties of Quadratic Maps.” Discrete & Computational Geometry 13: 189–202.

Bayer, Christian, and Josef Teichmann. 2006. “The Proof of Tchakaloff’s Theorem.” Proceedings of the American Mathematical Society 134 (10): 3035–40.

Bertsekas, Dimitri, Angelia Nedic, and Asuman Ozdaglar. 2003. Convex Analysis and Optimization. Vol. 1. Athena Scientific.

Bertsimas, Dimitris, and John N Tsitsiklis. 1997. Introduction to Linear Optimization. Vol. 6. Athena scientific Belmont, MA.

Blekherman, Grigoriy, Pablo A Parrilo, and Rekha R Thomas. 2012. Semidefinite Optimization and Convex Algebraic Geometry. SIAM.

Bochnak, Jacek, Michel Coste, and Marie-Françoise Roy. 2013. Real Algebraic Geometry. Vol. 36. Springer Science & Business Media.

Boumal, Nicolas, Vlad Voroninski, and Afonso Bandeira. 2016. “The Non-Convex Burer-Monteiro Approach Works on Smooth Semidefinite Programs.” Advances in Neural Information Processing Systems 29.

Boyd, Stephen P, and Lieven Vandenberghe. 2004. Convex Optimization. Cambridge university press.

Boyd, Stephen, Laurent El Ghaoui, Eric Feron, and Venkataramanan Balakrishnan. 1994. Linear Matrix Inequalities in System and Control Theory. SIAM.

Briales, Jesus, Laurent Kneip, and Javier Gonzalez-Jimenez. 2018. “A Certifiably Globally Optimal Solution to the Non-Minimal Relative Pose Problem.” In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 145–54.

Burer, Samuel, and Renato DC Monteiro. 2003. “A Nonlinear Programming Algorithm for Solving Semidefinite Programs via Low-Rank Factorization.” Mathematical Programming 95 (2): 329–57.

Cifuentes, Diego, and Ankur Moitra. 2022. “Polynomial Time Guarantees for the Burer-Monteiro Method.” Advances in Neural Information Processing Systems 35: 23923–35.

Corless, Robert M, Patrizia M Gianni, and Barry M Trager. 1997a. “A Reordered Schur Factorization Method for Zero-Dimensional Polynomial Systems with Multiple Roots.” In Proceedings of the 1997 International Symposium on Symbolic and Algebraic Computation, 133–40.

———. 1997b. “A Reordered Schur Factorization Method for Zero-Dimensional Polynomial Systems with Multiple Roots.” In Proceedings of the 1997 International Symposium on Symbolic and Algebraic Computation, 133–40.

Cox, David, John Little, and Donal OShea. 2013. Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra. Springer Science & Business Media.

Curto, Raúl E, and Lawrence A Fialkow. 2005. “Truncated k-Moment Problems in Several Variables.” Journal of Operator Theory, 189–226.

Dummit, David Steven, and Richard M Foote. 2004. Abstract Algebra. Vol. 3. Wiley Hoboken.

Eriksson, Anders, Carl Olsson, Fredrik Kahl, and Tat-Jun Chin. 2018. “Rotation Averaging and Strong Duality.” In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 127–35.

Fazel, Maryam, Rong Ge, Sham Kakade, and Mehran Mesbahi. 2018. “Global Convergence of Policy Gradient Methods for the Linear Quadratic Regulator.” In International Conference on Machine Learning, 1467–76. PMLR.

Fukuda, Mituhiro, Masakazu Kojima, Kazuo Murota, and Kazuhide Nakata. 2001. “Exploiting Sparsity in Semidefinite Programming via Matrix Completion i: General Framework.” SIAM Journal on Optimization 11 (3): 647–74.

Garcia-Salguero, Mercedes, Jesus Briales, and Javier Gonzalez-Jimenez. 2021. “Certifiable Relative Pose Estimation.” Image and Vision Computing 109: 104142.

Gavril, Fănică. 1972. “Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph.” SIAM Journal on Computing 1 (2): 180–87.

Goemans, Michel X, and David P Williamson. 1995. “Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems Using Semidefinite Programming.” Journal of the ACM (JACM) 42 (6): 1115–45.

Goldstein, Tom, Brendan O’Donoghue, Simon Setzer, and Richard Baraniuk. 2014. “Fast Alternating Direction Optimization Methods.” SIAM Journal on Imaging Sciences 7 (3): 1588–1623.

Hartley, Richard, and Andrew Zisserman. 2003. Multiple View Geometry in Computer Vision. Cambridge university press.

Helmberg, Christoph, Franz Rendl, Robert J Vanderbei, and Henry Wolkowicz. 1996. “An Interior-Point Method for Semidefinite Programming.” SIAM Journal on Optimization 6 (2): 342–61.

Henrion, Didier, and Jean-Bernard Lasserre. 2005. “Detecting Global Optimality and Extracting Solutions in GloptiPoly.” In Positive Polynomials in Control, 293–310. Springer.

Holmes, Connor, and Timothy D Barfoot. 2023. “An Efficient Global Optimality Certificate for Landmark-Based SLAM.” IEEE Robotics and Automation Letters 8 (3): 1539–46.

Hu, Bin, Kaiqing Zhang, Na Li, Mehran Mesbahi, Maryam Fazel, and Tamer Başar. 2023. “Toward a Theoretical Foundation of Policy Optimization for Learning Control Policies.” Annual Review of Control, Robotics, and Autonomous Systems 6: 123–58.

Journée, Michel, Francis Bach, P-A Absil, and Rodolphe Sepulchre. 2010. “Low-Rank Optimization on the Cone of Positive Semidefinite Matrices.” SIAM Journal on Optimization 20 (5): 2327–51.

Kim, Donghwan. 2021. “Accelerated Proximal Point Method for Maximally Monotone Operators.” Mathematical Programming 190 (1): 57–87.

Kojima, Masakazu, Susumu Shindoh, and Shinji Hara. 1997. “Interior-Point Methods for the Monotone Semidefinite Linear Complementarity Problem in Symmetric Matrices.” SIAM Journal on Optimization 7 (1): 86–125.

Lang, Serge. 2012. Algebra. Vol. 211. Springer Science & Business Media.

Lasserre, Jean B. 2001. “Global Optimization with Polynomials and the Problem of Moments.” SIAM Journal on Optimization 11 (3): 796–817.

Lofberg, Johan. 2004. “YALMIP: A Toolbox for Modeling and Optimization in MATLAB.” In 2004 IEEE International Conference on Robotics and Automation (IEEE Cat. No. 04CH37508), 284–89. IEEE.

Magron, Victor, and Jie Wang. 2023. Sparse Polynomial Optimization: Theory and Practice. World Scientific.

Mansour, Yishay, Mehryar Mohri, and Afshin Rostamizadeh. 2009. “Domain Adaptation: Learning Bounds and Algorithms.” arXiv Preprint arXiv:0902.3430.

Mohammadi, Hesameddin, Armin Zare, Mahdi Soltanolkotabi, and Mihailo R Jovanović. 2021. “Convergence and Sample Complexity of Gradient Methods for the Model-Free Linear–Quadratic Regulator Problem.” IEEE Transactions on Automatic Control 67 (5): 2435–50.

Monteiro, Renato DC. 1997. “Primal–Dual Path-Following Algorithms for Semidefinite Programming.” SIAM Journal on Optimization 7 (3): 663–78.

———. 1998. “Polynomial Convergence of Primal-Dual Algorithms for Semidefinite Programming Based on the Monteiro and Zhang Family of Directions.” SIAM Journal on Optimization 8 (3): 797–812.

Nie, Jiawang. 2023. Moment and Polynomial Optimization. SIAM.

Nistér, David. 2004. “An Efficient Solution to the Five-Point Relative Pose Problem.” IEEE Transactions on Pattern Analysis and Machine Intelligence 26 (6): 756–70.

Nocedal, Jorge, and Stephen J Wright. 1999. Numerical Optimization. Springer.

Pataki, Gábor. 1998. “On the Rank of Extreme Matrices in Semidefinite Programs and the Multiplicity of Optimal Eigenvalues.” Mathematics of Operations Research 23 (2): 339–58.

Prajna, Stephen, Antonis Papachristodoulou, and Pablo A Parrilo. 2002. “Introducing SOSTOOLS: A General Purpose Sum of Squares Programming Solver.” In Proceedings of the 41st IEEE Conference on Decision and Control, 2002., 1:741–46. IEEE.

Putinar, Mihai. 1993. “Positive Polynomials on Compact Semi-Algebraic Sets.” Indiana University Mathematics Journal 42 (3): 969–84.

Ramana, Motakuri V. 1997. “An Exact Duality Theory for Semidefinite Programming and Its Complexity Implications.” Mathematical Programming 77: 129–62.

Ramana, Motakuri, and Alan J Goldman. 1995. “Some Geometric Results in Semidefinite Programming.” Journal of Global Optimization 7 (1): 33–50.

Reznick, Bruce. 1978. “Extremal PSD Forms with Few Terms.” Duke Mathematical Journal.

———. 2000. “Some Concrete Aspects of Hilbert’s 17th Problem.” Contemporary Mathematics 253: 251–72.

Rockafellar, Ralph Tyrell. 1970. Convex Analysis. Princeton university press.

Rosen, David M, Luca Carlone, Afonso S Bandeira, and John J Leonard. 2019. “SE-Sync: A Certifiably Correct Algorithm for Synchronization over the Special Euclidean Group.” The International Journal of Robotics Research 38 (2-3): 95–125.

Schacke, Kathrin. 2004. “On the Kronecker Product.” Master’s Thesis, University of Waterloo.

Schmudgen, Konrad. 1991. “THE k-MOMENT PROBLEM FOR COMPACT SEMI-ALGEBRAIC SETS.” Mathematische Annalen.

Shor, Naum Z. 1987. “Quadratic Optimization Problems.” Soviet Journal of Computer and Systems Sciences 25: 1–11.

Stengle, Gilbert. 1974. “A Nullstellensatz and a Positivstellensatz in Semialgebraic Geometry.” Mathematische Annalen 207: 87–97.

Sturmfels, Bernd. 2005. “What Is... A Grobner Basis?” Notices-American Mathematical Society 52 (10): 1199.

Tang, Yukai, Jean-Bernard Lasserre, and Heng Yang. 2023. “Uncertainty Quantification of Set-Membership Estimation in Control and Perception: Revisiting the Minimum Enclosing Ellipsoid.” arXiv Preprint arXiv:2311.15962.

Todd, Michael J. 2001. “Semidefinite Optimization.” Acta Numerica 10: 515–60.

Todd, Michael J, Kim-Chuan Toh, and Reha H Tütüncü. 1998. “On the Nesterov–Todd Direction in Semidefinite Programming.” SIAM Journal on Optimization 8 (3): 769–96.

Vandenberghe, Lieven, Martin S Andersen, et al. 2015. “Chordal Graphs and Semidefinite Optimization.” Foundations and Trends in Optimization 1 (4): 241–433.

Wang, Lanhui, and Amit Singer. 2013. “Exact and Stable Recovery of Rotations for Robust Synchronization.” Information and Inference: A Journal of the IMA 2 (2): 145–93.

Wang, Qianqian, Xiaowei Zhou, Bharath Hariharan, and Noah Snavely. 2020. “Learning Feature Descriptors Using Camera Pose Supervision.” In Computer Vision–ECCV 2020: 16th European Conference, Glasgow, UK, August 23–28, 2020, Proceedings, Part i 16, 757–74. Springer.

Wolkowicz, Henry, Romesh Saigal, and Lieven Vandenberghe. 2000. Handbook of Semidefinite Programming: Theory, Algorithms, and Applications. Vol. 27. Springer.

Yang, Heng, and Luca Carlone. 2022. “Certifiably Optimal Outlier-Robust Geometric Perception: Semidefinite Relaxations and Scalable Global Optimization.” IEEE Transactions on Pattern Analysis and Machine Intelligence 45 (3): 2816–34.

Yang, Heng, Ling Liang, Luca Carlone, and Kim-Chuan Toh. 2022. “An Inexact Projected Gradient Method with Rounding and Lifting by Nonlinear Programming for Solving Rank-One Semidefinite Relaxation of Polynomial Optimization.” Mathematical Programming, 1–64.

Zhang, Richard Y, and Javad Lavaei. 2021. “Sparse Semidefinite Programs with Guaranteed Near-Linear Time Complexity via Dualized Clique Tree Conversion.” Mathematical Programming 188: 351–93.

Zhang, Yin. 1998. “On Extending Some Primal–Dual Interior-Point Algorithms from Linear Programming to Semidefinite Programming.” SIAM Journal on Optimization 8 (2): 365–86.

Zheng, Yang, Giovanni Fantuzzi, Antonis Papachristodoulou, Paul Goulart, and Andrew Wynn. 2020. “Chordal Decomposition in Operator-Splitting Methods for Sparse Semidefinite Programs.” Mathematical Programming 180 (1): 489–532.