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).

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

[3]

E. Artin, Über die zerlegung definiter funktionen in quadra,, Quadrate, 5 (1927), 100. 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. 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. 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.

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

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

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

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

[11]

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

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

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

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

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

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

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

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

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

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

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

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

[23]

A. Dolzmann and T. Sturm, Redlog: Computer algebra meets computer logic,, ACM SIGSAM Bulletin, 31 (1997), 2. 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. doi: 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. 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. 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. doi: 10.3934/dcds.2012.32.3539.

[28]

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

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

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

[32]

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

[33]

D. Hilbert, Uber ternare definite Formen,, Acta Math., 17 (1893), 169. 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. 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, (2012), 6259. 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, (2013), 5858. 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, (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), 5948. doi: 10.1109/ACC.2012.6315268.

[39]

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

[40]

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

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

[42]

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

[43]

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

[44]

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

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

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

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

[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).

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

[50]

P. Parrilo, Structured Semidefinite Programs and Semialgebraic Geometry Methods in Robustness and Optimization,, Ph.D thesis, (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. 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.

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

[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. 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. 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, (2004).

[58]

M. Putinar, Positive polynomials on compact semi-algebraic sets,, Indiana University Mathematics Journal, 42 (1993), 969. 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. 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.

[62]

B. Reznick, Uniform denominators in Hilbert's seventeenth problem,, Mathematische Zeitschrift, 220 (1995), 75. 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. 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, (2009), 271. 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. doi: 10.1007/BF01446568.

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

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

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

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

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

[72]

G. Stengle, A Nullstellensatz and a Positivstellensatz in semialgebraic geometry,, Mathematische Annalen, 207 (1974), 87. 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. doi: 10.1080/10556789908805766.

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

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

[76]

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

show all references

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

[3]

E. Artin, Über die zerlegung definiter funktionen in quadra,, Quadrate, 5 (1927), 100. 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. 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. 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.

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

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

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

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

[11]

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

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

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

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

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

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

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

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

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

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

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

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

[23]

A. Dolzmann and T. Sturm, Redlog: Computer algebra meets computer logic,, ACM SIGSAM Bulletin, 31 (1997), 2. 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. doi: 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. 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. 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. doi: 10.3934/dcds.2012.32.3539.

[28]

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

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

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

[32]

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

[33]

D. Hilbert, Uber ternare definite Formen,, Acta Math., 17 (1893), 169. 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. 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, (2012), 6259. 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, (2013), 5858. 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, (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), 5948. doi: 10.1109/ACC.2012.6315268.

[39]

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

[40]

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

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

[42]

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

[43]

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

[44]

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

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

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

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

[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).

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

[50]

P. Parrilo, Structured Semidefinite Programs and Semialgebraic Geometry Methods in Robustness and Optimization,, Ph.D thesis, (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. 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.

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

[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. 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. 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, (2004).

[58]

M. Putinar, Positive polynomials on compact semi-algebraic sets,, Indiana University Mathematics Journal, 42 (1993), 969. 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. 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.

[62]

B. Reznick, Uniform denominators in Hilbert's seventeenth problem,, Mathematische Zeitschrift, 220 (1995), 75. 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. 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, (2009), 271. 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. doi: 10.1007/BF01446568.

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

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

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

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

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

[72]

G. Stengle, A Nullstellensatz and a Positivstellensatz in semialgebraic geometry,, Mathematische Annalen, 207 (1974), 87. 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. doi: 10.1080/10556789908805766.

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

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

[76]

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

[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 (17)
  • HTML views (0)
  • Cited by (4)

Other articles
by authors

[Back to Top]