Journal Home Page

Cumulative Index

List of all Volumes

Complete Contents
of this Volume

Previous Article

Next Article

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

Jean Bernard Lasserre
LAAS-CNRS and Institute of Mathematics, University of Toulouse, 7 Avenue du Colonel Roche, 31077 Toulouse Cédex 4, France


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.