October  2015, 20(8): 2383-2417. doi: 10.3934/dcdsb.2015.20.2383

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

1. 

School of Matter, Transport and Energy, Arizona State University, 650 E. Tyler Mall - GWC 531, Tempe, 85281, United States

2. 

School of Matter, Transport and Energy, Arizona State University, 501 Tyler Mall - ECG 301, Tempe, 85281, United States

Received  June 2014 Revised  December 2014 Published  August 2015

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.
Citation: Reza Kamyar, Matthew M. Peet. Polynomial optimization with applications to stability analysis and control - Alternatives to sum of squares. Discrete & Continuous Dynamical Systems - B, 2015, 20 (8) : 2383-2417. doi: 10.3934/dcdsb.2015.20.2383
References:
[1]

W. Adams and P. Loustaunau, An Introduction to Groebner Bases,, American Mathematical Society, (1994). Google Scholar

[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. doi: 10.1137/S1052623496304700. Google Scholar

[3]

E. Artin, Über die zerlegung definiter funktionen in quadra,, Quadrate, 5 (1927), 100. doi: 10.1007/BF02952513. Google Scholar

[4]

M. Ben Sassi and A. Girard, Computation of polytopic invariants for polynomial dynamical systems using linear programming,, Automatica, 48 (2012), 3114. doi: 10.1016/j.automatica.2012.08.014. Google Scholar

[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. doi: 10.1007/978-3-642-33386-6_12. Google Scholar

[6]

S. Bernstein, Sur la repr sentation des polynomes positif,, Soobshch. Har'k. Mat. Obshch., 2 (1915), 227. Google Scholar

[7]

G. Blekherman, P. Parrilo and R. Thomas, Semidefinite Optimization and Convex Algebraic Geometry,, MOS-SIAM Series on Optimization, (2013). doi: 10.1137/1.9781611972290. Google Scholar

[8]

P. Bliman, An existence result for polynomial solutions of parameter-dependent LMIs,, Systems and Control Letters, 51 (2004), 165. doi: 10.1016/j.sysconle.2003.08.001. Google Scholar

[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. doi: 10.1109/CDC.2006.377429. Google Scholar

[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. doi: 10.1137/S0363012901398691. Google Scholar

[11]

L. Blum, F. Cucker, M. Shub and S. Smale, Complexity and Real Computation,, Springer-Verlag, (1998). Google Scholar

[12]

F. Boudaoud, F. Caruso and M Roy, Certificates of Positivity in the Bernstein Basis,, Discrete and Computational Geometry, 39 (2008), 639. doi: 10.1007/s00454-007-9042-x. Google Scholar

[13]

C. Brown, QEPCAD B: A program for computing with semi-algebraic sets using CADs,, ACM SIGSAM Bulletin, 37 (2003), 97. doi: 10.1145/968708.968710. Google Scholar

[14]

M. Castle, V. Powers and B. Reznick, Polya's theorem with zeros,, Journal of Symbolic Computation, 46 (2011), 1039. doi: 10.1016/j.jsc.2011.05.006. Google Scholar

[15]

Y. Chang and B. Wah, Polynomial programming using groebner bases,, IEEE Computer Software and Applications Conference, 3 (1994), 236. doi: 10.1109/CMPSAC.1994.342798. Google Scholar

[16]

G. Chesi, Establishing stability and instability of matrix hypercubes,, System and Control Letters, 54 (2005), 381. doi: 10.1016/j.sysconle.2004.08.016. Google Scholar

[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. doi: 10.1109/TAC.2005.843848. Google Scholar

[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. doi: 10.1002/rnc.967. Google Scholar

[19]

G. Collins and H. Hoon, Partial cylindrical algebraic decomposition for quantifier elimination,, Journal of Symbolic Computation, 12 (1991), 299. doi: 10.1016/S0747-7171(08)80152-6. Google Scholar

[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. doi: 10.1016/0022-4049(95)00042-9. Google Scholar

[21]

C. Delzell, Impossibility of extending Polya's theorem to forms with arbitrary real exponents,, Journal of Pure and Applied Algebra, 212 (2008), 2612. doi: 10.1016/j.jpaa.2008.04.006. Google Scholar

[22]

P. Dickinson and J. Pohv, On an extension of Polya's Positivstellensatz,, Journal of Global Optimization, 61 (2015), 515. doi: 10.1007/s10898-014-0196-9. Google Scholar

[23]

A. Dolzmann and T. Sturm, Redlog: Computer algebra meets computer logic,, ACM SIGSAM Bulletin, 31 (1997), 2. doi: 10.1145/261320.261324. Google Scholar

[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. doi: 10.1109/9.486646. Google Scholar

[25]

P. Gahinet, P. Apkarian, A linear matrix inequality approach to H infinity control,, International Journal of Robust and Nonlinear Control, 4 (1994), 421. doi: 10.1002/rnc.4590040403. Google Scholar

[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. doi: 10.1016/j.jmaa.2013.08.014. Google Scholar

[27]

P. Giesl and S. Hafstein, Existence of piecewise linear Lyapunov functions in arbitary dimensions,, Discrete and Continuous Dynamical Systems, 32 (2012), 3539. doi: 10.3934/dcds.2012.32.3539. Google Scholar

[28]

W. Habicht, Uber die Zerlegung strikte definiter Formen in Quadrate,, Commentarii Mathematici Helvetici, 12 (1939), 317. doi: 10.1007/BF01620655. Google Scholar

[29]

D. Handelman, Representing polynomials by positive linear functions on compact convex polyhedra,, Pacific Journal of Mathematics, 132 (1988), 35. doi: 10.2140/pjm.1988.132.35. Google Scholar

[30]

G. Hardy, J. Littlewood and G. Polya, Inequalities,, Cambridge University Press, (1934). Google Scholar

[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. doi: 10.1137/0806020. Google Scholar

[32]

D. Hilbert, Uber die Darstellung definiter Formen als Summe von Formen quadratens,, Math. Ann., 32 (1888), 342. doi: 10.1007/BF01443605. Google Scholar

[33]

D. Hilbert, Uber ternare definite Formen,, Acta Math., 17 (1893), 169. doi: 10.1007/BF02391990. Google Scholar

[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. doi: 10.1109/TAC.2013.2253253. Google Scholar

[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, (2012), 6259. doi: 10.1109/CDC.2012.6425907. Google Scholar

[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, (2013), 5858. doi: 10.1109/CDC.2013.6760813. Google Scholar

[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, (2014). doi: 10.1109/CDC.2014.7040246. Google Scholar

[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), 5948. doi: 10.1109/ACC.2012.6315268. Google Scholar

[39]

H. Khalil, Nonlinear Systems,, Third edition, (2002). Google Scholar

[40]

J. Lasserre, Global optimization with polynomials and the problem of moments,, SIAM Journal on Optimization, 11 (2001), 796. doi: 10.1137/S1052623400366802. Google Scholar

[41]

M. Laurent, Sums of squares, moment matrices and optimization over polynomials,, in Emerging Applications of Algebraic Geometry, (2009), 157. doi: 10.1007/978-0-387-09686-5_7. Google Scholar

[42]

R. Leroy, Convergence under subdivision and complexity of polynomial minimization in the simplicial bernstein basis,, Reliable Computing, 17 (2012), 11. Google Scholar

[43]

R. Monteiro, Primal-dual path-following algorithms for semidefinite programming,, SIAM Journal of Optimization, 7 (1997), 663. doi: 10.1137/S1052623495293056. Google Scholar

[44]

T. S. Motzkin, The arithmetic-geometric inequality,, in Inequalities: Proceedings of Symposium Wright-Patterson Air Force Base, (1967), 205. Google Scholar

[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, (2008), 2226. doi: 10.1109/CDC.2008.4739192. Google Scholar

[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. doi: 10.1109/TAC.2007.900848. Google Scholar

[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. doi: 10.1016/j.laa.2005.03.019. Google Scholar

[48]

A. Papachristodoulou, J. Anderson, G. Valmorbida, S. Prajna, P. Seiler and P. A. Parrilo, SOSTOOLS: Sum of squares optimization toolbox for MATLAB,, preprint, (2013). Google Scholar

[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. doi: 10.1109/TAC.2009.2017168. Google Scholar

[50]

P. Parrilo, Structured Semidefinite Programs and Semialgebraic Geometry Methods in Robustness and Optimization,, Ph.D thesis, (2000). Google Scholar

[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. doi: 10.1109/TAC.2012.2190163. Google Scholar

[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. Google Scholar

[53]

M. Peet and Y. Peet, A parallel-computing solution for optimization of polynomials,, American Control Conference, (2010), 4851. doi: 10.1109/ACC.2010.5530905. Google Scholar

[54]

V. Powers and B. Reznick, A Quantitative Polya's Theorem with Corner Zeros,, ACM International Symposium on Symbolic and Algebraic Computation, (2006). Google Scholar

[55]

V. Powers and B. Reznick, Polynomials that are positive on an interval,, Transactions of the American Mathematical Society, 352 (2000), 4677. doi: 10.1090/S0002-9947-00-02595-2. Google Scholar

[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. doi: 10.1016/S0022-4049(00)00155-9. Google Scholar

[57]

A. Prestel and C. Delzell, Positive Polynomials: From Hilbert's 17th Problem to Real Algebra,, Springer, (2004). Google Scholar

[58]

M. Putinar, Positive polynomials on compact semi-algebraic sets,, Indiana University Mathematics Journal, 42 (1993), 969. doi: 10.1512/iumj.1993.42.42045. Google Scholar

[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. doi: 10.1109/9.995048. Google Scholar

[60]

L. Ramshaw, A Connect-the-dots Approach to Splines,, Digital Systems Research Center, (1987). Google Scholar

[61]

B. Reznick, Some concrete aspects of Hilbert's 17th problem,, Contemporary Mathematics, 253 (2000), 251. Google Scholar

[62]

B. Reznick, Uniform denominators in Hilbert's seventeenth problem,, Mathematische Zeitschrift, 220 (1995), 75. doi: 10.1007/BF02572604. Google Scholar

[63]

B. Reznick, On the absence of uniform denominators in Hilbert's 17th problem,, Proceedings of the American Mathematical Society, 133 (2005), 2829. doi: 10.1090/S0002-9939-05-07879-2. Google Scholar

[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. Google Scholar

[65]

C. Scheiderer, Positivity and sums of squares: A guide to recent results,, in Emerging Applications of Algebraic Geometry, (2009), 271. doi: 10.1007/978-0-387-09686-5_8. Google Scholar

[66]

K. Schmudgen, The K-moment problem for compact semi-algebraic sets,, Mathematische Annalen, 289 (1991), 203. doi: 10.1007/BF01446568. Google Scholar

[67]

M. Schweighofer, Certificates for nonnegativity of polynomials with zeros on compact semialgebraic sets,, Manuscripta Mathematica, 117 (2005), 407. doi: 10.1007/s00229-005-0568-z. Google Scholar

[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. doi: 10.1137/0403036. Google Scholar

[69]

H. Sherali and L. Liberti, Reformulation-linearization technique for global optimization,, in Encyclopedia of Optimization, (2009), 3263. doi: 10.1007/978-0-387-74759-0_559. Google Scholar

[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. doi: 10.1007/BF00121304. Google Scholar

[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. doi: 10.1016/S0167-6377(97)00013-8. Google Scholar

[72]

G. Stengle, A Nullstellensatz and a Positivstellensatz in semialgebraic geometry,, Mathematische Annalen, 207 (1974), 87. doi: 10.1007/BF01362149. Google Scholar

[73]

J. Sturm, Using SeDuMi 1.02, a MATLAB toolbox for optimization over symmetric cones,, Optimization Methods and Software, 11 (1999), 625. doi: 10.1080/10556789908805766. Google Scholar

[74]

A. Tarski, A decision method for elementary algebra and geometry,, inQuantifier Elimination and Cylindrical Algebraic Decomposition, (1998), 24. doi: 10.1007/978-3-7091-9459-1_3. Google Scholar

[75]

R. Tutuncu, K. Toh and M. Todd, Solving semidefinite-quadratic-linear programs using SDPT3, Mathematical Programming,, Mathematical Programming Series B, 95 (2003), 189. doi: 10.1007/s10107-002-0347-5. Google Scholar

[76]

M. Yamashita, et al., A High-Performance Software Package for Semidefinite Programs: SDPA 7,, Tech. rep. B-460, (2010). Google Scholar

show all references

References:
[1]

W. Adams and P. Loustaunau, An Introduction to Groebner Bases,, American Mathematical Society, (1994). Google Scholar

[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. doi: 10.1137/S1052623496304700. Google Scholar

[3]

E. Artin, Über die zerlegung definiter funktionen in quadra,, Quadrate, 5 (1927), 100. doi: 10.1007/BF02952513. Google Scholar

[4]

M. Ben Sassi and A. Girard, Computation of polytopic invariants for polynomial dynamical systems using linear programming,, Automatica, 48 (2012), 3114. doi: 10.1016/j.automatica.2012.08.014. Google Scholar

[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. doi: 10.1007/978-3-642-33386-6_12. Google Scholar

[6]

S. Bernstein, Sur la repr sentation des polynomes positif,, Soobshch. Har'k. Mat. Obshch., 2 (1915), 227. Google Scholar

[7]

G. Blekherman, P. Parrilo and R. Thomas, Semidefinite Optimization and Convex Algebraic Geometry,, MOS-SIAM Series on Optimization, (2013). doi: 10.1137/1.9781611972290. Google Scholar

[8]

P. Bliman, An existence result for polynomial solutions of parameter-dependent LMIs,, Systems and Control Letters, 51 (2004), 165. doi: 10.1016/j.sysconle.2003.08.001. Google Scholar

[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. doi: 10.1109/CDC.2006.377429. Google Scholar

[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. doi: 10.1137/S0363012901398691. Google Scholar

[11]

L. Blum, F. Cucker, M. Shub and S. Smale, Complexity and Real Computation,, Springer-Verlag, (1998). Google Scholar

[12]

F. Boudaoud, F. Caruso and M Roy, Certificates of Positivity in the Bernstein Basis,, Discrete and Computational Geometry, 39 (2008), 639. doi: 10.1007/s00454-007-9042-x. Google Scholar

[13]

C. Brown, QEPCAD B: A program for computing with semi-algebraic sets using CADs,, ACM SIGSAM Bulletin, 37 (2003), 97. doi: 10.1145/968708.968710. Google Scholar

[14]

M. Castle, V. Powers and B. Reznick, Polya's theorem with zeros,, Journal of Symbolic Computation, 46 (2011), 1039. doi: 10.1016/j.jsc.2011.05.006. Google Scholar

[15]

Y. Chang and B. Wah, Polynomial programming using groebner bases,, IEEE Computer Software and Applications Conference, 3 (1994), 236. doi: 10.1109/CMPSAC.1994.342798. Google Scholar

[16]

G. Chesi, Establishing stability and instability of matrix hypercubes,, System and Control Letters, 54 (2005), 381. doi: 10.1016/j.sysconle.2004.08.016. Google Scholar

[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. doi: 10.1109/TAC.2005.843848. Google Scholar

[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. doi: 10.1002/rnc.967. Google Scholar

[19]

G. Collins and H. Hoon, Partial cylindrical algebraic decomposition for quantifier elimination,, Journal of Symbolic Computation, 12 (1991), 299. doi: 10.1016/S0747-7171(08)80152-6. Google Scholar

[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. doi: 10.1016/0022-4049(95)00042-9. Google Scholar

[21]

C. Delzell, Impossibility of extending Polya's theorem to forms with arbitrary real exponents,, Journal of Pure and Applied Algebra, 212 (2008), 2612. doi: 10.1016/j.jpaa.2008.04.006. Google Scholar

[22]

P. Dickinson and J. Pohv, On an extension of Polya's Positivstellensatz,, Journal of Global Optimization, 61 (2015), 515. doi: 10.1007/s10898-014-0196-9. Google Scholar

[23]

A. Dolzmann and T. Sturm, Redlog: Computer algebra meets computer logic,, ACM SIGSAM Bulletin, 31 (1997), 2. doi: 10.1145/261320.261324. Google Scholar

[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. doi: 10.1109/9.486646. Google Scholar

[25]

P. Gahinet, P. Apkarian, A linear matrix inequality approach to H infinity control,, International Journal of Robust and Nonlinear Control, 4 (1994), 421. doi: 10.1002/rnc.4590040403. Google Scholar

[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. doi: 10.1016/j.jmaa.2013.08.014. Google Scholar

[27]

P. Giesl and S. Hafstein, Existence of piecewise linear Lyapunov functions in arbitary dimensions,, Discrete and Continuous Dynamical Systems, 32 (2012), 3539. doi: 10.3934/dcds.2012.32.3539. Google Scholar

[28]

W. Habicht, Uber die Zerlegung strikte definiter Formen in Quadrate,, Commentarii Mathematici Helvetici, 12 (1939), 317. doi: 10.1007/BF01620655. Google Scholar

[29]

D. Handelman, Representing polynomials by positive linear functions on compact convex polyhedra,, Pacific Journal of Mathematics, 132 (1988), 35. doi: 10.2140/pjm.1988.132.35. Google Scholar

[30]

G. Hardy, J. Littlewood and G. Polya, Inequalities,, Cambridge University Press, (1934). Google Scholar

[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. doi: 10.1137/0806020. Google Scholar

[32]

D. Hilbert, Uber die Darstellung definiter Formen als Summe von Formen quadratens,, Math. Ann., 32 (1888), 342. doi: 10.1007/BF01443605. Google Scholar

[33]

D. Hilbert, Uber ternare definite Formen,, Acta Math., 17 (1893), 169. doi: 10.1007/BF02391990. Google Scholar

[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. doi: 10.1109/TAC.2013.2253253. Google Scholar

[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, (2012), 6259. doi: 10.1109/CDC.2012.6425907. Google Scholar

[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, (2013), 5858. doi: 10.1109/CDC.2013.6760813. Google Scholar

[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, (2014). doi: 10.1109/CDC.2014.7040246. Google Scholar

[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), 5948. doi: 10.1109/ACC.2012.6315268. Google Scholar

[39]

H. Khalil, Nonlinear Systems,, Third edition, (2002). Google Scholar

[40]

J. Lasserre, Global optimization with polynomials and the problem of moments,, SIAM Journal on Optimization, 11 (2001), 796. doi: 10.1137/S1052623400366802. Google Scholar

[41]

M. Laurent, Sums of squares, moment matrices and optimization over polynomials,, in Emerging Applications of Algebraic Geometry, (2009), 157. doi: 10.1007/978-0-387-09686-5_7. Google Scholar

[42]

R. Leroy, Convergence under subdivision and complexity of polynomial minimization in the simplicial bernstein basis,, Reliable Computing, 17 (2012), 11. Google Scholar

[43]

R. Monteiro, Primal-dual path-following algorithms for semidefinite programming,, SIAM Journal of Optimization, 7 (1997), 663. doi: 10.1137/S1052623495293056. Google Scholar

[44]

T. S. Motzkin, The arithmetic-geometric inequality,, in Inequalities: Proceedings of Symposium Wright-Patterson Air Force Base, (1967), 205. Google Scholar

[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, (2008), 2226. doi: 10.1109/CDC.2008.4739192. Google Scholar

[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. doi: 10.1109/TAC.2007.900848. Google Scholar

[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. doi: 10.1016/j.laa.2005.03.019. Google Scholar

[48]

A. Papachristodoulou, J. Anderson, G. Valmorbida, S. Prajna, P. Seiler and P. A. Parrilo, SOSTOOLS: Sum of squares optimization toolbox for MATLAB,, preprint, (2013). Google Scholar

[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. doi: 10.1109/TAC.2009.2017168. Google Scholar

[50]

P. Parrilo, Structured Semidefinite Programs and Semialgebraic Geometry Methods in Robustness and Optimization,, Ph.D thesis, (2000). Google Scholar

[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. doi: 10.1109/TAC.2012.2190163. Google Scholar

[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. Google Scholar

[53]

M. Peet and Y. Peet, A parallel-computing solution for optimization of polynomials,, American Control Conference, (2010), 4851. doi: 10.1109/ACC.2010.5530905. Google Scholar

[54]

V. Powers and B. Reznick, A Quantitative Polya's Theorem with Corner Zeros,, ACM International Symposium on Symbolic and Algebraic Computation, (2006). Google Scholar

[55]

V. Powers and B. Reznick, Polynomials that are positive on an interval,, Transactions of the American Mathematical Society, 352 (2000), 4677. doi: 10.1090/S0002-9947-00-02595-2. Google Scholar

[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. doi: 10.1016/S0022-4049(00)00155-9. Google Scholar

[57]

A. Prestel and C. Delzell, Positive Polynomials: From Hilbert's 17th Problem to Real Algebra,, Springer, (2004). Google Scholar

[58]

M. Putinar, Positive polynomials on compact semi-algebraic sets,, Indiana University Mathematics Journal, 42 (1993), 969. doi: 10.1512/iumj.1993.42.42045. Google Scholar

[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. doi: 10.1109/9.995048. Google Scholar

[60]

L. Ramshaw, A Connect-the-dots Approach to Splines,, Digital Systems Research Center, (1987). Google Scholar

[61]

B. Reznick, Some concrete aspects of Hilbert's 17th problem,, Contemporary Mathematics, 253 (2000), 251. Google Scholar

[62]

B. Reznick, Uniform denominators in Hilbert's seventeenth problem,, Mathematische Zeitschrift, 220 (1995), 75. doi: 10.1007/BF02572604. Google Scholar

[63]

B. Reznick, On the absence of uniform denominators in Hilbert's 17th problem,, Proceedings of the American Mathematical Society, 133 (2005), 2829. doi: 10.1090/S0002-9939-05-07879-2. Google Scholar

[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. Google Scholar

[65]

C. Scheiderer, Positivity and sums of squares: A guide to recent results,, in Emerging Applications of Algebraic Geometry, (2009), 271. doi: 10.1007/978-0-387-09686-5_8. Google Scholar

[66]

K. Schmudgen, The K-moment problem for compact semi-algebraic sets,, Mathematische Annalen, 289 (1991), 203. doi: 10.1007/BF01446568. Google Scholar

[67]

M. Schweighofer, Certificates for nonnegativity of polynomials with zeros on compact semialgebraic sets,, Manuscripta Mathematica, 117 (2005), 407. doi: 10.1007/s00229-005-0568-z. Google Scholar

[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. doi: 10.1137/0403036. Google Scholar

[69]

H. Sherali and L. Liberti, Reformulation-linearization technique for global optimization,, in Encyclopedia of Optimization, (2009), 3263. doi: 10.1007/978-0-387-74759-0_559. Google Scholar

[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. doi: 10.1007/BF00121304. Google Scholar

[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. doi: 10.1016/S0167-6377(97)00013-8. Google Scholar

[72]

G. Stengle, A Nullstellensatz and a Positivstellensatz in semialgebraic geometry,, Mathematische Annalen, 207 (1974), 87. doi: 10.1007/BF01362149. Google Scholar

[73]

J. Sturm, Using SeDuMi 1.02, a MATLAB toolbox for optimization over symmetric cones,, Optimization Methods and Software, 11 (1999), 625. doi: 10.1080/10556789908805766. Google Scholar

[74]

A. Tarski, A decision method for elementary algebra and geometry,, inQuantifier Elimination and Cylindrical Algebraic Decomposition, (1998), 24. doi: 10.1007/978-3-7091-9459-1_3. Google Scholar

[75]

R. Tutuncu, K. Toh and M. Todd, Solving semidefinite-quadratic-linear programs using SDPT3, Mathematical Programming,, Mathematical Programming Series B, 95 (2003), 189. doi: 10.1007/s10107-002-0347-5. Google Scholar

[76]

M. Yamashita, et al., A High-Performance Software Package for Semidefinite Programs: SDPA 7,, Tech. rep. B-460, (2010). Google Scholar

[1]

Jacques Féjoz. On "Arnold's theorem" on the stability of the solar system. Discrete & Continuous Dynamical Systems - A, 2013, 33 (8) : 3555-3565. doi: 10.3934/dcds.2013.33.3555

[2]

Fatiha Alabau-Boussouira, Piermarco Cannarsa. A constructive proof of Gibson's stability theorem. Discrete & Continuous Dynamical Systems - S, 2013, 6 (3) : 611-617. doi: 10.3934/dcdss.2013.6.611

[3]

Rabah Amir, Igor V. Evstigneev. On Zermelo's theorem. Journal of Dynamics & Games, 2017, 4 (3) : 191-194. doi: 10.3934/jdg.2017011

[4]

John Hubbard, Yulij Ilyashenko. A proof of Kolmogorov's theorem. Discrete & Continuous Dynamical Systems - A, 2004, 10 (1&2) : 367-385. doi: 10.3934/dcds.2004.10.367

[5]

Hahng-Yun Chu, Se-Hyun Ku, Jong-Suh Park. Conley's theorem for dispersive systems. Discrete & Continuous Dynamical Systems - S, 2015, 8 (2) : 313-321. doi: 10.3934/dcdss.2015.8.313

[6]

Sergei Ivanov. On Helly's theorem in geodesic spaces. Electronic Research Announcements, 2014, 21: 109-112. doi: 10.3934/era.2014.21.109

[7]

Sigurdur Freyr Hafstein. A constructive converse Lyapunov theorem on exponential stability. Discrete & Continuous Dynamical Systems - A, 2004, 10 (3) : 657-678. doi: 10.3934/dcds.2004.10.657

[8]

V. Niţicâ. Journé's theorem for $C^{n,\omega}$ regularity. Discrete & Continuous Dynamical Systems - A, 2008, 22 (1&2) : 413-425. doi: 10.3934/dcds.2008.22.413

[9]

Dmitry Kleinbock, Barak Weiss. Dirichlet's theorem on diophantine approximation and homogeneous flows. Journal of Modern Dynamics, 2008, 2 (1) : 43-62. doi: 10.3934/jmd.2008.2.43

[10]

Lena Noethen, Sebastian Walcher. Tikhonov's theorem and quasi-steady state. Discrete & Continuous Dynamical Systems - B, 2011, 16 (3) : 945-961. doi: 10.3934/dcdsb.2011.16.945

[11]

Koray Karabina, Edward Knapp, Alfred Menezes. Generalizations of Verheul's theorem to asymmetric pairings. Advances in Mathematics of Communications, 2013, 7 (1) : 103-111. doi: 10.3934/amc.2013.7.103

[12]

Mateusz Krukowski. Arzelà-Ascoli's theorem in uniform spaces. Discrete & Continuous Dynamical Systems - B, 2018, 23 (1) : 283-294. doi: 10.3934/dcdsb.2018020

[13]

Shalosh B. Ekhad and Doron Zeilberger. Proof of Conway's lost cosmological theorem. Electronic Research Announcements, 1997, 3: 78-82.

[14]

Florian Wagener. A parametrised version of Moser's modifying terms theorem. Discrete & Continuous Dynamical Systems - S, 2010, 3 (4) : 719-768. doi: 10.3934/dcdss.2010.3.719

[15]

Pengyan Wang, Pengcheng Niu. Liouville's theorem for a fractional elliptic system. Discrete & Continuous Dynamical Systems - A, 2019, 39 (3) : 1545-1558. doi: 10.3934/dcds.2019067

[16]

Rentsen Enkhbat, Evgeniya A. Finkelstein, Anton S. Anikin, Alexandr Yu. Gornov. Global optimization reduction of generalized Malfatti's problem. Numerical Algebra, Control & Optimization, 2017, 7 (2) : 211-221. doi: 10.3934/naco.2017015

[17]

Simão P. S. Santos, Natália Martins, Delfim F. M. Torres. Noether's theorem for higher-order variational problems of Herglotz type. Conference Publications, 2015, 2015 (special) : 990-999. doi: 10.3934/proc.2015.990

[18]

Delfim F. M. Torres. Proper extensions of Noether's symmetry theorem for nonsmooth extremals of the calculus of variations. Communications on Pure & Applied Analysis, 2004, 3 (3) : 491-500. doi: 10.3934/cpaa.2004.3.491

[19]

Gastão S. F. Frederico, Delfim F. M. Torres. Noether's symmetry Theorem for variational and optimal control problems with time delay. Numerical Algebra, Control & Optimization, 2012, 2 (3) : 619-630. doi: 10.3934/naco.2012.2.619

[20]

Ben Green, Terence Tao, Tamar Ziegler. An inverse theorem for the Gowers $U^{s+1}[N]$-norm. Electronic Research Announcements, 2011, 18: 69-90. doi: 10.3934/era.2011.18.69

2018 Impact Factor: 1.008

Metrics

  • PDF downloads (19)
  • HTML views (0)
  • Cited by (4)

Other articles
by authors

[Back to Top]