Polynomial upper and lower bounds Consider approximating smooth function $f(x): \mathbb{R} \to \mathbb{R}$ over the interval $[a,b]$ with a bounded $k$th derivative over the interval.  I would like to find degree $d$ polynomials $u(x)$ and $l(x)$ such that $l(x) < f(x) < u(x)$ for $x \in [a,b]$ but which also minimizes the $\ell_\infty$ approximation error.  Is there a general algorithm for doing this, or approximating the solution?
 A: If we discretize the problem, we can solve it exactly with a linear program.  Additionally, if $k\geq 1$, we can construct additional bounds on the continuous case using a semidefinite program.
I'll just describe the process for $l(x)$; $u(x)$ follows symmetrically.

We begin with the discrete case.  Choose an integer $N$.  We will divide $[a,b]$ into $n$ small intervals.  Let $\delta=(b-a)/N$ and let $x_i=a+i\delta$, for $i=0,1,...,N$.  This gives us $N+1$ points from $a$ to $b$.  We will find the degree $d$ polynomial $l(x)$ such that for all $i$, 
$$l(x_i)\leq f(x_i) \tag{1}$$
and that minimizes
$$\max_i [f(x_i)-u(x_i)] \tag{2}$$
Now we will construct the linear program.  Let $l(x)=l_0+l_1x+\cdots l_dx^d$.  Our linear program will have variables $l_0,...,l_d$ and $e$, where $e$ measures the $L^\infty$ norm of the error.  Note that for a fixed $i$ and $s$, $x_i^s$ is a constant.  So the constraint
$$\sum_{s=0}^d l_s (x_i^s)\leq f(x_i)$$
is a linear constraint in the $l_i$.  This enforces Equation 1.  We can also write
$$f(x_i) - \sum_{s=0}^d l_s (x_i^s)\leq b$$
If we choose the objective function of a linear program to minimize $b$, we enforce Equation 2.  The resulting linear program is feasible, and the $l_i$ and $b$ in the solution will provide the polynomial and error term.

Now we consider what we can say about the continuous case.
Suppose $k\geq 1$.  Then there is some finite $s\geq 0$ such that $|f'(x)|\leq s$ for all $x\in[a,b]$.  For any $i$, and any $x\in[x_i,x_{i+1})$, define
$$h_{-}(x)=f(x_i)-s(x-x_i)$$
Note that for any $x\in[a,b]$,
$$f(x)\geq h_{-}(x) \tag{3}$$
Next, let $p$ be a degree $d$ polynomials that satisfies
$$h_{-}(x)\geq p(x) \tag{4}$$
and consider $b$ such that
$$h_{-}(x)-p(x)\leq b \tag{5}$$
Now, suppose we consider the non-negative polynomial optimization problem with feasibility constraints defined by Equations 4 and 5, and in which we minimize $b$.  Because $p(x)$ is a univariate polynomial, this can be exactly expressed as a sum of squares optimization problem (if we treat each interval $[x_i,x_{i+1}]$ in turn), which can be solved efficiently with a semi-definite program solver.
Next, we define a counterpart to $h_{-}$.  For any $i$, and any $x\in[x_i,x_{i+1}]$, define
$$h_{+}(x)=f(x_i)+s(x-x_i)$$
Note that for any $x\in[a,b]$,
$$h_{-}(x)\leq f(x)\leq h_{+}$$
Also note that (where we take $|\cdot|_\infty$ on the interval $[a,b]$)
$$ |h_{-},h_{+}|_\infty = 2s(b-a)/N$$
Therefore,
$$ |h_{-},f|_\infty = 2s(b-a)/N$$
So, the sum of squares program will give us a polynomial with minimal $\ell_\infty$ distance to $h_{-}$, and as $N\rightarrow \infty$, the $\ell_\infty$ distance between $h_{-}$ and $f$ drops to zero; therefore, this asymptotically produces the correct answer (and the error is at worst $2s(b-a)/N$).
