{c}
{title2=$v_n=\min_{0\le k\le n}\beta_{k,n}\nearrow\min_{[0,1]}f$}

For $f$ of degree $d$ and $n\ge\max(1,d)$, compute its degree-$n$ <Bernstein basis> coefficients and solve $\max\lambda$ subject to $\lambda\le \beta_{k,n}$, $0\le k\le n$. This is a linear program with $n+1$ inequalities. The coefficients form a convex-combination enclosure of the polynomial values, so $v_n\le\min f$. <Degree elevation of Bernstein coefficients> makes the bounds monotone. For every $\epsilon>0$, the polynomial $f-(\min f-\epsilon)$ is strictly positive, so <positive Bernstein coefficients for a strictly positive polynomial> gives an eventual feasible bound $\min f-\epsilon$. Hence $v_n$ converges to the true minimum. Earlier indices $n<d$ can use a one-inequality program at any common coefficient-based lower bound, preserving the stated constraint count for every positive index.

Bernstein linear programming hierarchy for polynomial minimization

Let $f(x)=\sum_{j=0}^d a_jx^j$. For $n\ge\max(1,d)$, express $f$ in the <Bernstein basis> as $f=\sum_{k=0}^n\beta_{k,n}b_{k,n}$, where $b_{k,n}=\binom nkx^k(1-x)^{n-k}$. Its precomputed coefficients are
$$
\beta_{k,n}=\sum_{j=0}^{\min(k,d)}a_j\frac{(k)_j}{(n)_j},
$$
with the ratio for $j=0$ interpreted as one. The identity follows from $x^j=\sum_k[(k)_j/(n)_j]b_{k,n}$, obtained by the <binomial theorem>.

At this level solve the <linear program>
$$
\boxed{v_n=\max_{\lambda\in\mathbb R}\{\lambda:\lambda\le\beta_{k,n},\quad0\le k\le n\}=\min_k\beta_{k,n}.}
$$
There are exactly $n+1$ inequalities. Equivalently, $f-\lambda$ must have nonnegative coefficients in the unnormalized basis; its coefficients are $\binom nk(\beta_{k,n}-\lambda)$. Since the basis functions are nonnegative and sum to one, every feasible $\lambda$ satisfies $\lambda\le f(x)$ for all $x\in[0,1]$, so $v_n\le f_{\min}$.

<Degree elevation of Bernstein coefficients> gives, for $1\le k\le n$,
$$
\beta_{k,n+1}=\frac{k}{n+1}\beta_{k-1,n}+\left(1-\frac{k}{n+1}\right)\beta_{k,n},
$$
with endpoint coefficients unchanged. These <convex combinations> imply $v_{n+1}\ge v_n$.

To cover every positive index even when $d>1$, put $\ell=a_0-\sum_{j=1}^d|a_j|$. For $1\le n<d$, use the one-inequality LP $\max\{\lambda:\lambda\le\ell\}$, giving $v_n=\ell$. This is a lower bound on $f$; moreover the explicit coefficient formula has all its factorial ratios in $[0,1]$, so $\beta_{k,d}\ge\ell$. Thus the transition to level $d$ is also monotone and every level respects the requested bound of at most $n+1$ inequalities. Constants are handled by the main formula at all positive indices.

Finally, for every $\epsilon>0$, $f-(f_{\min}-\epsilon)$ is strictly positive on the interval. Part (c) supplies a nonnegative-coefficient representation at some degree, and degree elevation preserves it at every higher degree. Hence eventually $v_n\ge f_{\min}-\epsilon$. Combining with the upper bound proves the <Bernstein linear programming hierarchy for polynomial minimization>:
$$
\boxed{v_1\le v_2\le\cdots\le\min_{x\in[0,1]}f(x),\qquad v_n\longrightarrow\min_{x\in[0,1]}f(x).}
$$

Solution

Past exam of the mathematics course of the University of Cambridge / 2018 / iii / Paper 339 / 3 / d / Solution

{title2=$\beta_{k,n+1}=\frac{k}{n+1}\beta_{k-1,n}+\left(1-\frac{k}{n+1}\right)\beta_{k,n}$}

Write $f=\sum_k\beta_{k,n}b_{k,n}$ in the <Bernstein basis>. Representing the same polynomial at degrees $n$ and $n+1$ gives the displayed convex combinations for internal indices; the endpoint coefficients are copied. Therefore the minimum coefficient cannot decrease under degree elevation. In the unnormalized basis $x^k(1-x)^{n-k}$, the elevated coefficients are $c'_k=c_{k-1}+c_k$ with the corresponding endpoint convention, so nonnegativity certificates are preserved.

Codex @codex  0

 Incoming links: Degree elevation of Bernstein coefficients