×

Explicit convex and concave envelopes through polyhedral subdivisions. (English) Zbl 1273.90165

Authors’ abstract: We derive explicit characterizations of convex and concave envelopes of several nonlinear functions over various subsets of a hyper-rectangle. These envelopes are obtained by identifying polyhedral subdivisions of the hyper-rectangle over which the envelopes can be constructed easily. In particular, we use these techniques to derive, in closed-form, the concave envelopes of concave-extendable supermodular functions and the convex envelopes of disjunctive convex functions.

MSC:

90C26 Nonconvex programming, global optimization
90C11 Mixed integer programming
47N10 Applications of operator theory in optimization, convex analysis, mathematical programming, economics

Software:

LINDO; LINGO
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] Al-Khayyal, F.A.; Falk, J.E., Jointly constrained biconvex programming, Math. Oper. Res., 8, 273-286, (1983) · Zbl 0521.90087
[2] Balas, E.; Mazzola, J.B., Nonlinear 0-1 programming: I, Linearization Tech. Math. Program., 30, 1-21, (1984) · Zbl 0553.90067
[3] Bao, X.; Sahinidis, N.V.; Tawarmalani, M., Multiterm polyhedral relaxations for nonconvex, quadratically constrained quadratic programs, Optim. Methods Softw., 24, 485-504, (2009) · Zbl 1179.90252
[4] Belotti, P.; Lee, J.; Liberti, L.; Margot, F.; Waechter, A., Branching and bounds tightening techniques for non-convex MINLP, Optim. Methods Softw., 24, 597-634, (2009) · Zbl 1179.90237
[5] Benson, H.P., Concave envelopes of monomial functions over rectangles, Naval Res. Logist., 51, 467-476, (2004) · Zbl 1054.90056
[6] Busygin, S.; Prokopyev, O.A.; Pardalos, P.M., Feature selection for consistent biclustering via fractional 0-1 programming, J. Comb. Optim., 10, 7-21, (2005) · Zbl 1123.90073
[7] Ceria, S.; Soares, J., Convex programming for disjunctive convex optimization, Math. Program., 86, 595-614, (1999) · Zbl 0954.90049
[8] Coppersmith, D., Günlük, O., Lee, J., Leung, J.: A polytope for a product of real linear functions in 0/1 variables. IBM Research Report (2003) · Zbl 1001.90064
[9] Crama, Y., Recognition problems for special classes of polynomials in 0-1 variables, Math. Program., 44, 139-155, (1989) · Zbl 0674.90069
[10] Crama, Y., Concave extensions for nonlinear 0-1 maximization problems, Math. Program., 61, 53-60, (1993) · Zbl 0796.90040
[11] Edmonds, J.: Submodular functions, matroids, and certain polyhedra. In: Guy, R., Hanani, H., Sauer, N., Schoenheim, J. (eds.) Combinatorial Structures and Their Applications, pp. 69-87, Gordan and Breach (1970) · Zbl 0268.05019
[12] Grötschel M., Lovász L., Schrijver A.: Geometric Algorithms and Combinatorial Optimization. Princeton Mathematical Series. Springer, Berlin (1988) · Zbl 0634.05001
[13] Hardy G., Littlewood J., Pólya G.: Inequalities. Cambridge University Press, Cambridge (1988) · Zbl 0634.26008
[14] Hiriart-Urruty C., Lemaréchal J.-B.: Fundamentals of Convex Analysis. Springer, Berlin (2001) · Zbl 0998.49001
[15] Hock W., Schittkowski K.: Test Examples for Nonlinear Programming Codes. Springer, Berlin (1981) · Zbl 0452.90038
[16] Horst R., Tuy H.: Global Optimization: Deterministic Approaches, 3rd edn. Springer, Berlin (1996) · Zbl 0867.90105
[17] Lee, C.W.: Subdivisions and triangulations of polytopes. In: Goodman, J.E., O’Rourke, J. (eds.) Handbook of Discrete and Computational Geometry, Chap. 14, CRC Press, Boca Raton (1997) · Zbl 0917.52012
[18] Linderoth, J., A simplicial branch-and-bound algorithm for solving quadratically constrained quadratic programs, Math. Program., 103, 251-282, (2005) · Zbl 1099.90039
[19] LINDO Systems Inc.: LINGO 11.0 optimization modeling software for linear, nonlinear, and integer programming. Available at http://www.lindo.com (2008) · Zbl 1184.90130
[20] Lovász, L.; Grötschel, M. (ed.); Korte, B. (ed.), Submodular functions and convexity, 235-257, (1982), Berlin
[21] 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
[22] Meyer, C.A.; Floudas, C.A., Convex envelopes for edge-concave functions, Math. Program., 103, 207-224, (2005) · Zbl 1099.90045
[23] Nemhauser G.L., Wolsey L.A.: Integer and Combinatorial Optimization. Wiley-interscience Series in Discrete Mathematics and Optimization. Wiley, Newyork (1988)
[24] Richard, J.-P.P.; Tawarmalani, M., Lifted inequalities: a framework for generating strong cuts for nonlinear programs, Math. Program., 121, 61-104, (2010) · Zbl 1184.90130
[25] Rikun, A.D., A convex envelope formula for multilinear functions, J. Glob. Optim., 10, 425-437, (1997) · Zbl 0881.90099
[26] Rockafellar R.T.: Convex Analysis. Princeton Mathematical Series. Princeton University Press, Princeton (1970)
[27] Rodrigues, C.-D., Quadri, D., Michelon, P., Gueye, S.: A t-linearization scheme to exactly solve 0-1 quadratic knapsack problems. In: Proceedings of the European Workshop on Mixed Integer Programming, pp. 251-260. CIRM, Marseille, France (2010) · Zbl 0946.90054
[28] Ryoo, H.S.; Sahinidis, N.V., Analysis of bounds of multilinear functions, J. Glob. Optim., 19, 403-424, (2001) · Zbl 0982.90054
[29] Schrijver A.: Theory of Linear and Integer Programming. Chichester, New York (1986) · Zbl 0665.90063
[30] Schrijver A.: Combinatorial Optimization, Polyhedra and Efficiency. Springer, Heidelberg (2003) · Zbl 1041.90001
[31] Sherali, H.D., Convex envelopes of multilinear functions over a unit hypercube and over special discrete sets, Acta Math. Vietnam., 22, 245-270, (1997) · Zbl 0914.90205
[32] Sherali, H.D.; Wang, H., Global optimization of nonconvex factorable programming problems, Math. Program., 89, 459-478, (2001) · Zbl 0985.90073
[33] Stubbs, R.; Mehrotra, S., A branch-and-cut method for 0-1 mixed convex programming, Math. Program., 86, 515-532, (1999) · Zbl 0946.90054
[34] Tardella, F., Existence and sum decomposition of vertex polyhedral convex envelopes, Optim. Lett., 2, 363-375, (2008) · Zbl 1152.90614
[35] Tawarmalani, M.: Polyhedral Basis and Disjunctive Programming. Working paper (2005) · Zbl 1179.90237
[36] Tawarmalani, M.: Inclusion Certificates and Simultaneous Convexification of Functions. Math. Program. (2010, submitted) · Zbl 1179.90252
[37] Tawarmalani, M.; Richard, J.-P.P.; Chung, K., Strong valid inequalities for orthogonal disjunctions and bilinear covering sets, Math. Program., 124, 481-512, (2010) · Zbl 1198.90298
[38] Tawarmalani, M.; Sahinidis, N.V., Semidefinite relaxations of fractional programs via novel convexification techniques, J. Glob. Optim., 20, 137-158, (2001) · Zbl 1001.90064
[39] Tawarmalani, M.; Sahinidis, N.V., Convex extensions and envelopes of lower semi-continuous functions, Math. Program., 93, 247-263, (2002) · Zbl 1065.90062
[40] Tawarmalani M., Sahinidis N.V.: Convexification and Global Optimization in Continuous and Mixed-Integer Nonlinear Programming. Kluwer, Dordrecht (2002) · Zbl 1031.90022
[41] Tawarmalani, M.; Sahinidis, N.V., Global optimization of mixed-integer nonlinear programs: a theoretical and computational study, Math. Program., 99, 563-591, (2004) · Zbl 1062.90041
[42] Tawarmalani, M.; Sahinidis, N.V., A polyhedral branch-and-cut approach to global optimization, Math. Program., 103, 225-249, (2005) · Zbl 1099.90047
[43] Topkis D.M.: Supermodularity and Complementarity. Princeton University Press, Princeton (1998)
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.