×

zbMATH — the first resource for mathematics

A numerical evaluation of the bounded degree sum-of-squares hierarchy of Lasserre, Toh, and Yang on the pooling problem. (English) Zbl 1422.90039
Summary: The bounded degree sum-of-squares (BSOS) hierarchy of J. B. Lasserre et al. [EURO J. Comput. Optim. 5, No. 1–2, 87–117 (2017; Zbl 1368.90132)] constructs lower bounds for a general polynomial optimization problem with compact feasible set, by solving a sequence of semi-definite programming (SDP) problems. Lasserre, Toh, and Yang prove that these lower bounds converge to the optimal value of the original problem, under some assumptions. In this paper, we analyze the BSOS hierarchy and study its numerical performance on a specific class of bilinear programming problems, called pooling problems, that arise in the refinery and chemical process industries.

MSC:
90C26 Nonconvex programming, global optimization
90C22 Semidefinite programming
Software:
APOGEE
PDF BibTeX Cite
Full Text: DOI
References:
[1] Adhya, N; Tawarmalani, M; Sahinidis, NV, A Lagrangian approach to the pooling problem, Industrial and Engineering Chemistry Research, 38, 1956-1972, (1999)
[2] Alfaki, M. (2012). Models and solution methods for the pooling problem. Ph.D. thesis, University of Bergen · Zbl 1392.90117
[3] Alfaki, M; Haugland, D, Strong formulations for the pooling problem, Journal of Global Optimization, 56, 897-916, (2013) · Zbl 1272.90054
[4] Alfaki, M; Haugland, D, A cost minimization heuristic for the pooling problem, Annals of Operations Research, 222, 73-87, (2014) · Zbl 1303.90110
[5] Ben-Tal, A; Eiger, G; Gershovitz, V, Global minimization by reducing the duality gap, Mathematical Programming, 63, 193-212, (1994) · Zbl 0807.90101
[6] Boyd, S., & Vandenberghe, L. (2004). Convex optimization. Cambridge: Cambridge University Press. · Zbl 1058.90049
[7] Dey, SS; Gupte, A, Analysis of MILP techniques for the pooling problem, Operations Research, 63, 412-427, (2015) · Zbl 1327.90351
[8] Foulds, LR; Haugland, D; Jörnsten, K, A bilinear approach to the pooling problem, Optimization, 24, 165-180, (1992) · Zbl 0817.90073
[9] Frimannslund, L., El Ghami, M., Alfaki, M., & Haugland, D. (2010). Solving the pooling problem with LMI relaxations. In: S. Cafieri, B.G.-Tóth, E. Hendrix, L. Liberti & F. Messine (Eds.), Proceedings of the Toulous Global Optimization Workshop (TOGO), pp. 51-54.
[10] Gupte, A; Ahmed, S; Dey, SS; Cheon, MS, Relaxations and discretizations for the pooling problem, Journal of Global Optimization, 67, 631-669, (2017) · Zbl 1392.90117
[11] Haugland, D, The computational complexity of the pooling problem, Journal of Global Optimization, 64, 199-215, (2016) · Zbl 1360.90258
[12] Haverly, CA, Studies of the behavior of recursion for the pooling problem, ACM SIGMAP Bulletin, 25, 19-28, (1978)
[13] Karuppiah, R; Grossmann, IE, Global optimization for the synthesis of integrated water systems in chemical processes, Computers and Chemical Engineering, 30, 650-673, (2006)
[14] Krivine, JL, Anneaux préordonnés, Journal d’Analyse Mathématique, 12, 307-326, (1964) · Zbl 0134.03902
[15] Lasserre, JB, Global optimization with polynomials and the problem of moments, SIAM Journal on Optimization, 11, 796-817, (2001) · Zbl 1010.90061
[16] Lasserre, JB, Polynomial programming: LP-relaxations also converge, SIAM Journal on Optimization, 15, 383-393, (2005) · Zbl 1114.90086
[17] Lasserre, J. B., Toh, K., & Yang, S. (2015). A bounded degree SOS hierarchy for polynomial optimization. EURO Journal on Computational Optimization, 1-31. doi:10.1007/s13675-015-0050-y. · Zbl 0807.90101
[18] Laurent, M. (2009). Sums of squares, moment matrices and optimization over polynomials. In Emerging applications of algebraic geometry (pp. 157-270). Berlin: Springer. · Zbl 1163.13021
[19] Lofberg, J., & Parrilo, P. A. (2004). From coefficients to samples: A new approach to SOS optimization. In 2004. CDC. 43rd IEEE Conference on Decision and Control, vol. 3, pp 3154-3159. IEEE. · Zbl 1272.90054
[20] Misener, R., & Floudas, Ch. A. (2009). Advances for the pooling problem: Modeling, global optimization, and computational studies. Applied Computational Mathematics, \(8\)(1), 3-22. · Zbl 1188.90287
[21] Misener, R., Thompson, J. P., & Floudas, Ch. A. (2011). APOGEE: Global optimization of standard, generalized, and extended pooling problems via linear and logarithmic partitioning schemes. Computers and Chemical Engineering, 35(5), 876-892.
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.