On convex relaxations of quadrilinear terms. (English) Zbl 1202.90236

Cafieri, Sonia; Lee, Jon; Liberti, Leo

J. Glob. Optim. 47, No. 4, 661-685 (2010).

Summary: The best known method to find exact or at least \(\varepsilon \)-approximate solutions to polynomial-programming problems is the spatial branch-and-bound algorithm, which rests on computing lower bounds to the value of the objective function to be minimized on each region that it explores. These lower bounds are often computed by solving convex relaxations of the original program. Although convex envelopes are explicitly known (via linear inequalities) for bilinear and trilinear terms on arbitrary boxes, such a description is unknown, in general, for multilinear terms of higher order. In this paper, we study convex relaxations of quadrilinear terms. We exploit associativity to rewrite such terms as products of bilinear and trilinear terms. Using a general technique, we formally establish the intuitive fact that any relaxation for \(k\)-linear terms that employs a successive use of relaxing bilinear terms (via the bilinear convex envelope) can be improved by employing instead a relaxation of a trilinear term (via the trilinear convex envelope). We present a computational analysis which helps establish which relaxations are strictly tighter, and we apply our findings to two well-studied applications: the molecular distance geometry problem and the Hartree-Fock problem.

MSC:

90C30	Nonlinear programming
90C57	Polyhedral combinatorics, branch-and-bound, branch-and-cut

Keywords:

reformulation; global optimization; spatial branch and bound

Software:

AMPL; CPLEX; cdd; BARON; SNOPT; ROSE

References:

