Maximal quadratic-free sets

The intersection cut paradigm is a powerful framework that facilitates the generation of valid linear inequalities, or cutting planes, for a potentially complex set S. The key ingredients in this construction are a simplicial conic relaxation of S and an S-free set: a convex zone whose interior does not intersect S. Ideally, such S-free set would be maximal inclusion-wise, as it would generate a deeper cutting plane. However, maximality can be a challenging goal in general. In this work, we show how to construct maximal S-free sets when S is defined by a general quadratic inequality. Our maximal S-free sets are such that efficient separation of a vertex in LP-based approaches to quadratically constrained problems is guaranteed.

1. This citation deals with S being the lattice, but the argument extends trivially to any closed S.

2. The original motivation to look into the projection was to plot high-dimensional examples. These plots suggested that the complement of \({{\,\mathrm{proj}\,}}_{L^\perp } S_{\le 0}\) is formed by two disjoint convex sets. This motivated the definition and study of (5.7) below.

We are indebted to Franziska Schlösser for several inspiring conversations. We would like to thank Stefan Vigerske, Antonia Chmiela, Ksenia Bestuzheva, Nils-Christian Kempke and Joseph Paat for helpful discussions. We would also like to thank the two anonymous reviewers for their valuable feedback. Lastly, we would like to acknowledge the support of the IVADO Institute for Data Valorization for their support through the IVADO Post-Doctoral Fellowship program and to the IVADO-ZIB academic partnership. The described research activities are funded by the German Federal Ministry for Economic Affairs and Energy within the project EnBA-M (ID: 03ET1549D). The work for this article has been (partly) conducted within the Research Campus MODAL funded by the German Federal Ministry of Education and Research (BMBF Grant Numbers 05M14ZAM, 05M20ZBM). Financial support was also provided by the Government of Chile through the FONDECYT Grant Number 11190515.

Authors and Affiliations

1. Universidad de O’Higgins, Rancagua, Chile

   Gonzalo Muñoz

2. Zuse Institute Berlin, Takustr. 7, 14195, Berlin, Germany

   Felipe Serrano

Corresponding author

Correspondence to Gonzalo Muñoz.

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Appendix

1.1 Removing strict convexity matters

In Sect. 4 we construct a maximal \(S^h\)-free set for \(S^h= \{ (x,y) \in \mathbb {R}^{n+m} \,:\,\Vert x\Vert \le \Vert y\Vert \}\) using a concave underestimator of the function \(\Vert x\Vert - \Vert y\Vert \). It is worthwhile to show what happens if we use the same approach with an equivalent description of \(S^h\), namely

Recall we assume we are given \(({{\bar{x}}}, {{\bar{y}}} )\) such that \(\Vert \bar{x}\Vert ^2 > \Vert {{\bar{y}}}\Vert ^2\). A concave underestimator of \(f(x,y) = \Vert x\Vert ^2 - \Vert y\Vert ^2\), tight at \(({\bar{x}}, {\bar{y}})\), is given by \(\Vert {\bar{x}}\Vert ^2 + 2 \Vert {\bar{x}}\Vert (x - {\bar{x}}) - \Vert y\Vert ^2\). This concave underestimator yields the \(S^h\)-free set \(\{ (x,y) \in \mathbb {R}^{n+m} \,:\,\Vert {\bar{x}}\Vert ^2 + 2 \Vert {\bar{x}}\Vert (x - {\bar{x}}) - \Vert y\Vert ^2 \ge 0 \}\). A simple example shows that such an \(S^h\)-free set is not maximal.

Example A.1

The case \(n=m=1\) with \({\bar{x}}= 3\) yields the \(S^h\)-free set

In Fig. 8 we can see that the set is not maximal \(S^h\)-free.

\(S^h\) in Example A.1 (blue) and the \(S^h\)-free set constructed using a concave underestimator of \(\Vert x\Vert ^2 - \Vert y\Vert ^2\) (orange) (colour figure online)

Full size image

The problem seems to be that \(\Vert x\Vert ^2\) is a strictly convex function. Indeed, suppose \(S = \{ x \in \mathbb {R}^n \,:\,f(x) \le 0 \}\) where f is strictly convex. The S-free set obtained via a concave underestimator at \({\bar{x}}\) is \(C = \{ x \in \mathbb {R}^n \,:\,f({\bar{x}}) + \nabla f({\bar{x}})(x - {\bar{x}}) \ge 0\}\). It is not hard to see that the strict convexity of f implies that C is not maximal S-free. The reason is that the linearization of f at \({\bar{x}}\notin S\) will not support the region S. On the other hand, if f is instead sublinear, then any linearization of f will support S. See [43] for an extended discussion on this phenomenon.

