×

zbMATH — the first resource for mathematics

Extended formulations for convex envelopes. (English) Zbl 1335.90070
Summary: In this work we derive explicit descriptions for the convex envelope of nonlinear functions that are component-wise concave on a subset of the variables and convex on the other variables. These functions account for more than \(30~\%\) of all nonlinearities in common benchmark libraries. To overcome the combinatorial difficulties in deriving the convex envelope description given by the component-wise concave part of the functions, we consider an extended formulation of the convex envelope based on the Reformulation-Linearization-Technique introduced by H. D. Sherali and W. P. Adams [SIAM J. Discrete Math. 3, No. 3, 411–430 (1990; Zbl 0712.90050)]. Computational results are reported showing that the extended formulation strategy is a useful tool in global optimization.

MSC:
90C26 Nonconvex programming, global optimization
PDF BibTeX Cite
Full Text: DOI
References:
[1] Achterberg, T, SCIP: solving constraint integer programs, Math. Program. Comput., 1, 1-41, (2009) · Zbl 1171.90476
[2] Adams, WP; Sherali, HD, A hierarchy of relaxations leading to the convex hull representation for general discrete optimization problems, Ann. Oper. Res., 140, 21-47, (2005) · Zbl 1091.90060
[3] Anstreicher, KM; Burer, S, Computable representations for convex hulls of low-dimensional quadratic forms, Math. Program., 124, 33-43, (2010) · Zbl 1198.90311
[4] Ballerstein, M., Michaels, D.: Convex underestimation of edge-concave functions by a simultaneous convexification with multi-linear monomials. In: Alonse, D., Hansen, P., Rocha, C. (eds.) Proceedings of the Global Optimization Workshop, pp. 35-38 (2012). Available at http://www.hpca.ual.es/leo/gow/2012-XI-GOW.pdf · Zbl 1238.90104
[5] Bao, X; Sahinidis, NV; Tawarmalani, M, Multiterm polyhedral relaxations for nonconvex, quadratically constrained quadratic programs, Optim. Methods Softw., 24, 485-504, (2009) · Zbl 1179.90252
[6] Barber, CB; Dobkin, DP; Huhdanpaa, H, The quickhull algorithm for convex hulls, ACM Trans. Math. Softw., 22, 469-483, (1996) · Zbl 0884.65145
[7] Belotti, P., Lee, J., Liberti, L., Margot, F., Wächter, A.: Branching and bounds tightening techniques for non-convex MINLP. Optim. Methods Softw. 24(4-5), 597-634 (special issue: Global Optimization) (2009) · Zbl 1179.90237
[8] Burer, S; Letchford, A, On non-convex quadratic programming with box constraints, SIAM J. Optim., 20, 1073-1089, (2009) · Zbl 1201.90146
[9] Bussieck, MR; Drud, AS; Meeraus, A, Minlplib—a collection of test models for mixed-integer nonlinear programming, INFORMS J. Comput., 15, 114-119, (2003) · Zbl 1238.90104
[10] Cafieri, S; Lee, J; Liberti, L, On convex relaxations of quadrilinear terms, J. Glob. Optim., 47, 661-685, (2010) · Zbl 1202.90236
[11] GLOBAL Library: http://www.gamsworld.org/global/globallib.htm · Zbl 1208.93090
[12] Huggins, P; Sturmfels, B; Yu, J; Yuster, D, The hyperdeterminant and triangulations of the 4-cube, Math. Comput., 77, 1653-1679, (2008) · Zbl 1194.52016
[13] IBM: ILOG CPLEX: http://www.ibm.com/software/integration/optimization/cplex (2009-2012)
[14] Jach, M; Michaels, D; Weismantel, R, The convex envelope of (\(n\)-1)-convex functions, SIAM J. Optim., 19, 1451-1466, (2008) · Zbl 1176.90467
[15] Khajavirad, A; Sahidinidis, NV, Convex envelopes of products of convex and component-wise concave functions, J. Glob. Optim., 52, 391-409, (2012) · Zbl 1268.90052
[16] Khajavirad, A; Sahinidis, NV, Convex envelopes generated from finitely many compact convex sets, Math. Program. Ser. A, 137, 371-408, (2013) · Zbl 1284.90055
[17] Laurent, M, A comparison of the Sherali-Adams, lovász-schrijver, and Lasserre relaxations for 0-1 programming, Math. Oper. Res., 28, 470-496, (2003) · Zbl 1082.90084
[18] Lavor, C.: On generating instances for the molecular distance geometry problem. In: Liberti, L., Maculan, N. (eds.) Global Optimization. From Theory to Implementation, pp. 405-414. Springer, Berlin (2006) · Zbl 1100.90034
[19] Lavor, C., Liberti, L., Maculan, N.: Molecular distance geometry problem. In: Floudas, C.A., Pardalos, P.M. (eds.) Encyclopedia of Optimization, 2nd edn, pp. 2304-2311. Springer, Berlin (2009) · Zbl 0712.90050
[20] Locatelli, M.: Convex Envelopes for Quadratic and Polynomial Functions Over Polytopes (manuscript, 11 Mar 2010). Available at http://www.optimization-online.org/DB_FILE/2010/11/2788.pdf (2010) · Zbl 0349.90100
[21] Locatelli, M., Schoen, F.: On the Convex Envelopes and Underestimators For Bivariate Functions (manuscript, 17 Nov 2009). Available at http://www.optimization-online.org/DB_FILE/2009/11/2462.pdf (2009) · Zbl 1268.90052
[22] McCormick, GP, Computability of global solutions to factorable nonconvex programs. I: convex underestimating problems, Math. Program., 10, 147-175, (1976) · Zbl 0349.90100
[23] Meyer, CA; Floudas, CA, Convex envelopes for edge-concave functions, Math. Program., 103, 207-224, (2005) · Zbl 1099.90045
[24] Rockafellar, R.T.: Convex Analysis. Princeton Landmarks in Mathematics. Princeton University Press, Princeton (1970) · Zbl 0884.65145
[25] SCIP: Solving Constraint Integer Programs (2009). Available at http://scip.zib.de · Zbl 1171.90476
[26] Sherali, HD, Convex envelopes of multilinear functions over a unit hypercube and over special sets, Acta Math. Vietnam., 22, 245-270, (1997) · Zbl 0914.90205
[27] Sherali, HD; Adams, WP, A hierarchy of relaxations between the continuous and convex hull representations for zero-one programming problems, SIAM J. Discret. Math., 3, 411-430, (1990) · Zbl 0712.90050
[28] Sherali, HD; Adams, WP, A hierarchy of relaxations and convex hull characterizations for mixed-integer zero-one programming problems, Discret. Appl. Math., 52, 83-106, (1994) · Zbl 0819.90064
[29] Sherali, HD; Dalkiran, E; Desai, J, Enhancing RLT-based relaxations for polynomial programming problems via a new class of v-semidefinite cuts, Comput. Optim. Appl., 52, 483-506, (2012) · Zbl 1250.90092
[30] Sherali, HD; Dalkiran, E; Liberti, L, Reduced RLT representations for nonconvex polynomial programming problems, J. Glob. Optim., 52, 447-469, (2012) · Zbl 1244.90185
[31] Sherali, HD; Tuncbilek, CH, A global optimization algorithm for polynomial programming problems using a reformulation-linearization technique, J. Glob. Optim., 2, 101-112, (1992) · Zbl 0787.90088
[32] Tardella, F.: On the existence of polyedral convex envelopes. In: Floudas, C.A., Pardalos, P.M. (eds.) Frontiers in Global Optimization, pp. 563-573. Kluwer, Dordrecht (2003) · Zbl 1176.90473
[33] Tardella, F, Existence and sum decomposition of vertex polyhedral convex envelopes, Optim. Lett., 2, 363-375, (2008) · Zbl 1152.90614
[34] Tawarmalani, M.: Inclusion Certificates and Simultaneous Convexification of Functions (manuscript, 5 Sept 2010). Available at http://www.optimization-online.org/DB_FILE/2010/09/2722.pdf (2010) · Zbl 1171.90476
[35] Tawarmalani, M; Richard, JPP; Xiong, C, Explicit convex and concave envelopes through polyhedral subdivisions, Math. Program. Ser. A, 138, 531-577, (2013) · Zbl 1273.90165
[36] Tawarmalani, M; Sahinidis, NV, Semidefinite relaxations of fractional programs via novel convexification techniques, J. Glob. Optim., 20, 137-158, (2001) · Zbl 1001.90064
[37] Tawarmalani, M; Sahinidis, NV, Convex extensions and envelopes of lower semi-continuous functions, Math. Program., 93, 247-263, (2002) · Zbl 1065.90062
[38] Tawarmalani, M; Sahinidis, NV, Global optimization of mixed-integer nonlinear programs: a theoretical and computational study, Math. Program., 99, 563-591, (2004) · Zbl 1062.90041
[39] Tawarmalani, M; Sahinidis, NV, A polyhedral branch-and-cut approach to global optimization, Math. Program., 103, 225-249, (2005) · Zbl 1099.90047
[40] Wolfram Research: Mathematica. Wolfram Research, Champaign (2008)
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.