Optimization on linear matrix inequalities for polynomial systems control

Henrion, Didier

Journées Nationales de Calcul Formel. 13 – 17 Mai 2013, Les cours du CIRM, no. 1 (2013), Exposé no. 1, 44 p.

Many problems of systems control theory boil down to solving polynomial equations, polynomial inequalities or polyomial differential equations. Recent advances in convex optimization and real algebraic geometry can be combined to generate approximate solutions in floating point arithmetic.

In the first part of the course we describe semidefinite programming (SDP) as an extension of linear programming (LP) to the cone of positive semidefinite matrices. We investigate the geometry of spectrahedra, convex sets defined by linear matrix inequalities (LMIs) or affine sections of the SDP cone. We also introduce spectrahedral shadows, or lifted LMIs, obtained by projecting affine sections of the SDP cones. Then we review existing numerical algorithms for solving SDP problems.

In the second part of the course we describe several recent applications of SDP. First, we explain how to solve polynomial optimization problems, where a real multivariate polynomial must be optimized over a (possibly nonconvex) basic semialgebraic set. Second, we extend these techniques to ordinary differential equations (ODEs) with polynomial dynamics, and the problem of trajectory optimization (analysis of stability or performance of solutions of ODEs). Third, we conclude this part with applications to optimal control (design of a trajectory optimal w.r.t. a given functional).

For some of these decision and optimization problems, it is hoped that the numerical solutions computed by SDP can be refined a posteriori and certified rigorously with appropriate techniques.

Disclaimer

These lecture notes were written for a tutorial course given during the conference “Journées Nationales de Calcul Formel” held at Centre International de Rencontres Mathématiques, Luminy, Marseille, France in May 2013. They are aimed at giving an elementary and introductory account to recent applications of semidefinite programming to the numerical solution of decision problems involving polynomials in systems and control theory. The main technical results are gathered in a hopefully concise, notationally simple way, but for the sake of conciseness and readability, they are not proved in the document. The reader interested in mathematical rigorous comprehensive technical proofs is referred to the papers and books listed in the “Notes and references” section of each chapter. Comments, feedback, suggestions for improvement of these lectures notes are much welcome.

[1] L. Ambrosio, N. Gigli, G. Savaré. Gradient flows in metric spaces and in the space of probability measures. 2nd edition. Lectures in mathematics, ETH Zürich, Birkhäuser, Basel, 2008. | Zbl

[2] J. P. Aubin, H. Frankowska. Set-valued analysis. Springer-Verlag, Berlin, 1990. | Zbl

[3] A. Ben-Tal, A. Nemirovski. Lectures on modern convex optimization. SIAM, Philadelphia, 2001. | DOI | Zbl

[4] G. Blekerman, P. A. Parrilo, R. R. Thomas (Editors). Semidefinite optimization and convex algebraic geometry. SIAM, Philadelphia, 2013. | DOI

[5] S. Boyd, L. El Ghaoui, E. Feron, V. Balakrishnan. Linear matrix inequalities in system and control theory. SIAM, Philadelphia, 1994. | DOI | Zbl

[6] S. Boyd, L. Vandenberghe. Convex optimization. Cambridge Univ. Press, Cambridge, UK, 2005. | DOI | Zbl

[7] T. Carleman. Application de la théorie des équations intégrales linéaires aux systèmes d’équations différentielles non linéaires. Acta Math. 59:63-87, 1932. | DOI | Zbl

[8] D. A. Cox, J. B. Little, D. O’Shea. Ideals, varieties, and algorithms. 3rd edition, Springer-Verlag, New York, 2007. | DOI | MR

[9] R. Curto, L. Fialkow. Truncated K-moment problems in several variables. J. Operator Theory, 54:189-226, 2005. | Zbl

[10] B. Dacorogna. Direct methods in the calculus of variations. 2nd edition. Springer-Verlag, Berlin, 2007. | Zbl

[11] H. O. Fattorini. Infinite dimensional optimization and control theory. Cambridge Univ. Press, Cambridge, UK, 1999. | DOI | Zbl

[12] A. F. Filippov. Classical solutions of differential inclusions with multivalued right-hand side. SIAM J. Control 5(4):609-621, 1967. | DOI | MR | Zbl

[13] V. Gaitsgory, M. Quincampoix. Linear programming approach to deterministic infinite horizon optimal control problems with discounting. SIAM J. Control Optim. 48(4):2480-2512, 2009. | DOI | MR | Zbl

