Skip to main content
SpringerLink
Log in

Convex envelopes for ray-concave functions

  • Original Paper
  • Published:
Optimization Letters Aims and scope Submit manuscript

Abstract

Convexification based on convex envelopes is ubiquitous in the non-linear optimization literature. Thanks to considerable efforts of the optimization community for decades, we are able to compute the convex envelopes of a considerable number of functions that appear in practice, and thus obtain tight and tractable approximations to challenging problems. We contribute to this line of work by considering a family of functions that, to the best of our knowledge, has not been considered before in the literature. We call this family ray-concave functions. We show sufficient conditions that allow us to easily compute closed-form expressions for the convex envelope of ray-concave functions over arbitrary polytopes. With these tools, we are able to provide new perspectives to previously known convex envelopes and derive a previously unknown convex envelope for a function that arises in probability contexts.

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

Fig. 1
Fig. 2
Fig. 3

Similar content being viewed by others

Data availibility

Data sharing not applicable to this article as no datasets were generated or analysed during the current study.

Notes

  1. A function is polyhedral if its epigraph is a polyhedron.

References

  1. Al-Khayyal, F.A., Falk, J.E.: Jointly constrained biconvex programming. Math. Oper. Res. 8(2), 273–286 (1983). https://doi.org/10.1287/moor.8.2.273

    Article  MathSciNet  MATH  Google Scholar 

  2. Anstreicher, K.M., Burer, S.: Computable representations for convex hulls of low-dimensional quadratic forms. Math. Program. 124(1), 33–43 (2010). https://doi.org/10.1007/s10107-010-0355-9

    Article  MathSciNet  MATH  Google Scholar 

  3. Bao, X., Sahinidis, N.V., Tawarmalani, M.: Multiterm polyhedral relaxations for nonconvex, quadratically constrained quadratic programs. Optim. Methods Softw. 24(4–5), 485–504 (2009). https://doi.org/10.1080/10556780902883184

    Article  MathSciNet  MATH  Google Scholar 

  4. Benson, H.P.: On the construction of convex and concave envelope formulas for bilinear and fractional functions on quadrilaterals. Comput. Optim. Appl. 27(1), 5–22 (2004). https://doi.org/10.1023/B:COAP.0000004976.52180.7f

    Article  MathSciNet  MATH  Google Scholar 

  5. Hijazi, H.: Perspective envelopes for bilinear functions. In: AIP Conference Proceedings, vol. 2070, p. 020017. AIP Publishing LLC (2019)

  6. Inc., W.R.: Mathematica, Version 12.3.1. Champaign, IL (2021). https://www.wolfram.com/mathematica

  7. Jach, M., Michaels, D., Weismantel, R.: The convex envelope of (n-1)-convex functions. SIAM J. Optim. 19(3), 1451–1466 (2008). https://doi.org/10.1137/07069359X

    Article  MathSciNet  MATH  Google Scholar 

  8. Jensen, J.L.W.V.: Om konvekse funktioner og uligheder imellem middelvaerdier. Nyt tidsskrift for matematik 16, 49–68 (1905)

    MATH  Google Scholar 

  9. Khajavirad, A., Michalek, J.J., Sahinidis, N.V.: Relaxations of factorable functions with convex-transformable intermediates. Math. Program. 144(1), 107–140 (2014). https://doi.org/10.1007/s10107-012-0618-8

    Article  MathSciNet  MATH  Google Scholar 

  10. Khajavirad, A., Sahinidis, N.V.: Convex envelopes of products of convex and component-wise concave functions. J. Glob. Optim. 52(3), 391–409 (2012). https://doi.org/10.1007/s10898-011-9747-5

    Article  MathSciNet  MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

  12. Kuno, T.: A branch-and-bound algorithm for maximizing the sum of several linear ratios. J. Glob. Optim. 22(1), 155–174 (2002). https://doi.org/10.1023/A:1013807129844

    Article  MathSciNet  MATH  Google Scholar 

  13. Li, Y.C., Yeh, C.C.: Some characterizations of convex functions. Comput. Math. Appl. 59(1), 327–337 (2010). https://doi.org/10.1016/j.camwa.2009.05.020

    Article  MathSciNet  MATH  Google Scholar 

  14. Liberti, L., Pantelides, C.C.: Convex envelopes of monomials of odd degree. J. Glob. Optim. 25(2), 157–168 (2003). https://doi.org/10.1023/A:1021924706467

    Article  MathSciNet  MATH  Google Scholar 

  15. Linderoth, J.: A simplicial branch-and-bound algorithm for solving quadratically constrained quadratic programs. Math. Program. 103(2), 251–282 (2005). https://doi.org/10.1007/s10107-005-0582-7

    Article  MathSciNet  MATH  Google Scholar 

  16. Locatelli, M.: Polyhedral subdivisions and functional forms for the convex envelopes of bilinear, fractional and other bivariate functions over general polytopes. J. Glob. Optim. 66(4), 629–668 (2016). https://doi.org/10.1007/s10898-016-0418-4

    Article  MathSciNet  MATH  Google Scholar 

  17. Locatelli, M.: Convex envelopes of bivariate functions through the solution of KKT systems. J. Glob. Optim. 72(2), 277–303 (2018). https://doi.org/10.1007/s10898-018-0626-1

    Article  MathSciNet  MATH  Google Scholar 

  18. Locatelli, M.: Convex envelope of bivariate cubic functions over rectangular regions. J. Glob. Optim. 76(1), 1–24 (2020). https://doi.org/10.1007/s10898-019-00846-2

    Article  MathSciNet  MATH  Google Scholar 

  19. Locatelli, M., Schoen, F.: On convex envelopes for bivariate functions over polytopes. Math. Program. 144(1), 65–91 (2014). https://doi.org/10.1007/s10107-012-0616-x

    Article  MathSciNet  MATH  Google Scholar 

  20. Luedtke, J., Namazifar, M., Linderoth, J.: Some results on the strength of relaxations of multilinear functions. Math. Program. 136(2), 325–351 (2012). https://doi.org/10.1007/s10107-012-0606-z

    Article  MathSciNet  MATH  Google Scholar 

  21. McCormick, G.P.: Computability of global solutions to factorable nonconvex programs: part I—convex underestimating problems. Math. Program. 10(1), 147–175 (1976). https://doi.org/10.1007/BF01580665

    Article  MATH  Google Scholar 

  22. Meyer, C.A., Floudas, C.A.: Trilinear monomials with mixed sign domains: facets of the convex and concave envelopes. J. Glob. Optim. 29(2), 125–155 (2004). https://doi.org/10.1023/B:JOGO.0000042112.72379.e6

    Article  MathSciNet  MATH  Google Scholar 

  23. Meyer, C.A., Floudas, C.A.: Convex envelopes for edge-concave functions. Math. Program. 103(2), 207–224 (2005). https://doi.org/10.1007/s10107-005-0580-9

    Article  MathSciNet  MATH  Google Scholar 

  24. Muller, B., Serrano, F., Gleixner, A.: Using two-dimensional projections for stronger separation and propagation of bilinear terms. SIAM J. Optim. 30(2), 1339–1365 (2020). https://doi.org/10.1137/19M1249825

    Article  MathSciNet  MATH  Google Scholar 

  25. Rikun, A.D.: A convex envelope formula for multilinear functions. J. Glob. Optim. 10(4), 425–437 (1997). https://doi.org/10.1023/A:1008217604285

    Article  MathSciNet  MATH  Google Scholar 

  26. Ryoo, H.S., Sahinidis, N.V.: Analysis of bounds for multilinear functions. J. Glob. Optim. 19(4), 403–424 (2001). https://doi.org/10.1023/A:1011295715398

    Article  MathSciNet  MATH  Google Scholar 

  27. Satyanarayana, A., Wood, R.K.: A linear-time algorithm for computing k-terminal reliability in series-parallel networks. SIAM J. Comput. 14(4), 818–832 (1985). https://doi.org/10.1137/0214057

    Article  MathSciNet  MATH  Google Scholar 

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

    MathSciNet  MATH  Google Scholar 

  29. Sherali, H.D., Alameddine, A.: An explicit characterization of the convex envelope of a bivariate bilinear function over special polytopes. Ann. Oper. Res. 25(1), 197–209 (1990). https://doi.org/10.1007/BF02283695

    Article  MathSciNet  MATH  Google Scholar 

  30. Tardella, F.: On the existence of polyhedral convex envelopes. In: Floudas, C.A., Pardalos, P. (eds.) Frontiers in Global Optimization, pp. 563–573. Springer, Berlin (2004). https://doi.org/10.1007/978-1-4613-0251-3_30

    Chapter  Google Scholar 

  31. Tardella, F.: Existence and sum decomposition of vertex polyhedral convex envelopes. Optim. Lett. 2(3), 363–375 (2008). https://doi.org/10.1007/s11590-007-0065-2

    Article  MathSciNet  MATH  Google Scholar 

  32. Tawarmalani, M., Richard, J.P.P., Xiong, C.: Explicit convex and concave envelopes through polyhedral subdivisions. Math. Program. 138(1), 531–577 (2013). https://doi.org/10.1007/s10107-012-0581-4

    Article  MathSciNet  MATH  Google Scholar 

  33. Tawarmalani, M., Sahinidis, N.V.: Semidefinite relaxations of fractional programs via novel convexification techniques. J. Glob. Optim. 20(2), 133–154 (2001). https://doi.org/10.1023/A:1011233805045

    Article  MathSciNet  MATH  Google Scholar 

  34. Zamora, J.M., Grossmann, I.E.: A branch and contract algorithm for problems with concave univariate, bilinear and linear fractional terms. J. Glob. Optim. 14(3), 217–249 (1999). https://doi.org/10.1023/A:1008312714792

    Article  MathSciNet  MATH  Google Scholar 

Download references

Acknowledgements

The research leading to these results received funding from grants ANID/CONICYT-Fondecyt Regular 1200809 (J.B., E.M.), MathAmsud 19-MATH-03 (J.B.) and ANID/CONICYT-Fondecyt Iniciación 11190515 (G.M.). We would also like to thank Felipe Serrano for helpful discussions and to the anonymous reviewer for their valuable feedback.

Author information

Authors and Affiliations

  1. Faculty of Engineering and Sciences, Universidad Adolfo Ibáñez, Santiago, Chile

    Javiera Barrera & Eduardo Moreno

  2. Institute of Engineering Sciences, Universidad de O’Higgins, Rancagua, Chile

    Gonzalo Muñoz

Authors
  1. Javiera Barrera
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Eduardo Moreno
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Gonzalo Muñoz
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Gonzalo Muñoz.

Ethics declarations

Conflict of interest

The authors have no conflicts of interest to declare that are relevant to the content of this article.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Barrera, J., Moreno, E. & Muñoz, G. Convex envelopes for ray-concave functions. Optim Lett 16, 2221–2240 (2022). https://doi.org/10.1007/s11590-022-01852-2

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11590-022-01852-2

Keywords

Search

Navigation