×

Computation of sum of squares polynomials from data points. (English) Zbl 1456.90121

This paper proposes a new technique of numerically computing sums of squares certificates for nonnegativity of univariate polynomials on unions of intervals and, much more generally, of multivariate polynomials on basic closed semi-algebraic sets. In the univariate case, the existence of such certificates is a classical topic (see for example [G. Szegö, Orthogonal polynomials. 4th ed. Providence, RI: American Mathematical Society (AMS) (1975; Zbl 0305.42011)]) and in our days is understood to a large extent [D. Augustin, J. Pure Appl. Algebra 216, No. 10, 2204–2212 (2012; Zbl 1273.12002)]. In the multivariate case, their existence is guaranteed in many cases by Schmüdgen’s or Putinar’s Positivstellensatz [K. Schmüdgen, Math. Ann. 289, No. 2, 203–206 (1991; Zbl 0744.44008); M. Putinar, Indiana Univ. Math. J. 42, No. 3, 969–984 (1993; Zbl 0796.12002)]. Practical algorithms trying to decide the existence of such certificates and aiming at their computation are of highest relevance in polynomial optimization. To make the problem tractable, one fixes an upper degree bound for the sums of squares that is not too large. Up to present, mostly semidefinite programming has been employed to solve this problem [J. B. Lasserre, SIAM J. Optim. 11, No. 3, 796–817 (2001; Zbl 1010.90061); M. Laurent, IMA Vol. Math. Appl. 149, 157–270 (2009; Zbl 1163.13021)].
Assuming some technical conditions, the authors propose a new and interesting nonlinear convex optimization algorithm for the same problem which operates on interpolation data of the involved polynomials. It is based on the definition of a convex objective function arising from the dualization of a certain quadratic regression related to the sums of squares decomposition problem. The domain of this function is cleverly chosen, its convexity properties and its behavior at infinity are analyzed. For univariate polynomials positive on an interval the objective function is shown to be coercive and strictly convex which yields a unique critical point and its corresponding decomposition in sum of squares. For multivariate polynomials which admit a corresponding sum of squares decomposition, the objective function is still coercive after small perturbations, its unique minimizer still yields an approximate sums of squares decomposition. Various unconstrained descent algorithms are proposed for the minimization.

MSC:

90C23 Polynomial optimization
11E25 Sums of squares and representations by other particular quadratic forms
65K05 Numerical mathematical programming methods

Software:

