Skip to main content
SpringerLink
Log in

Convex envelopes generated from finitely many compact convex sets

  • Full Length Paper
  • Series A
  • Published:
Mathematical Programming Submit manuscript

Abstract

We consider the problem of constructing the convex envelope of a lower semi-continuous function defined over a compact convex set. We formulate the envelope representation problem as a convex optimization problem for functions whose generating sets consist of finitely many compact convex sets. In particular, we consider nonnegative functions that are products of convex and component-wise concave functions and derive closed-form expressions for the convex envelopes of a wide class of such functions. Several examples demonstrate that these envelopes reduce significantly the relaxation gaps of widely used factorable relaxation techniques.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Al-Khayyal F.A., Falk J.E.: Jointly constrained biconvex programming. Math. Oper. Res. 8, 273–286 (1983)

    Article  MathSciNet  MATH  Google Scholar 

  2. Balas E.: Disjunctive programming. Ann. Discrete Math. 5, 3–51 (1979)

    Article  MathSciNet  MATH  Google Scholar 

  3. Balas E.: Disjunctive programming and hierarchy of relaxations for discrete optimization problems. SIAM J. Alg. Disc. Meth. 6, 466–486 (1985)

    Article  MathSciNet  MATH  Google Scholar 

  4. Bao X., Sahinidis N.V., Tawarmalani M.: Multiterm polyhedral relaxations for nonconvex, quadratically-constrained quadratic programs. Optim. Methods Softw. 24, 485–504 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  5. Bertsekas D.: Convex Optimization Theory. Athena Scientific, Cambridge (2009)

    MATH  Google Scholar 

  6. Bussieck M.R., Drud A.S., Meeraus A.: MINLPLib—a collection of test models for mixed-integer nonlinear programming. INFORMS J. Comput. 15, 114–119 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  7. Carathéodory C.: Uber den variabilitatsbereich der Fourierschen konstanten von positiven harmonischen funktionen. Rendiconto Circolo Matematico Palermo 32, 193–217 (1911)

    Article  MATH  Google Scholar 

  8. Ceria S., Soares J.: Convex programming for disjunctive convex optimization. Math. Program. 86, 595–614 (1999)

    Article  MathSciNet  MATH  Google Scholar 

  9. Frangioni A., Gentile C.: Perspective cuts for a class of convex 0−1 mixed integer programs. Math. Program. 106, 225–236 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  10. GLOBAL Library. http://www.gamsworld.org/global/globallib.htm

  11. Grossmann I.E., Lee S.: Generalized convex disjunctive programming: nonlinear convex hull relaxation. Comput. Optim. Appl. 26, 83–100 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  12. Günlük O., Linderoth J.: Perspective relaxation of mixed integer nonlinear programs with indicator variables. Lect. Notes Comput. Sci. 5035, 1–16 (2008)

    Article  Google Scholar 

  13. Hiriart-Urruty J.-B., Lemaréchal C.: Fundamentals of Convex Analysis. Grundlehren Text Editions, New York (2001)

    Book  MATH  Google Scholar 

  14. Jach M., Michaels D., Weismantel R.: The convex envelope of (n − 1)-convex functions. SIAM J. Optim. 19, 1451–1466 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  15. Khajavirad, A., Sahinidis, N.V.: Convex envelopes of products of convex and component-wise concave functions. J. Global Optim. doi:10.1007/s10898-011-9747-5 (2011)

  16. Lovász L.: Submodular functions and convexity. In: Bachem, A., Grotschel, M., Korte, B. (eds) Mathematical Programming: The State of the Art, pp. 235–257. Springer, Berlin (1982)

    Google Scholar 

  17. McCormick G.P.: Computability of global solutions to factorable nonconvex programs: Part I—Convex underestimating problems. Math. Program. 10, 147–175 (1976)

    Article  MathSciNet  MATH  Google Scholar 

  18. Meyer C.A., Floudas C.A.: Trilinear monomials with mixed sign domains: facets of the convex and concave envelopes. J. Global Optim. 29, 125–155 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  19. Meyer C.A., Floudas C.A.: Convex envelopes for edge-concave functions. Math. Program. 103, 207–224 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  20. Minkowski H.: Theorie der Knovexen Körper, insbesondere begrundung ihres oberfla chenbegriffs. In: Hilbert, D., Speiser, A., Weyl, H. (eds) Gesammelte Abhandlungen von Hermann Minkowski, vol. 2, pp. 131–229. Teubner, Leipsig (1911)

    Google Scholar 

  21. Nemhauser, G.L., Wolsey, L.A.: Integer and combinatorial optimization. Wiley Interscience, Series in Discrete Mathematics and Optimization, New York (1988)

  22. Rikun A.D.: A convex envelope formula for multilinear functions. J. Global Optim. 10, 425–437 (1997)

    Article  MathSciNet  MATH  Google Scholar 

  23. Rockafellar R.T.: Convex Analysis. Princeton Mathematical Series. Princeton University Press, Princeton (1970)

    Google Scholar 

  24. Rockafellar R.T., Wets R.J.-B.: Variational Analysis. A Series of Comprehensive Studies in Mathematics. Springer, Berlin (1998)

    Book  Google Scholar 

  25. Sahinidis N.V.: BARON: a general purpose global optimization software package. J. Global Optim. 8, 201–205 (1996)

    Article  MathSciNet  MATH  Google Scholar 

  26. Sherali H.D.: Convex envelopes of multilinear functions over a unit hypercube and over special discrete sets. Acta Math. Vietnam. 22, 245–270 (1997)

    MathSciNet  MATH  Google Scholar 

  27. Stubbs R., Mehrotra S.: A branch and cut method for 0−1 mixed convex programming. Math. Program. 86, 515–532 (1999)

    Article  MathSciNet  MATH  Google Scholar 

  28. Tardella F.: Existence and sum decomposition of vertex polyhedral convex envelopes. Optim. Lett. 2, 363–375 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  29. Tawarmalani, M.: Inclusion certificates and simultaneous convexification of functions. Math. Program. (submitted)

  30. Tawarmalani M., Richard J.-P., Chung K.: Strong valid inequalities for orthogonal disjunctions and bilinear covering sets. Math. Program. 124, 481–512 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  31. Tawarmalani, M., Richard, J.-P., Xiong, C.: Explicit convex and concave envelopes through polyhedral subdivisions. Math. Program. (submitted)

  32. Tawarmalani M., Sahinidis N.V.: Semidefinite relaxations of fractional programs via novel techniques for constructing convex envelopes of nonlinear functions. J. Global Optim. 20, 137–158 (2001)

    Article  MathSciNet  MATH  Google Scholar 

  33. Tawarmalani M., Sahinidis N.V.: Convex extensions and convex envelopes of l.s.c. functions. Math. Program. 93, 247–263 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  34. Tawarmalani M., Sahinidis N.V.: Global optimization of mixed-integer nonlinear programs: a theoretical and computational study. Math. Program. 99, 563–591 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  35. Tawarmalani M., Sahinidis N.V.: A polyhedral branch-and-cut approach to global optimization. Math. Program. 103, 225–249 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  36. Topkis D.M.: Supermodularity and Complementarity. Princeton University Press, Princeton (1998)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Mechanical Engineering, Carnegie Mellon University, Pittsburgh, PA, USA

    Aida Khajavirad

  2. Department of Chemical Engineering, Carnegie Mellon University, Pittsburgh, PA, USA

    Nikolaos V. Sahinidis

Authors
  1. Aida Khajavirad
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Nikolaos V. Sahinidis
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Nikolaos V. Sahinidis.

Additional information

This research was supported in part by National Science Foundation award CMII-1030168.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Khajavirad, A., Sahinidis, N.V. Convex envelopes generated from finitely many compact convex sets. Math. Program. 137, 371–408 (2013). https://doi.org/10.1007/s10107-011-0496-5

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10107-011-0496-5

Keywords

Mathematics Subject Classification (2000)

Search

Navigation