1.2 Technical results

Lemma 4.1

Let \(\phi : \mathbb {R}^n \rightarrow \mathbb {R}\) be a sublinear function, \(\lambda \in D_1(0)\), and let

Let \(({\bar{x}}, {\bar{y}}) \in C\) be such that \(\phi \) is differentiable at \({\bar{y}}\) and \(\phi ({\bar{y}}) = \lambda ^{\textsf {T} }{\bar{x}}\). Then \(({\bar{x}}, {\bar{y}})\) exposes the valid inequality \(-\lambda ^{\textsf {T} }x + \nabla \phi ({\bar{y}})^{\textsf {T} }y \le 0\).

Proof

We need to verify both conditions of Definition 3.2. As \(\phi \) is positively homogeneous and differentiable at \({\bar{y}}\), then \(\phi ({\bar{y}}) = \nabla \phi ({\bar{y}}) {\bar{y}}\). Thus, evaluating \(-\lambda ^{\textsf {T} }x + \nabla \phi ({\bar{y}})^{\textsf {T} }y\) at \(({\bar{x}}, {\bar{y}})\) yields \(-\lambda ^{\textsf {T} }{\bar{x}}+ \phi ({\bar{y}})\), which is 0 by hypothesis. Thus the inequality is tight at \(({\bar{x}}, {\bar{y}})\).

Now, let \(\alpha ^{\textsf {T} }x + \gamma ^{\textsf {T} }y \le \delta \) be a non-trivial valid inequality tight at \(({\bar{x}}, {\bar{y}})\). Then, \(\delta = \alpha ^{\textsf {T} }{\bar{x}}+ \gamma ^{\textsf {T} }{\bar{y}}\) and we can rewrite the inequality as \(\alpha ^{\textsf {T} }(x - {\bar{x}}) + \gamma ^{\textsf {T} }(y - {\bar{y}}) \le 0\). Notice that \((\phi (y) \lambda , y) \in C\), thus, \(\alpha ^{\textsf {T} }\lambda (\phi (y) - \phi ({\bar{y}})) + \gamma ^{\textsf {T} }(y - {\bar{y}}) \le 0\) for every \(y \in \mathbb {R}^m\). Subtracting \(\alpha ^{\textsf {T} }\lambda \nabla \phi ({\bar{y}})^{\textsf {T} }(y - {\bar{y}})\) and dividing by \(\Vert y - {\bar{y}}\Vert \) we obtain the equivalent expression

Since \(\phi \) is differentiable at \({\bar{y}}\), the limit when y approaches \({\bar{y}}\) of the left hand side of the above expression is 0. However, one can make the expression \(\frac{y - {\bar{y}}}{\Vert y - {\bar{y}}\Vert }\) converge to any point of \(D_1(0)\). Therefore,

for every \(\beta \in D_1(0)\). This implies that \(\gamma = -\alpha ^{\textsf {T} }\lambda \nabla \phi ({\bar{y}})\). From here we see that \(\alpha \ne 0\) as otherwise \(\alpha = \gamma = 0\) and the inequality would be trivial.

Given that any (x, 0) such that \(\lambda ^{\textsf {T} }x = 0\) belongs to C, it follows that \(\alpha \) is parallel to \(\lambda \), i.e., there exists \(\nu \in \mathbb {R}\) such that \(\alpha = \nu \lambda \). Furthermore, \((\mu \lambda , 0) \in C\) for every \(\mu \ge 0\), implies that \(0 > \alpha ^{\textsf {T} }\lambda = \nu \). Therefore, \(\gamma = - \nu \nabla \phi ({\bar{y}})\) and the inequality reads \(\nu \lambda ^{\textsf {T} }(x - {\bar{x}}) - \nu \nabla \phi ({\bar{y}})^{\textsf {T} }(y - {\bar{y}}) \le 0\). Dividing by \(|\nu |\) and using that \(-\lambda ^{\textsf {T} }x + \nabla \phi ({\bar{y}})^{\textsf {T} }y \le 0\) is tight at \(({\bar{x}}, {\bar{y}})\), we conclude that the inequality can be written as

\(\square \)

Proposition A1

Let \(a,\lambda \in D_1(0)\), \(\lambda \ne \pm a\) and let \(d \in \mathbb {R}^m\) be such that \(\Vert d\Vert \le 1\). The (Lagrangian) dual problem of

is

The optimal solution to (A.1) is \(x : \mathbb {R}^m \rightarrow \mathbb {R}^n\),

