Report Number: CS-TR-65-23
Institution: Stanford University, Department of Computer Science
Title: Convex polynomial approximation
Author: Rudin, Bernard D.
Date: June 1965
Abstract: Let f(t) be a continuous function on [0,1], or let it be discretely defined on a finite point set in [0,1]. The problem is the following: among all polynomials p(t) of degree n or less which are convex on [0,1], find one which minimizes the functional $\l p(t)-f(t)\l$, where $\l\ \l$ is a suitably defined norm (in particular, the $L^p$, ${\ell}^p$, and Chebyshev norms). The problem is treated by showing it to be a particular case of a more general problem: let f be an element of a real normed linear space V; let $x_{1}(z),...,x_{k}(z)$ be continous functions on a subset S of the Euclidean space $E^n$ into V such that for each $z_o$ in S the set {$x_{1}(z_{o}),...,x_{k}(z_{o})$} is linearly independent in V; let $(y_{1},...,y_{k})$ denote an element of the Euclidean space $E^k$ and let H be a subset of $K^k$; then among all (y,z) in H $\times$ S, find one which minimizes the functional $\l y_1\ x_{1}(z)+ ... +y_{k}x_{k}(z) - f\l$. It is shown that solutions to this problem exist when H is closed and S is compact. Conditions for uniqueness and location of solutions on the boundary of H $\times$ S are also given. Each polynomial of degree n + 2 or less which is convex on [0,1] is shown to be uniquely representable in the form $y_{o}+y_{1}t+y_2\ \int\int\ p(z,t)dt^2$, where p(z,t) is a certain representation of the polynomials positive on [0,1], $y_2\ \geq\ 0$, and z is constrained to lie in a certain convex hyperpolyhedron. With this representation, the convex polynomial approximation problem can be treated by the theory mentioned above. It is reduced to a problem of minimizing a functional subject to linear constraints. Computation of best least squares convex polynomial approximation is illustrated in the continuous and discrete cases.