An Elementary Approach to Polynomial Optimization on Polynomial Meshes


  • Marco Vianello Department of Mathematics Università degli Studi di Padova Via Trieste, 63 - 35121 Padova



optimal polynomial meshes, polynomial norming inequalities, polynomial optimization


A polynomial mesh on a multivariate compact set or manifold is a sequence of finite norming sets for polynomials whose norming constant is independent of degree. We apply the recently developed theory of polynomial meshes to an elementary discrete approach for polynomial optimization on nonstandard domains, providing a rigorous (over)estimate of the convergence rate. Examples include surface/solid subregions of sphere or torus, such as caps, lenses, lunes, and slices.


Bos, L., Calvi, J.P., Levenberg, N. Sommariva, A. & Vianello, M., Geometric Weakly Admissible Meshes, Discrete Least Squares Approximation and Approximate Fekete Points, Math. Comp., 80, pp. 1601-1621, 2011. DOI: 10.1090/S0025-5718-2011-02442-7

Calvi, J.P. & Levenberg, N., Uniform Approximation by Discrete Least Squares Polynomials, J. Approx. Theory, 152, pp. 82-100, 2008. DOI:10.1016/j.jat.2007.05.005

Bloom, T., Levenberg, N., Piazzon, F. & Wielonsky, F. Bernstein-Markov: A survey, Dolomites Res. Notes Approx., 8, pp. 75-91, 2015. DOI: 10.14658/pupj-drna-2015-Special_Issue-8

Kroo, A., On Optimal Polynomial Meshes, J. Approx. Theory, 163(9), pp. 1107-1124, 2011. DOI: 10.1016/j.jat.2011.03.007

Piazzon, F., Optimal Polynomial Admissible Meshes on Some Classes of Compact Subsets of R^d, J. Approx. Theory, 207, pp. 241-264, 2016. DOI: 10.1016/j.jat.2016.02.015

Piazzon, F. & Vianello, M., Small Perturbations of Polynomial Meshes, Appl. Anal. 92(5), pp. 1063-1073, 2013. DOI: 10.1080/00036811.2011 .649730

Sommariva A. & Vianello, M., Polynomial fitting and interpolation on circular sections, Appl. Math. Comput. 258, Article Num. 20774, pp. 410-424, 2015. DOI:10.1016/j.amc.2015.02.013

de Klerk, E., The Complexity of Optimizing Over A Simplex, Hypercube or Sphere: A Short Survey, CEJOR Cent. Eur. J. Oper. Res., 16(2), pp. 111-125, 2008. DOI:L10.1007/s10100-007-0052-9

de Klerk, E., Lasserre, J.B., Laurent, M. & Sun, Z., Bound-constrained Polynomial Optimization using only Elementary Calculations, Mathematics of Operations Research, 42(3), pp. 834-853, 2017. DOI:10.1287/moor.2016.0829

Zhang, J.F. & Kwong, C.P., Some Applications of A Polynomial Inequality to Global Optimization, J. Optim. Theory Appl., 127(1), pp. 193-205, 2005. DOI: 10.1007/s10957-005-6400-9

Piazzon, F. & Vianello, M. A Note on Total Degree Polynomial Optimization by Chebyshev Grids, Optim. Lett., 12, pp. 63-71, 2017. DOI:10.1007/s11590-017-1166-1

Cox, D.A., Little, J. & O'Shea, D., Ideals, Varieties, and Algorithms, 4th Ed., Springer, 2015.

Gentile, M., Sommariva, A. & Vianello, M., Polynomial Approximation and Quadrature on Geographic Rectangles, Appl. Math. Comput. 297, pp. 159-179, 2017. DOI:10.1016/j.amc.2016.08.014

Sommariva, A. & Vianello, M. Discrete Norming Inequalities on Sections of Sphere, Ball and Torus, arXiv:1802.01711 [math.NA], 2018.

Townsend, A. & Trefethen, L.N., An Extension of Chebfun to Two Dimensions, SIAM J. Sci. Comput., 35(6), pp. C495-C518, 2013. DOI:10.1137/130908002