Abstract

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

Author information

Contact details are reproduced from the original publication and may be historical.

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

References

  1. G. A. Anastassiou: Moments in Probability and Approximation Theory, Longman, Harlow (1993).Google Scholar
  2. J. Benoist, J.-B. Hiriart-Urruty: What is the subdifferential of the closed convex hull of a function?, SIAM J. Math. Anal. 27 (1996) 1661–1679.https://doi.org/10.1137/S0036141094265936Google Scholar
  3. A. Ben-Tal, A. Nemirovski: Lectures on Modern Convex Optimization, SIAM, Philadelphia (2001).https://doi.org/10.1137/1.9780898718829Google Scholar
  4. B. Brighi, M. Chipot: Approximated convex envelope of a function, SIAM J. Numer. Anal. 31 (1994) 128–148.https://doi.org/10.1137/0731007Google Scholar
  5. G. Choquet: Lectures on Analysis. I: Integration and Topological Vector Spaces, W. A. Benjamin, New York (1969).Google Scholar
  6. J. W. Helton, V. Vinnikov: Linear matrix inequality representation of sets, Commun. Pure Appl. Math. 60 (2007) 654–674.https://doi.org/10.1002/cpa.20155Google Scholar
  7. T. Jacobi, A. Prestel: Distinguished representations of strictly positive polynomials, J. Reine. Angew. Math. 532 (2001) 223–235.https://doi.org/10.1515/crll.2001.023Google Scholar
  8. J. H. B. Kemperman: Geometry of the moment problem, in: Moments in Mathematics, H. J. Landau (ed.), Proc. Symp. Appl. Math. 37, American Mathematical Society, Providence (1987) 16–53.https://doi.org/10.1090/psapm/037/921083Google Scholar
  9. J. B. Kruskal: Two convex counterexamples: a discontinuous envelope function and a non differentiable nearest-point mapping, Proc. Amer. Math. Soc. 23 (1969) 697–703.https://doi.org/10.1090/S0002-9939-1969-0259752-9Google Scholar
  10. R. Laraki, W. D. Sudderth: The preservation of continuity and Lipschitz continuity by optimal reward operators, Math. Oper. Res. 29 (2004) 672–685.https://doi.org/10.1287/moor.1030.0085Google Scholar
  11. R. Laraki: On the regularity of the convexification operator on a compact set, J. Convex Analysis 11 (2004) 209–234.https://doi.org/10.68381/jca11014Google Scholar
  12. J. B. Lasserre: Global optimization with polynomials and the problem of moments, SIAM J. Optim. 11 (2001) 796–817.https://doi.org/10.1137/S1052623400366802Google Scholar
  13. A. S. Lewis, P. Parrilo, M. V. Ramana: The Lax conjecture is true, Proc. Amer. Math. Soc. 133 (2005) 2495–2499.https://doi.org/10.1090/S0002-9939-05-07752-XGoogle Scholar
  14. P. Parrilo, B. Sturmfels: Minimizing polynomial functions, in: Algorithmic and Quantitative Real Algebraic Geometry, S. Basu, L. Gonzalez-Vega (eds.), American Mathematical Society, Providence (2003) 83–100.https://doi.org/10.1090/dimacs/060/08Google Scholar
  15. M. Putinar: Positive polynomials on compact semi-algebraic sets, Indiana Univ. Math. J. 42 (1993) 969–984.https://doi.org/10.1512/iumj.1993.42.42045Google Scholar
  16. R. T. Rockafellar: Convex Analysis, Princeton University Press, Princeton (1970).https://doi.org/10.1515/9781400873173Google Scholar
  17. K. Schmüdgen: The K-moment problem for compact semi-algebraic sets, Math. Ann. 289 (1991) 203–206.https://doi.org/10.1007/BF01446568Google Scholar
  18. L. Vandenberghe, S. Boyd: Semidefinite programming, SIAM Rev. 38 (1996) 49–95.https://doi.org/10.1137/1038003Google Scholar

Suggested citation

R. Laraki, J. B. Lasserre. “Computing Uniform Convex Approximations for Convex Envelopes and Convex Hulls.” Journal of Convex Analysis 15 (2008), No. 3, 635–654. https://doi.org/10.68381/jca15044

Download BibTeXPublished by Heldermann Verlag.

Published by Heldermann Verlag, 2008. Rights now held by Banach Press LLC.