Computing Uniform Convex Approximations for Convex Envelopes and Convex Hulls

We provide a numerical procedure to compute uniform convex approximations $\{f_{r}\}$ of the convex envelope $\widehat{f}$ of a rational fraction $f$ defined on a compact basic semi-algebraic set $\mathbf{D}$. At each point $x$ of the convex hull $\mathbf{K}=\mathrm{co}(\mathbf{D})$, computing $f_{r}(x)$ reduces to solving a semidefinite program. We next characterize $\mathbf{K}$ in terms of the projection of a semi-infinite LMI, and provide outer convex approximations $\{\mathbf{K}_{r}\}\downarrow \mathbf{K}$. Testing whether $x\notin \mathbf{K}$ reduces to solving finitely many semidefinite programs