∎ 11institutetext:  G. Muñoz 22institutetext: Engineering Sciences Institute,
Universidad de O’Higgins, Rancagua, Chile
22email<EMAIL_ADDRESS>33institutetext: J. Paat 44institutetext: Sauder
School of Business, University of British Columbia, Vancouver BC, Canada
44email<EMAIL_ADDRESS>55institutetext: F. Serrano
66institutetext: COPT GmbH, Berlin, Germany
66email<EMAIL_ADDRESS>
# A characterization of maximal homogeneous-quadratic-free sets111An extended
abstract of this article appeared at IPCO 2023 MPS2023 . This full version
contains many new results, including a resolution of a conjecture posed in the
extended abstract.

Gonzalo Muñoz  Joseph Paat  Felipe Serrano

###### Abstract

The intersection cut framework was introduced by Balas in 1971 as a method for
generating cutting planes in integer optimization. In this framework, one uses
a full-dimensional convex $S$-free set, where $S$ is the feasible region of
the integer program, to derive a cut separating $S$ from a non-integral vertex
of a linear relaxation of $S$. Among all $S$-free sets, it is the inclusion-
wise maximal ones that yield the strongest cuts. Recently, this framework has
been extended beyond the integer case in order to obtain cutting planes in
non-linear settings. In this work, we consider the specific setting when $S$
is defined by a homogeneous quadratic inequality. In this ‘quadratic-free’
setting, every function $\Gamma:D^{m}\to D^{n}$, where $D^{k}$ is the unit
disk in $\mathbb{R}^{k}$, generates a representation of a quadratic-free set.
While not every $\Gamma$ generates a maximal quadratic free set, it is the
case that every full-dimensional maximal quadratic free set is generated by
some $\Gamma$. Our main result shows that the corresponding quadratic-free set
is full-dimensional and maximal if and only if $\Gamma$ is non-expansive and
satisfies a technical condition. This result yields a broader class of maximal
$S$-free sets than previously known. Our result stems from a new
characterization of maximal $S$-free sets (for general $S$ beyond the
quadratic setting) based on sequences that ‘expose’ inequalities defining the
$S$-free set.

Keywords. Quadratic programming, cutting planes, intersection cuts, $S$-free
sets

##  1 Introduction

Given a closed set $S\subseteq\mathbb{R}^{d}$, we say that a closed convex set
$C\subseteq\mathbb{R}^{d}$ is $S$-free if its interior
$\operatorname{intr}(C)$ contains no points from $S$. The family of $S$-free
sets forms the foundation of intersection cuts for mathematical programs of
the form

$\min\\{\boldsymbol{c}{}^{\mathsf{T}}\boldsymbol{s}:\ \boldsymbol{s}\in S\\},$
(1)

where $\boldsymbol{c}\in\mathbb{R}^{d}$. The overall intersection cuts
framework operates as follows: if one solves a linear relaxation of (1) and
obtains a vertex $\boldsymbol{s}\not\in S$, then the construction of an
$S$-free set containing $\boldsymbol{s}$ in its interior ensures the
separation of $\boldsymbol{s}$. For a general reference on intersection cuts
including more on the precise derivation of an intersection cut from an
$S$-free set, we point to (CCZ2014, , Chapter 6). Intersection cuts were
introduced by Balas B1971  when $S$ is a lattice and by Tuy T1964  when $S$ is
a reverse convex set. Since then, intersection cuts have been well-studied;
see, e.g., AJ2013 ; ALWW2007 ; ABP2018 ; BCM2019 ; BCM2020 ; CCDLM2014 ;
MKV2016 .

Inclusion-wise maximal $S$-free sets play an important role as they generate
the strongest intersection cuts. Through the lens of mixed-integer duality,
maximal $S$-free sets can also serve as optimality certificates for mixed-
integer programs; see BOW2016 ; BCCWW2017 ; PSS2022 . For the case when $S$ is
a lattice, Lovász L1989  demonstrates that full-dimensional maximal $S$-free
sets are polyhedra with integer points in the relative interior of each facet;
see also A2013 . See BCCZ2010 ; basu2010minimal  for extensions of Lovász’s
result to lattice points in linear subspaces and rational polyhedra.
Connections between maximal $S$-free sets and the Helly number of $S$ have
been established in averkov2013maximal ; conforti2016maximal ; BCCWW2017 .
There are some characterizations of maximality beyond the lattice setting,
e.g., BCM2019 ; BCM2020  characterize various maximal $S$-free sets when $S$
is the set of rank 1 real-valued symmetric matrices.

Muñoz and Serrano MS2020 ; MS2022  are the first to study the setting when $S$
is defined by an arbitrary quadratic inequality. They develop methods for
proving maximality when $S$ is defined by either a single homogeneous or a
single non-homogeneous quadratic inequality. A computational implementation of
the resulting intersection cuts is developed in chmiela2022implementation ,
with favorable results. In this paper, we focus on the homogeneous quadratic
setting

$S=\left\\{\boldsymbol{s}\in\mathbb{R}^{d}:\boldsymbol{s}{}^{\mathsf{T}}\boldsymbol{A}\boldsymbol{s}\leq
0\right\\},$

where $\boldsymbol{A}\in\mathbb{R}^{d\times d}$. We note that maximal $S$-free
sets derived in this setting extend to (not necessarily maximal) sets that can
be used in the non-homogeneous setting as well. Indeed, an $\widehat{S}$-free
set for the non-homogeneous setting

$\widehat{S}:=\left\\{\boldsymbol{s}\in\mathbb{R}^{d}:\boldsymbol{s}{}^{\mathsf{T}}\boldsymbol{A}\boldsymbol{s}+\boldsymbol{g}^{\mathsf{T}}\boldsymbol{s}+h\leq
0\right\\}$

can be constructed by taking an $S^{\prime}$-free set for the homogeneous set

$S^{\prime}:=\left\\{(\boldsymbol{s},z)\in\mathbb{R}^{d}\times\mathbb{R}:\boldsymbol{s}{}^{\mathsf{T}}\boldsymbol{A}\boldsymbol{s}+(\boldsymbol{g}^{\mathsf{T}}\boldsymbol{s})z+hz^{2}\leq
0\right\\}$

and intersecting the $S^{\prime}$-free set with $z=1$. To simplify our
presentation in the homogeneous setting, we follow reductions in MS2020 ;
MS2022  to assume, without significant loss of generality, that the
homogeneous setting has the form

$Q:=\left\\{(\boldsymbol{x},\boldsymbol{y})\in\mathbb{R}^{n}\times\mathbb{R}^{m}:\|\boldsymbol{x}\|\leq\|\boldsymbol{y}\|\right\\},$

where $\|\cdot\|$ is the $\ell_{2}$-norm. We replace $S$ (resp. $S$-free) with
$Q$ (resp. $Q$-free) to highlight that we are looking at quadratic-free sets.
We use this definition of $Q$ for the rest of the paper, and refer to any set
$C$ that is $Q$-free as homogeneous quadratic-free.

Among their results, Muñoz and Serrano prove that a particular homogeneous
quadratic-free set is maximal (MS2022, , Theorem 2.1). One of the motivations
in this paper is to provide more general characterizations of maximal $Q$-free
sets that can be used to generate alternative families of them and,
consequently, new families of cutting planes for quadratically-constrained
problems.

In this paper, we demonstrate that every maximal $Q$-free set has a special
form $C_{\Gamma}$ for a particular function $\Gamma$; see (2). Then, we
characterize maximality of $C_{\Gamma}$ based on properties of $\Gamma$. In
order to derive our characterizations, we also derive a new characterization
of maximality for $S$-free sets when $S$ is an arbitrary closed set.

Notation. Suppose $\mathcal{X}\subseteq\mathbb{R}^{d}$. We use
$\operatorname{conv}(\mathcal{X})$ to denote the convex hull of $\mathcal{X}$.
We use
$\operatorname{cone}(\mathcal{X}):=\\{\sum_{i=1}^{t}\lambda_{i}\boldsymbol{x}^{i}:\
t\in\mathbb{N},\ \lambda_{i}\geq 0\leavevmode\nobreak\
\text{and}\leavevmode\nobreak\
\boldsymbol{x}^{i}\in\mathcal{X}\leavevmode\nobreak\
\forall\leavevmode\nobreak\ i\in\\{1,\dotsc,t\\}\\}$ to denote the conic hull
of $\mathcal{X}$. Similarly, we use
$\overline{\operatorname{conv}}(\mathcal{X})$ and
$\overline{\operatorname{cone}}(\mathcal{X})$ to denote the closed convex hull
and closed conic hull of $\mathcal{X}$, respectively. For background on
convexity including common definitions, we point to R1970 . We use bold font
to denote vectors. We set $D^{d}:=\\{\boldsymbol{x}\in\mathbb{R}^{d}:\
\|\boldsymbol{x}\|=1\\}$.

###  1.1 Contributions

In order to study full-dimensional $Q$-free sets, we consider a special family
of sets parameterized by functions of the form $\Gamma:D^{m}\to D^{n}$. Given
such a $\Gamma$, define the set

$C_{\Gamma}:=\\{(\boldsymbol{x},\boldsymbol{y})\in\mathbb{R}^{n}\times\mathbb{R}^{m}:\Gamma(\boldsymbol{\beta})^{\mathsf{T}}\boldsymbol{x}-\boldsymbol{\beta}^{\mathsf{T}}\boldsymbol{y}\geq
0\leavevmode\nobreak\ \leavevmode\nobreak\ \forall\leavevmode\nobreak\
\boldsymbol{\beta}\in D^{m}\\}.$ (2)

Sets of this form play an important role for us because for every $\Gamma$,
the set $C_{\Gamma}$ is $Q$-free. Indeed, by the Cauchy-Schwarz inequality any
$(\boldsymbol{x},\boldsymbol{y})$ in the interior of $C_{\Gamma}$ satisfies
$\boldsymbol{\beta}^{\mathsf{T}}\boldsymbol{y}<\|\boldsymbol{x}\|$ for all
$\boldsymbol{\beta}\in D^{m}$ which implies that
$\|\boldsymbol{y}\|<\|\boldsymbol{x}\|$. We have observed the following:

######  Remark 1 (Every $C_{\Gamma}$ is $Q$-free)

Let $\Gamma:D^{m}\to D^{n}$ and $C_{\Gamma}$ be defined as in (2). The set
$C_{\Gamma}$ is closed, convex and $Q$-free.

Moreover, not only is $C_{\Gamma}$ $Q$-free for every $\Gamma$, but
interestingly every full-dimensional maximal $Q$-free set can be written in
the ‘standard form’ (2). This constitutes our first main result.

######  Theorem 1.1 (Standard form is necessary for maximality)

Let $C$ be a full-dimensional closed convex maximal $Q$-free set. There exists
a function $\Gamma:D^{m}\to D^{n}$ such that $C=C_{\Gamma}$.

###### Remark 2

(Lower-dimensional maximal $Q$-free sets are always hyperplanes) As with many
of our results, Theorem 1.1 focuses on sets that are full-dimensional. One
reason why we emphasize full-dimensionality is because lower-dimensional
maximal $Q$-free sets are necessarily hyperplanes. Indeed, a lower-dimensional
maximal $Q$-free sets is contained in a hyperplane $H$, which has empty
interior and is therefore trivially $Q$-free.

In light of Theorem 1.1, the question of characterizing full-dimensional
maximal $Q$-free sets can be reduced to characterizing the functions $\Gamma$
corresponding to maximal $C_{\Gamma}$. We demonstrate that a meaningful
property in this direction is the ‘expansivity’ of $\Gamma$.

###### Definition 1

(Expansive, Non-expansive, isometric, strictly non-expansive) Let
$\Gamma:D^{m}\to D^{n}$. Two points
$\boldsymbol{\beta},\boldsymbol{\beta}^{\prime}\in D^{m}$ are

  * •

expansive if
$\|\Gamma(\boldsymbol{\beta})-\Gamma(\boldsymbol{\beta}^{\prime})\|>\|\boldsymbol{\beta}-\boldsymbol{\beta}^{\prime}\|$.

  * •

isometric if
$\|\Gamma(\boldsymbol{\beta})-\Gamma(\boldsymbol{\beta}^{\prime})\|=\|\boldsymbol{\beta}-\boldsymbol{\beta}^{\prime}\|$.

  * •

non-expansive if
$\|\Gamma(\boldsymbol{\beta})-\Gamma(\boldsymbol{\beta}^{\prime})\|\leq\|\boldsymbol{\beta}-\boldsymbol{\beta}^{\prime}\|$.

  * •

strictly non-expansive
$\|\Gamma(\boldsymbol{\beta})-\Gamma(\boldsymbol{\beta}^{\prime})\|<\|\boldsymbol{\beta}-\boldsymbol{\beta}^{\prime}\|$.

The function $\Gamma$ is non-expansive (respectively, strictly non-expansive)
if every pair of distinct points
$\boldsymbol{\beta},\boldsymbol{\beta}^{\prime}\in D^{m}$ are non-expansive
(respectively, strictly non-expansive).

Observe that for a function $\Gamma:D^{m}\to D^{n}$, two points
$\boldsymbol{\beta},\boldsymbol{\beta}^{\prime}\in D^{m}$ are non-expansive
(respectively, expansive, isometric, or strictly non-expansive) if and only if
$\boldsymbol{\beta}{}^{\mathsf{T}}\boldsymbol{\beta}^{\prime}\leq\Gamma(\boldsymbol{\beta})^{\mathsf{T}}\Gamma(\boldsymbol{\beta}^{\prime})$
(respectively,
$\boldsymbol{\beta}{}^{\mathsf{T}}\boldsymbol{\beta}^{\prime}>\Gamma(\boldsymbol{\beta})^{\mathsf{T}}\Gamma(\boldsymbol{\beta}^{\prime})$,
$\boldsymbol{\beta}{}^{\mathsf{T}}\boldsymbol{\beta}^{\prime}=\Gamma(\boldsymbol{\beta})^{\mathsf{T}}\Gamma(\boldsymbol{\beta}^{\prime})$,
or
$\boldsymbol{\beta}{}^{\mathsf{T}}\boldsymbol{\beta}^{\prime}<\Gamma(\boldsymbol{\beta})^{\mathsf{T}}\Gamma(\boldsymbol{\beta}^{\prime})$)
because $\boldsymbol{\beta},\boldsymbol{\beta}^{\prime}\in D^{m}$ and
$\Gamma(\boldsymbol{\beta}),\Gamma(\boldsymbol{\beta}^{\prime})\in D^{n}$.

###### Remark 3

The reader may be familiar with the notion of a contracting function. The
function $\Gamma$ is contracting if there exists $L<1$ such that

$\|\Gamma(\boldsymbol{\beta}^{1})-\Gamma(\boldsymbol{\beta}^{2})\|\leq
L\|\boldsymbol{\beta}^{1}-\boldsymbol{\beta}^{2}\|\quad\forall\
\boldsymbol{\beta}^{1},\boldsymbol{\beta}^{2}\in D^{m}.$

If $\Gamma$ is contracting, then it is strictly non-expansive. However, the
converse is not true. Consider $n=m=2$ and define $\Gamma$ using polar
coordinates: for $\theta\in[0,2\pi]$, we define
$\gamma(\theta)=-\theta(\theta-2\pi)/(4\pi)$ and define $\Gamma$ such that

$\beta(\theta):=(\cos(\theta),\sin(\theta))\mapsto\Gamma(\beta(\theta)):=(\cos(\gamma(\theta)),\sin(\gamma(\theta))).$

