Centre de diffusion de revues académiques mathématiques


Les cours du CIRM

Table des matières de ce fascicule | Article suivant
Didier Henrion
Optimization on linear matrix inequalities for polynomial systems control
Les cours du CIRM, 3 no. 1: Journées Nationales de Calcul Formel (2013), Exp. No. 1, 44 p., doi: 10.5802/ccirm.17
Article PDF

Résumé - Abstract

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.


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.  MR 2401600 |  Zbl 1090.35002
[2] J. P. Aubin, H. Frankowska. Set-valued analysis. Springer-Verlag, Berlin, 1990.  MR 1048347 |  Zbl 0713.49021
[3] A. Ben-Tal, A. Nemirovski. Lectures on modern convex optimization. SIAM, Philadelphia, 2001.  MR 1857264 |  Zbl 0986.90032
[4] G. Blekerman, P. A. Parrilo, R. R. Thomas (Editors). Semidefinite optimization and convex algebraic geometry. SIAM, Philadelphia, 2013.  Zbl 1260.90006
[5] S. Boyd, L. El Ghaoui, E. Feron, V. Balakrishnan. Linear matrix inequalities in system and control theory. SIAM, Philadelphia, 1994.  MR 1284712 |  Zbl 0816.93004
[6] S. Boyd, L. Vandenberghe. Convex optimization. Cambridge Univ. Press, Cambridge, UK, 2005.  MR 2061575 |  Zbl 1058.90049
[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.  MR 1555355 |  JFM 58.0417.01
[8] D. A. Cox, J. B. Little, D. O’Shea. Ideals, varieties, and algorithms. 3rd edition, Springer-Verlag, New York, 2007.  MR 2290010 |  Zbl 0756.13017
[9] R. Curto, L. Fialkow. Truncated K-moment problems in several variables. J. Operator Theory, 54:189-226, 2005.  MR 2168867 |  Zbl 1119.47304
[10] B. Dacorogna. Direct methods in the calculus of variations. 2nd edition. Springer-Verlag, Berlin, 2007.  MR 2361288 |  Zbl 0703.49001
[11] H. O. Fattorini. Infinite dimensional optimization and control theory. Cambridge Univ. Press, Cambridge, UK, 1999.  MR 1669395 |  Zbl 1200.49001
[12] A. F. Filippov. Classical solutions of differential inclusions with multivalued right-hand side. SIAM J. Control 5(4):609-621, 1967.  MR 220995
[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.  MR 2556353 |  Zbl 1201.49040
[14] S. Galeani, D. Henrion, A. Jacquemard, L. Zaccarian. Design of Marx generators as a structured eigenvalue assignment. arXiv:1301.7741, Jan. 2013.
[15] R. V. Gamkrelidze. Principles of optimal control theory. Plenum Press, New York, 1978. English translation of a Russian original of 1975.  MR 686793 |  Zbl 0401.49001
[16] J. W. Helton, V. Vinnikov. Linear matrix inequality representation of sets. Comm. Pure Appl. Math. 60(5):654-674, 2007.  MR 2292953 |  Zbl 1116.15016
[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.  MR 2515796 |  Zbl 1190.14058
[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
[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.  MR 2123528 |  Zbl 1119.93301
[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.
[21] O. Hernández-Lerma, J. B. Lasserre. Markov chains and invariant probabilities. Birkhäuser, Basel, 2003.  MR 1974383 |  Zbl 1036.60003
[22] J.-B. Hiriart-Urruty, C. Lemaréchal. Fundamentals of convex analysis. Springer-Verlag, Berlin, 2001.  MR 1865628 |  Zbl 0998.49001
[23] A. N. Kolmogorov, S. V. Fomin. Introductory real analysis. Dover Publications, New York, 1970. English translation of a Russian original of 1968.  MR 267052 |  Zbl 0213.07305
[24] K. Kowalski, W. H. Steeb. Dynamical systems and Carleman linearization. World Scientific, Singapore, 1991.  MR 1178493
[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.  MR 1503326 |  JFM 63.1002.01
[26] A. Lasota, M. C. Mackey. Probabilistic properties of deterministic systems. Cambridge Univ. Press, Cambridge, UK, 1985.  MR 832868 |  Zbl 0606.58002
[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.  MR 1806434 |  Zbl 1016.90031
[28] J. B. Lasserre. Global optimization with polynomials and the problem of moments. SIAM J. Optim. 11(3):796–817, 2001.  MR 1814045 |  Zbl 1010.90061
[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.  MR 2421324 |  Zbl 1188.90193
[30] J. B. Lasserre. Moments, positive polynomials and their applications. Imperial College Press, London, UK, 2009.  MR 2589247 |  Zbl 1211.90007
[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.  MR 2500468 |  Zbl 1163.13021
[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.  Zbl 1194.90066
[34] D. G. Luenberger. Optimization by vector space methods. John Wiley and Sons, New York, 1969.  MR 238472 |  Zbl 0176.12701
[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.  MR 2334199 |  Zbl 1135.90379
[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.  MR 121520 |  Zbl 0089.29502
[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.  MR 1748764 |  Zbl 0958.90090
[38] Y. Nesterov, A. Nemirovski. Interior-point polynomial algorithms in convex programming. SIAM, Philaldelphia, 1994.  MR 1258086 |  Zbl 0824.90112
[39] J. Nie. Optimality conditions and finite convergence of Lasserre’s hierarchy. arXiv:1206.0319, June 2012.
[40] J. Nie, K. Ranestad, B. Sturmfels. The algebraic degree of semidefinite programming. Math. Prog. Ser. A 122(2):379-405, 2010.  MR 2546336 |  Zbl 1184.90119
[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.  MR 1452107 |  Zbl 0879.49017
[43] H. Poincaré. Méthodes nouvelles de la mécanique céleste. Tome III. Gauthier-Villars, Paris, 1899.  JFM 30.0834.08
[44] H. Poincaré. L’avenir des mathématiques. Revue générale des sciences pures et appliquées, 19:930-939, 1908.  JFM 39.0081.03
[45] S. Prajna, A. Rantzer. Convex programs for temporal verification of nonlinear dynamical systems. SIAM J. Control Optim. 46(3):999-1021, 2007.  MR 2338436 |  Zbl 1147.93023
[46] M. Putinar. Positive polynomials on compact semi-algebraic sets. Indiana Univ. Math. J. 42:969-984, 1993.  MR 1254128 |  Zbl 0796.12002
[47] S. T. Rachev, L. Rüschendorf. Mass transportation problems. Volume I: theory. Springer-Verlag, Berlin, 1998.  MR 1619170 |  Zbl 0990.60500
[48] A. Rantzer. A dual to Lyapunov’s stability theorem. Syst. Control Letters 42:161-168, 2001.  MR 2007046 |  Zbl 0974.93058
[49] J. Renegar. Hyperbolic programs, and their derivative relaxations. Found. Comput. Math. 6(1):59-79, 2006.  MR 2198215 |  Zbl 1130.90363
[50] F. Riesz, B. Sz.-Nagy. Leçons d’analyse fonctionnelle. 3ème édition. Gauthier-Villars, Paris, Akadémiai Kiadó, Budapest, 1955.  MR 68139 |  Zbl 0122.11205
[51] R. T. Rockafellar. Convex analysis. Princeton Univ. Press, Princeton, 1970.  Zbl 0932.90001
[52] T. Roubíček. Relaxation in optimization theory and variational calculus. Walter De Gruyter, Berlin, 1997.  MR 1458067 |  Zbl 0880.49002
[53] H. Royden, P. Fitzpatrick. Real analysis. 4th edition. Prentice Hall, Boston, 2010.  Zbl 1191.26002
[54] J. E. Rubio. Control and optimization. The linear treatment of nonlinear problems. Manchester Univ. Press, Manchester, UK, 1986.  MR 832189 |  Zbl 1095.49500
[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.  MR 2735935 |  Zbl pre05868720
[56] C. Scheiderer. Semidefinite representation for convex hulls of real algebraic curves. arXiv:1208.3865, Aug. 2012.
[57] M. J. Todd. Semidefinite optimization. Acta Numerica 10:515-560, 2001.  MR 2009698 |  Zbl 1105.65334
[58] L. Vandenberghe, S. Boyd. Semidefinite programming. SIAM Review 38(1):49-95, 1996.  MR 1379041 |  Zbl 0845.65023
[59] C. Villani. Topics in optimal transportation. Amer. Math. Society, Providence, 2003.  MR 1964483 |  Zbl 1106.90001
[60] J. Warga. Optimal control of differential and functional equations. Academic Press, New York, 1972.  MR 372708 |  Zbl 0253.49001
[61] L. C. Young. Lectures on the calculus of variations and optimal control theory, W. B. Saunders, Philadelphia, 1969.  MR 259704 |  Zbl 0177.37801
Copyright Cellule MathDoc 2017 | Crédit | Plan du site