SDPLR; YALMIP; SDLS
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] J. Barzilai and J. M. Borwein, Two-point step size gradient methods, IMA J. Numer. Anal., 8 (1988), pp. 141-148. · Zbl 0638.65055
[2] L. Beira͂o da Veiga, A. Buffa, G. Sangalli, and R. Vázquez, Mathematical analysis of variational isogeometric methods, Acta Numer., 23 (2014), pp. 157-287. · Zbl 1398.65287
[3] S. Boyd and L. Vandenberghe, Convex Optimization, Cambridge University Press, Cambridge, UK, 2004. · Zbl 1058.90049
[4] S. Burer and R. D. C. Monteiro, A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization, Math. Program., 95 (2003), pp. 329-357. · Zbl 1030.90077
[5] M. Campos-Pinto, F. Charles, and B. Després, Algorithms for positive polynomial approximation, SIAM J. Numer. Anal., 57 (2019), pp. 148-172, https://doi.org/10.1137/17M1131891. · Zbl 1415.65031
[6] B. Després, Polynomials with bounds and numerical approximation, Numer. Algorithms, 76 (2017), pp. 829-859. · Zbl 1379.65010
[7] B. Despres and M. Herda, Correction to: Polynomials with bounds and numerical approximation, Numer. Algorithms, 77 (2018), pp. 309-311. · Zbl 1381.65009
[8] R. A. DeVore and G. G. Lorentz, Constructive Approximation, Grundlehren Math. Wiss. 303, Springer-Verlag, Berlin, 1993. · Zbl 0797.41016
[9] D. di Serafino, V. Ruggiero, G. Toraldo, and L. Zanni, On the steplength selection in gradient methods for unconstrained optimization, Appl. Math. Comput., 318 (2018), pp. 176-195. · Zbl 1426.65082
[10] D. Henrion and J. Malick, Projection methods for conic feasibility problems: Applications to polynomial sum-of-squares decompositions, Optim. Methods Softw., 26 (2011), pp. 23-46. · Zbl 1228.90071
[11] J.-B. Hiriart-Urruty and C. Lemaréchal, Convex Analysis and Minimization Algorithms I. Fundamentals, Grundlehren Math. Wiss. 305, Springer-Verlag, Berlin, 1993. · Zbl 0795.49001
[12] M. Korda, D. Henrion, and C. N. Jones, Convergence rates of moment-sum-of-squares hierarchies for optimal control problems, Systems Control Lett., 100 (2017), pp. 1-5. · Zbl 1356.49058
[13] M. G. Kreĭn and A. A. Nudel’man, The Markov Moment Problem and Extremal Problems, American Mathematical Society, Providence, RI, 1977. · Zbl 0361.42014
[14] J. B. Lasserre, Moments, Positive Polynomials and Their Applications, Imp. Coll. Press Optim. Ser. 1, Imperial College Press, London, 2010. · Zbl 1211.90007
[15] J. B. Lasserre, An Introduction to Polynomial and Semi-algebraic Optimization, Cambridge Texts Appl. Math., Cambridge University Press, Cambridge, UK, 2015. · Zbl 1320.90003
[16] B.-G. Lee, T. Lyche, and K. Mørken, Some examples of quasi-interpolants constructed from local spline projectors, in Mathematical Methods for Curves and Surfaces (Oslo, 2000), Innov. Appl. Math., Vanderbilt University Press, Nashville, TN, 2001, pp. 243-252. · Zbl 0989.65009
[17] J. Löfberg, YALMIP: A toolbox for modeling and optimization in MATLAB, in Proceedings of the CACSD Conference, Taipei, Taiwan, 2004.
[18] J. Malick, A dual approach to semidefinite least-squares problems, SIAM J. Matrix Anal. Appl., 26 (2004), pp. 272-284, https://doi.org/10.1137/S0895479802413856. · Zbl 1080.65027
[19] T. S. Motzkin, The arithmetic-geometric inequality, in Inequalities (Proc. Sympos. Wright-Patterson Air Force Base, OH, 1965), Academic Press, New York, 1967, pp. 205-224.
[20] Y. Nesterov, Squared functional systems and optimization problems, in High Performance Optimization, Appl. Optim. 33, Kluwer Academic Publishers, Dordrecht, The Netherlands, 2000, pp. 405-440. · Zbl 0958.90090
[21] Y. Nesterov and A. Nemirovskii, Interior-Point Polynomial Algorithms in Convex Programming, Stud. Appl. Numer. Math. 13, SIAM, Philadelphia, 1994, https://doi.org/10.1137/1.9781611970791. · Zbl 0824.90112
[22] J. Nie and M. Schweighofer, On the complexity of Putinar’s Positivstellensatz, J. Complexity, 23 (2007), pp. 135-150. · Zbl 1143.13028
[23] J. Nocedal and S. J. Wright, Numerical Optimization, 2nd ed., Springer Ser. Oper. Res. Financ. Eng., Springer, New York, 2006. · Zbl 1104.65059
[24] V. Powers and T. Wörmann, An algorithm for sums of squares of real polynomials, J. Pure Appl. Algebra, 127 (1998), pp. 99-104. · Zbl 0936.11023
[25] M. Putinar, Positive polynomials on compact semi-algebraic sets, Indiana Univ. Math. J., 42 (1993), pp. 969-984. · Zbl 0796.12002
[26] M. Raydan, The Barzilai and Borwein gradient method for the large scale unconstrained minimization problem, SIAM J. Optim., 7 (1997), pp. 26-33, https://doi.org/10.1137/S1052623494266365. · Zbl 0898.90119
[27] C.-W. Shu, Bound-preserving high order finite volume schemes for conservation laws and convection-diffusion equations, in Finite Volumes for Complex Applications VIII-Methods and Theoretical Aspects, Springer Proc. Math. Stat. 199, Springer, Cham, 2017, pp. 3-14. · Zbl 1372.65251
[28] J. F. Sturm, Theory and algorithms of semidefinite programming, in High Performance Optimization, Appl. Optim. 33, Kluwer Academic Publishers, Dordrecht, The Netherlands, 2000, pp. 3-19.
[29] G. Szegö, Orthogonal Polynomials, 4th ed., Colloquium Publications XXIII, American Mathematical Society, Providence, RI, 1975. · Zbl 0305.42011
[30] B. Zhou, L. Gao, and Y.-H. Dai, Gradient methods with adaptive step-sizes, Comput. Optim. Appl., 35 (2006), pp. 69-86. · Zbl 1121.90099
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.