$\Gamma$ is strictly non-expansive; we omit a full technical proof of this,
but we illustrate this fact in Figure 1. Let us now argue that $\Gamma$ is not
contracting. Take $\boldsymbol{\beta}^{1}=(1,0)$ and
$\boldsymbol{\beta}^{2}(\theta)=(\cos(\theta),\sin(\theta))$. Note that
$\Gamma(\boldsymbol{\beta}^{1})=(1,0)$ and thus

$\lim_{\theta\to
0}\frac{\Gamma(\boldsymbol{\beta}^{1})^{\mathsf{T}}\Gamma(\boldsymbol{\beta}^{2})}{\boldsymbol{\beta}^{1}{}^{\mathsf{T}}\boldsymbol{\beta}^{2}}=\lim_{\theta\to
0}\frac{\cos(-\theta(\theta-2\pi)/(4\pi))}{\cos(\theta)}=1.$

This implies $\lim_{\theta\to
0}\|\Gamma(\boldsymbol{\beta}^{1})-\Gamma(\boldsymbol{\beta}^{2})\|/\|\boldsymbol{\beta}^{1}-\boldsymbol{\beta}^{2}\|=1$,
and thus $\Gamma$ cannot be contracting.

Figure 1: Plot of
$\beta(\theta_{1})^{\mathsf{T}}\beta(\theta_{2})-\Gamma(\beta(\theta_{1}))^{\mathsf{T}}\Gamma(\beta(\theta_{2}))$
for $\Gamma$ defined in Remark 3. This quantity is non-positive and takes the
value 0 only when $\theta_{1}=\theta_{2}$ (mod $2\pi$), which shows $\Gamma$
is strictly non-expansive.

Our second main result characterizes functions $\Gamma$ that yield full-
dimensional $Q$-free sets.

######  Theorem 1.2 (Characterizing maximality of $C_{\Gamma}$)

Let $\Gamma:D^{m}\to D^{n}$ and define $C_{\Gamma}$ as in (2). The set
$C_{\Gamma}$ is a full-dimensional maximal $Q$-free set if and only if
$\Gamma$ is non-expansive and
$(\boldsymbol{0},\boldsymbol{0})\not\in\operatorname{conv}(\\{(\Gamma(\boldsymbol{\beta}),-\boldsymbol{\beta})\,:\
\boldsymbol{\beta}\in D^{m}\\})$.

The backwards direction in Theorem 1.2 generalizes the work in (MPS2023, ,
Theorem 3), where the additional assumption that $C_{\Gamma}$ is polyhedral is
needed. Furthermore, the result settles the conjecture stated prior to Theorem
3 in their work. The forward direction in Theorem 1.2 is new to this work, and
it allows for a complete characterization of maximality. Note that Theorem 1.2
implies that a discontinuous $\Gamma$ cannot yield a maximal $Q$-free set.

For the case when $\Gamma$ is strictly non-expansive, we can prove that
$C_{\Gamma}$ is a full-dimensional maximal $Q$-free set without any extra
condition. Indeed, if $\Gamma$ is strictly non-expansive, then for each
$\boldsymbol{\beta}^{\prime}$, the point
$(\Gamma(\boldsymbol{\beta}^{\prime}),\boldsymbol{\beta}^{\prime})$ strictly
satisfies every defining inequality for $C_{\Gamma}$ except
$\Gamma(\boldsymbol{\beta}^{\prime}){}^{\top}\boldsymbol{x}-\boldsymbol{\beta}^{\prime}{}^{\mathsf{T}}\boldsymbol{y}\geq
0$; the set $\\{(\Gamma(\boldsymbol{\beta}),\boldsymbol{\beta}):\
\boldsymbol{\beta}\in D^{m}\\}$ is compact because $\Gamma$ is continuous;
thus, there is some $\delta>0$ such that
$\Gamma(\boldsymbol{\beta}){}^{\top}\Gamma(\boldsymbol{\beta}^{\prime})-\boldsymbol{\beta}{}^{\top}\boldsymbol{\beta}^{\prime}\geq\delta$;
hence, the midpoint of distinct points
$\boldsymbol{\beta}^{\prime},\boldsymbol{\beta}^{\prime\prime}\in D^{m}$
satisfies all inequalities strictly and with some slack; thus, $C_{\Gamma}$ is
full-dimensional. In Lemma 2 we show that if $C_{\Gamma}$ is full-dimensional
and $\Gamma$ is continuous, then
$(\boldsymbol{0},\boldsymbol{0})\not\in\operatorname{conv}(\\{(\Gamma(\boldsymbol{\beta}),-\boldsymbol{\beta})\,:\
\boldsymbol{\beta}\in D^{m}\\})$. Together with Theorem 1.2, we have arrived
at the following corollary.

######  Corollary 1 (Strictly non-expansive implies full-dimensionality)

Let $\Gamma:D^{m}\to D^{n}$ and define $C_{\Gamma}$ as in (2). If $\Gamma$ is
strictly non-expansive, then $C_{\Gamma}$ is a full-dimensional maximal
$Q$-free set.

Corollary 1 generalizes (MS2022, , Theorem 2.1), where $\Gamma$ is a constant
function. Example 1 in Section 2 illustrates the construction of a maximal
$Q$-free set using a non-constant $\Gamma$ function that is strictly non-
expansive.

Another result that we find to be of independent interest when studying
$Q$-free polyhedra is the following characterization of polyhedrality
depending on $\Gamma$.

######  Theorem 1.3 (A characterization of polyhedrality)

Let $\Gamma:D^{m}\to D^{n}$ be non-expansive and define $C_{\Gamma}$ as in
(2). $C_{\Gamma}$ is a polyhedron if and only if there is a finite set
$I\subseteq D^{m}$ such that for every $\overline{\boldsymbol{\beta}}\in
D^{m}$ there exists a set $J\subseteq I$ of pairwise isometric points
satisfying $\overline{\boldsymbol{\beta}}\in\operatorname{cone}(J)$. Moreover,
$C_{\Gamma}=\\{(\boldsymbol{x},\boldsymbol{y})\in\mathbb{R}^{n}\times\mathbb{R}^{m}:\Gamma(\boldsymbol{\beta})^{\mathsf{T}}\boldsymbol{x}-\boldsymbol{\beta}^{\mathsf{T}}\boldsymbol{y}\geq
0\leavevmode\nobreak\ \leavevmode\nobreak\ \forall\leavevmode\nobreak\
\boldsymbol{\beta}\in I\\}$.

Examples 3 and 4 in Section 2 show the construction of polyhedral maximal
$Q$-free sets using a non-expansive $\Gamma$. We point out one difference
between maximal $Q$-free polyhedra and maximal $S$-free polyhedra when $S$ is
a lattice. In Lovász’s characterization, the number of facets of a maximal
$S$-free polyhedra is upper bounded by a function of the dimension; this is
not the case for maximal $Q$-free polyhedra, which can have an arbitrary
number of facets (see Example 4 in Section 2). We also note that Theorem 1.3
can be used to construct, starting from a set $I\subseteq D^{m}$, a function
$\Gamma$ that yields a maximal $Q$-free polyhedron (see Example 4 for an
illustration of this).

Underlying the proof of Theorem 1.2 is our final main result, which is a
general characterization of maximality of $S$-free sets. We turn once again to
the case when $S$ is a lattice to motivate this result. Lovász proves that if
$C$ is maximal $S$-free, then $C$ is a polyhedron and every facet $F$ of $C$
contains a lattice point $\boldsymbol{z}^{F}$ in its relative interior. The
point $\boldsymbol{z}^{F}$ is similar to a ‘blocking point’ used to generate
maximal $S$-free sets when $S$ is a mixed-integer set through lifting BDP2019
; CCZ2011 ; DW2010 . In order for $C$ to be $S$-free in the lattice setting,
each $\boldsymbol{z}^{F}$ must be separated from $C$ by a facet defining
inequality. In fact, $F$ is the unique facet separating $\boldsymbol{z}^{F}$
from $C$; thus, in a way $\boldsymbol{z}^{F}$ ‘exposes’ $F$. The notion of
exposing points is considered by Muñoz and Serrano MS2022 , where they argue
that if every inequality defining a $Q$-free set $C$ has an exposing point,
then $C$ is maximal. However, there are maximal $Q$-free sets defined by
inequalities that do not have exposing points; see Example 3 in Section 2. A
generalization of this is the notion of an exposing sequence.

######  Definition 2 (Exposing sequence)

Let $C\subseteq\mathbb{R}^{d}$ be a convex set and let
$\boldsymbol{\alpha}^{\mathsf{T}}\boldsymbol{x}\leq\alpha_{0}$, with
$\boldsymbol{\alpha}\neq\boldsymbol{0}$, be a valid inequality for $C$. A
sequence $(\boldsymbol{x}^{t})_{t=1}^{\infty}$ in $\mathbb{R}^{d}$ is an
exposing sequence for
$\boldsymbol{\alpha}^{\mathsf{T}}\boldsymbol{x}\leq\alpha_{0}$ if
$\lim_{t\to\infty}(\boldsymbol{\delta}^{t},{\delta_{0}^{t}})=(\boldsymbol{\alpha},\alpha_{0})$
for every sequence
$((\boldsymbol{\delta}^{t},{\delta^{t}_{0}}))_{t=1}^{\infty}$ in
${\mathbb{R}}^{d}\times\mathbb{R}$ such that
$\|\boldsymbol{\delta}^{t}\|=\|\boldsymbol{\alpha}\|$,
$\boldsymbol{\delta}^{t}{}^{\mathsf{T}}\boldsymbol{x}\leq\delta^{t}_{0}$ is a
valid inequality for $C$, and
${\boldsymbol{\delta}^{t}}{}^{\mathsf{T}}\boldsymbol{x}^{t}\geq{\delta^{t}_{0}}$
for each $t$.

###### Remark 4

Muñoz and Serrano MS2022  define a notion of ‘exposing sequence at infinity’.
This is more restrictive than Definition 2. Moreover, it can be shown that an
exposing sequence at infinity reduces to an exposing point for $Q$ because $Q$
is a cone.

###### Theorem 1.4

Let $S\subseteq\mathbb{R}^{d}$ be closed, and let $C\subseteq\mathbb{R}^{d}$
be a closed convex full-dimensional $S$-free set. $C$ is a maximal $S$-free
set if and only if there exists a set
$I\subseteq\mathbb{R}^{d}\times\mathbb{R}$ such that

$C=\\{\boldsymbol{x}\in\mathbb{R}^{d}:\boldsymbol{\alpha}^{\mathsf{T}}\boldsymbol{x}\leq\alpha_{0}\leavevmode\nobreak\
\leavevmode\nobreak\ \forall\ (\boldsymbol{\alpha},\alpha_{0})\in I\\}$

and each $(\boldsymbol{\alpha},\alpha_{0})\in I$ has an exposing sequence
$(\boldsymbol{x}^{t})_{t=1}^{\infty}$ in $S$.

The rest of the paper is outlined as follows. We give examples of maximal
$Q$-free sets in Section 2. We prove the general characterization Theorem 1.4
in Section 3. The necessity of the standard form $C_{\Gamma}$ (Theorem 1.1) is
given in Section 4. Preliminary results from convex analysis and about non-
expansive functions are given in Section 5. We prove the characterization of
maximality (Theorem 1.2) in Section 6. We prove Theorem 1.4 in Section 7.
Finally, we discuss future work in Section 8.

##  2 Examples of maximal $Q$-free sets

###### Example 1

Our first example illustrates a non-polyhedral $Q$-free set using Corollary 1.
Consider $n=m=2$. We construct the function $\Gamma$ described in Remark 3:
using polar coordinates, for $\theta\in[0,2\pi]$, we define
$\gamma(\theta)=-\theta(\theta-2\pi)/(4\pi)$ and define $\Gamma$ such that
$\beta(\theta):=(\cos(\theta),\sin(\theta))\mapsto\Gamma(\beta(\theta)):=(\cos(\gamma(\theta)),\sin(\gamma(\theta)))$.
As discussed in Remark 3, $\Gamma$ is strictly non-expansive.

Figure 2: $3$-dimensional slices of the 4-dimensional sets $Q$ (boundary in
orange) and $C_{\Gamma}$ (red) of Example 1.

Therefore, Corollary 1 implies that $C_{\Gamma}$ is a full-dimensional maximal
$Q$-free set. Figure 2 shows a 3-dimensional slice of this 4-dimensional
$C_{\Gamma}$. Note how the non-differentiability of $\gamma$ at 0 translates
into a non-smooth region of the set.

Our next example shows an application of Theorem 1.2 in a non-polyhedral
setting.

###### Example 2

Consider $n=m=2$. Similarly to Remark 3, we construct a function $\Gamma$
using polar coordinates. For $\theta\in[0,2\pi]$, define

