Optimization on linear matrix inequalities for polynomial systems control

Didier Henrion[1]

  • [1] LAAS-CNRS, Univ. Toulouse, France Fac. Elec. Engr., Czech Tech. Univ. Prague, Czech Rep.

Les cours du CIRM (2013)

  • Volume: 3, Issue: 1, page 1-44
  • ISSN: 2108-7164

Abstract

top
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.DisclaimerThese 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.

How to cite

top

Henrion, Didier. "Optimization on linear matrix inequalities for polynomial systems control." Les cours du CIRM 3.1 (2013): 1-44. <http://eudml.org/doc/275418>.

@article{Henrion2013,
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.DisclaimerThese 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.},
affiliation = {LAAS-CNRS, Univ. Toulouse, France Fac. Elec. Engr., Czech Tech. Univ. Prague, Czech Rep.},
author = {Henrion, Didier},
journal = {Les cours du CIRM},
language = {eng},
number = {1},
pages = {1-44},
publisher = {CIRM},
title = {Optimization on linear matrix inequalities for polynomial systems control},
url = {http://eudml.org/doc/275418},
volume = {3},
year = {2013},
}

TY - JOUR
AU - Henrion, Didier
TI - Optimization on linear matrix inequalities for polynomial systems control
JO - Les cours du CIRM
PY - 2013
PB - CIRM
VL - 3
IS - 1
SP - 1
EP - 44
AB - 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.DisclaimerThese 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.
LA - eng
UR - http://eudml.org/doc/275418
ER -

References

