2016, 6(2): 91-102. doi: 10.3934/naco.2016001

On bounds of the Pythagoras number of the sum of square magnitudes of Laurent polynomials

1. 

Department of Mathematics, Quy Nhon University, Vietnam

2. 

Department of Computer Science, KU Leuven, Belgium

Received  October 2014 Revised  March 2016 Published  June 2016

This paper presents a lower and upper bound of the Pythagoras number of sum of square magnitudes of Laurent polynomials (sosm-polynomials). To prove these bounds, properties of the corresponding system of quadratic polynomial equations are used. Applying this method, a new proof for the best (known until now) upper bound of the Pythagoras number of real polynomials is also presented.
Citation: Thanh Hieu Le, Marc Van Barel. On bounds of the Pythagoras number of the sum of square magnitudes of Laurent polynomials. Numerical Algebra, Control & Optimization, 2016, 6 (2) : 91-102. doi: 10.3934/naco.2016001
References:
[1]

G. P. Barker, The lattice of faces of a finite dimensional cone,, Linear Algebra and its Applications, 7 (1973), 71.   Google Scholar

[2]

G. P. Barker, Theory of cones,, Linear Algebra and its Applications, 39 (1981), 263.  doi: 10.1016/0024-3795(81)90310-4.  Google Scholar

[3]

A. I. Barvinok, Problems of distance geometry and convex properties of quadratic maps,, Discrete & Computational Geometry, 13 (1995), 189.  doi: 10.1007/BF02574037.  Google Scholar

[4]

J. Bochnak, M. Coste and M.-F. Roy, Real Algebraic Geometry,, Springer-Verlag, (1998).  doi: 10.1007/978-3-662-03718-8.  Google Scholar

[5]

S. P. Boyd and L. Vandenberghe, Convex Optimization,, Cambridge University Press, (2004).  doi: 10.1017/CBO9780511804441.  Google Scholar

[6]

M.-D. Choi, T. Y. Lam and B. Reznick, Sums of squares of real polynomials,, in Proceedings of Symposia in Pure Mathematics, 58 (1995), 103.   Google Scholar

[7]

Y. V. Genin, Y. Hachez, Y. Nesterov and P. Van Dooren, Convex optimization over positive polynomials and filter design,, in Proceedings UKACC Int. Conf. Control 2000, (2000).   Google Scholar

[8]

J. S. Geronimo and M.-J. Lai, Factorization of multivariate positive Laurent polynomials,, Journal of Approximation Theory, 139 (2006), 327.  doi: 10.1016/j.jat.2005.09.010.  Google Scholar

[9]

O. Güler, Barrier function in interior point methods,, Mathematics of Operations Research, 21 (1996), 860.  doi: 10.1287/moor.21.4.860.  Google Scholar

[10]

R. D. Hill and S. R. Waters, On the cone of positive semidefinite matrices,, Linear Algebra and its Applications, 90 (1987), 81.  doi: 10.1016/0024-3795(87)90307-7.  Google Scholar

[11]

W. Hurewicz and H. Wallman, Dimension Theory,, Princeton University Press, (1948).   Google Scholar

[12]

J. B. Lasserre, A sum of squares approximation of nonnegative polynomials,, SIAM Review, 49 (2007), 651.  doi: 10.1137/070693709.  Google Scholar

[13]

T. H. Le, L. Sorber and M. Van Barel, The Pythagoras number of real sum of squares polynomials and sum of square magnitudes of polynomials,, Calcolo, 50 (2013), 283.  doi: 10.1007/s10092-012-0068-y.  Google Scholar

[14]

T. H. Le and M. Van Barel, A convex optimization method to solve a filter design problem,, Journal of Computational and Applied Mathematics, 255 (2014), 183.  doi: 10.1016/j.cam.2013.04.044.  Google Scholar

[15]

G. Marsaglia and G. P. H. Styan, When does rank(A+B) = rank(A) + rank(B)?,, Canadian Mathematical Bulletin, 15 (1972), 451.   Google Scholar

[16]

G. Pataki, Cone-LP's and semidefinite programs: Geometry and a simplex-type method,, in Integer Programming and Combinatorial Optimization, 1084 (1996), 162.  doi: 10.1007/3-540-61310-2_13.  Google Scholar

[17]

G. Pataki, On the rank of extreme matrices in semidefinite programs and the multiplicity of optimal eigenvalues,, Mathematics of Operations Research, 23 (1998), 339.  doi: 10.1287/moor.23.2.339.  Google Scholar

[18]

G. Pataki, The Geometry of Semidefinite Programming,, in Handbook of Semidefinite Programming: Theory, (2000).  doi: 10.1007/978-1-4615-4381-7.  Google Scholar

[19]

