×

zbMATH — the first resource for mathematics

Error bounds for monomial convexification in polynomial optimization. (English) Zbl 1412.90119
Summary: Convex hulls of monomials have been widely studied in the literature, and monomial convexifications are implemented in global optimization software for relaxing polynomials. However, there has been no study of the error in the global optimum from such approaches. We give bounds on the worst-case error for convexifying a monomial over subsets of \([0,1]^n\). This implies additive error bounds for relaxing a polynomial optimization problem by convexifying each monomial separately. Our main error bounds depend primarily on the degree of the monomial, making them easy to compute. Since monomial convexification studies depend on the bounds on the associated variables, in the second part, we conduct an error analysis for a multilinear monomial over two different types of box constraints. As part of this analysis, we also derive the convex hull of a multilinear monomial over \([-1,1]^n\).

MSC:
90C26 Nonconvex programming, global optimization
65G99 Error analysis and interval analysis
52A27 Approximation by convex sets
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Adams, W., Gupte, A., Xu, Y.: An RLT approach for convexifying symmetric multilinear polynomials. Working paper (2017)
[2] Al-Khayyal, F.; Falk, J., Jointly constrained biconvex programming, Math. Oper. Res., 8, 273-286, (1983) · Zbl 0521.90087
[3] Bao, X.; Khajavirad, A.; Sahinidis, NV; Tawarmalani, M., Global optimization of nonconvex problems with multilinear intermediates, Math. Program. Comput., 7, 1-37, (2015) · Zbl 1317.90243
[4] Belotti, P.; Lee, J.; Liberti, L.; Margot, F.; Wächter, A., Branching and bounds tightening techniques for non-convex MINLP, Optim. Methods Softw., 24, 597-634, (2009) · Zbl 1179.90237
[5] Belotti, P.; Miller, AJ; Namazifar, M., Valid inequalities and convex hulls for multilinear functions, Electron. Notes Discrete Math., 36, 805-812, (2010) · Zbl 1274.90499
[6] Benson, HP, Concave envelopes of monomial functions over rectangles, Naval Res. Logist. (NRL), 51, 467-476, (2004) · Zbl 1054.90056
[7] Boland, N.; Dey, SS; Kalinowski, T.; Molinaro, M.; Rigterink, F., Bounding the gap between the mccormick relaxation and the convex hull for bilinear functions, Math. Program., 162, 523-535, (2017) · Zbl 1384.90073
[8] Buchheim, C.; D’Ambrosio, C., Monomial-wise optimal separable underestimators for mixed-integer polynomial optimization, J. Glob. Optim., 67, 759-786, (2017) · Zbl 1370.90153
[9] Buchheim, C.; Michaels, D.; Weismantel, R., Integer programming subject to monomial constraints, SIAM J. Optim., 20, 3297-3311, (2010) · Zbl 1211.90134
[10] Crama, Y., Concave extensions for nonlinear 0-1 maximization problems, Math. Program., 61, 53-60, (1993) · Zbl 0796.90040
[11] Crama, Y.; Rodríguez-Heck, E., A class of valid inequalities for multilinear 0-1 optimization problems, Discrete Optim., 25, 28-47, (2017) · Zbl 1387.90125
[12] Dalkiran, E.; Sherali, HD, RLT-POS: reformulation-linearization technique-based optimization software for solving polynomial programming problems, Math. Program. Comput., 8, 1-39, (2016) · Zbl 1353.65052
[13] Klerk, E.; Laurent, M., Error bounds for some semidefinite programming approaches to polynomial minimization on the hypercube, SIAM J. Optim., 20, 3104-3120, (2010) · Zbl 1229.90279
[14] Klerk, E.; Laurent, M.; Sun, Z., An error analysis for polynomial optimization over the simplex based on the multivariate hypergeometric distribution, SIAM J. Optim., 25, 1498-1514, (2015) · Zbl 1333.90104
[15] Klerk, E.; Laurent, M.; Sun, Z., Convergence analysis for Lasserres measure-based hierarchy of upper bounds for polynomial optimization, Math. Program., 162, 1-30, (2016)
[16] Pia, A.; Khajavirad, A., A polyhedral study of binary polynomial programs, Math. Oper. Res., 42, 389-410, (2016) · Zbl 1364.90225
[17] Dey, SS; Gupte, A., Analysis of MILP techniques for the pooling problem, Oper. Res., 63, 412-427, (2015) · Zbl 1327.90351
[18] Lasserre, JB, Global optimization with polynomials and the problem of moments, SIAM J. Optim., 11, 796-817, (2001) · Zbl 1010.90061
[19] Lasserre, J.B.: An Introduction to Polynomial and Semi-algebraic Optimization, vol. 52. Cambridge University Press, Cambridge (2015) · Zbl 1320.90003
[20] Laurent, M.: Sums of squares, moment matrices and optimization over polynomials. In: Emerging Applications of Algebraic Geometry, pp. 157-270. Springer (2009) · Zbl 1163.13021
[21] Liberti, L.; Pantelides, CC, Convex envelopes of monomials of odd degree, J. Glob. Optim., 25, 157-168, (2003) · Zbl 1030.90117
[22] Linderoth, J., A simplicial branch-and-bound algorithm for solving quadratically constrained quadratic programs, Math. Program., 103, 251-282, (2005) · Zbl 1099.90039
[23] Locatelli, M., Polyhedral subdivisions and functional forms for the convex envelopes of bilinear, fractional and other bivariate functions over general polytopes, J. Glob. Optim. Online First, (2016) · Zbl 1393.90095
[24] Locatelli, M.; Schoen, F., On convex envelopes for bivariate functions over polytopes, Math. Program., 144, 65-91, (2014) · Zbl 1295.90055
[25] Luedtke, J.; Namazifar, M.; Linderoth, J., Some results on the strength of relaxations of multilinear functions, Math. Program., 136, 325-351, (2012) · Zbl 1286.90117
[26] McCormick, G., Computability of global solutions to factorable nonconvex programs: part I. Convex underestimating problems, Math. Program., 10, 147-175, (1976) · Zbl 0349.90100
[27] Meyer, C.; Floudas, C., Trilinear monomials with mixed sign domains: facets of the convex and concave envelopes, J. Glob. Optim., 29, 125-155, (2004) · Zbl 1085.90047
[28] Meyer, C.; Floudas, C., Convex envelopes for edge-concave functions, Math. Program., 103, 207-224, (2005) · Zbl 1099.90045
[29] Misener, R.; Floudas, CA, Antigone: algorithms for continuous/integer global optimization of nonlinear equations, J. Glob. Optim., 59, 503-526, (2014) · Zbl 1301.90063
[30] Misener, R.; Smadbeck, JB; Floudas, CA, Dynamically generated cutting planes for mixed-integer quadratically constrained quadratic programs and their incorporation into GloMIQO 2, Optim. Methods Softw., 30, 215-249, (2015) · Zbl 1325.90071
[31] Pang, JS, Error bounds in mathematical programming, Math. Program., 79, 299-332, (1997) · Zbl 0887.90165
[32] Rikun, A., A convex envelope formula for multilinear functions, J. Glob. Optim., 10, 425-437, (1997) · Zbl 0881.90099
[33] Ryoo, HS; Sahinidis, NV, Analysis of bounds for multilinear functions, J. Glob. Optim., 19, 403-424, (2001) · Zbl 0982.90054
[34] Sherali, H., Convex envelopes of multilinear functions over a unit hypercube and over special discrete sets, Acta Math. Vietnam., 22, 245-270, (1997) · Zbl 0914.90205
[35] Sherali, HD; Dalkiran, E.; Liberti, L., Reduced RLT representations for nonconvex polynomial programming problems, J. Glob. Optim., 52, 447-469, (2012) · Zbl 1244.90185
[36] Speakman, E.; Lee, J., Quantifying double McCormick, Math. Oper. Res., 42, 1230-1253, (2017) · Zbl 1386.90121
[37] Tawarmalani, M.; Richard, JPP; Xiong, C., Explicit convex and concave envelopes through polyhedral subdivisions, Math. Program., 138, 531-577, (2013) · Zbl 1273.90165
[38] Tawarmalani, M.; Sahinidis, N., Convex extensions and envelopes of lower semi-continuous functions, Math. Program., 93, 247-263, (2002) · Zbl 1065.90062
[39] Tawarmalani, M.; Sahinidis, N., A polyhedral branch-and-cut approach to global optimization, Math. Program., 103, 225-249, (2005) · Zbl 1099.90047
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.