The optimal dual solution is \(\theta : \mathbb {R}^m \rightarrow \mathbb {R}_+ \cup \{+\infty \}\),

Here, \(\frac{1}{0} = +\infty \) and \(r + (+\infty ) = +\infty \) for every \(r \in \mathbb {R}\). Moreover, strong duality holds, that is, (A.1) = (A.2), and

Finally, (A.5) holds even if \(\lambda = \pm a\).

Proof

First, note that since \(\lambda \ne \pm a\) and \(\Vert d\Vert \le 1\), x(y) and \(\theta (y)\) are defined for every \(y \in \mathbb {R}^m\). Second, to make some of the calculations that follow more amenable, let \(S(y) = \sqrt{\frac{\Vert y\Vert ^2 - (d^{\textsf {T} }y)^2}{1 - (\lambda ^{\textsf {T} }a)^2}}\). The Lagrangian of (A.1) is \(L : \mathbb {R}^n \times \mathbb {R}_+^2 \rightarrow \mathbb {R}\),

Thus, the dual function is

We have that \(d(\mu , \theta )\) is infinity whenever \(\mu < \Vert \lambda - a \theta \Vert \), and \(\mu \Vert y\Vert - \theta d^{\textsf {T} }y\) otherwise. Hence, the dual problem, \(\min _{\theta , \mu \ge 0} d(\mu , \theta )\), is \(\min \{ \mu \Vert y\Vert - \theta d^{\textsf {T} }y \theta \,:\,\theta \ge 0, \mu \ge \Vert \lambda - a \theta \Vert \}\) which is (A.2).

Let us assume that \(\lambda ^{\textsf {T} }a \Vert y\Vert + d^{\textsf {T} }y \le 0\). Clearly, \(x(y) = \lambda \Vert y\Vert \) is feasible for (A.1). Its objective value is \(\Vert y\Vert \). On the other hand, \(\theta (y) = 0\) is always feasible for (A.1). Its objective value is also \(\Vert y\Vert \), therefore, x(y) is the primal optimal solution and \(\theta (y)\) the dual optimal solution.

Now let us consider the case \(\lambda ^{\textsf {T} }a \Vert y\Vert + d^{\textsf {T} }y > 0\). Let us check that \(\theta (y)\) is dual feasible, that is, \(\theta (y) \ge 0\). Note that, due to the positive homogeneity of \(\theta (y)\) and the condition \(\lambda ^{\textsf {T} }a \Vert y\Vert + d^{\textsf {T} }y > 0\) with respect to y, we can assume without loss of generality that \(\Vert y\Vert = 1\).

Let \(\alpha = \lambda ^{\textsf {T} }a\) and \(\beta = d^{\textsf {T} }y\). Since \(\theta (d) = +\infty \ge 0\) when \(\Vert d\Vert =1\), we can assume that \(y \ne d\) when \(\Vert d\Vert =1\). Note that the same does not occur when \(y = -d\) since we are assuming \(\lambda ^{\textsf {T} }a \Vert y\Vert + d^{\textsf {T} }y > 0\). Thus, \(\alpha , \beta \in (-1,1)\).

We will prove that \(\theta (y) \sqrt{1 - \beta ^2} = \alpha \sqrt{1 - \beta ^2} + \beta \sqrt{1 - \alpha ^2} \ge 0\), which implies that \(\theta (y) \ge 0\). If \(\alpha , \beta \ge 0\), then we are done. As \(\alpha + \beta > 0\), at least one of them must be positive. Let us assume \(\alpha > 0\) and \(\beta < 0\), the other case is analogous. Then, \(\alpha > - \beta \ge 0\). This implies that \(\alpha ^2 > \beta ^2\). Subtracting \(\alpha ^2 \beta ^2\), factorizing and taking square roots we obtain the desired inequality.

Let us compute the value of the dual solution \(\theta (y)\). First, \(y = d\) and \(\Vert d\Vert = 1\), \(\theta (y) = +\infty \), which means that the optimal value is

One way of computing this limit is to multiply and divide the expression by \(\tfrac{\Vert \lambda - \theta a\Vert + \theta }{\theta }\), expand, and simplify the numerator and denominator until one obtains something simple enough.

Now assume \(y \ne d\) if \(\Vert d\Vert = 1\). Observe that \(\Vert \lambda - \theta (y) a\Vert \Vert y\Vert - \theta (y) d^{\textsf {T} }y =\sqrt{\Vert \lambda - \theta (y) a\Vert ^2} \Vert y\Vert - \theta (y) d^{\textsf {T} }y\). We have that

Replacing \(\theta (y)\), we obtain

Therefore,

