×

zbMATH — the first resource for mathematics

Exact algorithms for linear matrix inequalities. (English) Zbl 1356.90102

MSC:
90C22 Semidefinite programming
68W30 Symbolic computation and algebraic computation
14Q20 Effectivity, complexity and computational aspects of algebraic geometry
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] M. F. Anjos and J. B. Lasserre, eds., Handbook of Semidefinite, Conic and Polynomial Optimization, Internat. Ser. Oper. Res. Management Scie. 166, Springer, New York, 2012. · Zbl 1235.90002
[2] B. Bank, M. Giusti, J. Heintz, M. Safey El Din, and É. Schost, On the geometry of polar varieties, Appl. Algebra Engrg. Comm. Comput., 21 (2010), pp. 33–83.
[3] B. Bank, M. Giusti, J. Heintz, and G.-M. Mbakop, Polar varieties and efficient real elimination, Math. Z., 238 (2001), pp. 115–144. · Zbl 1073.14554
[4] R. G. Bartle and D. R. Sherbert, Introduction to Real Analysis, Wiley, New York, 1992. · Zbl 0810.26001
[5] S. Basu, R. Pollack, and M.-F. Roy, On the combinatorial and algebraic complexity of quantifier elimination, J. ACM, 43 (1996), pp. 1002–1046. · Zbl 0885.68070
[6] S. Basu, R. Pollack, and M.-F. Roy, Algorithms in Real Algebraic Geometry, Algorithms Comput. Math. 10., Springer-Verlag, Berlin, 2006. · Zbl 1102.14041
[7] A. Ben-Tal and A. Nemirovski, Lectures on Modern Convex Optimization: Analysis, Algorithms, and Engineering Applications, MPS-SIAM Ser. Optim., SIAM, Philadelphia, 2001. · Zbl 0986.90032
[8] G. Blekherman, P. A. Parrilo, and R. R. Thomas, eds., Semidefinite Optimization and Convex Algebraic Geometry, SIAM, Philadelphia, 2013. · Zbl 1260.90006
[9] S. P. Boyd, L. El Ghaoui, E. Feron, and V. Balakrishnan, Linear Matrix Inequalities in System and Control Theory, Stud. Appl. Math., 15, SIAM, Philadelphia, 1994. · Zbl 0816.93004
[10] S. Boyd and L. Vandenberghe, Semidefinite programming, SIAM Rev., 38 (1996), pp. 49–95. · Zbl 0845.65023
[11] M. Claeys, Mesures d’occupation et relaxations semi-définies pour la commande optimale, Ph.D. thesis, LAAS CNRS, Université, Toulouse, France, 2013.
[12] G. Collins, Quantifier elimination for real closed fields by cylindrical algebraic decompostion, in Automata Theory and Formal Languages, Springer, Berlin, 1975, pp. 134–183.
[13] D. A. Cox, J. Little, and D. O’Shea, Ideals, Varieties, and Algorithms, 3rd ed., Springer, New York, 2007.
[14] X. Dahan, and E. Schost, Sharp estimates for triangular sets, in Proceedings of the International Symposium on Symbolic and Algebraic Computation, 2004, pp. 103–110. · Zbl 1134.13308
[15] J. Draisma, E. Horobet, G. Ottaviani, B. Sturmfels, and R.R. Thomas, The Euclidean distance degree of an algebraic variety, Found. Comput. Math., 16 (2016), pp. 99–149. · Zbl 1370.51020
[16] D. Eisenbud, Commutative Algebra with a View Toward Algebraic Geometry, Springer, New York, 1995. · Zbl 0819.13001
[17] J.-C. Faugère, FGb: A library for computing Gröbner bases, in Mathematical Software—ICMS 2010, Springer, Berlin, 2010, pp. 84–87
[18] J.-C. Faugère, M. Safey El Din, and P.-J. Spaenlehauer, On the complexity of the generalized MinRank problem, J. Symbolic. Comput., 55 (2013), pp. 30–58. · Zbl 1302.13026
[19] J.-C. Faugère, P. Gaudry, L. Huot, and G. Renault, Polynomial Systems Solving by Fast Linear Algebra, , 2013.
[20] J.-C. Faugère, P. Gianni, D. Lazard, and T. Mora, Efficient computation of zero-dimensional Gröbner bases by change of ordering, J. Symbolic. Comput., 16 (1993), pp. 329–344. · Zbl 0805.13007
[21] J.-C. Faugère, and C. Mou, Sparse FGLM Algorithms, , 2013.
[22] J.-C. Faugère, M. Safey El Din, and P.-J. Spaenlehauer, Critical points and Gröbner bases: The unmixed case, Proceedings of the 37th International Symposium on Symbolic and Algebraic Computation, 2012, pp. 162–169. · Zbl 1308.68171
[23] M. Giusti, G. Lecerf, and B. Salvy, A Gröbner free alternative for polynomial system solving, J. Complexity, 17 (2011), pp. 154-211. · Zbl 1003.12005
[24] H.-C. Graf von Bothmer and K. Ranestad, A general formula for the algebraic degree in semidefinite programming, Bull. Lond. Math. Soc., 41 (2009), pp. 193–197. · Zbl 1185.14047
[25] A. Greuet and M. Safey El Din, Probabilistic algorithm for the global optimization of a polynomial over a real algebraic set, SIAM J. Optim., 24 (2014), pp. 1313–1343. · Zbl 1327.90232
[26] D. Grigoriev and N. Vorobjov, Solving systems of polynomial inequalities in subexponential time, J. Symbolic. Comput., 5 (1988), pp. 37–64. · Zbl 0662.12001
[27] M. Grötschel, L. Lovász, and A. Schrijver, Geometric Algorithms and Combinatorial Optimization, Springer, Berlin, 1988.
[28] Q. Guo, M. Safey El Din, and L. Zhi, Computing rational solutions of linear matrix inequalities, in Proceedings of ISSAC, Boston, 2013.
[29] F. Guo, E. Kaltofen, and L. Zhi, Certificates of impossibility of Hilbert-Artin representations of a given degree for definite polynomials and functions, in Proceedings of ISSAC, Grenoble, France, 2012, pp. 195–202. · Zbl 1323.65068
[30] J. Harris, Algebraic Geometry. A First Course, Springer, New York, 1992. · Zbl 0779.14001
[31] J. Heintz, M.-F. Roy, and P. Solernó, Description of the connected components of a semi-algebraic set in single exponential time, Discrete Comput. Geom., 11 (1994), pp. 121–140. · Zbl 0970.68201
[32] J. W. Helton and J. Nie, Sufficient and necessary conditions for semidefinite representability of convex hulls and sets, SIAM J. Optim., 20 (2009), pp. 759–791. · Zbl 1190.14058
[33] D. Henrion, Optimization on linear matrix inequalities for polynomial systems control, Lecture Notes of the International Summer School of Automatic Control, Grenoble, France, 2014.
[34] D. Henrion, S. Naldi, and M. Safey El Din, Real root finding for determinants of linear matrices, J. Symbolic. Comput., 74 (2016) pp. 205–238. · Zbl 1329.65090
[35] D. Henrion, S. Naldi, and M. Safey El Din, Real root finding for rank defects in linear Hankel matrices, in Proceedings of ISSAC, Bath, UK, 2015, pp. 221–228. · Zbl 1345.65024
[36] D. Henrion, S. Naldi, and M. Safey El Din, Real Root Finding for Low Rank Linear Matrices, , 2015.
[37] D. Henrion, J. B. Lasserre, C. Prieur, and E. Trélat, Nonlinear optimal control via occupation measures and LMI relaxations, SIAM J. Control Optim., 47 (2008), pp. 1643–1666. · Zbl 1188.90193
[38] D. Hilbert, Über die Dartstellung definiter Formen als Summe von Formenquadraten, Math. Ann., 32, (1888), pp. 342–350. · JFM 20.0198.02
[39] G. Jeronimo, G. Matera, P. Solernó, and A. Waissbein, Deformation techniques for sparse systems, Found. Comput. Math., 9 (2009), pp. 1–50. · Zbl 1167.14039
[40] L. Khachiyan and L. Porkolab, On the complexity of semidefinite programs, J. Global Optim., 10 (1997) pp. 351–365. · Zbl 0881.90127
[41] I. Klep and M. Schweighofer, An exact duality theory for semidefinite programming based on sums of squares, Math. Oper. Res., 38 (2013), pp. 569–590. · Zbl 1309.13031
[42] J. B. Lasserre, Global optimization with polynomials and the problem of moments, SIAM J. Optim., 11 (2001), pp. 796–817. · Zbl 1010.90061
[43] M. Laurent, Sums of squares, moment matrices and optimization over polynomials, in Emerging Applications of Algebraic Geometry, M. Putinar and S. Sullivant, ed., IMA, Vol. Maths. Appl., 149, Springer, New York, 2009, pp. 157–270. · Zbl 1163.13021
[44] H. Lombardi, D. Perrucci, and M.-F. Roy, An Elementary Recursive Bound for the Effective Positivestellensatz and Hilbert 17th Problem, , 2014.
[45] S. Melczer and B. Salvy, Symbolic-numeric tools for analytic combinatorics in several variables, in Proceedings of ISSAC, ACM, Waterloo, 2016, pp. 333–340. · Zbl 1360.68945
[46] Y. Nesterov and A. Nemirovsky, Interior-Point Polynomial Algorithms in Convex Programming, Stud. Appl. Math. 13, SIAM, Philadelphia, 1994.
[47] J. Nie, Optimality conditions and finite convergence of Lasserre’s hierarchy, Math. Progr. Ser. A, 146 (2014), pp. 97–121. · Zbl 1300.65041
[48] J. Nie, K. Ranestad, and B. Sturmfels, The algebraic degree of semidefinite programming, Math. Progr. Ser. A, 122 (2010), pp. 379–405. · Zbl 1184.90119
[49] J. Nie and M. Schweighofer, On the complexity of Putinar Positivstellensatz, J. Complexity, 23 (2007), pp. 135–150. · Zbl 1143.13028
[50] G. Ottaviani, P.-J. Spaenlehauer, and B. Sturmfels, Exact solutions in structured low-rank approximation, SIAM J. Matrix Anal. Appl, 35 (2014), pp. 1521–1542. · Zbl 1318.14057
[51] V. Powers and T. Woermann, An algorithm for sums of squares of real polynomials, J. Pure Appl. Algebra, 127 (1998), pp. 99–104. · Zbl 0936.11023
[52] M. Putinar, Positive polynomials on compact sets, Indiana Univ. Math. J., 42 (1993), pp. 969–984. · Zbl 0796.12002
[53] M. Ramana and A. J. Goldman, Some geometric results in semidefinite programming, J. Global Optim., 7 (1995), pp. 33–50. · Zbl 0839.90093
[54] J. Renegar, On the computational complexity and geometry of the first order theory of the reals, J. Symbolic. Comput., 13 (1992), pp. 255–352. · Zbl 0798.68073
[55] F. Rouillier, Solving zero-dimensional systems through the rational univariate representation, Appl. Algebra Engrg. Comm. Comput., 9 (1999), pp. 433–461. · Zbl 0932.12008
[56] M. Safey El Din, RAGlib Maple Package, .
[57] M. Safey El Din and L. Zhi, Computing rational points in convex semi-algebraic sets and sums of squares decompositions, SIAM J. Optim., 20 (2010), pp. 2876–2889. · Zbl 1279.90127
[58] M. Safey El Din and É. Schost, Polar varieties and computation of one point in each connected component of a smooth real algebraic set, in Proceedings of ISSAC, Philadelphia, 2003. · Zbl 1072.68693
[59] M. Safey El Din and É. Schost, Properness defects of projections and computation of one point in each connected component of a real algebraic set, Discrete Comput. Geom., 32 (2004), pp. 417–430. · Zbl 1067.14057
[60] M. Safey El Din and É. Schost, A Nearly Optimal Algorithm for Deciding Connectivity Queries in Smooth and Bounded Real Algebraic Sets, , 2013. · Zbl 1426.68311
[61] C. Scheiderer, Sums of Squares of Polynomials with Rational Coefficients, , 2012. · Zbl 1354.14036
[62] C. Scheiderer, Semidefinite Representation for Convex Hulls of Real Algebraic Curves, , 2012. · Zbl 1390.14173
[63] I. Shafarevich, Basic Algebraic Geometry 1, Springer, Berlin, 1977. · Zbl 0362.14001
[64] K. Schmüdgen, The K-moment problem for compact semi-algebraic sets, Math. Ann., 289 (1991), pp. 203–206.
[65] M. Schweighofer, On the complexity of Schmüdgen Positivstellensatz, J. Complexity, 20 (2004), pp. 529–543. · Zbl 1161.68480
[66] R. Sinn and B. Sturmfels, Generic spectrahedral shadows, SIAM J. Optim., 25 (2015), pp. 1209–1220. · Zbl 1346.14132
[67] S. Tarbouriech, G. Garcia, J. M. Gomes da Silva, and I. Queinnec, Stability and Stabilization of Linear Systems with Saturating Actuators, Springer, London, 2011. · Zbl 1279.93004
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.