Note that Remez algorithm can be used to find optimal (minimax/Chebyshev) rational functions (ratios of polynomials), not just polynomials, and it would be good to support this case as well.
Of course, you can do pretty well for many functions just by sampling at a lot of points, in which case the minimax problem turns into an finite-dimensional LP (for polynomials) or a sequence of LPs (for rational functions). The tricky "Remez" part is finding the extrema in order to sample at the optimal points, as I understand it.