[1]	Adjiman, C.S.: Global optimization techniques for process systems engineering. PhD thesis, Princeton University (1998)
[2]	Adjiman C.S., Dallwig S., Floudas C.A., Neumaier A.: A global optimization method, {\(\alpha\)}BB, for general twice-differentiable constrained NLPs: I. Theoretical advances. Comput. Chem. Eng. 22(9), 1137–1158 (1998)
[3]	Al-Khayyal F.A., Falk J.E.: Jointly constrained biconvex programming. Math. Oper. Res. 8(2), 273–286 (1983) · Zbl 0521.90087
[4]	Avis, D.: lrs. cgm.cs.mcgill.ca/\(\sim\)avis/C/lrs.html
[5]	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), 597–634 (2009) · Zbl 1179.90237
[6]	Crippen G.M., Havel T.F.: Distance Geometry and Molecular Conformation. Wiley, New York (1988) · Zbl 1066.51500
[7]	Floudas, C.: Personal communication (2007)
[8]	Fourer R., Gay D.: The AMPL Book. Duxbury Press, Pacific Grove (2002)
[9]	Fukuda, K.: cdd. www.ifor.math.ethz.ch/\(\sim\)fukuda/cdd_home/cdd.html
[10]	Gill, P.E.: User’s guide for SNOPT version 7. Systems Optimization Laboratory, Stanford University, California (2006)
[11]	Gounaris C.E., Floudas C.A.: Tight convex underestimators for C 2-continuous problems: I. Multivariate functions. J. Glob. Optim. 42(1), 69–89 (2008) · Zbl 1170.90459
[12]	Gounaris C.E., Floudas C.A.: Tight convex underestimators for C 2-continuous problems: I. Univariate functions. J. Glob. Optim. 42(1), 51–67 (2008) · Zbl 1173.90503
[13]	ILOG: ILOG CPLEX 11.0 User’s Manual. (ILOG S.A. Gentilly, France 2008)
[14]	Jach M., Michaels D., Weismantel R.: The convex envelope of (n-1)-convex functions. SIAM J. Optim. 19(3), 1451–1466 (2008) · Zbl 1176.90467
[15]	Lavor, C.: On generating instances for the molecular distance geometry problem. In Liberti and Maculan [22], pp 405–414 · Zbl 1100.90034
[16]	Lavor C., Liberti L., Maculan N.: Computational experience with the molecular distance geometry problem. In: Pintér, J. (eds) Global Optimization: Scientific and Engineering Case Studies, pp. 213–225. Springer, Berlin (2006) · Zbl 1129.90389
[17]	Lavor C., Liberti L., Maculan N.: Molecular distance geometry problem. In: Floudas, C., Pardalos, P. (eds) Encyclopedia of Optimization, pp. 2305–2311. Springer, New York (2008) · Zbl 1136.92037
[18]	Lavor C., Liberti L., Maculan N., Chaer Nascimento M.A.: Solving Hartree–Fock systems with global optimization metohds. Europhys. Lett. 5(77), 50006p1–50006p5 (2007)
[19]	Lee J., Morris W.D. Jr: Geometric comparison of combinatorial polytopes. Discrete Appl. Math. 55(2), 163–182 (1994) · Zbl 0813.90094
[20]	Liberti L. : Comparison of convex relaxations for monomials of odd degree. In: Tseveendorj, I., Pardalos, P.M., Enkhbat, R. (eds) Optimization and Optimal Control, World Scientific, Singapore (2003) · Zbl 1095.90590
[21]	Liberti, L.: Writing global optimization software. In Liberti and Maculan [22], pp 211–262 (2006) · Zbl 1100.90004
[22]	Liberti, L., Maculan, N. (eds.): Global Optimization: From Theory to Implementation. Springer, Berlin (2006) · Zbl 1087.90005
[23]	Liberti L., Pantelides C.C.: Convex envelopes of monomials of odd degree. J. Glob. Optim. 25, 157–168 (2003) · Zbl 1030.90117
[24]	Liberti L., Cafieri S., Tarissan F.: Reformulations in mathematical programming: a computational approach. In: Abraham, A., Hassanien, A.-E., Siarry, P., Engelbrecht, A. (eds) Foundations on Computational Intelligence, vol. 3, Studies in Computational Intelligence volume 203, pp. 153–234. Springer, Berlin (2009)
[25]	Liberti L., Lavor C., Chaer Nascimento M.A., Maculan N.: Reformulation in mathematical programming: an application to quantum chemistry. Discrete Appl. Math. 157(6), 1309–1318 (2009) · Zbl 1173.90494
[26]	Liberti L., Lavor C., Maculan N., Marinelli F.: Double variable neighbourhood search with smoothing for the molecular distance geometry problem. J. Glob. Optim. 43, 207–218 (2009) · Zbl 1169.90470
[27]	Liberti, L., Tsiakis, P., Keeping, B., Pantelides, C.C.: \({oo\mathcal {OPS}}\) . Centre for Process Systems Engineering, Chemical Engineering Department, Imperial College, London, UK (2001)
[28]	McCormick G.P.: Computability of global solutions to factorable nonconvex programs: Part I–Convex underestimating problems. Math. program. 10, 146–175 (1976) · Zbl 0349.90100
[29]	Meyer C.A., Floudas C.A.: Trilinear monomials with positive or negative domains: Facets of the convex and concave envelopes. In: Floudas, C.A., Pardalos, P.M. (eds) Frontiers in Global Optimization, pp. 327–352. Kluwer, Amsterdam (2003) · Zbl 1176.90469
[30]	Meyer C.A., Floudas C.A.: Trilinear monomials with mixed sign domains: facets of the convex and concave envelopes. J. Glob. Optim. 29, 125–155 (2004) · Zbl 1085.90047
[31]	Mosses P. : Denotational semantics. In: Leeuwen, J. (eds) Handbook of Theoretical Computer Science, vol. B, pp. 575–631. Elsevier, Amsterdam (1990) · Zbl 0900.68295
[32]	Neumaier A.: Molecular modeling of proteins and mathematical prediction of protein structure. SIAM Rev 39, 407–460 (1997) · Zbl 0939.92013
[33]	Rikun A.: A convex envelope formula for multilinear functions. J. Glob. Optim. 10(4), 425–437 (1997) · Zbl 0881.90099
[34]	Ryoo H.S., Sahinidis N.V.: A branch-and-reduce approach to global optimization. J. Glob. Optim. 8(2), 107–138 (1996) · Zbl 0856.90103
[35]	Ryoo H.S., Sahinidis N.V.: Analysis of bounds for multilinear functions. J. Glob. Optim. 19, 403–424 (2001) · Zbl 0982.90054
[36]	Sahinidis, N.V., Tawarmalani, M.: BARON 7.2.5: Global Optimization of Mixed-Integer Nonlinear Programs, User’s Manual (2005) · Zbl 1099.90047
[37]	Smith, E.M.B.: on the optimal design of continuous processes. PhD thesis, Imperial College of Science, Technology and Medicine, University of London, October (1996)
[38]	Smith E.M.B., Pantelides C.C.: A symbolic reformulation/spatial branch-and-bound algorithm for the global optimisation of nonconvex MINLPs. Comput. Chem. Eng. 23, 457–478 (1999)
[39]	Tardella F.: Existence and sum decomposition of vertex polyhedral convex envelopes. Optim. Lett. 2, 363–375 (2008) · Zbl 1152.90614
[40]	Tawarmalani M., Sahinidis N.: Convex extensions and envelopes of semi-continuous functions. Math. program. 93(2), 247–263 (2002) · Zbl 1065.90062
[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]	Yoon, J.-M., Gad, Y., Wu, Z.: Mathematical modeling of protein structure using distance geometry. Technical Report TR00-24, Dept. Comput. Applied Maths, Rice University, Houston (2000)