Polynomial optimization with applications to stability analysis and control - Alternatives to sum of squares

Reza  Kamyar; Matthew M.  Peet

doi:10.3934/dcdsb.2015.20.2383

Article Contents

2015, Volume 20, Issue 8: 2383-2417. Doi: 10.3934/dcdsb.2015.20.2383

This issue Previous Article Advances in computational Lyapunov analysis using sum-of-squares programming Next Article Efficient computation of Lyapunov functions for Morse decompositions

Polynomial optimization with applications to stability analysis and control - Alternatives to sum of squares

Reza Kamyar^1, and
Matthew M. Peet^2,

1.
School of Matter, Transport and Energy, Arizona State University, 650 E. Tyler Mall - GWC 531, Tempe, 85281
2.
School of Matter, Transport and Energy, Arizona State University, 501 Tyler Mall - ECG 301, Tempe, 85281

Received: May 31, 2014

Revised: November 30, 2014

Published: September 2015

Abstract Related Papers Cited by

Abstract

In this paper, we explore the merits of various algorithms for solving polynomial optimization and optimization of polynomials, focusing on alternatives to sum of squares programming. While we refer to advantages and disadvantages of Quantifier Elimination, Reformulation Linear Techniques, Blossoming and Groebner basis methods, our main focus is on algorithms defined by Polya's theorem, Bernstein's theorem and Handelman's theorem. We first formulate polynomial optimization problems as verifying the feasibility of semi-algebraic sets. Then, we discuss how Polya's algorithm, Bernstein's algorithm and Handelman's algorithm reduce the intractable problem of feasibility of semi-algebraic sets to linear and/or semi-definite programming. We apply these algorithms to different problems in robust stability analysis and stability of nonlinear dynamical systems. As one contribution of this paper, we apply Polya's algorithm to the problem of $H_\infty$ control of systems with parametric uncertainty. Numerical examples are provided to compare the accuracy of these algorithms with other polynomial optimization algorithms in the literature.

Keywords:

Mathematics Subject Classification: Primary: 93D05, 93D09; Secondary: 90C22.

Citation:

Related Papers

Cited by

References