A. Prestel and C. N. Delzell, Positive Polynomials,, Springer Monographs in Mathematics, (2001).  doi: 10.1007/978-3-662-04648-7.  Google Scholar

[20]

R. T. Rockafellar, Convex Analysis,, Princeton University Press, (1970).   Google Scholar

show all references

References:
[1]

G. P. Barker, The lattice of faces of a finite dimensional cone,, Linear Algebra and its Applications, 7 (1973), 71.   Google Scholar

[2]

G. P. Barker, Theory of cones,, Linear Algebra and its Applications, 39 (1981), 263.  doi: 10.1016/0024-3795(81)90310-4.  Google Scholar

[3]

A. I. Barvinok, Problems of distance geometry and convex properties of quadratic maps,, Discrete & Computational Geometry, 13 (1995), 189.  doi: 10.1007/BF02574037.  Google Scholar

[4]

J. Bochnak, M. Coste and M.-F. Roy, Real Algebraic Geometry,, Springer-Verlag, (1998).  doi: 10.1007/978-3-662-03718-8.  Google Scholar

[5]

S. P. Boyd and L. Vandenberghe, Convex Optimization,, Cambridge University Press, (2004).  doi: 10.1017/CBO9780511804441.  Google Scholar

[6]

M.-D. Choi, T. Y. Lam and B. Reznick, Sums of squares of real polynomials,, in Proceedings of Symposia in Pure Mathematics, 58 (1995), 103.   Google Scholar

[7]

Y. V. Genin, Y. Hachez, Y. Nesterov and P. Van Dooren, Convex optimization over positive polynomials and filter design,, in Proceedings UKACC Int. Conf. Control 2000, (2000).   Google Scholar

[8]

J. S. Geronimo and M.-J. Lai, Factorization of multivariate positive Laurent polynomials,, Journal of Approximation Theory, 139 (2006), 327.  doi: 10.1016/j.jat.2005.09.010.  Google Scholar

[9]

O. Güler, Barrier function in interior point methods,, Mathematics of Operations Research, 21 (1996), 860.  doi: 10.1287/moor.21.4.860.  Google Scholar

[10]

R. D. Hill and S. R. Waters, On the cone of positive semidefinite matrices,, Linear Algebra and its Applications, 90 (1987), 81.  doi: 10.1016/0024-3795(87)90307-7.  Google Scholar

[11]

W. Hurewicz and H. Wallman, Dimension Theory,, Princeton University Press, (1948).   Google Scholar

[12]

J. B. Lasserre, A sum of squares approximation of nonnegative polynomials,, SIAM Review, 49 (2007), 651.  doi: 10.1137/070693709.  Google Scholar

[13]

T. H. Le, L. Sorber and M. Van Barel, The Pythagoras number of real sum of squares polynomials and sum of square magnitudes of polynomials,, Calcolo, 50 (2013), 283.  doi: 10.1007/s10092-012-0068-y.  Google Scholar

[14]

T. H. Le and M. Van Barel, A convex optimization method to solve a filter design problem,, Journal of Computational and Applied Mathematics, 255 (2014), 183.  doi: 10.1016/j.cam.2013.04.044.  Google Scholar

[15]

G. Marsaglia and G. P. H. Styan, When does rank(A+B) = rank(A) + rank(B)?,, Canadian Mathematical Bulletin, 15 (1972), 451.   Google Scholar

[16]

G. Pataki, Cone-LP's and semidefinite programs: Geometry and a simplex-type method,, in Integer Programming and Combinatorial Optimization, 1084 (1996), 162.  doi: 10.1007/3-540-61310-2_13.  Google Scholar

[17]

G. Pataki, On the rank of extreme matrices in semidefinite programs and the multiplicity of optimal eigenvalues,, Mathematics of Operations Research, 23 (1998), 339.  doi: 10.1287/moor.23.2.339.  Google Scholar

[18]

G. Pataki, The Geometry of Semidefinite Programming,, in Handbook of Semidefinite Programming: Theory, (2000).  doi: 10.1007/978-1-4615-4381-7.  Google Scholar

[19]

A. Prestel and C. N. Delzell, Positive Polynomials,, Springer Monographs in Mathematics, (2001).  doi: 10.1007/978-3-662-04648-7.  Google Scholar

[20]

R. T. Rockafellar, Convex Analysis,, Princeton University Press, (1970).   Google Scholar

[1]

James Anderson, Antonis Papachristodoulou. Advances in computational Lyapunov analysis using sum-of-squares programming. Discrete & Continuous Dynamical Systems - B, 2015, 20 (8) : 2361-2381. doi: 10.3934/dcdsb.2015.20.2361

[2]

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

[3]

