×

Convexification of bilinear forms through non-symmetric lifting. (English) Zbl 1473.90127

Summary: We efficiently treat bilinear forms in the context of global optimization, by applying McCormick convexification and by extending an approach of A. Saxena et al. [Math. Program. 124, No. 1–2 (B), 383–411 (2010; Zbl 1198.90330)] for symmetric quadratic forms to bilinear forms. A key application of our work is in treating “structural convexity” in a symmetric quadratic form.

MSC:

90C26 Nonconvex programming, global optimization

Citations:

Zbl 1198.90330

Software:

quadprogIP
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Al-Khayyal, A.; Falk, JE, Jointly constrained biconvex programming, Math. Oper. Res., 8, 273-286 (1983) · Zbl 0521.90087 · doi:10.1287/moor.8.2.273
[2] 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. Ser. A, 162, 523-535 (2017) · Zbl 1384.90073 · doi:10.1007/s10107-016-1031-5
[3] Brimberg, J.; Hansen, P.; Mladenović, N., A note on reduction of quadratic and bilinear programs with equality constraints, J. Global Optim., 22, 1-4, 39-47 (2002) · Zbl 1045.90043 · doi:10.1023/A:1013838625301
[4] Caprara, A., Locatelli, M., Monaci, M.: Bidimensional packing by bilinear programming. In: Integer Programming and Combinatorial Optimization. Volume 3509 of Lecture Notes in Computer Science, pp. 377-391. Springer, Berlin (2005) · Zbl 1119.90357
[5] Castro, PM; Grossmann, IE, Optimality-based bound contraction with multiparametric disaggregation for the global optimization of mixed-integer bilinear problems, J. Global Optim., 59, 2-3, 277-306 (2014) · Zbl 1298.90058 · doi:10.1007/s10898-014-0162-6
[6] Dey, Santanu S.; Santana, Asteroide; Wang, Yang, New SOCP relaxation and branching rule for bipartite bilinear programs, Optim. Eng., 20, 307-336 (2019) · Zbl 1431.90148 · doi:10.1007/s11081-018-9402-9
[7] Fampa, M.; Lee, J.; Melo, W., On global optimization with indefinite quadratics, EURO J. Comput. Optim., 5, 3, 309-337 (2017) · Zbl 1384.90075 · doi:10.1007/s13675-016-0079-6
[8] Fuentes, V.K., Fampa, M., Lee, J.: Sparse pseudoinverses via LP and SDP relaxations of Moore-Penrose. In: Maturana, S. (ed.) Proceedings of the XVIII Latin-Iberoamerican Conference on Operations Research (CLAIO 2016), pp. 342-350. Instituto Chileno de Investigación Operativa (ICHIO) (2016)
[9] Günlük, O.; Lee, J.; Leung, J.; Lee, J.; Leyffer, S., A polytope for a product of real linear functions in 0/1 variables, Mixed Integer Nonlinear Programming Volume 154 of IMA Journal of Applied Mathematics, 513-529 (2012), New York: Springer, New York · Zbl 1242.90111 · doi:10.1007/978-1-4614-1927-3_18
[10] Gupte, A.; Ahmed, S.; Seok Cheon, M.; Dey, S., Solving mixed integer bilinear problems using MILP formulations, SIAM J. Optim., 23, 2, 721-744 (2013) · Zbl 1300.90021 · doi:10.1137/110836183
[11] Kolodziej, S.; Castro, PM; Grossmann, IE, Global optimization of bilinear programs with a multiparametric disaggregation technique, J. Glob. Optim., 57, 4, 1039-1063 (2013) · Zbl 1282.90137 · doi:10.1007/s10898-012-0022-1
[12] Locatelli, M., Polyhedral subdivisions and functional forms for the convex envelopes of bilinear, fractional and other bivariate functions over general polytopes, J. Glob. Optim., 66, 4, 629-668 (2016) · Zbl 1393.90095 · doi:10.1007/s10898-016-0418-4
[13] Nahapetyan, A.; Pardalos, PM, A bilinear relaxation based algorithm for concave piecewise linear network flow problems, J. Ind. Manag. Optim., 3, 1, 71-85 (2007) · Zbl 1166.90360
[14] Rebennack, S.; Nahapetyan, A.; Pardalos, PM, Bilinear modeling solution approach for fixed charge network flow problems, Optim. Lett., 3, 3, 347-355 (2009) · Zbl 1170.90334 · doi:10.1007/s11590-009-0114-0
[15] Ruiz, JP; Grossmann, IE, Exploiting vector space properties to strengthen the relaxation of bilinear programs arising in the global optimization of process networks, Optim. Lett., 5, 1, 1-11 (2011) · Zbl 1211.90186 · doi:10.1007/s11590-010-0228-4
[16] Saxena, A., Bonami, P., Lee, J.: Disjunctive cuts for non-convex mixed integer quadratically constrained programs. In: Integer Programming and Combinatorial Optimization, 13th International Conference, IPCO 2008, Bertinoro, Italy, May 26-28, 2008, Proceedings, pp. 17-33 (2008) · Zbl 1143.90365
[17] Saxena, A.; Bonami, P.; Lee, J., Convex relaxations of non-convex mixed integer quadratically constrained programs: extended formulations, Math. Program. Ser. B, 124, 383-411 (2010) · Zbl 1198.90330 · doi:10.1007/s10107-010-0371-9
[18] Saxena, A.; Bonami, P.; Lee, J., Convex relaxations of non-convex mixed integer quadratically constrained programs: projected formulations, Math. Program. Ser. B, 130, 359-413 (2010) · Zbl 1229.90144 · doi:10.1007/s10107-010-0340-3
[19] Xia, Wei; Vera, Juan C.; Zuluaga, Luis F., Globally solving nonconvex quadratic programs via linear integer programming techniques, INFORMS J. Comput., 32, 1, 40-56 (2020) · Zbl 07284452 · doi:10.1287/ijoc.2018.0883
[20] Zorn, K.; Sahinidis, NV, Global optimization of general non-convex problems with intermediate bilinear substructures, Optim. Methods Softw., 29, 3, 442-462 (2014) · Zbl 1285.90043 · doi:10.1080/10556788.2013.783032
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.