[1]	W. Adams and P. Loustaunau, An Introduction to Groebner Bases, American Mathematical Society, 1994.
[2]	F. Alizadeh, J. Haeberly and M. Overton, Primal-dual interior-point methods for semidefinite programming: Convergence rates, stability and numerical results, SIAM Journal of Optimization, 8 (1998), 746-768.doi: 10.1137/S1052623496304700.
[3]	E. Artin, Über die zerlegung definiter funktionen in quadra, Quadrate, Abh. Math. Sem. Univ. Hamburg, 5 (1927), 100-115.doi: 10.1007/BF02952513.
[4]	M. Ben Sassi and A. Girard, Computation of polytopic invariants for polynomial dynamical systems using linear programming, Automatica, 48 (2012), 3114-3121.doi: 10.1016/j.automatica.2012.08.014.
[5]	M. A. B. Sassi, R. Testylier, T. Dang and A. Girard, Reachability analysis of polynomial systems using linear programming relaxations, Springer: Automated Technology for Verification and Analysis, (2012), 137-151.doi: 10.1007/978-3-642-33386-6_12.
[6]	S. Bernstein, Sur la repr sentation des polynomes positif, Soobshch. Har'k. Mat. Obshch., 2 (1915), 227-228.
[7]	G. Blekherman, P. Parrilo and R. Thomas, Semidefinite Optimization and Convex Algebraic Geometry, MOS-SIAM Series on Optimization, {SIAM}, Philadelphia, 2013.doi: 10.1137/1.9781611972290.
[8]	P. Bliman, An existence result for polynomial solutions of parameter-dependent LMIs, Systems and Control Letters, 51 (2004), 165-169.doi: 10.1016/j.sysconle.2003.08.001.
[9]	P. Bliman, R. Oliveira, V. Montagner and P. Peres, Existence of Homogeneous Polynomial Solutions for Parameter-Dependent Linear Matrix Inequalities with Parameters in the Simplex, IEEE Conference on Decision and Controls, (2006), 1486-1491.doi: 10.1109/CDC.2006.377429.
[10]	P. Bliman, A convex approach to robust stability for linear systems with uncertain scalar parameters, SIAM journal on Control and Optimization, 42 (2004), 2016-2042.doi: 10.1137/S0363012901398691.
[11]	L. Blum, F. Cucker, M. Shub and S. Smale, Complexity and Real Computation, Springer-Verlag, New York, 1998.
[12]	F. Boudaoud, F. Caruso and M Roy, Certificates of Positivity in the Bernstein Basis, Discrete and Computational Geometry, 39 (2008), 639-655.doi: 10.1007/s00454-007-9042-x.
[13]	C. Brown, QEPCAD B: A program for computing with semi-algebraic sets using CADs, ACM SIGSAM Bulletin, 37 (2003), 97-108.doi: 10.1145/968708.968710.
[14]	M. Castle, V. Powers and B. Reznick, Polya's theorem with zeros, Journal of Symbolic Computation, 46 (2011), 1039-1048.doi: 10.1016/j.jsc.2011.05.006.
[15]	Y. Chang and B. Wah, Polynomial programming using groebner bases, IEEE Computer Software and Applications Conference, 3 (1994), 236-241.doi: 10.1109/CMPSAC.1994.342798.
[16]	G. Chesi, Establishing stability and instability of matrix hypercubes, System and Control Letters, 54 (2005), 381-388.doi: 10.1016/j.sysconle.2004.08.016.
[17]	G. Chesi, A. Garulli, A. Tesi and A. Vicino, Polynomially parameter-dependent Lyapunov functions for robust stability of polytopic systems: An LMI approach, IEEE Transactions on Automatic Control, 50 (2005), 365-370.doi: 10.1109/TAC.2005.843848.
[18]	G. Chesi, A. Garulli, A. Tesi and A. Vicino, LMI-based computation of optimal quadratic Lyapunov functions for odd polynomial systems, International Journal of Robust and Nonlinear Control, 15 (2005), 35-49.doi: 10.1002/rnc.967.
[19]	G. Collins and H. Hoon, Partial cylindrical algebraic decomposition for quantifier elimination, Journal of Symbolic Computation, 12 (1991), 299-328.doi: 10.1016/S0747-7171(08)80152-6.
[20]	J. de Loera and F. Santos, An effective version of Polya's theorem on positive definite forms, Journal of Pure and Applied Algebra, 108 (1996), 231-240.doi: 10.1016/0022-4049(95)00042-9.
[21]	C. Delzell, Impossibility of extending Polya's theorem to forms with arbitrary real exponents, Journal of Pure and Applied Algebra, 212 (2008), 2612-2622.doi: 10.1016/j.jpaa.2008.04.006.
[22]	P. Dickinson and J. Pohv, On an extension of Polya's Positivstellensatz, Journal of Global Optimization, 61 (2015), 515-625.doi: 10.1007/s10898-014-0196-9.
[23]	A. Dolzmann and T. Sturm, Redlog: Computer algebra meets computer logic, ACM SIGSAM Bulletin, 31 (1997), 2-9.doi: 10.1145/261320.261324.
[24]	P. Gahinet, P. Apkarian and M. Chilali, Affine parameter-dependent Lyapunov functions and real parametric uncertainty, IEEE Transactions on Automatic Control, 41 (1996), 436-442doi: 10.1109/9.486646.
[25]	P. Gahinet, P. Apkarian, A linear matrix inequality approach to H infinity control, International Journal of Robust and Nonlinear Control, 4 (1994), 421-448.doi: 10.1002/rnc.4590040403.
[26]	P. Giesl and S. Hafstein, Revised CPA method to compute Lyapunov functions for nonlinear systems, Journal of Mathematical Analysis and Applications, 410 (2014), 292-306.doi: 10.1016/j.jmaa.2013.08.014.
[27]	P. Giesl and S. Hafstein, Existence of piecewise linear Lyapunov functions in arbitary dimensions, Discrete and Continuous Dynamical Systems, 32 (2012), 3539-3565.doi: 10.3934/dcds.2012.32.3539.
[28]	W. Habicht, Uber die Zerlegung strikte definiter Formen in Quadrate, Commentarii Mathematici Helvetici, 12 (1939), 317-322.doi: 10.1007/BF01620655.
[29]	D. Handelman, Representing polynomials by positive linear functions on compact convex polyhedra, Pacific Journal of Mathematics, 132 (1988), 35-62.doi: 10.2140/pjm.1988.132.35.
[30]	G. Hardy, J. Littlewood and G. Polya, Inequalities, Cambridge University Press, 1934.
[31]	C. Helmberg, F. Rendl, R. J. Vanderbei and H. Wolkowicz, An interior-point method for semidefinite programming, SIAM Journal of Optimization, 6 (1996), 342-361.doi: 10.1137/0806020.
[32]	D. Hilbert, Uber die Darstellung definiter Formen als Summe von Formen quadratens, Math. Ann., 32 (1888), 342-350.doi: 10.1007/BF01443605.
[33]	D. Hilbert, Uber ternare definite Formen, Acta Math., 17 (1893), 169-197.doi: 10.1007/BF02391990.
[34]	R. Kamyar, M. Peet and Y. Peet, Solving large-scale robust stability problems by exploiting the parallel structure of Polya's theorem, IEEE Transactions on Automatic Control, 58 (2013), 1931-1947.doi: 10.1109/TAC.2013.2253253.
[35]	R. Kamyar and M. Peet, Decentralized computation for robust stability of large-scale systems with parameters on the hypercube, in IEEE 51st Conference on Decision and Control, IEEE, 2012, 6259-6264.doi: 10.1109/CDC.2012.6425907.
[36]	R. Kamyar and M. Peet, Decentralized polya's algorithm for stability analysis of large-scale nonlinear systems, in IEEE Conference on Decision and Control, IEEE, 2013, 5858-5863.doi: 10.1109/CDC.2013.6760813.
[37]	R. Kamyar, C. Murti and M. Peet, Constructing piecewise-polynomial Lyapunov functions on convex polytopes using Handelman's basis, in IEEE Conference on Decision and Controls, IEEE, 2014.doi: 10.1109/CDC.2014.7040246.
[38]	R. Kamyar and M. Peet, Decentralized computation for robust stability analysis of large state-space systems using Polya's theorem, in American Control Conference (ACC), 2012, IEEE, 2012, 5948-5954.doi: 10.1109/ACC.2012.6315268.
[39]	H. Khalil, Nonlinear Systems, Third edition, Prentice Hall, New Jersey, 2002.
[40]	J. Lasserre, Global optimization with polynomials and the problem of moments, SIAM Journal on Optimization, 11 (2001), 796-817.doi: 10.1137/S1052623400366802.
[41]	M. Laurent, Sums of squares, moment matrices and optimization over polynomials, in Emerging Applications of Algebraic Geometry, Vol. 11, Springer, New York, 2009, 157-270.doi: 10.1007/978-0-387-09686-5_7.
[42]	R. Leroy, Convergence under subdivision and complexity of polynomial minimization in the simplicial bernstein basis, Reliable Computing, 17 (2012), 11-21.
[43]	R. Monteiro, Primal-dual path-following algorithms for semidefinite programming, SIAM Journal of Optimization, 7 (1997), 663-678.doi: 10.1137/S1052623495293056.
[44]	T. S. Motzkin, The arithmetic-geometric inequality, in Inequalities: Proceedings of Symposium Wright-Patterson Air Force Base, Ohio, 1967, 205-224.
[45]	R. Oliveira, P. Bliman and P. Peres, Robust LMIs with parameters in multi-simplex: Existence of solutions and applications, in IEEE 47th Conference on Decision and Control, IEEE, 2008, 2226-2231.doi: 10.1109/CDC.2008.4739192.
[46]	R. Oliveira and P. Peres, Parameter-dependent LMIs in robust analysis: Characterization of homogeneous polynomially parameter-dependent solutions via LMI relaxations, IEEE Transactions on Automatic Control, 52 (2007), 1334-1340.doi: 10.1109/TAC.2007.900848.
[47]	R. Oliveira, P. Peres, Stability of polytopes of matrices via affine parameter-dependent Lyapunov functions: Asymptotically exact LMI conditions, Linear Algebra and its Applications, 405 (2005), 209-228.doi: 10.1016/j.laa.2005.03.019.
[48]	A. Papachristodoulou, J. Anderson, G. Valmorbida, S. Prajna, P. Seiler and P. A. Parrilo, SOSTOOLS: Sum of squares optimization toolbox for MATLAB, preprint, arXiv:1310.4716, 2013.
[49]	A. Papachristodoulou, M. Peet and S. Lall, Analysis of polynomial systems with time delays via the sum of squares decomposition, IEEE Transactions on Automatic Control, 54 (2009), 1058-1064.doi: 10.1109/TAC.2009.2017168.
[50]	P. Parrilo, Structured Semidefinite Programs and Semialgebraic Geometry Methods in Robustness and Optimization, Ph.D thesis, California Institute of Technology, 2000.
[51]	M. Peet and A. Papachristodoulou, A converse sum of squares Lyapunov result with a degree bound, IEEE Transactions on Automatic Control, 57 (2012), 2281-2293.doi: 10.1109/TAC.2012.2190163.
[52]	M. Peet, A. Papachristodoulou and S. Lall, Positive forms and stability of linear time-delay systems, SIAM Journal on Control and Optimization, 47 (2009), 3237-3258.
[53]	M. Peet and Y. Peet, A parallel-computing solution for optimization of polynomials, American Control Conference, (2010), 4851-4856.doi: 10.1109/ACC.2010.5530905.
[54]	V. Powers and B. Reznick, A Quantitative Polya's Theorem with Corner Zeros, ACM International Symposium on Symbolic and Algebraic Computation, 2006.
[55]	V. Powers and B. Reznick, Polynomials that are positive on an interval, Transactions of the American Mathematical Society, 352 (2000), 4677-4692.doi: 10.1090/S0002-9947-00-02595-2.
[56]	V. Powers and B. Reznick, A new bound for Polya's Theorem with applications to polynomials positive on polyhedra, Journal of Pure and Applied Algebra, 164 (2001), 221-229.doi: 10.1016/S0022-4049(00)00155-9.
[57]	A. Prestel and C. Delzell, Positive Polynomials: From Hilbert's 17th Problem to Real Algebra, Springer, New York, 2004.
[58]	M. Putinar, Positive polynomials on compact semi-algebraic sets, Indiana University Mathematics Journal, 42 (1993), 969-984.doi: 10.1512/iumj.1993.42.42045.
[59]	D. Ramos and P. Peres, An LMI Condition for the Robust Stability of Uncertain Continuous-Time Linear Systems, IEEE Transactions on Automatic Control, 47 (2002), 675-678.doi: 10.1109/9.995048.
[60]	L. Ramshaw, A Connect-the-dots Approach to Splines, Digital Systems Research Center, 1987.
[61]	B. Reznick, Some concrete aspects of Hilbert's 17th problem, Contemporary Mathematics, 253 (2000), 251-272.
[62]	B. Reznick, Uniform denominators in Hilbert's seventeenth problem, Mathematische Zeitschrift, 220 (1995), 75-97.doi: 10.1007/BF02572604.
[63]	B. Reznick, On the absence of uniform denominators in Hilbert's 17th problem, Proceedings of the American Mathematical Society, 133 (2005), 2829-2834.doi: 10.1090/S0002-9939-05-07879-2.
[64]	S. Sankaranarayanan, X. Chen and E. Ábrahám, Lyapunov Function Synthesis using Handelman Representations, The 9th IFAC Symposium on Nonlinear Control Systems, 2013.doi: 10.3182/20130904-3-FR-2041.00198.
[65]	C. Scheiderer, Positivity and sums of squares: A guide to recent results, in Emerging Applications of Algebraic Geometry, Springer, New York, 2009, 271-324.doi: 10.1007/978-0-387-09686-5_8.
[66]	K. Schmudgen, The K-moment problem for compact semi-algebraic sets, Mathematische Annalen, 289 (1991), 203-206.doi: 10.1007/BF01446568.
[67]	M. Schweighofer, Certificates for nonnegativity of polynomials with zeros on compact semialgebraic sets, Manuscripta Mathematica, 117 (2005), 407-428.doi: 10.1007/s00229-005-0568-z.
[68]	H. Sherali and W. Adams, A hierarchy of relaxations between the continuous and convex hull representations for zero-one programming problems, SIAM Journal on Discrete Mathematics, 3 (1990), 411-430.doi: 10.1137/0403036.
[69]	H. Sherali and L. Liberti, Reformulation-linearization technique for global optimization, in Encyclopedia of Optimization, Springer, USA, 2009, 3263-3268.doi: 10.1007/978-0-387-74759-0_559.
[70]	H. Sherali and C. Tuncbilek, A global optimization algorithm for polynomial programming problems using a reformulation-linearization technique, Journal of Global Optimization, 2 (1992), 101-112.doi: 10.1007/BF00121304.
[71]	H. Sherali and C. Tuncbilek, New reformulation- linearization technique based relaxations for univariate and multivariate polynomial programming problems, Operations Research Letters, 21 (1997), 1-9.doi: 10.1016/S0167-6377(97)00013-8.
[72]	G. Stengle, A Nullstellensatz and a Positivstellensatz in semialgebraic geometry, Mathematische Annalen, 207 (1974), 87-97.doi: 10.1007/BF01362149.
[73]	J. Sturm, Using SeDuMi 1.02, a MATLAB toolbox for optimization over symmetric cones, Optimization Methods and Software, 11 (1999), 625-653.doi: 10.1080/10556789908805766.
[74]	A. Tarski, A decision method for elementary algebra and geometry, inQuantifier Elimination and Cylindrical Algebraic Decomposition, Texts and Monographs in Symbolic Computation, 1998, 24-84.doi: 10.1007/978-3-7091-9459-1_3.
[75]	R. Tutuncu, K. Toh and M. Todd, Solving semidefinite-quadratic-linear programs using SDPT3, Mathematical Programming, Mathematical Programming Series B, 95 (2003), 189-217.doi: 10.1007/s10107-002-0347-5.
[76]	M. Yamashita, et al., A High-Performance Software Package for Semidefinite Programs: SDPA 7, Tech. rep. B-460, Dep. of Mathematical and Computing Sciences, Tokyo Inst. of Tech., 2010.