The sparse bounded degree sum-of-squares (sparse-BSOS) hierarchy of Weisser et al. (2017) constructs a sequence of lower bounds for a sparse polynomial optimization problem. Under some assumptions, it is proved by the authors that the sequence converges to the optimal value. In this paper, we modify the hierarchy to deal with problems containing equality constraints directly, without eliminating or replacing them by two inequalities. We also evaluate the sparse-BSOS hierarchy on a well-known bilinear programming problem, called the pooling problem, as well as a discrete-time optimal control problem.

The bounded degree sum-of-squares (BSOS) hierarchy of Lasserre et al. (EURO J Comput Optim 1–31, 2015) 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.