$\gamma(\theta)=\left\\{\begin{array}[]{cc}\theta&0\leq\theta\leq\frac{\pi}{2}\\\
\pi-\theta&\frac{\pi}{2}\leq\theta\leq\pi\\\
\theta-\pi&\pi\leq\theta\leq\frac{5\pi}{4}\\\
\frac{1}{3}(2\pi-\theta)&\frac{5\pi}{4}\leq\theta\leq 2\pi\\\
\end{array}\right.$

and define $\Gamma$ such that

$\boldsymbol{\beta}(\theta):=(\cos(\theta),\sin(\theta))\mapsto\Gamma(\boldsymbol{\beta}(\theta)):=(\cos(\gamma(\theta)),\sin(\gamma(\theta))).$

In Figure 3 we show plots of $\gamma$ and of
$\boldsymbol{\beta}(\theta_{1})^{\mathsf{T}}\boldsymbol{\beta}(\theta_{2})-\Gamma(\boldsymbol{\beta}(\theta_{1}))^{\mathsf{T}}\Gamma(\boldsymbol{\beta}(\theta_{2}))$
that illustrate that $\Gamma$ is non-expansive. Note that $\Gamma$ is not
strictly non-expansive: this can be seen in Figure 3(b), as
$\boldsymbol{\beta}(\theta_{1})^{\mathsf{T}}\boldsymbol{\beta}(\theta_{2})-\Gamma(\boldsymbol{\beta}(\theta_{1}))^{\mathsf{T}}\Gamma(\boldsymbol{\beta}(\theta_{2}))=0$
for some values $\theta_{1}\neq\theta_{2}$ (mod $2\pi$). Additionally,
$(\boldsymbol{0},\boldsymbol{0})\not\in\operatorname{conv}(\\{(\Gamma(\boldsymbol{\beta}),-\boldsymbol{\beta})\,:\
\boldsymbol{\beta}\in D^{2}\\})$, as $\gamma(\theta)\in[0,\pi/2]$ and thus
$\Gamma(\boldsymbol{\beta})$ lies on an arc segment in the non-negative
orthant.

(a) Plot of $\gamma$ function in Example 2. This function is a representation
of the $\Gamma$ function in polar coordinates.

(b) Plot of
$\boldsymbol{\beta}(\theta_{1})^{\mathsf{T}}\boldsymbol{\beta}(\theta_{2})-\Gamma(\boldsymbol{\beta}(\theta_{1}))^{\mathsf{T}}\Gamma(\boldsymbol{\beta}(\theta_{2}))$
for $\Gamma$ defined in Example 2. This quantity is non-positive.

Figure 3: Plots of $\gamma$ and
$\boldsymbol{\beta}(\theta_{1})^{\mathsf{T}}\boldsymbol{\beta}(\theta_{2})-\Gamma(\boldsymbol{\beta}(\theta_{1}))^{\mathsf{T}}\Gamma(\boldsymbol{\beta}(\theta_{2}))$
in Example 2 which lead to a maximal quadratic-free set.

Theorem 1.2 implies that $C_{\Gamma}$ is a full-dimensional maximal $Q$-free
set. Figure 4 shows a 3-dimensional slice of this 4-dimensional $C_{\Gamma}$.

Figure 4: $3$-dimensional slices of the 4-dimensional sets $Q$ (boundary in
orange) and $C_{\Gamma}$ (red) of Example 2. Maximality may not be evident in
this picture because maximality is not necessarily preserved when taking
slices.

###### Example 3

Suppose $n=m$ and define $\Gamma(\boldsymbol{\beta})=|\boldsymbol{\beta}|$,
where the absolute value is taken component-wise. The reverse triangle
inequality $||a|-|b||\leq|a-b|$ implies $\Gamma$ is non-expansive. Set
$I=\\{\boldsymbol{e}^{1},\dotsc,\boldsymbol{e}^{m},-\boldsymbol{e}^{1},\dotsc,-\boldsymbol{e}^{m}\\}\subseteq
D^{m}$ where $\boldsymbol{e}^{i}\in\mathbb{Z}^{m}$ is the $i$th standard unit
vector. Each $\boldsymbol{\beta}\in D^{m}$ is in $\operatorname{cone}(J)$ for
a linearly independent set $J\subseteq I$. By definition of $I$ and because
$J$ is linearly independent, each pair of distinct points
$\boldsymbol{\beta},\boldsymbol{\beta}^{\prime}\in J$ is isometric. Theorem
1.3 then ensures that $C_{\Gamma}$ is a polyhedron. Moreover, from Theorem 1.3
we see that

$\displaystyle C_{\Gamma}=$
$\displaystyle\\{(\boldsymbol{x},\boldsymbol{y})\in\mathbb{R}^{n}\times\mathbb{R}^{m}:\Gamma(\boldsymbol{\beta}){}^{\mathsf{T}}\boldsymbol{x}-\boldsymbol{\beta}{}^{\mathsf{T}}\boldsymbol{y}\geq
0\leavevmode\nobreak\ \leavevmode\nobreak\ \forall\leavevmode\nobreak\
\boldsymbol{\beta}\in I\\}$ $\displaystyle=$
$\displaystyle\\{(\boldsymbol{x},\boldsymbol{y})\in\mathbb{R}^{n}\times\mathbb{R}^{m}:x_{i}\geq|y_{i}|\leavevmode\nobreak\
\leavevmode\nobreak\ \forall\ i\in\\{1,\dotsc,m\\}\\}.$

For each $\boldsymbol{\beta}\in D^{m}$, the point $\Gamma(\boldsymbol{\beta})$
is non-negative and strictly positive in at least one component. Hence,
$(\boldsymbol{0},\boldsymbol{0})\not\in\operatorname{conv}(\\{(\Gamma(\boldsymbol{\beta}),-\boldsymbol{\beta})\,:\
\boldsymbol{\beta}\in D^{m}\\})$. Theorem 1.2 then ensures that $C_{\Gamma}$
is a full-dimensional maximal $Q$-free set. Figure 5 illustrates a
$3$-dimensional slice of the $4$-dimensional sets $Q$ and $C_{\Gamma}$
obtained for $n=m=2$.

Figure 5: $3$-dimensional slice of the $4$-dimensional sets $Q$ (boundary in
orange) and $C_{\Gamma}$ (red) obtained when $n=m=2$ in Example 3.

The maximality of this example could not have been proved with the results of
Muñoz and Serrano MS2022 . Indeed, it can be seen that $C_{\Gamma}\cap
Q=\\{(\boldsymbol{x},\boldsymbol{y})\in\mathbb{R}^{n}\times\mathbb{R}^{m}:x_{i}=|y_{i}|\leavevmode\nobreak\
\leavevmode\nobreak\ \forall\ i\in\\{1,\dotsc,m\\}\\}$. Therefore, every facet
of $C_{\Gamma}$ intersects $Q$ and, more importantly, any
$(\boldsymbol{x},\boldsymbol{y})\in C_{\Gamma}\cap Q$ is contained in $m$
different facets of $C_{\Gamma}$. Consequently, there is no exposing point in
$C_{\Gamma}\cap Q$ for any of the facets of $C_{\Gamma}$.

###### Example 4

In this example we show how to construct a polyhedral maximal $Q$-free set
from a starting set of points in $D^{m}$. In Figure 6 (left) consider
$\\{\pm\boldsymbol{e}^{3}\\}$ (in blue),
$\\{\pm\boldsymbol{e}^{1},-\boldsymbol{e}^{2}\\}$ (in red),
$\\{\boldsymbol{e}^{2}\\}$ (in green), and
$\\{-\nicefrac{{1}}{{\sqrt{2}}}\cdot\boldsymbol{e}^{1}\pm\nicefrac{{1}}{{\sqrt{2}}}\cdot\boldsymbol{e}^{2}\\}$
(in black) in $D^{3}$; let $I$ be the set of these $8$ points. We define
$\Gamma$ to map $\\{\pm\boldsymbol{e}^{3}\\}$ to $\boldsymbol{e}^{3}$,
$\\{\pm\boldsymbol{e}^{1},-\boldsymbol{e}^{2}\\}$ to $-\boldsymbol{e}^{2}$,
$\\{\boldsymbol{e}^{2}\\}$ to $-\boldsymbol{e}^{1}$, and
$\\{-\nicefrac{{1}}{{\sqrt{2}}}\cdot\boldsymbol{e}^{1}\pm\nicefrac{{1}}{{\sqrt{2}}}\cdot\boldsymbol{e}^{2}\\}$
to
$-\nicefrac{{1}}{{\sqrt{2}}}\cdot\boldsymbol{e}^{1}+\nicefrac{{1}}{{\sqrt{2}}}\cdot\boldsymbol{e}^{2}$;
see Figure 6 (right). Each $\boldsymbol{\beta}\in D^{3}$ is a conic
combination of at most three points in $I$ that are pairwise isometric.

Figure 6: Representation of $\Gamma$ in the $6$-dimensional set of Example 4.
A point on the left plot represents a $\boldsymbol{\beta}$ that gets mapped by
$\Gamma$ to the point on the right plot of the same color.

One can extend $\Gamma$ from $I$ to a non-expansive function on $D^{3}$
through a conic interpolation; see Lemma 5. Note that the set
$\\{\Gamma(\boldsymbol{\beta}):\ \boldsymbol{\beta}\in D^{3}\\}$ is contained
in a pointed cone. Thus, we also have
$(\boldsymbol{0},\boldsymbol{0})\not\in\operatorname{conv}(\\{(\Gamma(\boldsymbol{\beta}),-\boldsymbol{\beta})\,:\
\boldsymbol{\beta}\in D^{3}\\})$. Theorem 1.2 then implies that

$C_{\Gamma}=\\{(\boldsymbol{x},\boldsymbol{y})\in\mathbb{R}^{3}\times\mathbb{R}^{3}:\Gamma(\boldsymbol{\beta}){}^{\mathsf{T}}\boldsymbol{x}-\boldsymbol{\beta}{}^{\mathsf{T}}\boldsymbol{y}\geq
0\leavevmode\nobreak\ \leavevmode\nobreak\ \forall\ \boldsymbol{\beta}\in
I\\}.$

is maximal $Q$-free. Figure 7 shows a 3-dimensional slice of the 6-dimensional
$C_{\Gamma}$.

Figure 7: $3$-dimensional slices of the 6-dimensional sets $Q$ (boundary in
orange) and $C_{\Gamma}$ (red) obtained using the $\Gamma$ function depicted
in Figure 6. We note that maximality may not be evident in this picture since
maximality is not preserved when taking slices.

The construction in this example can be generalized to an arbitrarily large
set $I$ as long as their conic combinations generate $D^{m}$. This produces a
maximal $Q$-free polyhedra with arbitrarily many facets.

##  3 A proof of Theorem 1.4

The remainder of the paper is dedicated to proving our results. We begin these
proof sections with the maximality criterion in Theorem 1.4. We remark that
this results hold for arbitrary $S$, and not only for the quadratically-
defined $Q$.

######  Proof (Proof of Theorem 1.4)

$(\Leftarrow)$ Assume to the contrary that $C$ is not maximal and let
$K\supsetneq C$ be a convex $S$-free set. There exists
$(\overline{\boldsymbol{\alpha}},\overline{\alpha}_{0})\in I$ such that
$\overline{\boldsymbol{\alpha}}^{\mathsf{T}}\boldsymbol{x}\leq\overline{\alpha}_{0}$
is not valid for $K$. Let $(\boldsymbol{x}^{t})_{t=1}^{\infty}$ be a sequence
in $S$ as in the hypothesis of the theorem. Since $\boldsymbol{x}^{t}\in S$
and $K$ is $S$-free, there exists an inequality
$\boldsymbol{\delta}^{t}{}^{\mathsf{T}}\boldsymbol{x}\leq\delta^{t}_{0}$ such
that $\|\boldsymbol{\delta}^{t}\|=\|\overline{\boldsymbol{\alpha}}\|$, is
valid for $K$, and
$\boldsymbol{\delta}^{t}{}^{\mathsf{T}}\boldsymbol{x}^{t}\geq{\delta^{t}_{0}}$.
The inequality
$\boldsymbol{\delta}^{t}{}^{\mathsf{T}}\boldsymbol{x}\leq\delta^{t}_{0}$ is
valid for $C$ because $C\subsetneq K$. By the definition of exposing sequence,
we have
$\lim_{t\to\infty}(\boldsymbol{\delta}^{t},\delta^{t}_{0})=(\overline{\boldsymbol{\alpha}},\overline{\alpha}_{0})$,
so
$\overline{\boldsymbol{\alpha}}{}^{\mathsf{T}}\boldsymbol{x}\leq\overline{\alpha}_{0}$
is valid for $K$. This is a contradiction.

$(\Rightarrow)$ Let $C^{\circ}\subseteq\mathbb{R}^{d}\times\mathbb{R}$ be the
polar of $C$, i.e., the set of coefficients corresponding to valid
inequalities for $C$:

$C=\\{\boldsymbol{x}\in\mathbb{R}^{d}:\boldsymbol{\alpha}{}^{\mathsf{T}}\boldsymbol{x}\leq\alpha_{0}\leavevmode\nobreak\
\forall\leavevmode\nobreak\ (\boldsymbol{\alpha},\alpha_{0})\in C^{\circ}\\}.$

The set $C^{\circ}$ is a closed convex cone, and $C^{\circ}$ is pointed
because $C$ is full-dimensional. Since $C^{\circ}$ is a closed pointed cone,
there is a set $I\subseteq C^{\circ}$ generating the extreme rays of
$C^{\circ}$ and $C^{\circ}=\operatorname{cone}(I)$; see, e.g., (R1970, ,
Theorem 18.5). Hence,

$C=\left\\{\boldsymbol{x}\in\mathbb{R}^{d}:\boldsymbol{\alpha}{}^{\mathsf{T}}\boldsymbol{x}\leq\alpha_{0}\leavevmode\nobreak\
\leavevmode\nobreak\ \forall\leavevmode\nobreak\
(\boldsymbol{\alpha},\alpha_{0})\in I\right\\}.$

Without loss of generality, we can scale each
$(\boldsymbol{\alpha},\alpha_{0})\in I$ by a positive number so that
$\|(\boldsymbol{\alpha},\alpha_{0})\|=1$. Let
$(\overline{\boldsymbol{\alpha}},\overline{\alpha}_{0})\in I$ and define

$\displaystyle K_{t}$
$\displaystyle:=\left\\{(\boldsymbol{\alpha},{\alpha}_{0})\in\mathbb{R}^{d}\times\mathbb{R}:\
\|(\overline{\boldsymbol{\alpha}},\overline{\alpha}_{0})-(\boldsymbol{\alpha},{\alpha}_{0})\|<\frac{1}{t}\right\\},$
$\displaystyle C_{t}$
$\displaystyle:=\left\\{\boldsymbol{x}\in\mathbb{R}^{d}:\boldsymbol{\alpha}{}^{\mathsf{T}}\boldsymbol{x}\leq\alpha_{0}\leavevmode\nobreak\
\forall\leavevmode\nobreak\ (\boldsymbol{\alpha},\alpha_{0})\in I\setminus
K_{t}\right\\}.$

We proceed to show that $C\subsetneq C_{t}$. Assume to the contrary that
$C=C_{t}$. This implies that
$I\subseteq\overline{\operatorname{cone}}(I\setminus K_{t})$. In particular,
$(\overline{\boldsymbol{\alpha}},\overline{\alpha}_{0})\in\overline{\operatorname{cone}}(I\setminus
K_{t})$. Thus, by Carathéodory’s Theorem, we can write

$(\overline{\boldsymbol{\alpha}},\overline{\alpha}_{0})=\lim_{s\to\infty}\sum_{i=1}^{d+1}\lambda_{[i,s]}(\boldsymbol{\alpha}_{[i,s]},\alpha_{[0,i,s]})$

where each $\lambda_{[i,s]}\geq 0$ and
$(\boldsymbol{\alpha}_{[i,s]},\alpha_{[0,i,s]})\in I\setminus K_{t}$. Given
that each point in $I$ has norm $1$ and $I\setminus K_{t}$ is closed, we may
assume that $(\boldsymbol{\alpha}_{[i,s]},\alpha_{[0,i,s]})$ converges to a
norm-1 vector $(\boldsymbol{\alpha}_{[i]},\alpha_{[0,i]})\in
C^{\circ}\setminus K_{t}$ for each $i$. Furthermore, we assume that
$\lambda_{[i,s]}$ converges to $\lambda_{i}\geq 0$ for each $i$; otherwise,
say $\lambda_{[1,s]}$ diverges to $\infty$, then

$\displaystyle\boldsymbol{0}=\lim_{s\to\infty}\frac{1}{\lambda_{[1,s]}}(\overline{\boldsymbol{\alpha}},\overline{\alpha}_{0})$
$\displaystyle=\lim_{s\to\infty}\frac{1}{\lambda_{[1,s]}}\sum_{i=1}^{d+1}\lambda_{[i,s]}(\boldsymbol{\alpha}_{[i,s]},\alpha_{[0,i,s]})$
$\displaystyle=(\boldsymbol{\alpha}_{[1]},\alpha_{[0,1]})+\lim_{s\to\infty}\sum_{i=2}^{d+1}\frac{\lambda_{[i,s]}}{\lambda_{[1,s]}}(\boldsymbol{\alpha}_{[i,s]},\alpha_{[0,i,s]}).$

However, then
$\lim_{s\to\infty}\sum_{i=2}^{d+1}\frac{\lambda_{[i,s]}}{\lambda_{[1,s]}}(\boldsymbol{\alpha}_{[i,s]},\alpha_{[0,i,s]})=-(\boldsymbol{\alpha}_{[1]},\alpha_{[0,1]})$,
implying that $C^{\circ}$ is not pointed, which is a contradiction. Hence,

$(\overline{\boldsymbol{\alpha}},\overline{\alpha}_{0})=\lim_{s\to\infty}\sum_{i=1}^{d+1}\lambda_{[i,s]}(\boldsymbol{\alpha}_{[i,s]},\alpha_{[0,i,s]})=\sum_{i=1}^{d+1}\lambda_{i}(\boldsymbol{\alpha}_{i},\alpha_{[0,i]}),$

where each $(\boldsymbol{\alpha}_{i},\alpha_{[0,i]})$ is in
$C^{\circ}\setminus K_{t}$. However, since $K_{t}$ is a ball of positive
radius, this means that
$(\overline{\boldsymbol{\alpha}},\overline{\alpha}_{0})$ does not generate an
extreme ray of $C^{\circ}$. Therefore, $C\subsetneq C_{t}$.

Due to the maximality of $C$, there is a vector
$\boldsymbol{x}^{t}\in\operatorname{intr}(C_{t})\cap S$. If
$\boldsymbol{\delta}^{t}{}^{\mathsf{T}}\boldsymbol{x}\leq\delta^{t}_{0}$ is
valid for $C$ and
${\boldsymbol{\delta}^{t}}{}^{\mathsf{T}}\boldsymbol{x}^{t}\geq{\delta^{t}_{0}}$,
then $(\boldsymbol{\delta}^{t},{\delta^{t}_{0}})\in K_{t}$. Thus,
$\lim_{t\to\infty}(\boldsymbol{\delta}^{t},{\delta^{t}})=(\overline{\boldsymbol{\alpha}},\overline{\alpha}_{0})$.

##  4 A proof of Theorem 1.1

We use the following theorem from Rockafellar R1970 , albeit slightly
rephrased.

######  Theorem 4.1 (Theorem 17.3 from R1970 )

Let $S^{*}\subseteq\mathbb{R}^{d}\times\mathbb{R}$ be a non-empty compact set
of vectors $(\boldsymbol{x}^{*},\mu^{*})\in\mathbb{R}^{d}\times\mathbb{R}$,
and set

$B:=\left\\{\boldsymbol{x}\in\mathbb{R}^{d}\,:\,\boldsymbol{x}{}^{\top}\boldsymbol{x}^{*}\leq\mu^{*}\quad\forall\
(\boldsymbol{x}^{*},\mu^{*})\in S^{*}\right\\}.$

Suppose $B$ is full-dimensional and $(\boldsymbol{0},0)\not\in S^{*}$. Then,
for a given vector $(\widehat{\boldsymbol{x}},\widehat{\mu})$, where
$\widehat{\boldsymbol{x}}\neq\boldsymbol{0}$, the inequality
$\boldsymbol{x}{}^{\top}\widehat{\boldsymbol{x}}\leq\widehat{\mu}$ is valid
for $B$ if and only if there exist vectors
$(\boldsymbol{x}^{*}_{1},\mu^{*}_{1}),\dotsc,(\boldsymbol{x}^{*}_{k},\mu^{*}_{k})\in
S^{*}$ with $k\leq d$, and $\lambda_{1},\dotsc,\lambda_{k}\geq 0$ such that

$\widehat{\boldsymbol{x}}=\sum_{i=1}^{k}\lambda_{i}\boldsymbol{x}^{*}_{i}\quad\text{and}\quad\sum_{i=1}^{k}\lambda_{i}\mu^{*}_{i}\leq\mu^{*}.$

###### Remark 5

Theorem 4.1 has a slight difference with the statement of Theorem 17.3 from
R1970 : the latter is missing the assumption $(\boldsymbol{0},0)\not\in
S^{*}$. This assumption is a subtle detail which is implicitly used in the
proof and in all the discussions leading to Theorem 17.3. Moreover, one can
prove that without it, the theorem does not hold.

Consider $d=2$ and
$S^{*}=\\{(\cos(\theta)-1,\sin(\theta),0)\,:\,\theta\in[0,\pi]\\}$, which is
compact. Note that $\theta=0$ implies $(\boldsymbol{0},0)\in S^{*}$. It can be
shown that in this case $B=\\{(x_{1},x_{2})\,:\,x_{1}\geq 0,\,x_{2}\leq 0\\}$
and thus $B$ is full-dimensional. The valid inequality $x_{2}\leq 0$ can be
obtained by noting that

$\frac{(\cos(\theta)-1)}{\theta}x_{1}+\frac{\sin(\theta)}{\theta}x_{2}\leq 0$

is always valid for $\theta>0$, and then taking limit $\theta\to 0$. However,
$(0,1)$ cannot be obtained as a conic combination of vectors of the form
$(\cos(\theta)-1,\sin(\theta))$ $\theta\in[0,\pi]$.

###### Remark 6

We also note that in Theorem 4.1 we can replace the requirements “$B$ is full-
dimensional and $(\boldsymbol{0},0)\not\in S^{*}$” simply with
“$(\boldsymbol{0},0)\not\in\operatorname{conv}(S^{*})$”. The proof is exactly
the same, as the first two assumptions are used to prove the second. We use of
this subtle variation in one proof below.

To prove Theorem 1.1, we write $Q=\bigcup_{\boldsymbol{\beta}\in
D^{m}}Q_{\boldsymbol{\beta}}$, where

$\displaystyle Q_{\boldsymbol{\beta}}:\,=$
$\displaystyle\left\\{(\boldsymbol{x},\boldsymbol{y})\in\mathbb{R}^{n}\times\mathbb{R}^{m}:\|\boldsymbol{x}\|-\boldsymbol{\beta}{}^{\mathsf{T}}\boldsymbol{y}\leq
0\right\\}$ $\displaystyle=$
$\displaystyle\left\\{(\boldsymbol{x},\boldsymbol{y})\in\mathbb{R}^{n}\times\mathbb{R}^{m}:\boldsymbol{\gamma}{}^{\mathsf{T}}\boldsymbol{x}-\boldsymbol{\beta}{}^{\mathsf{T}}\boldsymbol{y}\leq
0\leavevmode\nobreak\ \leavevmode\nobreak\ \forall\ \boldsymbol{\gamma}\in
D^{n}\right\\}.$ (3)

Note that each $Q_{\boldsymbol{\beta}}$ is convex. The following lemma is a
direct consequence of Theorem 4.1.

###### Lemma 1

Let $\boldsymbol{\beta}\in D^{m}$. Every tight valid inequality for
$Q_{\boldsymbol{\beta}}$ has the form (possibly after scaling by a positive
number)
$\boldsymbol{\gamma}{}^{\mathsf{T}}\boldsymbol{x}-\boldsymbol{\beta}{}^{\mathsf{T}}\boldsymbol{y}\leq
0$ for some $\|\boldsymbol{\gamma}\|\leq 1$.

We remark that this lemma does not follow immediately from (3); Lemma 1 refers
to _every_ tight valid inequality, which, in principle, can include
inequalities not explicitly considered in the description (3).

We now proceed to the main proof of this section.

######  Proof (of Theorem 1.1)

For each $\boldsymbol{\beta}\in D^{m}$, there is a hyperplane separating $C$
and $Q_{\boldsymbol{\beta}}$ because both sets are convex and $C$ is $Q$-free.
For each $\boldsymbol{\beta}\in D^{m}$, by Lemma 1 we can take the
corresponding inequality to be
$\boldsymbol{\gamma}^{\mathsf{T}}\boldsymbol{x}-\boldsymbol{\beta}^{\mathsf{T}}\boldsymbol{y}\geq
0$ with $\|\boldsymbol{\gamma}\|\leq 1$. From this discussion, it follows that
we can define a function
$\gamma:D^{m}\to\\{\boldsymbol{x}\in\mathbb{R}^{n}:\|\boldsymbol{x}\|\leq
1\\}$ such that for each $\boldsymbol{\beta}$, we have that
$\gamma(\boldsymbol{\beta})^{\mathsf{T}}\boldsymbol{x}-\boldsymbol{\beta}^{\mathsf{T}}\boldsymbol{y}\geq
0$ is valid for $C$ and separates $Q_{\boldsymbol{\beta}}$ from $C$. Thus,

$C\subseteq\left\\{(\boldsymbol{x},\boldsymbol{y})\in\mathbb{R}^{n}\times\mathbb{R}^{m}:\gamma(\boldsymbol{\beta})^{\mathsf{T}}\boldsymbol{x}-\boldsymbol{\beta}^{\mathsf{T}}\boldsymbol{y}\geq
0\leavevmode\nobreak\ \leavevmode\nobreak\ \forall\leavevmode\nobreak\
\boldsymbol{\beta}\in D^{m}\right\\}.$ (4)

Each $Q_{\boldsymbol{\beta}}$ is separated from the set on the right-hand side
of (4), implying that it is $Q$-free. By the maximality of $C$, we have that
(4) is an equality.

We now show that we can further restrict $\gamma(\boldsymbol{\beta})$ to have
unit norm since $C$ is a maximal $Q$-free set222Note that Lemma 1 does not
directly imply that $\gamma(\boldsymbol{\beta})$ can be assumed to have unit
norm. Moreover, one could produce a (not necessarily maximal) $Q$-free set
with $\gamma$ that satisfies $\|\gamma(\boldsymbol{\beta})\|<1$ for some
$\boldsymbol{\beta}$.. For this, consider the pair of valid inequalities for
$C$:

$\gamma(\boldsymbol{\beta})^{\mathsf{T}}\boldsymbol{x}-\boldsymbol{\beta}^{\mathsf{T}}\boldsymbol{y}\geq
0\qquad\text{and}\qquad\gamma(-\boldsymbol{\beta})^{\mathsf{T}}\boldsymbol{x}-(-\boldsymbol{\beta})^{\mathsf{T}}\boldsymbol{y}\geq
0$

for each $\boldsymbol{\beta}\in D^{m}$. Multiplying the first inequality by
$\lambda+1$, the second one by $\lambda$ with $\lambda\geq 0$, and adding them
we obtain the following valid inequality for $C$:

$\big{(}\lambda(\gamma(\boldsymbol{\beta})+\gamma(-\boldsymbol{\beta}))+\gamma(\boldsymbol{\beta})\big{)}{}^{\mathsf{T}}\boldsymbol{x}-\boldsymbol{\beta}^{\mathsf{T}}\boldsymbol{y}\geq
0.$

Notice that
$\gamma(\boldsymbol{\beta})+\gamma(-\boldsymbol{\beta})\neq\boldsymbol{0}$ for
each $\boldsymbol{\beta}$ as otherwise
$-(\gamma(-\boldsymbol{\beta})^{\mathsf{T}}\boldsymbol{x}-(-\boldsymbol{\beta})^{\mathsf{T}}\boldsymbol{y})=\gamma(\boldsymbol{\beta})^{\mathsf{T}}\boldsymbol{x}-\boldsymbol{\beta}^{\mathsf{T}}\boldsymbol{y}\geq
0$ is valid for $C$ implying that $C$ satisfies an equation and is not full-
dimensional; this is a contradiction. So, there exists
$\lambda(\boldsymbol{\beta})\geq 0$ such that
$\|\lambda(\boldsymbol{\beta})(\gamma(\boldsymbol{\beta})+\gamma(-\boldsymbol{\beta}))+\gamma(\boldsymbol{\beta})\|=1$.
Define $\Gamma:D^{m}\to D^{n}$ by

$\Gamma(\boldsymbol{\beta}):=\lambda(\boldsymbol{\beta})(\gamma(\boldsymbol{\beta})+\gamma(-\boldsymbol{\beta}))+\gamma(\boldsymbol{\beta}).$

Therefore,

$C\subseteq\left\\{(\boldsymbol{x},\boldsymbol{y})\in\mathbb{R}^{n}\times\mathbb{R}^{m}:\Gamma(\boldsymbol{\beta})^{\mathsf{T}}\boldsymbol{x}-\boldsymbol{\beta}^{\mathsf{T}}\boldsymbol{y}\geq
0\leavevmode\nobreak\ \leavevmode\nobreak\ \forall\leavevmode\nobreak\
\boldsymbol{\beta}\in D^{m}\right\\}=C_{\Gamma}.$ (5)

Again using that the right-hand side in (5) is $Q$-free and $C$ is maximal, we
conclude that (5) is an equality.

##  5 Preliminary lemmata

In this section we collect a variety of lemmata to prove our characterization
of maximality (Theorem 1.2). Each lemma is classified as a result from convex
analysis or about non-expansive functions.

###  5.1 Preliminaries about convexity

Many of the results in this subsection follow from known results in convexity
theory. When proving these results, we often use the fact that if $\Gamma$ is
continuous, then $\\{(\Gamma(\boldsymbol{\beta}),-\boldsymbol{\beta})\
:\boldsymbol{\beta}\in D^{m}\\}$ is compact. Consequently,

$\operatorname{conv}(\\{(\Gamma(\boldsymbol{\beta}),-\boldsymbol{\beta})\
:\boldsymbol{\beta}\in
D^{m}\\})=\overline{\operatorname{conv}}(\\{(\Gamma(\boldsymbol{\beta}),-\boldsymbol{\beta})\
:\boldsymbol{\beta}\in D^{m}\\}).$

See (R1970, , Theorem 17.2). We begin by providing conditions under which
$C_{\Gamma}$ is full-dimensional. In what follows, we use $C_{\Gamma}^{\circ}$
to denote the reverse polar cone of $C_{\Gamma}$, i.e., the set of
coefficients corresponding to tight valid inequalities for $C_{\Gamma}$:

$C^{\circ}_{\Gamma}:=\left\\{\boldsymbol{c}\in\mathbb{R}^{d}:\
\boldsymbol{c}^{\top}\boldsymbol{x}\geq 0\quad\forall\leavevmode\nobreak\
\boldsymbol{x}\in C_{\Gamma}\right\\}.$

###### Lemma 2

Let $\Gamma:D^{m}\to D^{n}$ be continuous and define $C_{\Gamma}$ as in (2).
Then $C_{\Gamma}$ is full-dimensional if and only if
$(\boldsymbol{0},\boldsymbol{0})\not\in\operatorname{conv}(\\{(\Gamma(\boldsymbol{\beta}),-\boldsymbol{\beta})\
:\boldsymbol{\beta}\in D^{m}\\})$.

###### Proof

($\Rightarrow$) Assume that $C_{\Gamma}$ is full-dimensional. Furthermore,
assume to the contrary that
$(\boldsymbol{0},\boldsymbol{0})\in\operatorname{conv}\\{(\Gamma(\boldsymbol{\beta}),-\boldsymbol{\beta})\
:\boldsymbol{\beta}\in D^{m}\\}$. The set
$\\{(\Gamma(\boldsymbol{\beta}),-\boldsymbol{\beta})\ :\boldsymbol{\beta}\in
D^{m}\\}$ is compact because $\Gamma$ is continuous, so its closed convex hull
is equal to its convex hull. Hence, there exists a set
$\\{\boldsymbol{\beta}^{i}\\}_{i=1}^{k}\subseteq D^{m}$ and numbers
$\lambda_{1},\dotsc,\lambda_{k}>0$ such that

$\sum_{i=1}^{k}\lambda_{i}(\Gamma(\boldsymbol{\beta}^{i}),-\boldsymbol{\beta}^{i})=(\boldsymbol{0},\boldsymbol{0}).$

Note that $k>1$, as $\boldsymbol{\beta}\neq\boldsymbol{0}$ for all
$\boldsymbol{\beta}\in D^{m}$. This implies

$\boldsymbol{\beta}^{k}=-\sum_{i=1}^{k-1}\frac{\lambda_{i}}{\lambda_{k}}\boldsymbol{\beta}^{i}\quad\text{and}\quad\Gamma(\boldsymbol{\beta}^{k})=-\sum_{i=1}^{k-1}\frac{\lambda_{i}}{\lambda_{k}}\Gamma(\boldsymbol{\beta}^{i}).$

The valid inequality
$\Gamma(\boldsymbol{\beta}^{k})^{\top}\boldsymbol{x}-\boldsymbol{\beta}^{k}\boldsymbol{y}\geq
0$ can then be rewritten as

$-\left(\sum_{i=1}^{k-1}\frac{\lambda_{i}}{\lambda_{k}}\Gamma(\boldsymbol{\beta}^{i})\right){}^{\mathsf{T}}\boldsymbol{x}\geq-\left(\sum_{i=1}^{k-1}\frac{\lambda_{i}}{\lambda_{k}}\boldsymbol{\beta}^{i}\right){}^{\mathsf{T}}\boldsymbol{y}.$

On the other hand, taking a conic combination of the inequalities given by
$\\{\boldsymbol{\beta}^{1},\dotsc,\boldsymbol{\beta}^{k-1}\\}$ using the
weights $\nicefrac{{\lambda_{i}}}{{\lambda_{k}}}>0$ we obtain the valid
inequality

$\left(\sum_{i=1}^{k-1}\frac{\lambda_{i}}{\lambda_{k}}\Gamma(\boldsymbol{\beta}^{i})\right){}^{\mathsf{T}}\boldsymbol{x}\geq\left(\sum_{i=1}^{k-1}\frac{\lambda_{i}}{\lambda_{k}}\boldsymbol{\beta}^{i}\right){}^{\mathsf{T}}\boldsymbol{y}.$

Hence,
$C_{\Gamma}\subseteq\\{(\boldsymbol{x},\boldsymbol{y})\,:\,\Gamma(\boldsymbol{\beta}^{k})^{\top}\boldsymbol{x}-\boldsymbol{\beta}^{k}\boldsymbol{y}=0\\}$.
Since
$(\Gamma(\boldsymbol{\beta}^{k}),-\boldsymbol{\beta}^{k})\neq(\boldsymbol{0},\boldsymbol{0})$,
we conclude that $C_{\Gamma}$ is contained in a hyperplane. This is a
contradiction.

($\Leftarrow$) Assume that
$(\boldsymbol{0},\boldsymbol{0})\not\in\operatorname{conv}(\\{(\Gamma(\boldsymbol{\beta}),-\boldsymbol{\beta})\
:\boldsymbol{\beta}\in D^{m}\\})$. Assume to the contrary that $C_{\Gamma}$ is
not full-dimensional. Hence, there exists a non-zero vector
$(\boldsymbol{g},\boldsymbol{b})\in\mathbb{R}^{n}\times\mathbb{R}^{m}$ such
that
$\boldsymbol{g}^{\top}\boldsymbol{x}-\boldsymbol{b}^{\top}\boldsymbol{y}=0$
for all $(\boldsymbol{x},\boldsymbol{y})\in C_{\Gamma}$; note that the right-
hand side is $0$ because $(\boldsymbol{0},\boldsymbol{0})\in C_{\Gamma}$. In
other words, both
$\boldsymbol{g}^{\top}\boldsymbol{x}-\boldsymbol{b}^{\top}\boldsymbol{y}\geq
0$ and
$-\boldsymbol{g}^{\top}\boldsymbol{x}-(-\boldsymbol{b})^{\top}\boldsymbol{y}\geq
0$ are valid for $C_{\Gamma}$, so
$(\boldsymbol{g},-\boldsymbol{b}),(-\boldsymbol{g},\boldsymbol{b})\in
C^{\circ}_{\Gamma}$. Since
$(\boldsymbol{0},\boldsymbol{0})\not\in\operatorname{conv}(\\{(\Gamma(\boldsymbol{\beta}),-\boldsymbol{\beta})\
:\boldsymbol{\beta}\in D^{m}\\})$, both $(\boldsymbol{g},-\boldsymbol{b})$ and
$(-\boldsymbol{g},\boldsymbol{b})$ are in
$\operatorname{cone}(\\{(\Gamma(\boldsymbol{\beta}),-\boldsymbol{\beta})\
:\boldsymbol{\beta}\in D^{m}\\})$ (see Remark 6). So,
$(\boldsymbol{g},-\boldsymbol{b})$ and $(-\boldsymbol{g},\boldsymbol{b})$ are
conic combinations of vectors in
$\\{(\Gamma(\boldsymbol{\beta}),-\boldsymbol{\beta})\ :\boldsymbol{\beta}\in
D^{m}\\}$. However, after properly scaling $(\boldsymbol{g},-\boldsymbol{b})$
and $(-\boldsymbol{g},\boldsymbol{b})$ by positive numbers, we see that
$(\boldsymbol{0},\boldsymbol{0})\in\operatorname{conv}(\\{(\Gamma(\boldsymbol{\beta}),-\boldsymbol{\beta})\
:\boldsymbol{\beta}\in D^{m}\\})$, which is a contradiction.

The next lemma provides a way of describing all the valid inequalities of
$C_{\Gamma}$ when $\Gamma$ is continuous.

###### Lemma 3

Let $\Gamma:D^{m}\to D^{n}$ be continuous and define $C_{\Gamma}$ as in (2).
Assume that
$(\boldsymbol{0},\boldsymbol{0})\not\in\operatorname{conv}(\\{(\Gamma(\boldsymbol{\beta}),-\boldsymbol{\beta})\
:\boldsymbol{\beta}\in D^{m}\\})$. If
$\overline{\boldsymbol{\gamma}}{}^{\mathsf{T}}\boldsymbol{x}-\overline{\boldsymbol{\beta}}{}^{\mathsf{T}}\boldsymbol{y}\geq
0$ is valid for $C_{\Gamma}$, then there exist
$\boldsymbol{\beta}^{1},\dotsc,\boldsymbol{\beta}^{k}$ such that
$(\overline{\boldsymbol{\gamma}\vphantom{\beta}},-\overline{\boldsymbol{\beta}})\in\operatorname{cone}(\\{(\Gamma(\boldsymbol{\beta})^{i},-\boldsymbol{\beta}^{i}):\
i\in\\{1,\dotsc,k\\}\\})$.

We omit the proof of Lemma 3 as it follows directly from Lemma 2 and Theorem
4.1.

The following lemma gives the representation of $C_{\Gamma}$ that we will use
to prove maximality in Subsection 6.1. For a pointed closed convex cone
$K\subseteq\mathbb{R}^{d}$, we say that $\boldsymbol{v}\in K$ is an exposed
ray if $\operatorname{cone}(\boldsymbol{v})$ is an exposed ray of $K$.

###### Lemma 4

Let $\Gamma:D^{m}\to D^{n}$ be continuous and define $C_{\Gamma}$ as in (2).
Assume that
$(\boldsymbol{0},\boldsymbol{0})\not\in\operatorname{conv}(\\{(\Gamma(\boldsymbol{\beta}),-\boldsymbol{\beta})\
:\boldsymbol{\beta}\in D^{m}\\}).$ Then

$\displaystyle C_{\Gamma}$
$\displaystyle=\left\\{(\boldsymbol{x},\boldsymbol{y})\in\mathbb{R}^{n}\times\mathbb{R}^{m}:\
\Gamma(\boldsymbol{\beta})^{\top}\boldsymbol{x}-\boldsymbol{\beta}{}^{\top}\boldsymbol{y}\geq
0\quad\forall\leavevmode\nobreak\
(\Gamma(\boldsymbol{\beta}),-\boldsymbol{\beta})\in K\right\\}$
$\displaystyle=\left\\{(\boldsymbol{x},\boldsymbol{y})\in\mathbb{R}^{n}\times\mathbb{R}^{m}:\
\Gamma(\boldsymbol{\beta})^{\top}\boldsymbol{x}-\boldsymbol{\beta}{}^{\top}\boldsymbol{y}\geq
0\quad\forall\leavevmode\nobreak\
(\Gamma(\boldsymbol{\beta}),-\boldsymbol{\beta})\in I\right\\}.$

where $I$ is the set of exposed rays of
$K:=\operatorname{cone}(\left\\{(\Gamma(\boldsymbol{\beta}),-\boldsymbol{\beta})\,:\boldsymbol{\beta}\in
D^{m}\,\right\\})$.

###### Proof

The first equation follows from Lemma 3. To prove the second equation it is
sufficient to show that $K=\overline{\operatorname{cone}}(I)$. Define
$H:=\left\\{(\Gamma(\boldsymbol{\beta}),-\boldsymbol{\beta})\,:\boldsymbol{\beta}\in
D^{m}\,\right\\}.$ Notice that
$K=\operatorname{cone}(H)=\operatorname{cone}(\operatorname{conv}(H))=C^{\circ}_{\Gamma}$,
where the second equation follows by definition and the third equation follows
from Lemma 3. Observe that $K$ is pointed because
$(\boldsymbol{0},\boldsymbol{0})\not\in\operatorname{conv}(H)$. Furthermore,
$K$ is closed because $C^{\circ}_{\Gamma}$ is closed. Given that $K$ is a
closed and pointed convex cone, it follows that
$K=\overline{\operatorname{cone}}(I)$; see (R1970, , Theorems 18.5 and 18.6).

###  5.2 Preliminaries about non-expansive functions

###### Lemma 5

Let $\Gamma:D^{m}\to D^{n}$ be non-expansive. Let $I\subseteq D^{m}$ be a
finite set of pairwise isometric points. The following properties hold true:

  1. 1.

If $\sum_{\boldsymbol{\beta}\in
I}\epsilon_{\boldsymbol{\beta}}\boldsymbol{\beta}\in D^{m}$, where
$\epsilon_{\boldsymbol{\beta}}\geq 0$ for each $\boldsymbol{\beta}\in I$, then
$\sum_{\boldsymbol{\beta}\in
I}\epsilon_{\boldsymbol{\beta}}\Gamma(\boldsymbol{\beta})\in D^{n}$ and
$\Gamma(\sum_{\boldsymbol{\beta}\in
I}\epsilon_{\boldsymbol{\beta}}\boldsymbol{\beta})=\sum_{\boldsymbol{\beta}\in
I}\epsilon_{\boldsymbol{\beta}}\Gamma(\boldsymbol{\beta})$.

  2. 2.

If $\sum_{\boldsymbol{\beta}\in
I}\epsilon_{\boldsymbol{\beta}}\Gamma(\boldsymbol{\beta})\in D^{n}$, where
$\epsilon_{\boldsymbol{\beta}}\geq 0$ for each $\boldsymbol{\beta}\in I$, then
$\sum_{\boldsymbol{\beta}\in
I}\epsilon_{\boldsymbol{\beta}}\boldsymbol{\beta}\in D^{m}$ and
$\Gamma(\sum_{\boldsymbol{\beta}\in
I}\epsilon_{\boldsymbol{\beta}}\boldsymbol{\beta})=\sum_{\boldsymbol{\beta}\in
I}\epsilon_{\boldsymbol{\beta}}\Gamma(\boldsymbol{\beta})$.

###### Proof

Set $\widehat{\boldsymbol{\beta}}:=\sum_{\boldsymbol{\beta}\in
I}\epsilon_{\boldsymbol{\beta}}\boldsymbol{\beta}$. Using the isometry of
points in $I$, we have

$\|\sum_{\boldsymbol{\beta}\in
I}\epsilon_{\boldsymbol{\beta}}\Gamma(\boldsymbol{\beta})\|^{2}=\sum_{\boldsymbol{\beta},\boldsymbol{\beta}^{\prime}\in
I}\epsilon_{\boldsymbol{\beta}}\epsilon_{\boldsymbol{\beta}^{\prime}}\Gamma(\boldsymbol{\beta}){}^{\mathsf{T}}\Gamma(\boldsymbol{\beta}^{\prime})\\\
=\sum_{\boldsymbol{\beta},\boldsymbol{\beta}^{\prime}\in
I}\epsilon_{\boldsymbol{\beta}}\epsilon_{\boldsymbol{\beta}^{\prime}}\boldsymbol{\beta}^{\mathsf{T}}\boldsymbol{\beta}^{\prime}=\|\widehat{\boldsymbol{\beta}}\|^{2}.$

In the case of Property 1, we assume $\widehat{\boldsymbol{\beta}}\in D^{m}$,
so the previous equation proves that $\|\sum_{\boldsymbol{\beta}\in
I}\epsilon_{\boldsymbol{\beta}}\Gamma(\boldsymbol{\beta})\|=1$. In the case of
Property 2, we assume $\|\sum_{\boldsymbol{\beta}\in
I}\epsilon_{\boldsymbol{\beta}}\Gamma(\boldsymbol{\beta})\|^{2}=1$, so the
previous equation proves that $\widehat{\boldsymbol{\beta}}\in D^{m}$.
Therefore, it remains to show that
$\Gamma(\widehat{\boldsymbol{\beta}})=\sum_{\boldsymbol{\beta}\in
I}\epsilon_{\boldsymbol{\beta}}\Gamma(\boldsymbol{\beta})$ in both cases; we
prove these simultaneously.

Using the non-expansive property of $\Gamma$ and the nonnegativity of
$\epsilon_{\boldsymbol{\beta}}$, we have

$1=\widehat{\boldsymbol{\beta}}{}^{\mathsf{T}}\widehat{\boldsymbol{\beta}}=\sum_{\boldsymbol{\beta}\in
I}\epsilon_{\boldsymbol{\beta}}\widehat{\boldsymbol{\beta}}{}^{\mathsf{T}}\boldsymbol{\beta}\leq\sum_{\boldsymbol{\beta}\in
I}\epsilon_{\boldsymbol{\beta}}\Gamma(\widehat{\boldsymbol{\beta}})^{\mathsf{T}}\Gamma(\boldsymbol{\beta})=\Gamma(\widehat{\boldsymbol{\beta}})^{\mathsf{T}}\big{(}\sum_{\boldsymbol{\beta}\in
I}\epsilon_{\boldsymbol{\beta}}\Gamma(\boldsymbol{\beta})\big{)}.$

The Cauchy-Schwarz inequality implies that
$1=\Gamma(\widehat{\boldsymbol{\beta}})^{\mathsf{T}}(\sum_{\boldsymbol{\beta}\in
I}\epsilon_{\boldsymbol{\beta}}\Gamma(\boldsymbol{\beta}))$. Since both
vectors have unit norm, we conclude that
$\Gamma(\widehat{\boldsymbol{\beta}})=\sum_{\boldsymbol{\beta}\in
I}\epsilon_{\boldsymbol{\beta}}\Gamma(\boldsymbol{\beta})$.

Our final lemma states that if an inequality
$\Gamma(\overline{\boldsymbol{\beta}})^{\mathsf{T}}\boldsymbol{x}-\overline{\boldsymbol{\beta}}{}^{\mathsf{T}}\boldsymbol{y}\geq
0$ is implied by other inequalities of the same form indexed by $I\subseteq
D^{m}$, then $\overline{\boldsymbol{\beta}}$ must be isometric with
$\boldsymbol{\beta}\in I$. This will be used in the proof of Theorem 1.3 to
help establish that we have a covering of $D^{m}$ by isometric points.

###### Lemma 6

Let $\Gamma:D^{m}\to D^{n}$ be non-expansive. Let
$\overline{\boldsymbol{\beta}}\in D^{m}$, let $I\subseteq D^{m}$ be a finite
set, and let $\lambda_{\boldsymbol{\beta}}>0$ for each $\boldsymbol{\beta}\in
I$ be such that
$(\Gamma(\overline{\boldsymbol{\beta}}),\overline{\boldsymbol{\beta}})=\sum_{\boldsymbol{\beta}\in
I}\lambda_{\boldsymbol{\beta}}(\Gamma(\boldsymbol{\beta}),\boldsymbol{\beta})$.
Then $\overline{\boldsymbol{\beta}}$ and $\boldsymbol{\beta}$ are isometric
for each $\boldsymbol{\beta}\in I$.

###### Proof

Notice that

$\begin{array}[]{rclclcl}0&=&\displaystyle\Gamma(\overline{\boldsymbol{\beta}})^{\mathsf{T}}\Gamma(\overline{\boldsymbol{\beta}})-\overline{\boldsymbol{\beta}}{}^{\mathsf{T}}\overline{\boldsymbol{\beta}}&=&\displaystyle\left(\sum_{\boldsymbol{\beta}\in
I}\lambda_{\boldsymbol{\beta}}\Gamma(\boldsymbol{\beta})\right){}^{\mathsf{T}}\Gamma(\overline{\boldsymbol{\beta}})-\left(\sum_{\boldsymbol{\beta}\in
I}\lambda_{\boldsymbol{\beta}}\boldsymbol{\beta}\right){}^{\mathsf{T}}\overline{\boldsymbol{\beta}}\\\\[21.33955pt]
&&&=&\displaystyle\sum_{\boldsymbol{\beta}\in
I}\lambda_{\boldsymbol{\beta}}\left(\Gamma(\boldsymbol{\beta})^{\mathsf{T}}\Gamma(\overline{\boldsymbol{\beta}})-{\boldsymbol{\beta}}{}^{\mathsf{T}}\overline{\boldsymbol{\beta}}\right),\end{array}$

where the first equality follow from $\overline{\boldsymbol{\beta}}\in D^{m}$
and $\Gamma(\overline{\boldsymbol{\beta}})\in D^{n}$. Due to the non-
expansiveness of $\Gamma$, every summand is non-negative. Since the sum is 0,
every summand must be 0. As $\lambda_{\boldsymbol{\beta}}>0$, we conclude that
$\Gamma(\boldsymbol{\beta})^{\mathsf{T}}\Gamma(\overline{\boldsymbol{\beta}})={\boldsymbol{\beta}}{}^{\mathsf{T}}\overline{\boldsymbol{\beta}}$
for all $\boldsymbol{\beta}\in I$.

##  6 A Proof of Theorem 1.2

For the sake of presentation, we divide the proof of Theorem 1.2 into its
sufficient and necessary conditions for maximality. The proof follows by
combining Lemmata 7 and 8.

###  6.1 A sufficient condition for maximality

In this section, we prove the following result. We do not explicitly assume
continuity in Lemma 7 as we do in Theorem 1.2 because it is implied by the
non-expansivity of $\Gamma$.

###### Lemma 7

Let $\Gamma:D^{m}\to D^{n}$ and define $C_{\Gamma}$ as in (2). If $\Gamma$ is
non-expansive and
$(\boldsymbol{0},\boldsymbol{0})\not\in\operatorname{conv}(\\{(\Gamma(\boldsymbol{\beta}),-\boldsymbol{\beta})\
:\boldsymbol{\beta}\in D^{m}\\})$, then $C_{\Gamma}$ is a full-dimensional
maximal $Q$-free set.

###### Proof

The function $\Gamma$ is continuous because it is non-expansive. Therefore,
Lemma 2 implies that $C_{\Gamma}$ is full-dimensional. For the remainder of
the proof, we focus on establishing that $C_{\Gamma}$ is maximal $Q$-free.

According to Lemma 4, we can write

$C_{\Gamma}=\left\\{(\boldsymbol{x},\boldsymbol{y})\in\mathbb{R}^{n}\times\mathbb{R}^{m}:\
\Gamma(\boldsymbol{\beta})^{\top}\boldsymbol{x}-\boldsymbol{\beta}{}^{\top}\boldsymbol{y}\geq
0\quad\forall\leavevmode\nobreak\
(\Gamma(\boldsymbol{\beta}),-\boldsymbol{\beta})\in I\right\\}.$

where $I$ is the set of exposed rays of
$\operatorname{cone}(\operatorname{conv}(\left\\{(\Gamma(\boldsymbol{\beta}),-\boldsymbol{\beta})\,:\boldsymbol{\beta}\in
D^{m}\,\right\\}))$.

To prove that $C_{\Gamma}$ is maximal, it suffices to prove that the
inequality
$\Gamma(\boldsymbol{\beta})^{\top}\boldsymbol{x}-\boldsymbol{\beta}{}^{\top}\boldsymbol{y}\geq
0$ for each $(\Gamma(\boldsymbol{\beta}),-\boldsymbol{\beta})\in I$ has an
exposing sequence. To this end, fix
$(\Gamma(\overline{\boldsymbol{\beta}}),-\overline{\boldsymbol{\beta}})\in I$.
Given that
$(\Gamma(\overline{\boldsymbol{\beta}}),-\overline{\boldsymbol{\beta}})$ is an
exposed ray of $K$, there exists a vector
$(\overline{\boldsymbol{x}},\overline{\boldsymbol{y}})\in\mathbb{R}^{n}\times\mathbb{R}^{m}$
such that

$\Gamma(\overline{\boldsymbol{\beta}})^{\top}\overline{\boldsymbol{x}}-\overline{\boldsymbol{\beta}}{}{}^{\top}\overline{\boldsymbol{y}}=0<\Gamma({\boldsymbol{\beta}})^{\top}\overline{\boldsymbol{x}}-{\boldsymbol{\beta}}{}{}^{\top}\overline{\boldsymbol{y}}\qquad\forall\
\boldsymbol{\beta}\in D^{m}\setminus\\{\overline{\boldsymbol{\beta}}\\}.$ (6)

We consider two cases; Case 2 is the more involved case that constitutes most
of the remainder of the proof.

Case 1. Assume that $(\overline{\boldsymbol{x}},\overline{\boldsymbol{y}})\in
Q$. Consider the _constant_ sequence
$((\overline{\boldsymbol{x}},\overline{\boldsymbol{y}}))_{t=1}^{\infty}$ of
points in $Q$.333Using the language in MS2022 , the constant sequence here is
an exposing point. Consider any sequence
$((\boldsymbol{g}^{t},\boldsymbol{b}^{t}))_{t=1}^{\infty}$ of points in
$\mathbb{R}^{n}\times\mathbb{R}^{m}$ with
$\|(\boldsymbol{g}^{t},\boldsymbol{b}^{t})\|=\|(\Gamma(\overline{\boldsymbol{\beta}}),\overline{\boldsymbol{\beta}})\|$
such that the inequality
$\boldsymbol{g}^{t}{}^{\top}\boldsymbol{x}-\boldsymbol{b}^{t}{}^{\top}\boldsymbol{y}\geq
0$ is valid for $C_{\Gamma}$ and separates
$(\overline{\boldsymbol{x}},\overline{\boldsymbol{y}})$, that is,
$\boldsymbol{g}^{t}{}^{\top}\overline{\boldsymbol{x}}-\boldsymbol{b}^{t}{}^{\top}\overline{\boldsymbol{y}}\leq
0$. According to Lemma 3, the point $(\boldsymbol{g}^{t},\boldsymbol{b}^{t})$
is a conic combination of points in
$\\{(\Gamma(\boldsymbol{\beta}),\boldsymbol{\beta})\ :\boldsymbol{\beta}\in
D^{m}\\}$, say
$(\boldsymbol{g}^{t},\boldsymbol{b}^{t})=\sum_{i=1}^{k}\lambda_{i}(\Gamma(\boldsymbol{\beta}^{i}),\boldsymbol{\beta}^{i})$,
where $\lambda_{1},\dotsc,\lambda_{k}>0$. Hence, using (6), we have
$\boldsymbol{g}^{t}{}^{\top}\boldsymbol{x}-\boldsymbol{b}^{t}{}^{\top}\boldsymbol{y}\geq
0$ with equality if and only if
$(\Gamma(\boldsymbol{\beta}^{i}),\boldsymbol{\beta}^{i})=(\Gamma(\overline{\boldsymbol{\beta}}),\overline{\boldsymbol{\beta}})$
for each $i\in\\{1,\dotsc,k\\}$. This shows that
$(\boldsymbol{g}^{t},\boldsymbol{b}^{t})=(\Gamma(\overline{\boldsymbol{\beta}}),\overline{\boldsymbol{\beta}})$.
In particular,
$\lim_{t\to\infty}(\boldsymbol{g}^{t},\boldsymbol{b}^{t})=(\Gamma(\overline{\boldsymbol{\beta}}),\overline{\boldsymbol{\beta}})$,
so $((\overline{\boldsymbol{x}},\overline{\boldsymbol{y}}))_{t=1}^{\infty}$ is
an exposing sequence for
$\Gamma(\overline{\boldsymbol{\beta}})^{\top}\boldsymbol{x}-\overline{\boldsymbol{\beta}}{}^{\top}\boldsymbol{y}\geq
0$.

Case 2. Assume that
$(\overline{\boldsymbol{x}},\overline{\boldsymbol{y}})\not\in Q$. That is, we
may assume that

$\Delta:=\|\overline{\boldsymbol{x}}\|^{2}-\|\overline{\boldsymbol{y}}\|^{2}>0.$
(7)

The proposed exposing sequence for
$\Gamma(\overline{\boldsymbol{\beta}})^{\top}{\boldsymbol{x}}-\overline{\boldsymbol{\beta}}{}{}^{\top}{\boldsymbol{y}}\geq
0$ is $((\boldsymbol{x}^{t},\boldsymbol{y}^{t}))_{t=1}^{\infty}$, where

$\begin{array}[]{rcl}\boldsymbol{x}^{t}&:=&\displaystyle\Gamma(\overline{\boldsymbol{\beta}})+\frac{\sqrt{2t+1}}{t}\cdot\overline{\boldsymbol{x}}\\\\[7.11317pt]
\boldsymbol{y}^{t}&:=&\displaystyle\left(1+\frac{4}{t}\Delta\right)\overline{\boldsymbol{\beta}}+\frac{\sqrt{2t+1}}{t}\cdot\overline{\boldsymbol{y}}.\end{array}$

We will start the sequence at large enough $t$. More precisely, let
$\overline{t}$ be large enough so that

$6t-8\sqrt{2t+1}\cdot\|\overline{\boldsymbol{y}}\|-1\geq
0\quad\forall\leavevmode\nobreak\ t\geq\overline{t}.$

Our choice to restrict the sequence to $t\geq\overline{t}$ is apparent from
the next claim, which shows that the candidate sequence
$((\boldsymbol{x}^{t},\boldsymbol{y}^{t}))_{t=\overline{t}}^{\infty}$ is
indeed a sequence of points in $Q$.

###### Claim 1

For each $t\geq\overline{t}$, we have
$(\boldsymbol{x}^{t},\boldsymbol{y}^{t})\in Q$.

  * Proof of Claim. Note that

$\|\boldsymbol{x}^{t}\|^{2}=1+\frac{2\sqrt{2t+1}}{t}\cdot\Gamma(\overline{\boldsymbol{\beta}}){}{}^{\top}\overline{\boldsymbol{x}}+\frac{2t+1}{t^{2}}\cdot\overline{\boldsymbol{x}}{}^{\top}\overline{\boldsymbol{x}}.$

Using the equation
$\Gamma(\overline{\boldsymbol{\beta}})^{\top}\overline{\boldsymbol{x}}-\overline{\boldsymbol{\beta}}{}{}^{\top}\overline{\boldsymbol{y}}=0$
in (6), we see that

$\|\boldsymbol{x}^{t}\|^{2}=1+\frac{2\sqrt{2t+1}}{t}\cdot\overline{\boldsymbol{\beta}}{}{}^{\top}\overline{\boldsymbol{y}}+\frac{2t+1}{t^{2}}\cdot\overline{\boldsymbol{x}}{}^{\top}\overline{\boldsymbol{x}}.$

Furthermore, we have

$\|\boldsymbol{y}^{t}\|^{2}=\left(1+\frac{4}{t}\Delta\right)^{2}+2\left(1+\frac{4}{t}\Delta\right)\frac{\sqrt{2t+1}}{t}\cdot\overline{\boldsymbol{\beta}}{}{}^{\top}\overline{\boldsymbol{y}}+\frac{2t+1}{t^{2}}\cdot\overline{\boldsymbol{y}}{}^{\top}\overline{\boldsymbol{y}}.$

We would like to show $(\boldsymbol{x}^{t},\boldsymbol{y}^{t})\in Q$ when
$t\geq\overline{t}$; this is equivalent to
$\|\boldsymbol{y}^{t}\|^{2}-\|\boldsymbol{x}^{t}\|^{2}\geq 0$. Using the
previous two displayed equations, we have

$\|\boldsymbol{y}^{t}\|^{2}-\|\boldsymbol{x}^{t}\|^{2}=\frac{8}{t}\Delta+\frac{16}{t^{2}}\Delta^{2}+\Delta\frac{8\sqrt{2t+1}}{t^{2}}\overline{\boldsymbol{\beta}}{}{}^{\top}\overline{\boldsymbol{y}}-\frac{2t+1}{t^{2}}\Delta.$

To show $\|\boldsymbol{y}^{t}\|^{2}-\|\boldsymbol{x}^{t}\|^{2}\geq 0$, we can
multiply both sides in the previous equation by $\frac{t^{2}}{\Delta}>0$ and
prove the resulting right-hand side is nonnegative. That is, it suffices to
prove that the quantity

$8t+16\Delta+8\sqrt{2t+1}\cdot\overline{\boldsymbol{\beta}}{}{}^{\top}\overline{\boldsymbol{y}}-(2t+1)$

is nonnegative. By Cauchy-Schwarz, we have
$|\overline{\boldsymbol{\beta}}{}{}^{\top}\overline{\boldsymbol{y}}|\leq\|\overline{\boldsymbol{y}}\|\cdot\|\overline{\boldsymbol{\beta}}\|=\|\overline{\boldsymbol{y}}\|$.
Hence,

$8t+\underbrace{16\Delta}_{\geq 0\leavevmode\nobreak\
\text{by}\leavevmode\nobreak\
\eqref{eqNotExpansive}}+8\sqrt{2t+1}\cdot\underbrace{\overline{\boldsymbol{\beta}}{}{}^{\top}\overline{\boldsymbol{y}}}_{\geq-\|\overline{\boldsymbol{y}}\|}-(2t+1)\geq
6t-8\sqrt{2t+1}\cdot\|\overline{\boldsymbol{y}}\|-1.$

The assumption $t\geq\overline{t}$ means that the right-hand side of the
previous inequality is nonnegative. $\diamond$

Now, consider a sequence of inequalities that are valid for $C_{\Gamma}$ and
that separate
$((\boldsymbol{x}^{t},\boldsymbol{y}^{t}))_{t=\overline{t}}^{\infty}$. Using
Lemma 3, we may assume that the inequality that separates
$(\boldsymbol{x}^{t},\boldsymbol{y}^{t})$ has the form

$\sum_{i=1}^{n+m}\lambda_{[i,t]}\left(\Gamma(\boldsymbol{\beta}^{[i,t]})^{\top}\boldsymbol{x}^{t}-\boldsymbol{\beta}^{[i,t]}{}{}^{\top}\boldsymbol{y}^{t}\right)\leq
0,$ (8)

where each $\lambda_{[i,t]}\geq 0$ and $\boldsymbol{\beta}^{[i,t]}\in
D^{m}$444Note that we cannot assume
$(\Gamma(\boldsymbol{\beta}^{[i,t]}),\boldsymbol{\beta}^{[i,t]})\in I$ because
Lemma 3 does not hold if
$\left\\{(\Gamma(\boldsymbol{\beta}),-\boldsymbol{\beta})\,:\boldsymbol{\beta}\in
D^{m}\,\right\\}$ is replaced by $I$, which is not closed. We will not require
that these points be in $I$, though. Here, we are implicitly using two
representations of $C_{\Gamma}$, one obtained by intersecting inequalities
whose coefficients belong to $I$ and another obtained by intersecting
inequalities whose coefficients belong to
$\left\\{(\Gamma(\boldsymbol{\beta}),-\boldsymbol{\beta})\,:\boldsymbol{\beta}\in
D^{m}\,\right\\}$. . Furthermore, in order to demonstrate that
$((\boldsymbol{x}^{t},\boldsymbol{y}^{t}))_{t=\overline{t}}^{\infty}$ is an
exposing sequence, we assume that all of these separating inequalities have
the same norm as
$(\Gamma(\overline{\boldsymbol{\beta}}),\overline{\boldsymbol{\beta}})$, that
is

$\left\|\sum_{i=1}^{n+m}\lambda_{[i,t]}\left(\Gamma(\boldsymbol{\beta}^{[i,t]}),\boldsymbol{\beta}^{[i,t]}\right)\right\|=\left\|(\Gamma(\overline{\boldsymbol{\beta}}),\overline{\boldsymbol{\beta}})\right\|=\sqrt{2}\qquad\forall\leavevmode\nobreak\
t.$ (9)

###### Claim 2

There exists $\tau\in\mathbb{R}_{+}$ such that $\lambda_{[i,t]}\leq\tau$ for
each $i\in\\{1,\dotsc,n+m\\}$ and $t\geq\overline{t}$.

  * Proof of Claim. Assume to the contrary that no $\tau$ exists. Then, there exists some $i$, say $i=1$, and a subsequence of $(\lambda_{[1,t]})_{t=\overline{t}}^{\infty}$ that diverges to $\infty$. By re-indexing the sequence, we assume that $(\lambda_{[1,t]})_{t=\overline{t}}^{\infty}$ is increasing and diverges to $\infty$.

According to (9), the sequence
$(\sum_{i=1}^{n+m}\lambda_{[i,t]}(\Gamma(\boldsymbol{\beta}^{[i,t]}),\boldsymbol{\beta}^{[i,t]}))_{t=\overline{t}}^{\infty}$
has a convergent subsequence. After re-indexing along this subsequence, we may
assume that the limit exists, say

$\lim_{t\to\infty}\sum_{i=1}^{n+m}\lambda_{[i,t]}\left(\Gamma(\boldsymbol{\beta}^{[i,t]}),\boldsymbol{\beta}^{[i,t]}\right)=:(\boldsymbol{g},\boldsymbol{b}),$

where $\|(\boldsymbol{g},\boldsymbol{b})\|=\sqrt{2}$. Furthermore, after
taking additional subsequences, we may assume that the limit of
$((\Gamma(\boldsymbol{\beta}^{[1,t]}),\boldsymbol{\beta}^{[1,t]}))_{t=\overline{t}}^{\infty}$
exists, say
$(\Gamma(\boldsymbol{\beta}^{1}),\boldsymbol{\beta}^{1})=:\lim_{t\to\infty}(\Gamma(\boldsymbol{\beta}^{[1,t]},\boldsymbol{\beta}^{[1,t]})$.

We have

$\displaystyle\boldsymbol{0}=\lim_{t\to\infty}\frac{1}{\lambda_{[1,t]}}(\boldsymbol{g},\boldsymbol{b})$
$\displaystyle=\lim_{t\to\infty}\sum_{i=1}^{n+m}\frac{\lambda_{[i,t]}}{\lambda_{[1,t]}}\left(\Gamma(\boldsymbol{\beta}^{[i,t]}),\boldsymbol{\beta}^{[i,t]}\right)$
$\displaystyle=(\Gamma(\boldsymbol{\beta}^{1}),\boldsymbol{\beta}^{1})+\lim_{t\to\infty}\sum_{i=2}^{n+m}\frac{\lambda_{[i,t]}}{\lambda_{[1,t]}}\left(\Gamma(\boldsymbol{\beta}^{[i,t]}),\boldsymbol{\beta}^{[i,t]}\right).$

Thus,
$-(\Gamma(\boldsymbol{\beta}^{1}),\boldsymbol{\beta}^{1})=\lim_{t\to\infty}\sum_{i=2}^{n+m}\frac{\lambda_{[i,t]}}{\lambda_{[1,t]}}\left(\Gamma(\boldsymbol{\beta}^{[i,t]}),\boldsymbol{\beta}^{[i,t]}\right)$.
Hence, the inequality
$-(\Gamma(\boldsymbol{\beta}^{[1,t]}){}{}^{\top}\boldsymbol{x}-\boldsymbol{\beta}^{[1,t]}{}{}^{\top}\boldsymbol{y})\leq
0$ is a limit of valid inequalities for $C_{\Gamma}$, and is therefore itself
valid for $C_{\Gamma}$. However,
$\Gamma(\boldsymbol{\beta}^{[1,t]}){}{}^{\top}\boldsymbol{x}-\boldsymbol{\beta}^{[1,t]}{}{}^{\top}\boldsymbol{y}\leq
0$ is also valid for $C_{\Gamma}$, implying that $C_{\Gamma}$ is not full-
dimensional. This is a contradiction. $\diamond$

To show that
$((\boldsymbol{x}^{t},\boldsymbol{y}^{t}))_{t=\overline{t}}^{\infty}$ is an
exposing sequence, we need to show that

$\lim_{t\to\infty}\sum_{i=1}^{n+m}\lambda_{[i,t]}\left(\Gamma(\boldsymbol{\beta}^{[i,t]}),\boldsymbol{\beta}^{[i,t]}\right)=\left(\Gamma(\overline{\boldsymbol{\beta}}),\overline{\boldsymbol{\beta}}\right).$

Since the sequence is bounded (see (9)), it is enough to show that every
convergent subsequence converges to
$\left(\Gamma(\overline{\boldsymbol{\beta}}),\overline{\boldsymbol{\beta}}\right)$.
Abusing notation, let
$\left(\sum_{i=1}^{n+m}\lambda_{[i,t]}\left(\Gamma(\boldsymbol{\beta}^{[i,t]}),\boldsymbol{\beta}^{[i,t]}\right)\right)_{t=\overline{t}}^{\infty}$
be our convergent subsequence. After taking more subsequences, we may assume
that for each $i\in\\{1,\dotsc,n+m\\}$ we have

$\lim_{t\to\infty}\left(\Gamma(\boldsymbol{\beta}^{[i,t]}),\boldsymbol{\beta}^{[i,t]}\right)=:\left(\Gamma(\boldsymbol{\beta}^{i}),\boldsymbol{\beta}^{i}\right),$

and furthermore because $\lambda_{[i,t]}$ is uniformly bounded from Claim 2,
we can also assume

$\lim_{t\to\infty}\lambda_{[i,t]}=:\lambda_{i}.$

To prove the limit we are going to exploit the fact that the convergent
subsequence satisfies (8). Consider multiplying (8) by $t$. Notice that for
each $\boldsymbol{\beta}\in D^{m}$ and $t\geq\overline{t}$, we have

$\displaystyle
t\left(\Gamma(\boldsymbol{\beta}){}{}^{\top}\boldsymbol{x}^{t}-\boldsymbol{\beta}{}^{\top}\boldsymbol{y}^{t}\right)$
$\displaystyle=$ $\displaystyle
t\left(\Gamma(\boldsymbol{\beta}){}{}^{\top}\Gamma(\overline{\boldsymbol{\beta}})-\boldsymbol{\beta}{}^{\top}\overline{\boldsymbol{\beta}}\right)+\sqrt{2t+1}\left(\Gamma(\boldsymbol{\beta}){}{}^{\top}\overline{\boldsymbol{x}}-\boldsymbol{\beta}{}^{\top}\overline{\boldsymbol{y}}\right)-4\Delta\boldsymbol{\beta}{}^{\top}\overline{\boldsymbol{\beta}}.$

Then, multiplying (8) by $t$ can be written as

$\begin{array}[]{rccl}0&\geq&t&\displaystyle\left[\sum_{i=1}^{n+m}\lambda_{[i,t]}\left((\Gamma(\boldsymbol{\beta}^{[i,t]}){}{}^{\top}\Gamma(\overline{\boldsymbol{\beta}})-\boldsymbol{\beta}^{[i,t]}{}^{\top}\overline{\boldsymbol{\beta}}\right)\right]\\\\[21.33955pt]
&+&\sqrt{2t+1}&\displaystyle\left[\sum_{i=1}^{n+m}\lambda_{[i,t]}\left((\Gamma(\boldsymbol{\beta}^{[i,t]}){}{}^{\top}\overline{\boldsymbol{x}}-\boldsymbol{\beta}^{[i,t]}{}^{\top}\overline{\boldsymbol{y}}\right)\right]\\\\[21.33955pt]
&-&&\displaystyle\left[\sum_{i=1}^{n+m}\lambda_{[i,t]}\left(4\Delta\boldsymbol{\beta}^{[i,t]}{}^{\top}\overline{\boldsymbol{\beta}}\right)\right].\end{array}$
(10)

Recall $\lambda_{[i,t]}$ is uniformly bounded by $\tau$ from Claim 2.
Furthermore, because $\Gamma$ is non-expansive,
$(\Gamma(\boldsymbol{\beta}^{[i,t]}){}{}^{\top}\Gamma(\overline{\boldsymbol{\beta}})-\boldsymbol{\beta}^{[i,t]}{}^{\top}\overline{\boldsymbol{\beta}}\geq
0$. Hence, we can lower bound (10) by

$0\geq\sqrt{2t+1}\left[\sum_{i=1}^{n+m}\lambda_{[i,t]}\left((\Gamma(\boldsymbol{\beta}^{[i,t]}){}{}^{\top}\overline{\boldsymbol{x}}-\boldsymbol{\beta}^{[i,t]}{}^{\top}\overline{\boldsymbol{y}}\right)\right]-\tau\cdot
4\Delta.$ (11)

Now, suppose there exists some $i\in\\{1,\dotsc,n+m\\}$ for which
$\boldsymbol{\beta}^{i}$ is not equal to $\overline{\boldsymbol{\beta}}$ and
$\lambda_{i}>0$. According to (6), we then have
$\Gamma(\boldsymbol{\beta}^{i}){}{}^{\top}\overline{\boldsymbol{x}}-\boldsymbol{\beta}^{i}{}{}^{\top}\overline{\boldsymbol{y}}>0$.
Under this assumption, the right-hand side of (11) is lower bounded by
$\sqrt{2t+1}\cdot\lambda_{[i,t]}\cdot(\Gamma(\boldsymbol{\beta}^{[i,t]}){}{}^{\top}\overline{\boldsymbol{x}}-\boldsymbol{\beta}^{[i,t]}{}{}^{\top}\overline{\boldsymbol{y}})-\tau\cdot
4\Delta$, which tends to $\infty$ as $t\to\infty$. However, this contradicts
the inequality in (11). So, if $\boldsymbol{\beta}^{i}$ is not equal to
$\overline{\boldsymbol{\beta}}$, then $\lambda_{i}=0$.

In conclusion, if $\lambda_{i}>0$, then
$\boldsymbol{\beta}^{i}=\overline{\boldsymbol{\beta}}$. Hence,

$\lim_{t\to\infty}\sum_{i=1}^{n+m}\lambda_{[i,t]}\left(\Gamma(\boldsymbol{\beta}^{[i,t]}),\boldsymbol{\beta}^{[i,t]}\right)=\left(\Gamma(\overline{\boldsymbol{\beta}}),\overline{\boldsymbol{\beta}}\right),$

which demonstrates that
$((\boldsymbol{x}^{t},\boldsymbol{y}^{t}))_{t=\overline{t}}^{\infty}$ is an
exposing sequence for
$\Gamma(\overline{\boldsymbol{\beta}})^{\top}{\boldsymbol{x}}-\overline{\boldsymbol{\beta}}{}{}^{\top}{\boldsymbol{y}}\geq
0$.

###  6.2 A necessary condition for maximality

In this section, we prove the following result.

###### Lemma 8

Let $\Gamma:D^{m}\to D^{n}$ and define $C_{\Gamma}$ as in (2). If $C_{\Gamma}$
is a full-dimensional maximal $Q$-free set, then $\Gamma$ is non-expansive and
$(\boldsymbol{0},\boldsymbol{0})\not\in\operatorname{conv}(\\{(\Gamma(\boldsymbol{\beta}),-\boldsymbol{\beta})\
:\boldsymbol{\beta}\in D^{m}\\})$.

###### Proof

Let us first prove that $\Gamma$ is non-expansive. By contradiction, assume
$\boldsymbol{\beta}^{1},\boldsymbol{\beta}^{2}\in D^{m}$ are such that

$\|\Gamma(\boldsymbol{\beta}^{1})-\Gamma(\boldsymbol{\beta}^{2})\|>\|\boldsymbol{\beta}^{1}-\boldsymbol{\beta}^{2}\|\Leftrightarrow\boldsymbol{\beta}^{1}{}^{\top}\boldsymbol{\beta}^{2}>\Gamma(\boldsymbol{\beta}^{1})^{\top}\Gamma(\boldsymbol{\beta}^{2})$

This implies that
$(\Gamma(\boldsymbol{\beta}^{1}),\boldsymbol{\beta}^{1})\not\in C_{\Gamma}$.
Define the convex cone

$C^{\prime}:=C_{\Gamma}+\operatorname{cone}((\Gamma(\boldsymbol{\beta}^{1}),\boldsymbol{\beta}^{1})),$

where the addition is the Minkowski sum. We claim $C^{\prime}$ is $Q$-free and
strictly contains $C_{\Gamma}$.

The fact that $C_{\Gamma}\subsetneq C^{\prime}$ follows because
$(\Gamma(\boldsymbol{\beta}^{1}),\boldsymbol{\beta}^{1})\in
C^{\prime}\setminus C_{\Gamma}$. To prove that $C^{\prime}$ is $Q$-free, we
show that if
$(\widetilde{\boldsymbol{x}},\widetilde{\boldsymbol{y}})\in\operatorname{intr}(C^{\prime})$,
then $(\widetilde{\boldsymbol{x}},\widetilde{\boldsymbol{y}})\not\in Q$. Given
$(\widetilde{\boldsymbol{x}},\widetilde{\boldsymbol{y}})\in\operatorname{intr}(C^{\prime})$,
we can write

$(\widetilde{\boldsymbol{x}},\widetilde{\boldsymbol{y}})=(\boldsymbol{x},\boldsymbol{y})+\lambda(\Gamma(\boldsymbol{\beta}^{1}),\boldsymbol{\beta}^{1})$

for some $(\boldsymbol{x},\boldsymbol{y})\in\operatorname{intr}(C_{\Gamma})$
(as $C_{\Gamma}$ is full-dimensional) and $\lambda>0$ (see (R1970, , Corollary
6.6.2)). From this,

$\displaystyle\|\widetilde{\boldsymbol{x}}\|^{2}=\|\boldsymbol{x}\|^{2}+\lambda^{2}+2\lambda\Gamma(\boldsymbol{\beta}^{1})^{\top}\boldsymbol{x}\geq$
$\displaystyle\|\boldsymbol{x}\|^{2}+\lambda^{2}+2\lambda\boldsymbol{\beta}^{1}{}^{\top}\boldsymbol{y}$
$\displaystyle>$
$\displaystyle\|\boldsymbol{y}\|^{2}+\lambda^{2}+2\lambda\boldsymbol{\beta}^{1}{}^{\top}\boldsymbol{y}$
$\displaystyle=$ $\displaystyle\|\widetilde{\boldsymbol{y}}\|^{2},$

where the first inequality holds because $(\boldsymbol{x},\boldsymbol{y})\in
C_{\Gamma}$ and the second inequality holds because $C_{\Gamma}$ is $Q$-free.
Therefore, $(\widetilde{\boldsymbol{x}},\widetilde{\boldsymbol{y}})\not\in Q$
and $C^{\prime}$ is $Q$-free. However, this contradicts the maximality of
$C_{\Gamma}$.

Now that we have established that $\Gamma$ is non-expansive, we see that it is
continuous. Thus, we can use Lemma 2 to conclude that
$(\boldsymbol{0},\boldsymbol{0})\not\in\operatorname{conv}(\\{(\Gamma(\boldsymbol{\beta}),-\boldsymbol{\beta})\
:\boldsymbol{\beta}\in D^{m}\\})$.

##  7 A proof of Theorem 1.3

$(\Leftarrow)$ We show that if $\overline{\boldsymbol{\beta}}\in
D^{m}\setminus I$, then
$\Gamma(\overline{\boldsymbol{\beta}}){}^{\mathsf{T}}\boldsymbol{x}-\overline{\boldsymbol{\beta}}{}^{\mathsf{T}}\boldsymbol{y}\geq
0$ is implied by the inequalities indexed by $I$. Let
$\overline{\boldsymbol{\beta}}\in D^{m}\setminus I$. By assumption, there
exists a set $J\subseteq I$ of pairwise isometric points satisfying
$\overline{\boldsymbol{\beta}}\in\operatorname{cone}(J)$. Hence, there exist
$\lambda_{\boldsymbol{\beta}}\geq 0$ for each $\boldsymbol{\beta}\in J$ such
that $\overline{\boldsymbol{\beta}}=\sum_{\boldsymbol{\beta}\in
J}\lambda_{\boldsymbol{\beta}}\boldsymbol{\beta}$. We have
$\Gamma(\overline{\boldsymbol{\beta}})=\sum_{\boldsymbol{\beta}\in
J}\lambda_{\boldsymbol{\beta}}\Gamma(\boldsymbol{\beta})$ by Lemma 5. This
shows that
$(\Gamma(\overline{\boldsymbol{\beta}}),-\overline{\boldsymbol{\beta}})\in\operatorname{cone}(\\{(\Gamma(\boldsymbol{\beta}),-\boldsymbol{\beta}):\boldsymbol{\beta}\in
J\\})$. Hence,
$\Gamma(\overline{\boldsymbol{\beta}})^{\mathsf{T}}\boldsymbol{x}-\overline{\boldsymbol{\beta}}{}^{\mathsf{T}}\boldsymbol{y}\geq
0$ is implied by the inequalities indexed by $I$.

$(\Rightarrow)$ $C_{\Gamma}$ is a polyhedron, so by Lemma 3 there is a finite
representation

$C_{\Gamma}=\left\\{(\boldsymbol{x},\boldsymbol{y})\in\mathbb{R}^{n}\times\mathbb{R}^{n}:\
\Gamma(\boldsymbol{\beta})^{\mathsf{T}}\boldsymbol{x}-{\boldsymbol{\beta}}{}^{\mathsf{T}}\boldsymbol{y}\geq
0\leavevmode\nobreak\ \leavevmode\nobreak\ \forall\ \boldsymbol{\beta}\in
I\right\\}.$

Let $\overline{\boldsymbol{\beta}}\in D^{m}\setminus I$. The inequality
$\Gamma(\overline{\boldsymbol{\beta}})^{\mathsf{T}}\boldsymbol{x}-\overline{\boldsymbol{\beta}}{}^{\mathsf{T}}\boldsymbol{y}\geq
0$ is valid for $C_{\Gamma}$, so there exists a set $J\subseteq I$ and
positive coefficients $\lambda_{\boldsymbol{\beta}}$ for each
$\boldsymbol{\beta}\in J$ such that

$(\Gamma(\overline{\boldsymbol{\beta}}),\overline{\boldsymbol{\beta}})=\sum_{\boldsymbol{\beta}\in
J}\lambda_{\boldsymbol{\beta}}(\Gamma(\boldsymbol{\beta}),\boldsymbol{\beta}).$

Lemma 6 states that
$\overline{\boldsymbol{\beta}}{}^{\mathsf{T}}\boldsymbol{\beta}=\Gamma(\overline{\boldsymbol{\beta}})^{\mathsf{T}}\Gamma(\boldsymbol{\beta})$
for all $\boldsymbol{\beta}\in J$. For each $\boldsymbol{\beta}^{\prime}\in
J$, we have

$\Gamma(\boldsymbol{\beta}^{\prime})^{\mathsf{T}}\Gamma(\overline{\boldsymbol{\beta}})-\boldsymbol{\beta}^{\prime}{}^{\mathsf{T}}\overline{\boldsymbol{\beta}}=\sum_{\boldsymbol{\beta}\in
J}\lambda_{\boldsymbol{\beta}}(\Gamma(\boldsymbol{\beta}^{\prime})^{\mathsf{T}}\Gamma({\boldsymbol{\beta}})-\boldsymbol{\beta}^{\prime}{}^{\mathsf{T}}{\boldsymbol{\beta}}).$

The left-hand side is 0 because $\overline{\boldsymbol{\beta}}$ and
$\boldsymbol{\beta}^{\prime}$ are isometric, and every summand on the right-
hand side is nonnegative because $\lambda_{\boldsymbol{\beta}}>0$ and
$\Gamma(\boldsymbol{\beta}^{\prime})^{\mathsf{T}}\Gamma({\boldsymbol{\beta}})-\boldsymbol{\beta}^{\prime}{}^{\mathsf{T}}{\boldsymbol{\beta}}\geq
0$ by the non-expansive property of $\Gamma$. Hence,
$\Gamma(\boldsymbol{\beta}^{\prime})^{\mathsf{T}}\Gamma(\boldsymbol{\beta})=\boldsymbol{\beta}^{\prime}{}^{\mathsf{T}}{\boldsymbol{\beta}}$
for all $\boldsymbol{\beta}\in J$. As ${\boldsymbol{\beta}}^{\prime}$ was
arbitrarily chosen in $J$, we see that all elements of $J$ are pairwise
isometric and $\overline{\boldsymbol{\beta}}\in\operatorname{cone}(J)$.

##  8 Future Work

Even though we have fully characterized full-dimensional maximal $Q$-free
sets, there are multiple lines of future work on maximal quadratic-free sets.

One future line of work we consider interesting is related to maximal
polyhedral $Q$-free sets. Theorem 1.3 characterizes when $C_{\Gamma}$ is
polyhedral; loosely speaking, it reduces polyhedrality to finding a set of
isometric points that cover $D^{m}$. With this in mind, one may consider
whether an arbitrary finite set of points in $D^{m}$ can be extended to an
‘isometric cover’ for some function $\Gamma$. The following example
illustrates that this is not always possible.

###### Example 5

Set
$I:=\\{\boldsymbol{\beta}^{1},\boldsymbol{\beta}^{2},\boldsymbol{\beta}^{3},\boldsymbol{\beta}^{4}\\}\subseteq
D^{2}$, where

$\boldsymbol{\beta}^{1}:=\big{(}0,1\big{)},\leavevmode\nobreak\
\boldsymbol{\beta}^{2}:=\big{(}1,0\big{)},\leavevmode\nobreak\
\boldsymbol{\beta}^{3}:=\big{(}0,-1\big{)},\leavevmode\nobreak\
\text{and}\leavevmode\nobreak\
\boldsymbol{\beta}^{4}:=\big{(}-\sqrt{\nicefrac{{2}}{{3}}},-\sqrt{\nicefrac{{1}}{{3}}}\big{)}.$

The points are drawn in the next figure.

$\boldsymbol{\beta}^{1}$$\boldsymbol{\beta}^{2}$$\boldsymbol{\beta}^{3}$$\boldsymbol{\beta}^{4}$

We claim that the set $I$ cannot be used in Theorem 1.3 to define a non-
expansive map $\Gamma$ that corresponds to a full-dimensional $Q$-free
polyhedron $C_{\Gamma}$. Indeed, if $I$ could be used to construct such a
$\Gamma$, then the $I$ must cover $D^{2}$ with isometric pairs of points, that
is, each consecutive pair of $\boldsymbol{\beta}^{i}$ and
$\boldsymbol{\beta}^{i+1}$ in $I$ must be isometric. Thus, the image of the
arc $(\boldsymbol{\beta}^{1},\boldsymbol{\beta}^{2})$ under $\Gamma$ must be a
rotation of the red arc; similarly the image of the purple arc under $\Gamma$
must be a rotation of the purple arc. Given that $C_{\Gamma}$ is full-
dimensional, we then conclude that
$\Gamma(\boldsymbol{\beta}^{1})=\Gamma(\boldsymbol{\beta}^{3})$ otherwise we
would have
$(\boldsymbol{0},\boldsymbol{0})\in\operatorname{conv}(\\{(\Gamma(\boldsymbol{\beta}),-\boldsymbol{\beta})\,:\
\boldsymbol{\beta}\in D^{2}\\})$ and contradict Theorem 1.2. However, the blue
(respectively, the green) arc must be mapped by $\Gamma$ to an arc of the same
length. The equation
$\Gamma(\boldsymbol{\beta}^{1})=\Gamma(\boldsymbol{\beta}^{3})$ then shows
that the blue and green arcs must have the same length, which is not true.

We believe that finding a characterization of when a set of points in $D^{m}$
can be used to define a maximal $Q$-free polyhedron is an important follow-up
question in the understanding of maximal $Q$-free sets.

Beyond the homogeneous setting, it is interesting and potentially impactful to
consider the non-homogeneous case. For instance, which maximal sets in the
homogeneous setting are maximal for the non-homogeneous setting, or how can
one lift maximal $Q$-free sets to handle the non-homogeneous setting.

## Statements and Declaration.

Funding. J. Paat was supported by a Natural Sciences and Engineering Research
Council of Canada Discovery Grant [RGPIN-2021-02475]. G. Muñoz was supported
by the National Research and Development Agency of Chile (ANID) through the
Fondecyt Grant 1231522.

Competing interests. The authors have no relevant financial or non-financial
interests to disclose.

Compliance with Ethical Standards. The authors have no conflicts of interest
to declare that are relevant to the content of this article.

Acknowledgements The authors would like to thank Roberto Cominetti for
fruitful discussions; in particular, for discussions leading to Remark 3, for
noticing the subtlety in Theorem 17.3 from R1970  discussed in Remark 5, and
for the example provided in the latter.

## References

  * (1) Andersen, K., Jensen, A.: Intersection cuts for mixed integer conic quadratic sets.  In: Integer Programming and Combinatorial Optimization, pp. 37–48. Springer (2013)
  * (2) Andersen, K., Louveaux, Q., Weismantel, R., Wolsey, L.: Cutting planes from two rows of the simplex tableau.  Proceedings of Integer Programming and Combinatorial Optimization (IPCO) pp. 1–15 (2007)
  * (3) Averkov, G.: On maximal s-free sets and the helly number for the family of s-convex sets.  SIAM Journal on Discrete Mathematics 27(3), 1610–1624 (2013)
  * (4) Averkov, G.: A proof of Lovász’s theorem on maximal lattice-free sets.  Contributions to Algebra and Geometry (2013)
  * (5) Averkov, G., Basu, A., Paat, J.: Approximation of corner polyhedra with families of intersection cuts.  SIAM Journal on Optimization 28(1), 904–929 (2018)
  * (6) Baes, M., Oertel, T., Weismantel, R.: Duality for mixed-integer convex minimization.  Mathematical Programming 158, 547–564 (2016)
  * (7) Balas, E.: Intersection cuts - a new type of cutting planes for integer programming.  Operations Research (1971)
  * (8) Basu, A., Conforti, M., Cornuéjols, G., Weismantel, R., Weltge, S.: Optimality certificates for convex minimization and Helly numbers.  Operations Research Letters 45(6), 671–674 (2017)
  * (9) Basu, A., Conforti, M., Cornuéjols, G., Zambelli, G.: Maximal lattice-free convex sets in linear subspaces.  Mathematics of Operations Research 35(3), 704–720 (2010)
  * (10) Basu, A., Conforti, M., Cornuéjols, G., Zambelli, G.: Minimal inequalities for an infinite relaxation of integer programs.  SIAM Journal on Discrete Mathematics 24(1), 158–168 (2010)
  * (11) Basu, A., Dey, S., Paat, J.: Nonunique lifting of integer variables in minimal inequalities.  SIAM Journal on Discrete Mathematics (2019)
  * (12) Bienstock, D., Chen, C., Muñoz, G.: Intersection cuts for polynomial optimization.  In: A. Lodi, V. Nagarajan (eds.) Integer Programming and Combinatorial Optimization, pp. 72–87. Springer International Publishing, Cham (2019)
  * (13) Bienstock, D., Chen, C., Muñoz, G.: Outer-product-free sets for polynomial optimization and oracle-based cuts.  Mathematical Programming 183, 105–148 (2020)
  * (14) Chmiela, A., Muñoz, G., Serrano, F.: On the implementation and strengthening of intersection cuts for qcqps.  Mathematical Programming pp. 1–38 (2022)
  * (15) Conforti, M., Cornuéjols, G., Daniilidis, A., Lemaréchal, C., Malick, J.: Cut-generating functions and S-free sets.  Mathematics of Operations Research (2014)
  * (16) Conforti, M., Cornuéjols, G., Zambelli, G.: A geometric perspective on lifting.  Operations Research 59(3), 569–577 (2011)
  * (17) Conforti, M., Cornuéjols, G., Zambelli, G.: Integer Programming.  Springer (2014)
  * (18) Conforti, M., Summa, M.D.: Maximal s-free convex sets and the helly number.  SIAM Journal on Discrete Mathematics 30(4), 2206–2216 (2016)
  * (19) Dey, S., Wolsey, L.: Two row mixed-integer cuts via lifting.  Mathematical Programming 124, 143–174 (2010)
  * (20) Lovász, L.: Geometry of numbers and integer programming.  In: M.Iri, K. Tanabe (eds.) Mathematical Programming: Recent Developments and Applications, pp. 177 – 201. Kluwer Academic Publishers (1989)
  * (21) Modaresi, S., Kılınç, M., Vielma, J.: Intersection cuts for nonlinear integer programming convexification techniques for structured sets.  Mathematical Programming (2016)
  * (22) Muñoz, G., Paat, J., Serrano, F.: Towards a characterization of maximal quadratic-free sets.  In: A. Del Pia, V. Kaibel (eds.) Integer Programming and Combinatorial Optimization, pp. 334–347. Springer International Publishing, Cham (2023)
  * (23) Muñoz, G., Serrano, F.: Maximal quadratic-free sets.  Proceedings of the International Conference on Integer Programming and Combinatorial Optimization pp. 307–321 (2020)
  * (24) Muñoz, G., Serrano, F.: Maximal quadratic-free sets.  Mathematical Programming 192, 229–270 (2022)
  * (25) Paat, J., Schlöter, M., Speakman, E.: Constructing lattice-free gradient polyhedra in dimension two.  Mathematical Programming 192(1), 293–317 (2022)
  * (26) Rockafellar, R.T.: Convex analysis.  Princeton university press (1970)
  * (27) Tuy, H.: Concave minimization under linear constraints with special structure.  Doklady Akademii Nauk 159, 32–35 (1964)