Sigurdur Hafstein, Skuli Gudmundsson, Peter Giesl, Enrico Scalas. Lyapunov function computation for autonomous linear stochastic differential equations using sum-of-squares programming. Discrete & Continuous Dynamical Systems - B, 2018, 23 (2) : 939-956. doi: 10.3934/dcdsb.2018049

[4]

Xiangxiang Huang, Xianping Guo, Jianping Peng. A probability criterion for zero-sum stochastic games. Journal of Dynamics & Games, 2017, 4 (4) : 369-383. doi: 10.3934/jdg.2017020

[5]

Jean Louis Woukeng. $\sum $-convergence and reiterated homogenization of nonlinear parabolic operators. Communications on Pure & Applied Analysis, 2010, 9 (6) : 1753-1789. doi: 10.3934/cpaa.2010.9.1753

[6]

Marianne Akian, Stéphane Gaubert, Antoine Hochart. Ergodicity conditions for zero-sum games. Discrete & Continuous Dynamical Systems - A, 2015, 35 (9) : 3901-3931. doi: 10.3934/dcds.2015.35.3901

[7]

Giuseppe Di Fazio, Maria Stella Fanciullo, Pietro Zamboni. Harnack inequality for degenerate elliptic equations and sum operators. Communications on Pure & Applied Analysis, 2015, 14 (6) : 2363-2376. doi: 10.3934/cpaa.2015.14.2363

[8]

Sylvain Sorin, Guillaume Vigeral. Reversibility and oscillations in zero-sum discounted stochastic games. Journal of Dynamics & Games, 2015, 2 (1) : 103-115. doi: 10.3934/jdg.2015.2.103

[9]

Marc Kessböhmer, Bernd O. Stratmann. On the asymptotic behaviour of the Lebesgue measure of sum-level sets for continued fractions. Discrete & Continuous Dynamical Systems - A, 2012, 32 (7) : 2437-2451. doi: 10.3934/dcds.2012.32.2437

[10]

Yuk L. Yung, Cameron Taketa, Ross Cheung, Run-Lie Shia. Infinite sum of the product of exponential and logarithmic functions, its analytic continuation, and application. Discrete & Continuous Dynamical Systems - B, 2010, 13 (1) : 229-248. doi: 10.3934/dcdsb.2010.13.229

[11]

Josef Hofbauer, Sylvain Sorin. Best response dynamics for continuous zero--sum games. Discrete & Continuous Dynamical Systems - B, 2006, 6 (1) : 215-224. doi: 10.3934/dcdsb.2006.6.215

[12]

J. Scott Carter, Daniel Jelsovsky, Seiichi Kamada, Laurel Langford and Masahico Saito. State-sum invariants of knotted curves and surfaces from quandle cohomology. Electronic Research Announcements, 1999, 5: 146-156.

[13]

Guanglu Zhou. A quadratically convergent method for minimizing a sum of Euclidean norms with linear constraints. Journal of Industrial & Management Optimization, 2007, 3 (4) : 655-670. doi: 10.3934/jimo.2007.3.655

[14]

Alexander J. Zaslavski. Structure of approximate solutions of dynamic continuous time zero-sum games. Journal of Dynamics & Games, 2014, 1 (1) : 153-179. doi: 10.3934/jdg.2014.1.153

[15]

Zhi-Wei Sun. Unification of zero-sum problems, subset sums and covers of Z. Electronic Research Announcements, 2003, 9: 51-60.

[16]

Beatris Adriana Escobedo-Trujillo, José Daniel López-Barrientos. Nonzero-sum stochastic differential games with additive structure and average payoffs. Journal of Dynamics & Games, 2014, 1 (4) : 555-578. doi: 10.3934/jdg.2014.1.555

[17]

Beatris A. Escobedo-Trujillo. Discount-sensitive equilibria in zero-sum stochastic differential games. Journal of Dynamics & Games, 2016, 3 (1) : 25-50. doi: 10.3934/jdg.2016002

[18]

Qingmeng Wei, Zhiyong Yu. Time-inconsistent recursive zero-sum stochastic differential games. Mathematical Control & Related Fields, 2018, 8 (3&4) : 1051-1079. doi: 10.3934/mcrf.2018045

[19]

Antoine Hochart. An accretive operator approach to ergodic zero-sum stochastic games. Journal of Dynamics & Games, 2019, 6 (1) : 27-51. doi: 10.3934/jdg.2019003

[20]

Ming Huang, Cong Cheng, Yang Li, Zun Quan Xia. The space decomposition method for the sum of nonlinear convex maximum eigenvalues and its applications. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-21. doi: 10.3934/jimo.2019034

 Impact Factor: 

Metrics

  • PDF downloads (16)
  • HTML views (0)
  • Cited by (0)

Other articles
by authors

[Back to Top]