Journal of Convex Analysis 15 (2008), No. 3, 635--654
Copyright 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.