Are McCormick Envelopes exact for the following class of optimization problems?

Question

I have the following optimization problem: \begin{align*} \text{minimize} \quad &\mathbf{c^T x} \\ \text{such that} \quad &\mathbf{x} \in S. \end{align*} Here, $S$ is a polyhedron of the form $S = \{(x_1, x_2, x_3, x_4) \in \mathbb{R}^4 \,:\, \mathbf{Ax} \leq \mathbf{b} , \; x_4 = x_3\cdot x_2 \}$, where $\mathbf{Ax} \leq \mathbf{b}$ are a set of linear constraints. Among other things, the set of constraints $\mathbf{Ax} \leq \mathbf{b}$ set bounds for each $x_i$ to be in a finite range. Namely, within this set of constraints there are constraints of the form $\ell_i \leq x_i \leq u_i$ for all $i=1, 2, 3, 4$. I want to transform this from a nonlinear problem into a linear problem. One promising technique I have found is to use McCormick Envelopes. However, it is not clear to me whether they would work for my problem. Is it the case then that the McCormick envelope of $S$ would give the convex hull of $S$? If McCormick Envelopes are not the way to go, then could someone point me in the right direction?

I have looked at several sources: namely this and this, but those left me more confused. Namely, it is unclear to me if the fact that I have the additional constraints $\mathbf{Ax} \leq \mathbf{b}$ means the McCormick Envelope will no longer be exact.

Answer 1

I think the answer to your question is no under a certain caveat (mentioned below). I'll explain with the help of a figure in 3 dimensions. Let the polyhedral set in your question correspond to the set: \begin{align} 0 \leq x \leq 1 \tag{1} \label{eq:x_bound}\\ 0 \leq y \leq 1 \tag{2} \label{eq:y_bound}\\ 0.5 = z \tag{3} \label{eq:z_bound} \end{align} and let the non-linear constraint correspond to: \begin{equation} z = x\cdot y \tag{4} \label{eq:xy} \end{equation} In the figure below, I have plotted the feasible set for the constraints \eqref{eq:x_bound},\eqref{eq:y_bound} and \eqref{eq:xy}.

Under the caveat that you derive the McCormick envelope only using constraints \eqref{eq:x_bound},\eqref{eq:y_bound} and \eqref{eq:xy} (i.e. you omit the bounds on $z$), then the convex hull reformulation to your problem can be defined as: \begin{equation} S' = \lbrace{ (x, y, z) | \eqref{eq:x_bound}, \eqref{eq:y_bound}, \eqref{eq:z_bound}, z \leq x, \, z \leq y, \, z \geq x +y -1, \, z \geq 0 \rbrace} \end{equation} Note that $S'$ contains the point $(0.5, 0.5, 0.5)$.

Using your notation here, in my example $S$ would correspond to $\lbrace{ (x, y, z) | \eqref{eq:x_bound}, \eqref{eq:y_bound}, \eqref{eq:z_bound}, z = x \cdot y \rbrace}$. Note that $z = 0.5$ in $S$ due to \eqref{eq:z_bound}. If we plot the level set of $z = 0.5$ along x-y axis, the points that appear on the level-set curve are $(1, 0.5)$, $(0.5, 1)$, $(\sqrt{.5}, \sqrt{.5})$ etc., see below.

$xy = 0.5$" />

If we compute the convex hull of the level set curve, I bet the line $x + y = \sqrt{2}-0.00001$ separates $(0.5, 0.5)$ from the level set curve. In other words, what we have managed to show is:

If we project $S$ on to the $x-y$ plane, then there is a line separating $(0.5, 0.5)$ from the projection of $S$

$\implies$ $(0.5, 0.5)$ lies outside the convex full of the projection of $S$

$\implies$ $(0.5, 0.5, z) \, \forall z \in \mathbb{R}$ lies outside the convex hull of $S$.

$\implies$ $S'$ contains a point not included in the convex hull of $S$.

PS: I dont have access to get a 3D plot generation tool.

Answer 2

Let us consider the simpler case when $l_i = 0$ and $u_i = 1$ for each $i \in \{1,\dots,4\}$.

Essentially, what you are asking is if $$\text{conv}(S) = \{\mathbf{x} \in \mathbb{R}^4 : A\mathbf{x} \leq \mathbf{b}, \: x_4 \geq x_2 + x_3 - 1, \: x_4 \leq x_2, \: x_4 \leq x_3\}$$ always holds.

The paper [1] shows that a counterexample is $$S = \{\mathbf{x} \in [0,1]^4 : x_2 + x_3 \leq 1.5, \: x_4 = x_2 x_3\},$$ see equations (5) through (7) therein. It also proposes an approach for strengthening the McCormick relaxation of $S$.

[1] Muller BE, Serrano F, Gleixner A. Using two-dimensional projections for stronger separation and propagation of bilinear terms. SIAM Journal on Optimization. 2020;30(2):1339-65. Available at https://arxiv.org/pdf/1903.05521