top
  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. Zbl1090.35002MR2401600
  2. J. P. Aubin, H. Frankowska. Set-valued analysis. Springer-Verlag, Berlin, 1990. Zbl0713.49021MR1048347
  3. A. Ben-Tal, A. Nemirovski. Lectures on modern convex optimization. SIAM, Philadelphia, 2001. Zbl0986.90032MR1857264
  4. G. Blekerman, P. A. Parrilo, R. R. Thomas (Editors). Semidefinite optimization and convex algebraic geometry. SIAM, Philadelphia, 2013. Zbl1260.90006
  5. S. Boyd, L. El Ghaoui, E. Feron, V. Balakrishnan. Linear matrix inequalities in system and control theory. SIAM, Philadelphia, 1994. Zbl0816.93004MR1284712
  6. S. Boyd, L. Vandenberghe. Convex optimization. Cambridge Univ. Press, Cambridge, UK, 2005. Zbl1058.90049MR2061575
  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. Zbl0005.20703MR1555355
  8. D. A. Cox, J. B. Little, D. O’Shea. Ideals, varieties, and algorithms. 3rd edition, Springer-Verlag, New York, 2007. Zbl0756.13017MR2290010
  9. R. Curto, L. Fialkow. Truncated K-moment problems in several variables. J. Operator Theory, 54:189-226, 2005. Zbl1119.47304MR2168867
  10. B. Dacorogna. Direct methods in the calculus of variations. 2nd edition. Springer-Verlag, Berlin, 2007. Zbl0703.49001MR2361288
  11. H. O. Fattorini. Infinite dimensional optimization and control theory. Cambridge Univ. Press, Cambridge, UK, 1999. Zbl1200.49001MR1669395
  12. A. F. Filippov. Classical solutions of differential inclusions with multivalued right-hand side. SIAM J. Control 5(4):609-621, 1967. MR220995
  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. Zbl1201.49040MR2556353
  14. S. Galeani, D. Henrion, A. Jacquemard, L. Zaccarian. Design of Marx generators as a structured eigenvalue assignment. arXiv:1301.7741, Jan. 2013. Zbl1302.93119
  15. R. V. Gamkrelidze. Principles of optimal control theory. Plenum Press, New York, 1978. English translation of a Russian original of 1975. Zbl0401.49001MR686793
  16. J. W. Helton, V. Vinnikov. Linear matrix inequality representation of sets. Comm. Pure Appl. Math. 60(5):654-674, 2007. Zbl1116.15016MR2292953
  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. Zbl1190.14058MR2515796
  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. Zbl1119.93301MR2123528
  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. Zbl1036.60003MR1974383
  22. J.-B. Hiriart-Urruty, C. Lemaréchal. Fundamentals of convex analysis. Springer-Verlag, Berlin, 2001. Zbl0998.49001MR1865628
  23. A. N. Kolmogorov, S. V. Fomin. Introductory real analysis. Dover Publications, New York, 1970. English translation of a Russian original of 1968. Zbl0213.07305MR267052
  24. K. Kowalski, W. H. Steeb. Dynamical systems and Carleman linearization. World Scientific, Singapore, 1991. Zbl0753.34003MR1178493
  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. Zbl0016.08604MR1503326
  26. A. Lasota, M. C. Mackey. Probabilistic properties of deterministic systems. Cambridge Univ. Press, Cambridge, UK, 1985. Zbl0606.58002MR832868
  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. Zbl1016.90031MR1806434
  28. J. B. Lasserre. Global optimization with polynomials and the problem of moments. SIAM J. Optim. 11(3):796–817, 2001. Zbl1010.90061MR1814045
  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. Zbl1188.90193MR2421324
  30. J. B. Lasserre. Moments, positive polynomials and their applications. Imperial College Press, London, UK, 2009. Zbl1211.90007MR2589247
  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. Zbl1163.13021MR2500468
  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. Zbl1194.90066
  34. D. G. Luenberger. Optimization by vector space methods. John Wiley and Sons, New York, 1969. Zbl0176.12701MR238472
  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. Zbl1135.90379MR2334199
  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. Zbl0089.29502MR121520
  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. Zbl0958.90090MR1748764
  38. Y. Nesterov, A. Nemirovski. Interior-point polynomial algorithms in convex programming. SIAM, Philaldelphia, 1994. Zbl0824.90112MR1258086
  39. J. Nie. Optimality conditions and finite convergence of Lasserre’s hierarchy. arXiv:1206.0319, June 2012. Zbl1300.65041
  40. J. Nie, K. Ranestad, B. Sturmfels. The algebraic degree of semidefinite programming. Math. Prog. Ser. A 122(2):379-405, 2010. Zbl1184.90119MR2546336
  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. Zbl0879.49017MR1452107
  43. H. Poincaré. Méthodes nouvelles de la mécanique céleste. Tome III. Gauthier-Villars, Paris, 1899. Zbl30.0834.08
  44. H. Poincaré. L’avenir des mathématiques. Revue générale des sciences pures et appliquées, 19:930-939, 1908. Zbl39.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. Zbl1147.93023MR2338436
  46. M. Putinar. Positive polynomials on compact semi-algebraic sets. Indiana Univ. Math. J. 42:969-984, 1993. Zbl0796.12002MR1254128
  47. S. T. Rachev, L. Rüschendorf. Mass transportation problems. Volume I: theory. Springer-Verlag, Berlin, 1998. Zbl0990.60500MR1619170
  48. A. Rantzer. A dual to Lyapunov’s stability theorem. Syst. Control Letters 42:161-168, 2001. Zbl0974.93058MR2007046
  49. J. Renegar. Hyperbolic programs, and their derivative relaxations. Found. Comput. Math. 6(1):59-79, 2006. Zbl1130.90363MR2198215
  50. F. Riesz, B. Sz.-Nagy. Leçons d’analyse fonctionnelle. 3ème édition. Gauthier-Villars, Paris, Akadémiai Kiadó, Budapest, 1955. Zbl0122.11205MR68139
  51. R. T. Rockafellar. Convex analysis. Princeton Univ. Press, Princeton, 1970. Zbl0932.90001
  52. T. Roubíček. Relaxation in optimization theory and variational calculus. Walter De Gruyter, Berlin, 1997. Zbl0880.49002MR1458067
  53. H. Royden, P. Fitzpatrick. Real analysis. 4th edition. Prentice Hall, Boston, 2010. Zbl1191.26002
  54. J. E. Rubio. Control and optimization. The linear treatment of nonlinear problems. Manchester Univ. Press, Manchester, UK, 1986. Zbl1095.49500MR832189
  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. Zbl1279.90127MR2735935
  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. Zbl1105.65334MR2009698
  58. L. Vandenberghe, S. Boyd. Semidefinite programming. SIAM Review 38(1):49-95, 1996. Zbl0845.65023MR1379041
  59. C. Villani. Topics in optimal transportation. Amer. Math. Society, Providence, 2003. Zbl1106.90001MR1964483
  60. J. Warga. Optimal control of differential and functional equations. Academic Press, New York, 1972. Zbl0253.49001MR372708
  61. L. C. Young. Lectures on the calculus of variations and optimal control theory, W. B. Saunders, Philadelphia, 1969. Zbl0177.37801MR259704

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.