[14] S. Galeani, D. Henrion, A. Jacquemard, L. Zaccarian. Design of Marx generators as a structured eigenvalue assignment. arXiv:1301.7741, Jan. 2013. | DOI | MR | Zbl

[15] R. V. Gamkrelidze. Principles of optimal control theory. Plenum Press, New York, 1978. English translation of a Russian original of 1975. | DOI

[16] J. W. Helton, V. Vinnikov. Linear matrix inequality representation of sets. Comm. Pure Appl. Math. 60(5):654-674, 2007. | DOI | MR | Zbl

[17] J. W. Helton, J. Nie. Sufficient and necessary conditions for semidefinite representability of convex hulls and sets. SIAM J. Optim. 20(2):759–791, 2009. | DOI | MR | Zbl

[18] D. Henrion, J. B. Lasserre. Solving nonconvex optimization problems - How GloptiPoly is applied to problems in robust and nonlinear control. IEEE Control Systems Magazine, 24(3):72-83, 2004 | DOI

[19] D. Henrion, J. B. Lasserre. Detecting global optimality and extracting solutions in GloptiPoly. pp. 293-320 in D. Henrion, A. Garulli (Editors). Positive polynomials in control. Lecture Notes on Control and Information Sciences, Vol. 312, Springer-Verlag, Berlin, 2005. | DOI | Zbl

[20] D. Henrion, M. Ganet-Schoeller, S. Bennani. Measures and LMI for space launcher robust control validation. Proceedings of the IFAC Symposium on Robust Control Design, Aalborg, Denmark, June 2012. See also arXiv:1205.2168, May 2012. | DOI

[21] O. Hernández-Lerma, J. B. Lasserre. Markov chains and invariant probabilities. Birkhäuser, Basel, 2003. | DOI | Zbl

[22] J.-B. Hiriart-Urruty, C. Lemaréchal. Fundamentals of convex analysis. Springer-Verlag, Berlin, 2001. | DOI | Zbl

[23] A. N. Kolmogorov, S. V. Fomin. Introductory real analysis. Dover Publications, New York, 1970. English translation of a Russian original of 1968.

[24] K. Kowalski, W. H. Steeb. Dynamical systems and Carleman linearization. World Scientific, Singapore, 1991. | DOI | Zbl

[25] N. Kryloff, N. Bogoliouboff. La théorie générale de la mesure dans son application à l’étude des systèmes dynamiques de la mécanique non linéaire. Annals Math. 38(1):65-113, 1937. | DOI | Zbl

[26] A. Lasota, M. C. Mackey. Probabilistic properties of deterministic systems. Cambridge Univ. Press, Cambridge, UK, 1985. | DOI | Zbl

[27] J. B. Lasserre, Optimisation globale et théorie des moments. Comptes Rendus de l’Académie des Sciences Paris, Série I, Mathématique, 331(11):929-934, 2000. | DOI | Zbl

[28] J. B. Lasserre. Global optimization with polynomials and the problem of moments. SIAM J. Optim. 11(3):796–817, 2001. | DOI | MR | Zbl

[29] J. B. Lasserre, D. Henrion, C. Prieur, E. Trélat. Nonlinear optimal control via occupation measures and LMI relaxations. SIAM J. Control Optim. 47(4):1643-1666, 2008. | DOI | MR | Zbl

[30] J. B. Lasserre. Moments, positive polynomials and their applications. Imperial College Press, London, UK, 2009. | DOI

[31] J. Liouville. Sur la théorie de la variation des constantes arbitraires. Journal de Mathématiques Pures et Appliquées, 3:342-349, 1838.

[32] M. Laurent. Sums of squares, moment matrices and optimization over polynomials. Pages 157-270 in M. Putinar, S. Sullivant (Editors). Emerging applications of algebraic geometry, Vol. 149 of IMA Volumes in Mathematics and its Applications, Springer-Verlag, New York, 2009. | DOI | Zbl

[33] M. Laurent, F. Rendl. Semidefinite programming and integer programming. Pages 393-514 in K. Aardal, G. Nemhauser, R. Weismantel (Editors). Handbook on Discrete Optimization, Elsevier, North Holland, 2005. | DOI | Zbl

[34] D. G. Luenberger. Optimization by vector space methods. John Wiley and Sons, New York, 1969. | Zbl

