= Bernstein linear programming hierarchy for polynomial minimization
{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.
Back to article page
