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 and 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-82.

[2]

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

[3]

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

[4]

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

[5]

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

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

[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, Paper SS41.

[8]

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

[9]

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

[10]

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

[11]

W. Hurewicz and H. Wallman, Dimension Theory, Princeton University Press, 1948.

[12]

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

[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-303. doi: 10.1007/s10092-012-0068-y.

[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-192. doi: 10.1016/j.cam.2013.04.044.

[15]

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

[16]

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

[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-358. doi: 10.1287/moor.23.2.339.

[18]

G. Pataki, The Geometry of Semidefinite Programming, in Handbook of Semidefinite Programming: Theory, Algorithms, and Applications (eds. H. Wolkowicz, R. Saigal and L. Vandenberghe), International series in operations research and management science, Kluwer Academic Publishers, 2000. doi: 10.1007/978-1-4615-4381-7.

[19]

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

[20]

R. T. Rockafellar, Convex Analysis, Princeton University Press, 1970.

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

[2]

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

[3]

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

[4]

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

[5]

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

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

[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, Paper SS41.

[8]

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

[9]

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

[10]

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

[11]

W. Hurewicz and H. Wallman, Dimension Theory, Princeton University Press, 1948.

[12]

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

[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-303. doi: 10.1007/s10092-012-0068-y.

[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-192. doi: 10.1016/j.cam.2013.04.044.

[15]

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

[16]

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

[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-358. doi: 10.1287/moor.23.2.339.

[18]

G. Pataki, The Geometry of Semidefinite Programming, in Handbook of Semidefinite Programming: Theory, Algorithms, and Applications (eds. H. Wolkowicz, R. Saigal and L. Vandenberghe), International series in operations research and management science, Kluwer Academic Publishers, 2000. doi: 10.1007/978-1-4615-4381-7.

[19]

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

[20]

R. T. Rockafellar, Convex Analysis, Princeton University Press, 1970.

[1]

James Anderson, Antonis Papachristodoulou. Advances in computational Lyapunov analysis using sum-of-squares programming. Discrete and 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 and 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 and Continuous Dynamical Systems - B, 2018, 23 (2) : 939-956. doi: 10.3934/dcdsb.2018049

[4]

Claude Carlet, Stjepan Picek. On the exponents of APN power functions and Sidon sets, sum-free sets, and Dickson polynomials. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2021064

[5]

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

[6]

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

[7]

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

[8]

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

[9]

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 and Management Optimization, 2020, 16 (4) : 1885-1905. doi: 10.3934/jimo.2019034

[10]

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

[11]

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

[12]

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 and Continuous Dynamical Systems - B, 2010, 13 (1) : 229-248. doi: 10.3934/dcdsb.2010.13.229

[13]

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

[14]

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

[15]

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.

[16]

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

[17]

Guangmei Shao, Wei Xue, Gaohang Yu, Xiao Zheng. Improved SVRG for finite sum structure optimization with application to binary classification. Journal of Industrial and Management Optimization, 2020, 16 (5) : 2253-2266. doi: 10.3934/jimo.2019052

[18]

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

[19]

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

[20]

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

 Impact Factor: 

Metrics

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

Other articles
by authors

[Back to Top]