Seems also worth noting that although the usual algorithm for finding the minimax polynomial is the very old Remez algorithm, I'm playing with a minimax finder that relies on what I think is a novel algorithm. My algorithm seems better than Remez, and certainly beats it (as in, finds the solution when Remez can not) in many cases, even though I don't have an analysis of the algorithm.

The main idea is to use linear programming with some chosen points from the interval to look for the polynomial that approximates the chosen function over that interval. Unlike Remez, this enables control over which individual points from the interval are chosen as representatives, which enables avoiding ill-behaved points. An example of where this leads to improvements over Remez is when optimizing relative error: Remez would trip over zeros of the function, because they cause singularities in the relative error, however my algorithm works (by avoiding ill-behaved points) as long as the discontinuities are removable.

My algorithm is also a lot more flexible than Remez', for example it allows optimizing over multiple intervals instead of a single one.

The Git repo of the (still in-progress) project is here: https://gitlab.com/nsajko/FindMinimaxPolynomial.jl

The Julia package is already registered (installable from the official Julia registry): https://juliahub.com/ui/Packages/FindMinimaxPolynomial/kNIo8...