×

zbMATH — the first resource for mathematics

Convex envelopes for edge-concave functions. (English) Zbl 1099.90045
Summary: Deterministic global optimization algorithms frequently rely on the convex underestimation of nonconvex functions. In this paper we describe the structure of the polyhedral convex envelopes of edge-concave functions over polyhedral domains using geometric arguments. An algorithm for computing the facets of the convex envelope over hyperrectangles in \(\mathbb R^{3}\) is described. Sufficient conditions are described under which the convex envelope of a sum of edge-concave functions may be shown to be equivalent to the sum of the convex envelopes of these functions.

MSC:
90C26 Nonconvex programming, global optimization
90C59 Approximation methods and heuristics in mathematical programming
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Al-Khayyal, F.A., Falk, J.E.: Jointly constrained biconvex programming. Math. Oper. Res. 8 (2), 273–286 (1983) · Zbl 0521.90087
[2] Bertsekas, D.P., Nedić, A., Ozdaglar, A.E.: Convex Analysis and Optimization. Athena Scientific, Belmont, Massachusetts, 2003 · Zbl 1140.90001
[3] Björner, A., Las Vergnas, M., Sturmfels, B., White, N., Ziegler, G.M.: Oriented Matroids. Volume 46 of Encyclopedia of Mathematics and its Applications. Cambridge University Press, 1993
[4] Cottle, R.W.: Minimal triangulations of the 4-cube. Discrete Math. 40, 25–29 (1982) · Zbl 0483.52005
[5] Crama, Y.: Concave extensions for nonlinear 0-1 maximization problems. Math. Program. 61, 53–60 (1993) · Zbl 0796.90040
[6] Floudas, C.A.: Deterministic Global Optimization: Theory, Algorithms and Applications. Kluwer Academic Publishers, 2000
[7] Haiman, M.: A simple and relatively efficient triangulation of the n-cube. Discrete Comput. Geom. 6, 287–289 (1991) · Zbl 0727.68044
[8] Horst, R., Tuy, H.: Global optimization: deterministic approaches. Springer-Verlag, Berlin, 1993. 2nd. rev. edition · Zbl 0704.90057
[9] Hughes, R.B., Anderson, M.R.: Simplexity of the cube. Discrete Mathematics. 158, 99–150 (1999) · Zbl 0862.52005
[10] Hughs, R.B.: Lower bounds on cube simplexity. Discrete Math. 133, 123–138 (1994) · Zbl 0822.90101
[11] Lee, C.W.: Triangulating the d-cube. In: J.W. Goodman (ed.), Discrete Geometry and Convexity. Volume 440 of Ann. N.Y. Acad. Sci., 1985, pp. 205–212 · Zbl 0574.52013
[12] Mara, P.S.: Triangulations for the cube. J. Comb. Theory Ser. A. 20, 170–176 (1976) · Zbl 0341.50001
[13] McCormick, G.P.: Computability of global solutions to factorable nonconvex programs: Part I – convex underestimating problems. Math. Program. 10, 147–175 (1976) · Zbl 0349.90100
[14] Meyer, C.A.: Convex Relaxations and Convex Envelopes for Deterministic Global Optimization. PhD thesis, Princeton University, Princeton, New Jersey, 2004
[15] Meyer, C.A., Floudas, C.A.: Convex envelopes of trilinear monomials with mixed sign domains. In: C.A. Floudas, P.M. Pardalos (eds.), Frontiers in Global Optimization, Dordrecht, 2003. Kluwer Academic Publishers, pp. 327–352 · Zbl 1176.90469
[16] Meyer, C.A., Floudas, C.A. Convex envelopes of trilinear monomials with positive or negative domains. J. Global Optim. 29, 125–155 (2004) · Zbl 1085.90047
[17] Rikun, A.D.: A convex envelope formula for multilinear functions. J. Global Optim. 10, 425–437 (1997) · Zbl 0881.90099
[18] Sallee, J.F.: A triangulation of the n-cube. Discrete Math. 40, 81–86 (1982) · Zbl 0483.52003
[19] Sherali, H.D.: Convex envelopes of multilinear functions over a unit hypercube and over special discrete sets. Acta Mathematica Vietnamica 22, 245–270 (1997) · Zbl 0914.90205
[20] Sherali, H.D., Adam, W. P.: A Reformulation-Linearization Technique for Solving Discrete and Continous Nonconvex Problems. Volume 31, Kluwer Academic Publishers, Dordrecht, 1999
[21] Sherali, H.D., Alameddine, A.: A new reformulation-linearization technique for bilinear programming problems. J. Global Optim. 2, 379–410 (1992) · Zbl 0791.90056
[22] Smith, W.D.: A lower bound on the simplexity of the n-cube via hyperbolic volumes. Europ. J. Combinatorics 21, 131–137 (2000) · Zbl 0982.51015
[23] Tardella, F.: On the existence of polyhedral convex envelopes. In: C.A. Floudas, P.M. Pardalos (eds.), Frontiers in Global Optimization, Dordrecht, 2003. Kluwer Academic Publishers, pp. 563–574 · Zbl 1176.90473
[24] Tawarmalani, M., Ahmed, S., Sahinidis, N.V.: Product disaggregation in global optimization and relaxations of rational programs. Optimization and Engineering 3, 281–303 (2002) · Zbl 1035.90064
[25] Tawarmalani, M., Sahinidis, N.V.: Convex extensions and convex envelopes of lower semi-continuous functions. Math. Program. 2, 247–263 (2002) · Zbl 1065.90062
[26] Ziegler, G.M.: Lectures on Polytopes. Volume 152 of Graduate Texts in Mathematics. Springer Verlag, 1994 · Zbl 0890.60029
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.