Let us now check the feasibility of x(y). Let us first check that \(\Vert x(y)\Vert ^2 \le \Vert y\Vert ^2\). We have \(\Vert x(y)\Vert ^2 = S^2(y) - 2 S(y)(d^{\textsf {T} }y + S(y) \lambda ^{\textsf {T} }a) \lambda ^{\textsf {T} }a + (d^{\textsf {T} }y + \lambda ^{\textsf {T} }a S(y))^2\). Expanding and removing common terms yields \(\Vert x(y)\Vert ^2 = S^2(y)(1 - (\lambda ^{\textsf {T} }a)^2) + (d^{\textsf {T} }y)^2 = \Vert y\Vert ^2\). Thus, the first constraint is satisfied.

To check the second constraint just notice that, as \(\Vert a\Vert = 1\), \(a^{\textsf {T} }x(y) = -d^{\textsf {T} }y\).

The primal value of x(y) is

As it coincides with the value of the dual solution, even when \(y = d\) and \(\Vert d\Vert =1\), we conclude that both are optimal.

It only remains to check (A.5) for \(\lambda = \pm a\). If \(\lambda = -a\), then the linear constraint becomes \(\lambda ^{\textsf {T} }x \ge d^{\textsf {T} }y\) and the optimal solution is \(x = \lambda \Vert y\Vert \). If \(\lambda = a\), then the linear constraint becomes \(\lambda ^{\textsf {T} }x \le -d^{\textsf {T} }y\) and \(x = -d^{\textsf {T} }y \lambda \) is then optimal. In both cases (A.5) holds. \(\square \)

Lemma A1

Consider the set

with a, d such that \(\Vert a\Vert > \Vert d\Vert \). Let \(\lambda , \beta \in D_1(0)\) be two vectors satisfying \(\lambda ^{\textsf {T} }a + d^{\textsf {T} }\beta \ge 0\) and consider \(C_{2}\) defined in (5.8).

Then, the face of \(C_{2}\) defined by the valid inequality \(-\lambda ^{\textsf {T} }x + \nabla \phi _{\lambda ,a,d}(\beta )^{\textsf {T} }y \le 0\) does not intersect \(S^g\).

Proof

Recall that in this case \(C_{2}= C_{\phi _{\lambda ,a,d}}\). By contradiction, suppose that \(({\bar{x}}, {\bar{y}}) \in C_{2}\) is such that

The latter equality and the fact that \(\phi _{\lambda ,a,d}\) is sublinear implies \(\phi _{\lambda ,a,d}({\bar{y}}) = \lambda ^{\textsf {T} }{\bar{x}}\). Moreover, \({\bar{x}}\) is a feasible solution of the optimization problem \(\phi _{\lambda ,a,d}({\bar{y}})\), which implies it is an optimal solution.

By Lemma 4.1 we know \(({\bar{x}}, {\bar{y}})\) exposes the valid inequality of \(C_{2}\) given by \(-\lambda ^{\textsf {T} }x + \nabla \phi _{\lambda ,a,d}({\bar{y}})^{\textsf {T} }y \le 0\). By definition of exposing point this means

From (6.9), since W is invertible, we can see that this implies \(\beta = \frac{{\bar{y}}}{\Vert {\bar{y}}\Vert }\). However, as \(\lambda ^{\textsf {T} }a + d^{\textsf {T} }\beta \ge 0\), the optimal solution of in the definition of \(\phi _{\lambda ,a,d}({\bar{y}})\), \(x_0\), must satisfy \(a^{\textsf {T} }x_0 + d^{\textsf {T} }{\bar{y}}= 0\). This contradicts \(\phi _{\lambda ,a,d}({\bar{y}}) = \lambda ^{\textsf {T} }{\bar{x}}\), since \({\bar{x}}\) is an optimal solution but \(a^{\textsf {T} }{\bar{x}}+ d^{\textsf {T} }{\bar{y}}= -1\). \(\square \)

Lemma 6.3

For every \(\beta \in D_1(0)\) and every \(\mu \in \mathbb {R}\), \(\mu > 0\), it holds that \(r(\beta ) = \theta (\mu \beta )\), where \(\theta (\mu \beta )\) is the optimal dual solution of the optimization problem (5.7).

Proof

From (A.4), we see that it suffices to show the result for \(\mu =1\). If \(\lambda ^{\textsf {T} }a + d^{\textsf {T} }\beta \le 0\), \(r(\beta ) = 0 = \theta (\beta )\). Let \(\beta \in D_1(0)\) be such that \(\lambda ^{\textsf {T} }a + d^{\textsf {T} }\beta > 0\). Then,

\(\square \)

Reprints and permissions