Journal Home Page Cumulative Index List of all Volumes Complete Contentsof this Volume Previous Article Journal of Convex Analysis 15 (2008), No. 3, 635--654Copyright Heldermann Verlag 2008 Computing Uniform Convex Approximations for Convex Envelopes and Convex Hulls Rida Laraki Laboratoire d'Econométrie and CNRS, Ecole Polytechnique, 1 rue Descartes, 75005 Paris, France rida.laraki@shs.polytechnique.fr Jean Bernard Lasserre LAAS-CNRS and Institute of Mathematics, University of Toulouse, 7 Avenue du Colonel Roche, 31077 Toulouse Cédex 4, France lasserre@laas.fr [Abstract-pdf] 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 \textit{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. [ Fulltext-pdf  (420  KB)] for subscribers only.