A suggestion: have nonnegative polynomial over an interval

Thanks Michael and all folks at CVX for a wonderful service.

I have a suggestion and question. First the suggestion. There are two types of predefined sets regarding nonnegative polynomials: nonneg_poly_coeffs(n) and convex_poly_coeffs(n). I find these very useful in principle. However most applications I have encountered actually involve nonnegative, convex (and also monotonically increasing/decreasing) polynomials over an interval. So it would be nice if these sets are extended to nonneg_poly_coeffs(n,a,b) and convex_poly_coeffs(n,a,b) where a,b indicate the interval [a,b] over which the polynomial is nonnegative or convex. Of course one can write nonnegativity constraints on an interval either directly using semidefinite matrices, or construct them using nonnegativity over the entire line. But this is tedious and error prone, and distracts the modeler from his/her real concerns.

My question is how do you implement these constraints. Do you use the direct method (i.e p(t) >= 0 iff there is a psd matrix such that sum of i’th reverse diagonals equals p_i)? which is numerically poor, or do you first turn the polynomial to a more numerically stable basis (say some orthogonal polynomials basis such as Chebyshev)?

Farid Alizadeh

Hello Farid,
Thanks a lot for the post, and I apologize for the delay! Both nonneg_poly_coeffs and convex_poly_coeffs are implemented naïvely, simply because we haven’t had a lot of demand for it. Your idea of implementing the interval versions is a great one. Would you mind point me to perhaps the best current reference? I’ll certainly add it to the to-do list. I can’t make any promises on timeline… I
f you want try out some different strategies yourself, I can show you how to build the functions yourself…

A good reference would be the '06 paper by Toh and Vandenberghe: http://www.seas.ucla.edu/~vandenbe/publications/nnp.pdf

Thanks Joachim!

Hi Michael,
The best reference I have is Karlin and Studden:

S. Karlin nad W. Studden, “Tchebycheff Systems: with Applications in Analysis and Statistics”, Wiley, 1966.

Chapter IV Theorem 1.1 on pages 106-107 has all you need for the dual problem. Also Chapter V sec. 11 Theorem 10.1 on page 173 has the result for the dual problem over half open interval.

By the way I have implemented the functions already for a problem I was working on. But I used direct hankel SDP representation. It was very tedious. If you wish I can e-mail you the scripts. (It involves a maximum flow problem where capacities are time-varying polynomials, and flows are also required to be time varying polynomials.)

Are you totally positive that’s the best reference? O.k., just kidding, but if you liked Karlin and Studden, you’ll love Samuel Karlin’s Total Positivity Volume 1, Stanford University Press, 1968. If you master that material, I believe it will help you in convex analysis and convex optimization.

Volume 1 addresses the univariate theory, but what you should really be jonesing for is volume 2, addressing multivariate theory - unfortunately, that volume was never completed or published, and never will be.

Thanks Farid and Mark, both! I can’t promise a short timeline here, so I’m glad you were able to implement your functions yourself. Farid, if you want to email me those functions, I can scrub them to see if perhaps there’s a more efficient way to code them up (keeping the mathematics equivalent).

Just to be clear, the Total Positivity reference is more for general edification, not for purposes of the specific problem at hand - I defer to falizadeh for that.

Hi, polynomial lovers !

Positivity on intervals and many other types of polynomial positivity are implemented in POS3POLY (www.schur.pub.ro/pos3poly), on top of CVX. For a beginner, the difficulty may be in describing the type of polynomial. Otherwise, a polynomial positivity constraint is written as a single function call. No Hankel or Toeplitz matrices, one can work directly with the polynomial coefficients as variables.

Hope it helps,


What a great contribution, thank you!