[35] A. Nemirovski. Advances in convex optimization: conic programming. Pages 413-444 in M. Sanz-Sol, J. Soria, J. L. Varona, J. Verdera (Editors). Proceedings of International Congress of Mathematicians, Madrid, Spain, August 2006. Vol. 1, EMS Publishing House, 2007. | DOI

[36] V. V. Nemytskii, V. V. Stepanov. Qualitative theory of differential equations. Princeton Univ. Press, Princeton, NJ, 1960. English translation of a Russian original of 1947. | DOI | Zbl

[37] Y. Nesterov. Squared functional systems and optimization problems. Pages 405-440 in H. Frenk, K. Roos, T. Terlaky (Editors). High performance optimization. Kluwer Academic Publishers, Dordrecht, 2000. | DOI | Zbl

[38] Y. Nesterov, A. Nemirovski. Interior-point polynomial algorithms in convex programming. SIAM, Philaldelphia, 1994. | DOI

[39] J. Nie. Optimality conditions and finite convergence of Lasserre’s hierarchy. arXiv:1206.0319, June 2012. | DOI | MR | Zbl

[40] J. Nie, K. Ranestad, B. Sturmfels. The algebraic degree of semidefinite programming. Math. Prog. Ser. A 122(2):379-405, 2010. | DOI | MR | Zbl

[41] P. A. Parrilo. Structured semidefinite programs and semialgebraic geometry methods in robustness and optimization. PhD Thesis, Calif. Inst. Tech., Pasadena, 2000.

[42] P. Pedregal. Parametrized measures and variational principles. Birkhäuser, Basel, 1997. | DOI | Zbl

[43] H. Poincaré. Méthodes nouvelles de la mécanique céleste. Tome III. Gauthier-Villars, Paris, 1899. | Zbl

[44] H. Poincaré. L’avenir des mathématiques. Revue générale des sciences pures et appliquées, 19:930-939, 1908.

[45] S. Prajna, A. Rantzer. Convex programs for temporal verification of nonlinear dynamical systems. SIAM J. Control Optim. 46(3):999-1021, 2007. | DOI | MR | Zbl

[46] M. Putinar. Positive polynomials on compact semi-algebraic sets. Indiana Univ. Math. J. 42:969-984, 1993. | DOI | Zbl

[47] S. T. Rachev, L. Rüschendorf. Mass transportation problems. Volume I: theory. Springer-Verlag, Berlin, 1998. | Zbl

[48] A. Rantzer. A dual to Lyapunov’s stability theorem. Syst. Control Letters 42:161-168, 2001. | DOI | MR | Zbl

[49] J. Renegar. Hyperbolic programs, and their derivative relaxations. Found. Comput. Math. 6(1):59-79, 2006. | DOI | MR | Zbl

[50] F. Riesz, B. Sz.-Nagy. Leçons d’analyse fonctionnelle. 3ème édition. Gauthier-Villars, Paris, Akadémiai Kiadó, Budapest, 1955. | Zbl

[51] R. T. Rockafellar. Convex analysis. Princeton Univ. Press, Princeton, 1970. | Zbl

[52] T. Roubíček. Relaxation in optimization theory and variational calculus. Walter De Gruyter, Berlin, 1997. | DOI | Zbl

[53] H. Royden, P. Fitzpatrick. Real analysis. 4th edition. Prentice Hall, Boston, 2010. | Zbl

[54] J. E. Rubio. Control and optimization. The linear treatment of nonlinear problems. Manchester Univ. Press, Manchester, UK, 1986. | Zbl

[55] M. Safey El Din, L. Zhi. Computing rational points in convex semi-algebraic sets and sums of squares decompositions. SIAM J. Optim. 20(6):2876-2889, 2010. | DOI | MR | Zbl

[56] C. Scheiderer. Semidefinite representation for convex hulls of real algebraic curves. arXiv:1208.3865, Aug. 2012. | DOI | MR | Zbl

[57] M. J. Todd. Semidefinite optimization. Acta Numerica 10:515-560, 2001. | DOI | MR | Zbl

[58] L. Vandenberghe, S. Boyd. Semidefinite programming. SIAM Review 38(1):49-95, 1996. | DOI | MR | Zbl

[59] C. Villani. Topics in optimal transportation. Amer. Math. Society, Providence, 2003. | DOI | Zbl

[60] J. Warga. Optimal control of differential and functional equations. Academic Press, New York, 1972. | DOI | Zbl

[61] L. C. Young. Lectures on the calculus of variations and optimal control theory, W. B. Saunders, Philadelphia, 1969. | Zbl