On the 8th of March 2018, an interesting paper on the pooling problem landed on
arxiv. The authors take the pq-formulation, known to have the strongest continuous relaxation, and strengthen it further it by adding convex hull-describing valid inequalities for subproblems -- one for each (product, attibute, pool)-combination. Two of the inequalities are linear, one is conic quadratic, and the final is general convex. We took up the challenge and also cast the latter on conic quadratic form. Here is what we learned.
The inequality is this:
$$
\label{eq:cut}
\overline{\beta}(\overline{\gamma} x - u) + h(y, v) \leq \overline{\beta}(\overline{\gamma} - t),
$$
valid on $y > 0$ when
$$
h(y,v) := A y + B g(y,v),\quad g(y,v) := \frac{yv}{y+v},\quad v \geq 0,
$$
where $A = \overline{\gamma}-\underline{\gamma} > 0$ and $B = \underline{\gamma} < 0$ are coefficients. The challenge is first to put this on conic quadratic form, and then to extend its validity to all of $y \in \mathbb{R}$, while staying tight on $y > 0$. On the first challenge of conic representability, our analysis led to a small surprise, namely, the possibility to represent harmonic means (
see this blog post). The inequality $\eqref{eq:cut}$ is thus representable on $y > 0$ by $\overline{\beta}(\overline{\gamma} x - u) + h \leq \overline{\beta}(\overline{\gamma} - t)$ and
$$
\label{eq:repr:ypos}
h = A y + B g,\quad \left(\begin{matrix}0.5 (y-g)\\ y+v\\ y\end{matrix}\right) \in Q_r^3,\quad v \geq 0.
$$
We stress that the conic form is a proof of convexity. Next is the challenge of extending this representation to be valid on all of $y \in \mathbb{R}$, while staying tight on $y > 0$. That is, as proven in the paper, we need to extend the representation such that $h \leq 0$ on $y \leq 0$. Notably, however, the current representation in $\eqref{eq:repr:ypos}$ fails this criterion as shown by the graph of $h(y, 5)$ where $A=1$ and $B=-3$.
For this task we deploy another reformulation technique which, in lack of better names, may be denoted as
stretching the extremum. The idea is to locally, in the representation of $h(y,v)$, exchange $y$ by $\hat{y} = y + s$ for some amount of stretch $\underline{s} \leq s \leq \overline{s}$. To see the effect of this let $y_{min} = \arg\min_{y \in \mathbb{R}} h(y,v)$, and note that
$$
\min_{s \in \mathbb{R}} h(y+s,v) = \begin{cases}
h(y+\overline{s},v), & {\rm if\ } y_{min} \geq y+\overline{s}, \\
h(y_{min},v), & {\rm if\ } y+\underline{s} \leq y_{min} \leq y+\overline{s},\\
h(y+\underline{s},v), & {\rm if\ } y+\underline{s} \geq y_{min}.
\end{cases}
$$
The visual interpretation of this is that we cut the graph of the function in two parts at $y_{min}$, move the two parts away from each other along the y-axis by amounts determined by $\underline{s}$ and $\overline{s}$, and finally fill in the gap with the extremum value $h(y_{min},v)$. In case of $\eqref{eq:repr:ypos}$ we use $\underline{s} = 0$ and $\overline{s} = \infty$ to allow $h$ to take smaller values of $h(y,v)$ at any higher value of $y$. In the graphed example of $h(y, 5)$ above, we get that the lower bound on $h$ is relaxed to the left of the extremum.
As $h(0,v) = 0$ for all $v \geq 0$, we get the desired property that $h \leq 0$ is possible on $y \leq 0$. In conclusion, the globally valid conic quadratic representation of the convex inequality we started out from, is given by $\overline{\beta}(\overline{\gamma} x - u) + h \leq \overline{\beta}(\overline{\gamma} - t)$ and
$$
h = A \hat{y} + B g,\quad \left(\begin{matrix}0.5 (\hat{y}-g)\\ \hat{y}+v\\ \hat{y}\end{matrix}\right) \in Q_r^3,\quad v \geq 0, \quad \hat{y} \geq y.
$$
