Polynomial upper and lower bounds

Question

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?

Answer 1

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$).