# On the Polyhedrality of the Chvátal-Gomory Closure

Haoran Zhu Department of Industrial and Systems Engineering, University of
Wisconsin-Madison. E-mail<EMAIL_ADDRESS>
###### Abstract

In this paper, we provide an equivalent condition for the Chvátal-Gomory (CG)
closure of a closed convex set to be finitely-generated. Using this result, we
are able to prove that, for any closed convex set that can be written as the
Minkowski sum of a compact convex set and a closed convex cone, its CG closure
is a rational polyhedron if and only if its recession cone is a rational
polyhedral cone. As a consequence, this generalizes and unifies all the
currently known results, for the case of rational polyhedron [24] and compact
convex set [9].

_Key words:_ Chvátal-Gomory closure $\cdot$ polyhedral $\cdot$ cutting-planes

##  1 Introduction

Cutting-plane method is one of the most fundamental techniques for solving
(mixed) integer programming problems, and often times in practice, it is
combined with the branch-and-bound method. Since the early days of Integer
Programming (IP), numerous types of cutting-planes have been introduced and
studied in the literature, several of them have also been widely implemented
into commercial solvers. Among those cuts, Chvàtal-Gomory (CG) cut ([18, 5])
was the first cutting-plane that has ever been proposed, and various
interesting results have been obtained from both the theoretical and practical
point of view (see, e.g., [6, 3, 15]).

One of the theoretical questions regarding to CG cut is, what are the
structural properties of the region obtained from intersecting all of those
cuts? In the terminology of cutting-plane theory, this region is referred to
as _Chvàtal-Gomory (CG) closure_. Although the definition of CG cut has
traditionally been defined with respect to a rational polyhedron for an
Integer Linear Programming (ILP) problem, they straightforwardly generalize to
the nonlinear setting and hence can be used for convex Integer Nonlinear
Programming (INLP). Let $K$ be a closed convex set and let $\sigma_{K}$ denote
the support function of $K:\sigma_{K}(c)=\sup_{x\in K}cx$. For the ease of
notation, here we abbreviate the inner product $c^{T}x$ as $cx$. Given
$c\in\mathbb{Z}^{n}$, the CG cut for $K$ that is derived from $c$ is defined
as: $cx\leq\lfloor\sigma_{K}(c)\rfloor.$ Then, the so-called CG closure of $K$
is:

$K^{\prime}:=\bigcap_{c\in\mathbb{Z}^{n}}\\{x\in\mathbb{R}^{n}\mid
cx\leq\lfloor\sigma_{K}(c)\rfloor\\}.$

Here the CG closure $K^{\prime}$ is essentially obtained from the intersection
of potentially infinitely many half-spaces, hence the polyhedrality of
$K^{\prime}$ is unclear. As named in [1], here we call $K^{\prime}$ is
_finitely-generated_ , if there exists a finite set
$F\subseteq\mathbb{Z}^{n}$, such that $K^{\prime}=\bigcap_{f\in
F}\\{x\in\mathbb{R}^{n}\mid fx\leq\lfloor\sigma_{K}(f)\rfloor\\}.$ Obviously,
a finitely-generated CG closure is a rational polyhedron. Four decades ago,
Schrijver [24] shows that, when $K$ is a rational polyhedron, $K^{\prime}$ is
finitely-generated. Schrijver further asks the following question: when $K$ is
an irrational polytope, is $K^{\prime}$ still a (rational) polytope?

As attempts to fully understand this question, a series of studies have been
conducted for the polyhedrality of CG closure of various convex sets. In [12],
Dey and Vielma show that, the CG closure of a bounded full-dimensional
ellipsoid, described by rational data, is a rational polytope. In [8], Dadush,
Dey and Vielma show the CG closure of a set obtained as an intersection of a
strictly convex body and a rational polyhedron is a polyhedron. Along this
line of work, in [9], the same group of authors extend the same result to
compact convex sets, therefore giving affirmation answer to the long-standing
open problem raised by Schrijver. Almost simultaneously this problem was also
proved by Dunkel and Schulz [14] independently, where they specifically prove
for the case of irrational polytope, instead of a more general compact convex
set. All their proofs are very much involved, a few years later Braun and
Pokutta [4] give a short proof for the same result as [9]. However, no matter
how different these proofs might seem, they all share some high-level
similarities. For example, they all rely heavily on the _homogeneity property_
of CG closure: $F^{\prime}=K^{\prime}\cap F$ for any face $F$ of $K$. By
inductive hypothesis that $F^{\prime}$ is rational polyhedral and some
additional argument, they will be able to obtain the polyhedrality of
$K^{\prime}$. As we will see later, in contrast to all these work in the
literature, we are taking a completely different perspective and do not make
use of the homogeneity property of CG closure. Key is here a characterization
result for general cutting-plane closures from which a fundamental Theorem 1
is derived. We believe that the basic proof technique here lends itself to
potentially many more classes of cutting-planes.

Now we highlight the main results of this paper in the next section.

###  1.1 Main Results

With respect to the CG closure of general closed convex set, we have the first
main result:

######  Theorem 1.

Given a closed convex set $K$ in $\mathbb{R}^{n}$, then $K^{\prime}$ is
finitely-generated if and only if there exists a finite subset
$F\subseteq\mathbb{Z}^{n}$, such that $\left\\{x\in\mathbb{R}^{n}\mid
fx\leq\lfloor\sigma_{K}(f)\rfloor,\forall f\in F\right\\}\subseteq K.$

Based on this above theorem, we are able to prove the following result.

######  Theorem 2.

If $K$ is a Motzkin-decomposable set, then the following statements are
equivalent:

  1. 1.

$K^{\prime}$ is a finitely-generated.

  2. 2.

$K^{\prime}$ is a rational polyhedron.

  3. 3.

$K$ has rational polyhedral recession cone.

Here a set $K\subseteq\mathbb{R}^{n}$ is called _Motzkin-decomposable_ (see,
e.g., [17, 20]), if there exist a compact convex set $C$ and a closed convex
cone $D$ such that $K=C+D$. By Minkowski-Weyl theorem, a polyhedron is a
Motzkin-decomposable set, thus the last theorem generalizes and unifies all
the currently known results for rational polyhedron and compact convex set.
Moreover, using the characterization result in [11] for the polyhedrality of
integer hull, we can immediately obtain the next result as a corollary:

######  Corollary 1.

If $K$ is a Motzkin-decomposable set in $\mathbb{R}^{n}$ and contains integer
points in its interior, then $K^{\prime}$ is a rational polyhedron if and only
if $\operatorname{conv}(K\cap\mathbb{Z}^{n})$ is a polyhedron.

Here $\operatorname{conv}(K\cap\mathbb{Z}^{n})$ is called the _integer hull_
of $K$. As a footnote in [9], the authors wrote the following sentences to
justify the reason why they focus on the case of a compact convex set:

> “ If the convex hull of integer points in a convex set is not polyhedral,
> then the CG closure cannot be expected to be polyhedral. Since we do not
> have a good understanding of when this holds for unbounded convex set, we
> restrict our attention here to the CG closure of compact convex sets. ”

Therefore, our Corollary 1 directly addresses their concern.

This paper is organized as follows. In Section 2 we present some
characterizations for the polyhedrality of general cutting-plane closure and
some preliminary results that will be used later. In Section 3, we verify
Theorem 1, and in Section 4, we verify Theorem 2 and Corollary 1.

#### _Notations and assumptions._

For any $x\in\mathbb{R}^{n}$ and a linear subspace $L\subseteq\mathbb{R}^{n}$,
we denote by $\operatorname{proj}_{L}x$ the orthogonal projection of $x$ onto
$L$, and for any
$X\subseteq\mathbb{R}^{n},\operatorname{proj}_{L}X:=\\{\operatorname{proj}_{L}x\mid
x\in X\\}$. For any set
$S\subseteq\mathbb{R}^{n},\operatorname{lin}(S):=S\cap(-S)$ denotes the
_lineality space_ of $S$, which is the largest linear subspace contained in
$S$. $\operatorname{cone}(S):=\\{\sum_{i=1}^{k}\lambda_{i}s_{i}\mid\forall
k\in\mathbb{N},\lambda_{i}\geq 0,s_{i}\in S\ \forall i\in[k]\\}$ denotes the
_conical hull_ of $S$, and $(S)_{+}:=\\{\lambda s\mid\forall\lambda\geq 0,s\in
S\\}$ denotes the cone that contains all non-negative multiplication of
elements in $S$. For a linear subspace $L$, we denote by $L^{\perp}$ the
orthogonal complement of $L$. For a closed convex set
$K,\operatorname{rec}(K):=\\{r\mid k+\lambda r\in K,\forall k\in K,\lambda\geq
0\\}$ denotes the _recession cone_ of $K$, and $\operatorname{ext}(K)$ denotes
the set of extreme points of $K$.
$O_{\epsilon}(x^{*})=\\{x\in\mathbb{R}^{n}\mid\|x-x^{*}\|\leq\epsilon\\}$
denotes the $\epsilon$-ball centered at $x^{*}$ in its ambient space.
Throughout, all norm $\|\cdot\|$ refers to the Euclidean norm. For a matrix
$M$, we denote by $\ker(M)$ the kernel of $M$.

##  2 Preliminary Results

The well-known Dickson’s lemma will be used in our later proof, and it also
played an important role in some other relevant closure papers, see, e.g., [1,
10, 28].

######  Lemma 1 (Dickson’s lemma [13]).

For any $X\subseteq\mathbb{N}^{n}$, the partially-ordered set (poset)
$(X,\leq)$ has no infinite antichain.

In order theory, an _antichain (chain)_ is a subset of a poset such that any
two distinct elements in the subset are incomparable (comparable).

Now we define a new concept for the convergence of rays in a cone.

######  Definition 1.

Given a sequence $\\{\alpha^{i}\\}_{i\in\mathbb{N}}\subseteq\mathbb{R}^{n}$
and $\alpha^{*}\neq 0\in\mathbb{R}^{n}$, if there exists
$\\{\lambda_{i}\\}_{i\in\mathbb{N}}>0$ such that
$\lim_{i\rightarrow\infty}\lambda_{i}\alpha^{i}=\alpha^{*}$, then we say
$\\{\alpha^{i}\\}$ conically converges to $\alpha^{*}$, or
$\alpha^{i}\xrightarrow{c}\alpha^{*}$.

For the conical convergence, we have the following easy result.

######  Lemma 2.

Given a sequence $\\{\alpha^{i}\\}_{i\in\mathbb{N}}\subseteq\mathbb{R}^{n}$
such that $\alpha^{i}\xrightarrow{c}\alpha^{*}$ and
$\alpha^{i}\xrightarrow{c}\beta^{*}$ when $i\rightarrow\infty$, then there
exists $\lambda>0,$ such that $\alpha^{*}=\lambda\beta^{*}.$

###### Proof.

By assumption, we know there exists
$\\{\gamma_{i}\\},\\{\mu_{i}\\}\subseteq\mathbb{R}_{+}$, such that
$\gamma_{i}\alpha^{i}\rightarrow\alpha^{*},\mu_{i}\alpha^{i}\rightarrow\beta^{*}$.
Let $\beta^{i}:=\mu_{i}\alpha^{i}$. Then we have:
$\beta^{i}\rightarrow\beta^{*},\frac{\gamma_{i}}{\mu_{i}}\beta^{i}\rightarrow\alpha^{*}$.
Hence
$\frac{\gamma_{i}}{\mu_{i}}\rightarrow\frac{\|\alpha^{*}\|}{\|\beta^{*}\|}$,
and $\alpha^{*}=\frac{\|\alpha^{*}\|}{\|\beta^{*}\|}\beta^{*}$. ∎

In a recent paper [28], the authors study the equivalent condition for a
general cutting-plane closure to be polyhedral. In this section, we will
follow the same notations and definitions as in [28], and exploit the
characterization results therein to derive new results for CG closure. For the
completeness of this paper, we will include the proofs for those results in
the Appendix.

Given a family of cutting-planes $\alpha x\leq\beta$ for any
$(\alpha,\beta)\in\Omega$, it is referred to as “a family of cuts given by
$\Omega$”. Then the corresponding _(cutting-plane) closure_ is defined as:

$\mathscr{I}(\Omega):=\bigcap_{(\alpha,\beta)\in\Omega}\\{x\in\mathbb{R}^{n}\mid\alpha
x\leq\beta\\}.$ (1)

Here without loss of generality (w.l.o.g.) we can assume that
$(0,\ldots,0,1)\in\Omega$, since $(0,\ldots,0,1)$ corresponds to the trivial
inequality $0\cdot x\leq 1$.

For the valid inequality of the closure, we have the following result.

######  Proposition 1 (Proposition 1 [28]).

Given $\Omega\subseteq\mathbb{R}^{n+1}$ containing $(0,\ldots,0,1)$, such that
$\mathscr{I}(\Omega)\neq\emptyset$. Then $\alpha x\leq\beta$ is a valid
inequality to $\mathscr{I}(\Omega)$ if and only if
$(\alpha,\beta)\in\operatorname{cl}\operatorname{cone}(\Omega)$.

For any set $S$, we use $\operatorname{cl}(S)$ to denote the smallest closed
set containing $S$, which is also called _closure_ in topology. To avoid
confusion, we will only use $\operatorname{cl}(S)$ to refer the topological
closure. This above proposition immediately implies the following consequence.

######  Corollary 2.

Given $\Omega\subseteq\mathbb{R}^{n+1}$ containing $(0,\ldots,0,1)$ with
$\mathscr{I}(\Omega)\neq\emptyset$. Then $\mathscr{I}(\Omega)$ is finitely-
generated if and only if there exists a finite subset
$\bar{\Omega}\subseteq\Omega$ such that
$\operatorname{cone}(\bar{\Omega})=\operatorname{cl}\operatorname{cone}(\Omega)$.

The proofs for both Proposition 1 and Corollary 2 can be found in Appendix C.
From this above Corollary 2, we know that in order to show
$\mathscr{I}(\Omega)$ is finitely-generated, it suffices to show
$\operatorname{cl}\operatorname{cone}(\Omega)$ is a polyhedral cone and can be
generated by finitely many elements from $\Omega$. The next easy lemma is
helpful for characterizing $\operatorname{cl}\operatorname{cone}(\Omega)$.
Here the $\oplus$ denotes the _direct sum_.

######  Lemma 3.

For any $\Omega\subseteq\mathbb{R}^{n}$, let
$L=\operatorname{lin}(\operatorname{cl}\operatorname{cone}(\Omega))$. Then
$\operatorname{cl}\operatorname{cone}(\Omega)=\operatorname{cl}\operatorname{cone}(\operatorname{proj}_{L^{\perp}}\Omega)\oplus
L$, where
$\operatorname{cl}\operatorname{cone}(\operatorname{proj}_{L^{\perp}}\Omega)$
is a pointed, closed convex cone.

Recall that a cone is called _pointed_ if its lineality space is the origin.
In order to prove such result, we will also require the following lemma.

######  Lemma 4 (fact 9 [26]).

Given a non-empty closed convex cone $K$, $K\cap\operatorname{lin}(K)^{\perp}$
is a pointed cone and
$K=(K\cap\operatorname{lin}(K)^{\perp})\oplus\operatorname{lin}(K)$.

###### Proof of Lemma 3.

By Lemma 4, it suffices to show:
$\operatorname{cl}\operatorname{cone}(\operatorname{proj}_{L^{\perp}}\Omega)=\operatorname{cl}\operatorname{cone}(\Omega)\cap
L^{\perp}$. First, we want to show
$\operatorname{cl}\operatorname{cone}(\operatorname{proj}_{L^{\perp}}\Omega)\subseteq\operatorname{cl}\operatorname{cone}(\Omega)\cap
L^{\perp}$. The relation
$\operatorname{cl}\operatorname{cone}(\operatorname{proj}_{L^{\perp}}\Omega)\subseteq\operatorname{cl}\operatorname{cone}(L^{\perp})=L^{\perp}$
is obvious. Moreover, for any $\omega\in\Omega,\
\operatorname{proj}_{L^{\perp}}\omega=\omega-r,$ for some $r\in L$. Hence
$\operatorname{proj}_{L^{\perp}}\Omega\subseteq\Omega+L\subseteq\operatorname{cl}\operatorname{cone}(\Omega)+\operatorname{cl}\operatorname{cone}(\Omega)=\operatorname{cl}\operatorname{cone}(\Omega)$.
Therefore,
$\operatorname{cl}\operatorname{cone}(\operatorname{proj}_{L^{\perp}}\Omega)\subseteq\operatorname{cl}\operatorname{cone}(\Omega)$,
which completes the proof of this $\subseteq$ direction.

Then, we want to show that
$\operatorname{cl}\operatorname{cone}(\operatorname{proj}_{L^{\perp}}\Omega)\supseteq\operatorname{cl}\operatorname{cone}(\Omega)\cap
L^{\perp}$. Arbitrarily pick
$x^{*}\in\operatorname{cl}\operatorname{cone}(\Omega)\cap L^{\perp}$. If
$x^{*}\in\operatorname{cone}(\Omega)$, then
$x^{*}=\operatorname{proj}_{L^{\perp}}x^{*}\in\operatorname{proj}_{L^{\perp}}\operatorname{cone}(\Omega)=\operatorname{cone}(\operatorname{proj}_{L^{\perp}}\Omega)$.
If $x^{i}\rightarrow x^{*}$ for a sequence of
$\\{x^{i}\\}\subseteq\operatorname{cone}(\Omega)$, then
$\operatorname{proj}_{L^{\perp}}x^{i}\rightarrow x^{*}$ where
$\operatorname{proj}_{L^{\perp}}x^{i}\in\operatorname{proj}_{L^{\perp}}\operatorname{cone}(\Omega)=\operatorname{cone}(\operatorname{proj}_{L^{\perp}}\Omega).$
Hence
$x^{*}\in\operatorname{cl}\operatorname{cone}(\operatorname{proj}_{L^{\perp}}\Omega)$.
This completes the proof. ∎

It is well-known that, a pointed, closed convex cone is a polyhedral cone, if
and only if it has finitely many different extreme rays. For a pointed
$\operatorname{cl}\operatorname{cone}(\Omega)$, its extreme rays can be
exactly characterized by elements in $\Omega$, as stated by the next lemma. We
include its proof in Appendix D.

######  Lemma 5 (Corollary 1, Lemma 3 [28]).

Given $\Omega\subseteq\mathbb{R}^{n+1}$ with $(0,\ldots,0,1)\in\Omega$ and
$0\notin\Omega$. If $\operatorname{cl}\operatorname{cone}(\Omega)$ is pointed,
then for any extreme ray $r$ of
$\operatorname{cl}\operatorname{cone}(\Omega)$, either $r\in(\Omega)_{+}$, or
there exist different $\\{r^{i}\\}\subseteq\Omega$ such that
$r^{i}\xrightarrow{c}r$.

Henceforth, when we mention a ray $r$ of a cone, we will make no distinction
between $r$ and its positive scalar multiplication. In other words, we say two
rays $r^{1}$ and $r^{2}$ are different, if and only if there does not exist
$\lambda>0$, such that $r^{1}=\lambda r^{2}$.

##  3 Chvátal-Gomory Closure of Closed Convex Set.

We will prove Theorem 1 in this section.

For a given closed convex set $K$, we denote the family of CG cuts of $K$ to
be:

$\Omega_{\text{CG}}:=\\{(0,\ldots,0,1)\\}\cup\\{(c,\lfloor\sigma_{K}(c)\rfloor),\forall
c\in\mathbb{Z}^{n}\\}.$ (2)

Then by definition of CG closure, there is
$K^{\prime}=\mathscr{I}(\Omega_{\text{CG}})$. For ease of notation, when it is
clear from the context, we will not specify what is the corresponding closed
convex set $K$ of $\Omega_{\text{CG}}$. Throughout, a CG cut
$cx\leq\lfloor\sigma_{K}(c)\rfloor$ will sometimes also be referred to as a
vector $(c,\lfloor\sigma_{K}(c)\rfloor)$.

Before presenting the proof for the main Theorem 1, we will need the following
lemmas.

######  Lemma 6 (Gordan’s lemma).

Given a lattice $L\subseteq\mathbb{Z}^{n}$ and a rational polyhedral cone
$C\subseteq\mathbb{R}^{n}$. Then there exists a finite set of lattice points
$\\{g^{1},\ldots,g^{m}\\}\subset C\cap L$ such that every point $x\in C\cap L$
is an integer conical combination of these points:
$x=\sum_{j=1}^{m}\lambda_{j}g^{j},\lambda_{j}\in\mathbb{N}$ for all $j\in[m].$

Here the finite generator $\\{g^{1},\ldots,g^{m}\\}$ of $C\cap L$ in the above
lemma is usually referred to as the _Hilbert basis_ of $C$ (see, e.g., [7]).
From Gordan’s lemma we obtain the next result.

######  Lemma 7.

Given a rational polyhedral cone $C\subseteq\mathbb{R}^{n}$, a sequence of
integer vectors $\\{v^{i}\\}_{i\in\mathbb{N}}\subseteq C\cap\mathbb{Z}^{n}$,
and a rational vector $q^{*}\in\mathbb{Q}^{n}$. Then there must exist an
infinite set $I\subseteq\mathbb{N}$ and $i^{*}\in\mathbb{N}$, such that for
any $i\in I,v^{i}-v^{i^{*}}\in C$, and $v^{i}q^{*}-\lfloor
v^{i}q^{*}\rfloor=v^{i^{*}}q^{*}-\lfloor v^{i^{*}}q^{*}\rfloor$.

###### Proof.

By Lemma 6, we know there exist $g^{1},\ldots,g^{m}\in C\cap\mathbb{Z}^{n}$,
such that $x\in C\cap\mathbb{Z}^{n}$ if and only if $x$ can be written as the
integer conical combination of these points. Therefore, for each $v^{i}$,
there exists $\lambda^{i}\in\mathbb{N}^{m}$ such that
$v^{i}=\sum_{j=1}^{m}\lambda^{i}_{j}g^{j}$.

Folklore _An infinite poset contains either an infinite chain or an infinite
antichain._

Within the infinite poset
$\Lambda:=\\{\lambda^{i}\\}_{i\in\mathbb{N}}\subseteq\mathbb{N}^{m}$ ordered
by component-wise order $\leq$, from the Dickson’s Lemma 1 and this above
folklore, we know there must exist an infinite index set
$I^{\prime}\subseteq\mathbb{N}$, such that $\\{\lambda^{i}\\}_{i\in
I^{\prime}}$ is an infinite chain within $\mathbb{N}^{m}.$

Since $q^{*}$ is a rational vector, we can write it as $q^{*}:=\frac{1}{D}z$,
where $z\in\mathbb{Z}^{n}$, and $D$ is the least common multiple of the
denominators of each $q_{1},\ldots,q_{n}$. So for any
$v^{i}\in\mathbb{Z}^{n},v^{i}q^{*}$ can be written as $\frac{1}{D}\cdot
v^{i}z$ , where $c^{i}z\in\mathbb{Z}$. Therefore, $\\{v^{i}q^{*}-\lfloor
v^{i}q^{*}\rfloor\mid i\in
I^{\prime}\\}\subseteq\\{0,\frac{1}{D},\ldots,\frac{D-1}{D}\\}$, which is a
finite set. Here $I^{\prime}$ is an infinite index set, by the pigeonhole
principle, there also exists another infinite index set $I\subseteq
I^{\prime}$, such that $v^{i}q^{*}-\lfloor
v^{i}q^{*}\rfloor=v^{j}q^{*}-\lfloor v^{j}q^{*}\rfloor$ for any $i,j\in I.$

So far we have obtained an infinite index set $I$, such that for any $i\in
I,v^{i}=\sum_{j=1}^{m}\lambda^{i}_{j}g^{j}$, $\\{\lambda^{i}\\}_{i\in I}$ is
an infinite chain within $\mathbb{N}^{m}$, and $v^{i}q^{*}-\lfloor
v^{i}q^{*}\rfloor=v^{j}q^{*}-\lfloor v^{j}q^{*}\rfloor$ for any $i,j\in I$.
Since $\\{\lambda^{i}\\}_{i\in I}$ is an infinite chain within
$\mathbb{N}^{m}$, then there must exist $i^{*}\in I$ such that
$\lambda^{i^{*}}$ is the least element (a.k.a. minimum element) of
$\\{\lambda^{i}\\}_{i\in I}$. Therefore, for any $i\in I$, $v^{i}q^{*}-\lfloor
v^{i}q^{*}\rfloor=v^{i^{*}}q^{*}-\lfloor v^{i^{*}}q^{*}\rfloor$ and
$\lambda^{i}\geq\lambda^{i^{*}}$, which implies that
$v^{i}-v^{i^{*}}=\sum_{j=1}^{m}(\lambda^{i}_{j}-\lambda^{i^{*}}_{j})g^{j}\in
C$. ∎

The next lemma states that, within any infinite sequence of CG cuts of $K$,
there must exist a conically convergent subsequence which converges to a valid
inequality of $K$.

######  Lemma 8.

Given a closed convex set $K$ and a sequence
$\\{(r^{i},\lfloor\sigma_{K}(r^{i})\rfloor)\\}_{i\in\mathbb{N}}\subseteq\Omega_{\text{CG}}$.
Then there exists a subsequence
$\\{(r^{i},\lfloor\sigma_{K}(r^{i})\rfloor)\\}_{i\in I}$, such that when $i\in
I,i\rightarrow\infty$,
$(r^{i},\lfloor\sigma_{K}(r^{i})\rfloor)\xrightarrow{c}(r^{*},r^{*}_{0})$ for
some valid inequality $r^{*}x\leq r^{*}_{0}$ of $K$.

###### Proof.

Picking $\gamma_{i}:=\frac{1}{\|(r^{i},\lfloor\sigma_{K}(r^{i})\rfloor)\|}$
for all $i\in\mathbb{N}$. Then
$\gamma_{i}(r^{i},\lfloor\sigma_{K}(r^{i})\rfloor)\in O_{1}(0)$ which is a
compact set. By Bolzano-Weierstrass theorem, we can find a convergent
subsequence $\\{\gamma_{i}(r^{i},\lfloor\sigma_{K}(r^{i})\rfloor)\\}_{i\in
I}$. Denote
$\gamma_{i}(r^{i},\lfloor\sigma_{K}(r^{i})\rfloor)\rightarrow(r^{*},r^{*}_{0})$.
Since each $r^{i}\in\mathbb{Z}^{n}$, we know there exists an infinite
subsequence of $\\{r^{i}\\}_{i\in I}$ such that $\|r^{i}\|\rightarrow\infty$.
W.l.o.g. we assume $\|r^{i}\|\rightarrow\infty$ when $i\rightarrow\infty$,
since $\gamma_{i}r^{i}\rightarrow r^{*}$, then there is $\gamma_{i}\rightarrow
0$. Furthermore, because $\gamma_{i}\lfloor\sigma_{K}(r^{i})\rfloor\rightarrow
r^{*}_{0}$ and
$\gamma_{i}(\sigma_{K}(r^{i})-1)<\gamma_{i}\lfloor\sigma_{K}(r^{i})\rfloor\leq\gamma_{i}\sigma_{K}(r^{i})$,
we know that $\gamma_{i}\sigma_{K}(r^{i})\rightarrow r^{*}_{0}$. Now we want
to argue that $r^{*}x\leq r^{*}_{0}$ is valid to $K$. If not, then there
exists $x^{*}\in K$ such that $r^{*}x^{*}>r^{*}_{0}$. Denote
$\epsilon:=r^{*}x^{*}-r^{*}_{0}>0$. Since
$\gamma_{i}(r^{i},\sigma_{K}(r^{i}))\rightarrow(r^{*},r^{*}_{0})$, then there
exist $N_{0}\in\mathbb{N}$ and $\kappa:=\frac{\epsilon}{2(1+\|x^{*}\|)}$, such
that when $i\geq N_{0}:$

$\|r^{*}-\gamma_{i}r^{i}\|\leq\kappa,\quad|r^{*}_{0}-\gamma_{i}\sigma_{K}(r^{i})|\leq\kappa.$

Therefore, when $i\geq N_{0}$:

$\displaystyle\begin{split}\gamma_{i}r^{i}x^{*}-\gamma_{i}\sigma_{K}(r^{i})&\geq
r^{*}x^{*}-\kappa\|x^{*}\|-r^{*}_{0}-\kappa\\\
&=\epsilon-\kappa(1+\|x^{*}\|)\\\ &=\frac{1}{2}\epsilon>0.\end{split}$

This gives the contradiction since $r^{i}x\leq\sigma_{K}(r^{i})$ is valid to
$K$. ∎

Next we present the most crucial result for establishing the proof of the main
theorem.

######  Proposition 2.

Given a closed convex set $K\subseteq\mathbb{R}^{n}$ and a rational polyhedron
$P\subseteq K$ such that $P=\left\\{x\in\mathbb{R}^{n}\mid
fx\leq\lfloor\sigma_{K}(f)\rfloor,\forall f\in F\right\\}$ for some finite set
$F\subseteq\mathbb{Z}^{n}$. If
$\\{(c^{i},\lfloor\sigma_{K}(c^{i})\rfloor)\\}_{i\in\mathbb{N}}\subseteq\Omega_{\text{CG}}$
is a sequence of vectors with
$\sigma_{P}(c^{i})>\lfloor\sigma_{K}(c^{i})\rfloor$ for any $i\in\mathbb{N}$,
then there exist a finite set $\Lambda\subseteq\Omega_{\text{CG}}$ and an
infinite index set $I\subseteq\mathbb{N}$, such that
$(c^{i},\lfloor\sigma_{K}(c^{i})\rfloor)\in\operatorname{cone}(\Lambda)$ for
any $i\in I$.

###### Proof.

For each $i\in\mathbb{N}$, since $P\subseteq K$, there is
$\sigma_{P}(c^{i})\leq\sigma_{K}(c^{i})<\infty$, we know there exists extreme
point $p^{i}$ of $P$, such that $c^{i}p^{i}=\sigma_{P}(c^{i})$. So from the
condition of this proposition, we have the following inequalities:

$\sigma_{K}(c^{i})\geq
c^{i}p^{i}=\sigma_{P}(c^{i})>\lfloor\sigma_{K}(c^{i})\rfloor.$

Hence $c^{i}p^{i}>\lfloor\sigma_{K}(c^{i})\rfloor=\lfloor c^{i}p^{i}\rfloor$,
for all $i\in\mathbb{N}$. This can be visualized in Fig. 1. Since the number
of extreme points of polyhedron $P$ is finite, by the pigeonhole principle, we
know there exist a single extreme point $p^{*}$ of $P$ and an infinite subset
$I_{1}\subseteq\mathbb{N}$, such that $p^{i}=p^{*}$ for any $i\in I_{1}$. Note
that for a rational polyhedron $P$ and an extreme point $p^{*}\in P$,
$c^{i}p^{*}=\sigma_{P}(c^{i})$ if and only if

$c^{i}\in C:=\\{x\in\mathbb{R}^{n}\mid(p^{*}-p)x\geq 0\ \forall
p\in\operatorname{ext}(P),rx\leq 0\ \forall r\in\operatorname{rec}(P)\\},$

where $C$ is a rational polyhedral cone. For the rational vector $p^{*}$ and
rational polyhedral cone $C$, by Lemma 7, we know there exist another infinite
subset $I\subseteq I_{1}$ and $i^{*}\in I_{1}$, such that for any $i\in
I,c^{i}-c^{i^{*}}\in C$, and $c^{i}p^{*}-\lfloor
c^{i}p^{*}\rfloor=c^{i^{*}}p^{*}-\lfloor c^{i^{*}}p^{*}\rfloor$. Now we denote

$\Lambda:=\\{(f,\lfloor\sigma_{K}(f)\rfloor)\ \forall f\in
F,(c^{i^{*}},\lfloor\sigma_{K}(c^{i^{*}})\rfloor),(0,\ldots,0,1)\\}.$

Here we have $\Lambda\subseteq\Omega_{\text{CG}}$ and $\Lambda$ is a finite
set.

Lastly, we want to show that the above constructed $I$ and $\Lambda$ satisfy
the condition of this proposition, namely, for any $i\in I$, there is
$(c^{i},\lfloor\sigma_{K}(c^{i})\rfloor)\in\operatorname{cone}(\Lambda)$. By
condition of $I$ and $i^{*}$, we know $c^{i}-c^{i^{*}}\in C$, which means
$(c^{i}-c^{i^{*}})x\leq(c^{i}-c^{i^{*}})p^{*}$ is valid to $P$. By definition
of $P$, so this implies that
$(c^{i}-c^{i^{*}},c^{i}p^{*}-c^{i^{*}}p^{*})\in\operatorname{cone}(\\{(f,\lfloor\sigma_{K}(f)\rfloor)\
\forall f\in F,(0,\ldots,0,1)\\})$. Note that for any $i\in
I,c^{i}p^{*}-\lfloor c^{i}p^{*}\rfloor=c^{i^{*}}p^{*}-\lfloor
c^{i^{*}}p^{*}\rfloor$, therefore:

$\displaystyle\begin{split}(c^{i},\lfloor\sigma_{K}(c^{i})\rfloor)&=(c^{i},\lfloor
c^{i}p^{*}\rfloor)\\\ &=(c^{i^{*}},\lfloor
c^{i^{*}}p^{*}\rfloor)+(c^{i}-c^{i^{*}},c^{i}p^{*}-c^{i^{*}}p^{*})\\\
&=(c^{i^{*}},\lfloor\sigma_{K}(c^{i^{*}})\rfloor)+(c^{i}-c^{i^{*}},c^{i}p^{*}-c^{i^{*}}p^{*})\\\
&\in\operatorname{cone}(\Lambda).\end{split}$

Hence we complete the proof. ∎

$p^{*}$$P$$K$ Figure 1: The red solid lines represent the CG cuts of $K$ that
cut off extreme point $p^{*}$, and the dashed red and blue lines represent the
corresponding valid inequalities of $K$ and $P$. Then these two CG cuts of $K$
are also the CG cuts of $P$.

The following is the last piece of result we will need to prove Theorem 1.

######  Proposition 3.

Given a closed convex set $K$ in $\mathbb{R}^{n}$, and there exists a finite
subset $F\subseteq\mathbb{Z}^{n}$, such that $\left\\{x\in\mathbb{R}^{n}\mid
fx\leq\lfloor\sigma_{K}(f)\rfloor,\forall f\in F\right\\}\subseteq K.$ Then
for any $v\in\operatorname{cl}\operatorname{cone}(\Omega_{\text{CG}})$, there
exists a finite set $\Lambda_{v}\subseteq\Omega_{\text{CG}}$, such that
$v\in\operatorname{cone}(\Lambda_{v})$.

###### Proof.

If $v\in\operatorname{cone}(\Omega_{\text{CG}})$, then by Carathéodory’s
theorem, there exists a finite subset $\Lambda\subseteq\Omega_{\text{CG}}$
with at most $\dim(\Omega_{\text{CG}})$ elements, such that
$v\in\operatorname{cone}(\Lambda)$.

If $v\notin\operatorname{cone}(\Omega_{\text{CG}})$, since $v\in
L\subseteq\operatorname{cl}\operatorname{cone}(\Omega_{\text{CG}})$, we can
find a sequence in $\operatorname{cone}(\Omega_{\text{CG}})$ converging to
$v$. Assume $\sum_{j=1}^{d}\lambda_{i,j}v^{i,j}\rightarrow v$ when
$i\rightarrow\infty$, here $d=\dim(\Omega_{\text{CG}})$ and
$v^{i,j}\in\Omega_{\text{CG}},\lambda_{i,j}\geq 0$ for all
$i\in\mathbb{N},j\in[d]$. Denote $P=\left\\{x\in\mathbb{R}^{n}\mid
fx\leq\lfloor\sigma_{K}(f)\rfloor,\forall f\in F\right\\}$, which is contained
in $K$. First, within the set
$\\{v^{i,1}\\}_{i\in\mathbb{N}}\subseteq\Omega_{\text{CG}}$, there must exist
an infinite index subset $I_{1}\subseteq\mathbb{N}$ such that CG cuts within
$\\{v^{i,1}\\}_{i\in I_{1}}$ are either all valid to $P$, or all invalid to
$P$. If $\\{v^{i,1}\\}_{i\in I_{1}}$ all correspond to valid inequalities of
$P$, then $\\{v^{i,1}\\}_{i\in
I_{1}}\subseteq\operatorname{cone}(\\{(f,\lfloor\sigma_{K}(f)\rfloor)\ \forall
f\in F,(0,\ldots,0,1)\\})$, where $\\{(f,\lfloor\sigma_{K}(f)\rfloor)\ \forall
f\in F,(0,\ldots,0,1)\\}\subseteq\Omega_{\text{CG}}$. If they all correspond
to invalid inequalities of $P$, then by Proposition 2, there exists another
infinite index set $\bar{I}_{1}\subseteq I_{1}$ and finite set
$\Lambda_{1}\subseteq\Omega_{\text{CG}}$, such that
$v^{i,1}\in\operatorname{cone}(\Lambda_{1})$ for all $i\in\bar{I}_{1}$. In
other words, no matter whether CG cuts within $\\{v^{i,1}\\}_{i\in I_{1}}$ are
all valid to $P$ or not, we can always find an infinite index set
$\bar{I}_{1}\subseteq I_{1}$ and finite set
$\Lambda_{1}\subseteq\Omega_{\text{CG}}$, such that
$v^{i,1}\in\operatorname{cone}(\Lambda_{1})$ for all $i\in\bar{I}_{1}$. Now,
within the set $\\{v^{i,2}\\}_{i\in\bar{I}_{1}}\subseteq\Omega_{\text{CG}}$,
we can do the above argument one more time, and obtain another infinite index
subset $\bar{I}_{2}\subseteq\bar{I}_{1}$ and another finite set
$\Lambda_{2}\subseteq\Omega_{\text{CG}}$, such that
$v^{i,2}\in\operatorname{cone}(\Lambda_{2})$ for all $i\in\bar{I}_{2}$. In
fact, since $\bar{I}_{2}\subseteq\bar{I}_{1}$, we also have
$v^{i,1}\in\operatorname{cone}(\Lambda_{1})$ for all $i\in\bar{I}_{2}$. After
doing such argument for $d$ times, eventually, we will obtain an infinite
index set $\bar{I}_{d}\subseteq\mathbb{N}$ and $d$ finite sets
$\Lambda_{1},\ldots,\Lambda_{d}\subseteq\Omega_{\text{CG}}$, such that
$v^{i,j}\in\operatorname{cone}(\Lambda_{j})$ for any
$i\in\bar{I}_{d},j\in[d]$. Note that
$\sum_{j=1}^{d}\lambda_{i,j}v^{i,j}\rightarrow v$ when
$i\in\bar{I}_{d},i\rightarrow\infty$, and
$\sum_{j=1}^{d}\lambda_{i,j}v^{i,j}\in\operatorname{cone}(\Lambda_{1}\cup\ldots\cup\Lambda_{d})$,
for any $i\in\bar{I}_{d}$. Therefore, we obtain
$v\in\operatorname{cone}(\Lambda_{1}\cup\ldots\cup\Lambda_{d})$. Here
$\Lambda_{1}\cup\ldots\cup\Lambda_{d}\subseteq\Omega_{\text{CG}}$ is a finite
set, by picking $\Lambda_{v}:=\Lambda_{1}\cup\ldots\cup\Lambda_{d}$ we
conclude the proof. ∎

Now we are ready to verify the main theorem in this section.

###### Proof of Theorem 1.

It suffices for us to show the “if” direction: if there exists a finite subset
$F\subseteq\mathbb{Z}^{n}$ such that $\left\\{x\in\mathbb{R}^{n}\mid
fx\leq\lfloor\sigma_{K}(f)\rfloor,\forall f\in F\right\\}\subseteq K$, then
$K^{\prime}$ is finitely-generated. Denote $P=\left\\{x\in\mathbb{R}^{n}\mid
fx\leq\lfloor\sigma_{K}(f)\rfloor,\forall f\in F\right\\}$, and
$L=\operatorname{lin}(\operatorname{cl}\operatorname{cone}(\Omega_{\text{CG}}))$.

By Lemma 3,
$\operatorname{cl}\operatorname{cone}(\Omega_{\text{CG}})=\operatorname{cl}\operatorname{cone}(\operatorname{proj}_{L^{\perp}}\Omega_{\text{CG}})\oplus
L$ and
$\operatorname{cl}\operatorname{cone}(\operatorname{proj}_{L^{\perp}}\Omega_{\text{CG}})$
is a pointed, closed convex cone. We start our argument by analyzing the
extreme rays of
$\operatorname{cl}\operatorname{cone}(\operatorname{proj}_{L^{\perp}}\Omega_{\text{CG}})$.
By Lemma 5, any extreme ray of
$\operatorname{cl}\operatorname{cone}(\operatorname{proj}_{L^{\perp}}\Omega_{\text{CG}})$
is either in $(\operatorname{proj}_{L^{\perp}}\Omega_{\text{CG}})_{+}$, or can
be conically converged by elements from
$\operatorname{proj}_{L^{\perp}}\Omega_{\text{CG}}$. Define
$\Omega^{\uparrow}$ as the set of extreme rays of
$\operatorname{cl}\operatorname{cone}(\operatorname{proj}_{L^{\perp}}\Omega_{\text{CG}})$
that can be conically converged by elements from
$\operatorname{proj}_{L^{\perp}}\Omega_{\text{CG}}$, and define $\Omega^{*}$
as the set of extreme rays of
$\operatorname{cl}\operatorname{cone}(\operatorname{proj}_{L^{\perp}}\Omega_{\text{CG}})$
that are in $(\operatorname{proj}_{L^{\perp}}\Omega_{\text{CG}})_{+}$.

First we consider the set $\Omega^{\uparrow}$. Let
$(r^{*},r^{*}_{0})\in\Omega^{\uparrow}$. By assumption of vectors in
$\Omega^{\uparrow}$, we know there exists a sequence
$\\{(r^{i},\lfloor\sigma_{K}(r^{i})\rfloor)\\}_{i\in\mathbb{N}}\subseteq\Omega_{\text{CG}}$
and $\\{\gamma_{i}\\}_{i\in\mathbb{N}}\subseteq\mathbb{R}_{+}$, such that

$\gamma_{i}\operatorname{proj}_{L^{\perp}}(r^{i},\lfloor\sigma_{K}(r^{i})\rfloor)\rightarrow(r^{*},r^{*}_{0})\text{
when }i\rightarrow\infty.$ (3)

By Lemma 8, within this sequence
$\\{(r^{i},\lfloor\sigma_{K}(r^{i})\rfloor)\\}_{i\in\mathbb{N}}$, there exists
a subsequence $\\{(r^{i},\lfloor\sigma_{K}(r^{i})\rfloor)\\}_{i\in I}$, such
that when $i\in I,i\rightarrow\infty,$
$(r^{i},\lfloor\sigma_{K}(r^{i})\rfloor)\xrightarrow{c}(v^{*},v^{*}_{0})$ for
some valid inequality $v^{*}x\leq v^{*}_{0}$ of $K$. Let

$\lambda_{i}(r^{i},\lfloor\sigma_{K}(r^{i})\rfloor)\rightarrow(v^{*},v^{*}_{0})\text{
when }i\in I,i\rightarrow\infty.$ (4)

Here each $\lambda_{i}>0$. We can rewrite (4) as follows:

$\lambda_{i}\operatorname{proj}_{L^{\perp}}(r^{i},\lfloor\sigma_{K}(r^{i})\rfloor)+\lambda_{i}\operatorname{proj}_{L}(r^{i},\lfloor\sigma_{K}(r^{i})\rfloor)\rightarrow(v^{*},v^{*}_{0})\text{
when }i\in I,i\rightarrow\infty.$ (5)

If $(v^{*},v^{*}_{0})\in L$, then for each $i\in I$, take the inner product of
both sides of (5) with the vector
$\frac{\gamma_{i}^{2}}{\lambda_{i}}\operatorname{proj}_{L^{\perp}}(r^{i},\lfloor\sigma_{K}(r^{i})\rfloor)$,
this gives us
$\gamma_{i}^{2}\|\operatorname{proj}_{L^{\perp}}(r^{i},\lfloor\sigma_{K}(r^{i})\rfloor)\|^{2}\rightarrow
0$. Together with (3) we get the contradiction, since $(r^{*},r^{*}_{0})\neq
0$. Hence $(v^{*},v^{*}_{0})\notin L$, and
$\operatorname{proj}_{L^{\perp}}(v^{*},v^{*}_{0})\neq 0$. From
$\lambda_{i}(r^{i},\lfloor\sigma_{K}(r^{i})\rfloor)\rightarrow(v^{*},v^{*}_{0})$
for $i\in I,i\rightarrow\infty$, we simply obtain that
$\operatorname{proj}_{L^{\perp}}(r^{i},\lfloor\sigma_{K}(r^{i})\rfloor)\xrightarrow{c}\operatorname{proj}_{L^{\perp}}(v^{*},v^{*}_{0})$,
for $i\in I,i\rightarrow\infty$. Since there is also
$\operatorname{proj}_{L^{\perp}}(r^{i},\lfloor\sigma_{K}(r^{i})\rfloor)\xrightarrow{c}(r^{*},r^{*}_{0})$,
by Lemma 2, we know
$(r^{*},r^{*}_{0})=\lambda\operatorname{proj}_{L^{\perp}}(v^{*},v^{*}_{0})$,
for some $\lambda>0$. Since $v^{*}x\leq v^{*}_{0}$ is valid to $K$, which
contains $P$, so
$(v^{*},v^{*}_{0})\in\operatorname{cone}(\bar{\Omega}^{\uparrow}),$ where

$\bar{\Omega}^{\uparrow}:=\\{(f,\lfloor\sigma_{K}(f)\rfloor)\ \forall f\in
F,(0,\ldots,0,1)\\}\subseteq\Omega_{\text{CG}}.$

From
$(r^{*},r^{*}_{0})=\lambda\operatorname{proj}_{L^{\perp}}(v^{*},v^{*}_{0})$,
we also have
$(r^{*},r^{*}_{0})\in\operatorname{cone}(\operatorname{proj}_{L^{\perp}}\bar{\Omega}^{\uparrow})$.
Since here $(r^{*},r^{*}_{0})\in\Omega^{\uparrow}$ is arbitrary, in the end,
we have shown
$\Omega^{\uparrow}\subseteq\operatorname{cone}(\operatorname{proj}_{L^{\perp}}\bar{\Omega}^{\uparrow})$,
for some finite subset $\bar{\Omega}^{\uparrow}$ of $\Omega_{\text{CG}}$.

Now we consider the other set $\Omega^{*}$. Assuming $\Omega^{*}$ contains
infinitely many different extreme rays of
$\operatorname{cl}\operatorname{cone}(\operatorname{proj}_{L^{\perp}}\Omega_{\text{CG}})$:
let $\\{(r^{i},r^{i}_{0})\\}_{i\in\mathbb{N}}\subseteq\Omega^{*}$ be one
sequence of different extreme rays of
$\operatorname{cl}\operatorname{cone}(\operatorname{proj}_{L^{\perp}}\Omega_{\text{CG}})$,
where
$(r^{i},r^{i}_{0})=\operatorname{proj}_{L^{\perp}}(c^{i},\lfloor\sigma_{K}(c^{i})\rfloor)$
for CG cut $c^{i}x\leq\lfloor\sigma_{K}(c^{i})\rfloor,c^{i}\in\mathbb{Z}^{n}$.
Since $(r^{i},r^{i}_{0})$ is an extreme ray, then
$(r^{i},r^{i}_{0})\notin\operatorname{cone}(\operatorname{proj}_{L^{\perp}}\bar{\Omega}^{\uparrow})$,
so there is also
$(c^{i},\lfloor\sigma_{K}(c^{i})\rfloor)\notin\operatorname{cone}(\bar{\Omega}^{\uparrow})$.
By Proposition 1 and definition of $\bar{\Omega}^{\uparrow}$, this implies
that inequality $c^{i}x\leq\lfloor\sigma_{K}(c^{i})\rfloor$ is not valid to
$P$, for any $i\in\mathbb{N}$. By Proposition 2, we know there exists a finite
set $\Lambda\subseteq\Omega_{\text{CG}}$ and an infinite set
$I^{\prime}\subseteq\mathbb{N}$, such that
$(c^{i},\lfloor\sigma_{K}(c^{i})\rfloor)\in\operatorname{cone}(\Lambda)$ for
any $i\in I^{\prime}$. Hence
$(r^{i},r^{i}_{0})=\operatorname{proj}_{L^{\perp}}(c^{i},\lfloor\sigma_{K}(c^{i})\rfloor)\in\operatorname{proj}_{L^{\perp}}\operatorname{cone}(\Lambda)=\operatorname{cone}(\operatorname{proj}_{L^{\perp}}\Lambda)\subseteq\operatorname{cone}(\operatorname{proj}_{L^{\perp}}\Omega_{\text{CG}}).$
However, by our above assumption, for any $i\in
I^{\prime},(r^{i},r^{i}_{0})\in\Omega^{*}$ is extreme ray of
$\operatorname{cl}\operatorname{cone}(\operatorname{proj}_{L^{\perp}}\Omega_{\text{CG}})$,
we get the contradiction. So $\Omega^{*}$ can only contain finitely many
different extreme rays of
$\operatorname{cl}\operatorname{cone}(\operatorname{proj}_{L^{\perp}}\Omega_{\text{CG}})$.
By assumption of $\Omega^{*}$, here we can find a finite subset
$\bar{\Omega}^{*}\subseteq\Omega_{\text{CG}}$, such that
$\Omega^{*}\subseteq\operatorname{cone}(\operatorname{proj}_{L^{\perp}}\bar{\Omega}^{*})$.

So far, we have shown that, there exists finite subsets
$\bar{\Omega}^{\uparrow}$ and $\bar{\Omega}^{*}$ of $\Omega_{\text{CG}}$, such
that
$\Omega^{\uparrow}\cup\Omega^{*}\subseteq\operatorname{cone}\big{(}\operatorname{proj}_{L^{\perp}}(\bar{\Omega}^{\uparrow}\cup\bar{\Omega}^{*})\big{)}$.
Since $\Omega^{\uparrow}\cup\Omega^{*}$ contains all the extreme rays of
$\operatorname{cl}\operatorname{cone}(\operatorname{proj}_{L^{\perp}}\Omega_{\text{CG}})$,
we have:

$\operatorname{cl}\operatorname{cone}(\operatorname{proj}_{L^{\perp}}\Omega_{\text{CG}})=\operatorname{cone}\big{(}\operatorname{proj}_{L^{\perp}}(\bar{\Omega}^{\uparrow}\cup\bar{\Omega}^{*})\big{)}.$

For the lineality space $L$, which is a subset of
$\operatorname{cl}\operatorname{cone}(\Omega)$, by Proposition 3, we can find
a finite subset $\bar{\Omega}_{L}\subseteq\Omega_{\text{CG}}$, such that
$L\subseteq\operatorname{cone}(\bar{\Omega}_{L})$. Hence:

$\operatorname{cl}\operatorname{cone}(\Omega_{\text{CG}})=\operatorname{cl}\operatorname{cone}(\operatorname{proj}_{L^{\perp}}\Omega_{\text{CG}})\oplus
L\subseteq\operatorname{cone}\big{(}\bar{\Omega}^{\uparrow}\cup\bar{\Omega}^{*}\cup\bar{\Omega}_{L}\big{)}.$

Therefore, we obtain that:
$\operatorname{cl}\operatorname{cone}(\Omega_{\text{CG}})=\operatorname{cone}\big{(}\bar{\Omega}^{\uparrow}\cup\bar{\Omega}^{*}\cup\bar{\Omega}_{L}\big{)}$,
where $\bar{\Omega}^{\uparrow},\bar{\Omega}^{*}$ and $\bar{\Omega}_{L}$ are
finite subsets of $\Omega_{\text{CG}}$. By Corollary 2 we conclude the proof.
∎

##  4 Chvátal-Gomory Closure of Motzkin-Decomposable Set.

In this section, we will prove that, the CG closure of a Motzkin-decomposable
set is a rational polyhedron if and only if it has rational polyhedral
recession cone. Before presenting the proof for such main result, we first
develop some intuition by examining the following examples. As we shall see in
a moment, in some sense, the assumptions of Motzkin-decomposable is necessary.

######  Example 1.

Consider closed convex set

$K_{1}=\\{x\in\mathbb{R}^{2}_{+}\mid x_{1}\cdot x_{2}\geq 2\\},$

see fig. 2(a). Note that $\operatorname{rec}(K_{1})=\mathbb{R}^{2}_{+}$ a
rational polyhedral cone, but $K_{1}$ is not Motzkin-decomposable since there
does not exist a compact convex set $C$ such that
$K_{1}=C+\mathbb{R}^{2}_{+}$.

Moreover, $K_{1}$ has integer hull

$\operatorname{conv}(K_{1}\cap\mathbb{Z}^{2})=\\{x\in\mathbb{R}^{2}\mid
x_{1}+x_{2}\geq 3,x_{1}\geq 1,x_{2}\geq 1\\},$

while $K_{1}^{\prime}$ is not finitely-generated. To observe this, realize
that $\operatorname{conv}(K_{1}\cap\mathbb{Z}^{2})\subseteq
K_{1}^{\prime}\subseteq K_{1}$ where
$\operatorname{rec}(K_{1})=\operatorname{rec}(\operatorname{conv}(K_{1}\cap\mathbb{Z}^{2}))=\mathbb{R}^{2}_{+}$,
so $\operatorname{rec}(K_{1}^{\prime})=\mathbb{R}^{2}_{+}$. If
$K_{1}^{\prime}$ is finitely-generated, then $K_{1}^{\prime}$ will have facet-
defining inequalities $x_{1}\geq\alpha_{1},x_{2}\geq\alpha_{2}$ for some
$\alpha_{1},\alpha_{2}\geq 0$, and inequalities
$x_{1}\geq\alpha_{1},x_{2}\geq\alpha_{2}$ are both CG cuts of $K_{1}$. Clearly
$\alpha_{1}=\alpha_{2}=1$. However, there does not exist any fractional
$\beta_{1},\beta_{2}\in(0,1)$, such that $x_{1}\geq\beta_{1}$ and
$x_{2}\geq\beta_{2}$ are valid to $K_{1}$, so $x_{1}\geq 1,x_{2}\geq 1$ cannot
be CG cuts of $K_{1}$, which means $K_{1}^{\prime}$ is not finitely-generated.

######  Example 2.

Consider another closed convex set

$K_{2}=\\{x\in\mathbb{R}^{2}\mid(x_{1}-0.2)\cdot(x_{2}-0.2)\geq
2,x_{1}>0.2,x_{2}>0.2\\},$

see fig. 2(b). Note that $K_{2}$ here can be obtained by translating the
closed convex set $K_{1}$ in Example 1. Here $K_{2}$ is also not Motzkin-
decomposable, and

$\operatorname{conv}(K_{2}\cap\mathbb{Z}^{2})=\\{x\in\mathbb{R}^{2}\mid
x_{1}+x_{2}\geq 4,x_{1}\geq 1,x_{2}\geq 1\\}.$

However, $x_{1}\geq 0.2,x_{2}\geq 0.2,x_{1}+x_{2}\geq 0.4+2\sqrt{2}$ are all
valid inequalities of $K_{2}$, so $x_{1}\geq 1,x_{2}\geq 1,x_{1}+x_{2}\geq 4$
are CG cuts of $K_{2}$. Therefore, $K_{2}^{\prime}$ is finitely-generated.

$x_{1}$$x_{2}$ (a) The blue region is $K_{1}$, whose integer hull is marked in
red and it is rational polyhedral, while $K_{1}^{\prime}$ is not.

$x_{1}$$x_{2}$0.20.2 (b) The blue region denotes $K_{2}$, red region denotes
$\operatorname{conv}(K_{2}\cap\mathbb{Z}^{2})$, and dashed lines
$x_{1}=\frac{1}{2}$ and $x_{2}=\frac{1}{2}$ are two asymptotes of $K_{2}$. Red
line represents the CG cut of $K_{2}$, derived from the blue dashed line.

Figure 2: Figures (a) and (b) demonstrate two congruent closed convex sets,
whose integer hulls are both rational polyhedral, while their CG closures have
completely different properties.

Henceforth, we will only consider exposed faces of closed convex sets, and for
the sake of brevity we refer to them as _faces_. In other words, a face $F$ of
a closed convex set $K$ is a subset of the form $F=\\{x\in K\mid\pi
x=\sigma_{K}(\pi)\\}$ for some supporting hyperplane $\pi x=\sigma_{K}(\pi)$.
We will call the face $F$ the _$\pi$ -face_ of $K$. Detailed definitions and
properties of faces can be found in [25] and [2].

For any vector $\pi\in\mathbb{R}^{n}$, we can associate an unique rational
linear subspace $V_{\pi}$ with it.

######  Definition 2.

Given $\pi\in\mathbb{R}^{n}$, define
$V_{\pi}:=\\{x\in\mathbb{R}^{n}\mid\alpha^{T}x=0\text{ for any
}\alpha\in\mathbb{Q}^{n}\text{ such that }\alpha^{T}\pi\in\mathbb{Q}\\}.$

######  Lemma 9.

Given a rational linear subspace $L\subseteq\mathbb{R}^{n}$, and $\pi\in L$.
Then $V_{\pi}\subseteq L$.

###### Proof.

Let $L:=\\{x\in\mathbb{R}^{n}\mid Bx=0\\}$, where $B\in\mathbb{Q}^{k\times
n}$. Then $B_{\ell}^{T}\pi=0\in\mathbb{Q}$, here $B_{\ell}$ is the $\ell$-th
row of $B$. By Definition 2, we know
$V_{\pi}\subseteq\\{x\in\mathbb{R}^{n}\mid B_{\ell}^{T}x=0\
\forall\ell\in[k]\\}=L$. ∎

For the rational linear subspace $V_{\pi}$ associated with any vector
$\pi\in\mathbb{R}^{n}$, we have the following well-known simultaneous
diophantine approximation theorem which is due to Kronecker [22]. Note that
the version we used here is similar to the one used by [4]. We include its
proof in Appendix E.

######  Lemma 10 ([22, 27, 4]).

Let $n,N_{0}\in\mathbb{N}$ and $\pi\in\mathbb{R}^{n}$ with $\pi\neq 0$. Then
$\mathbb{Z}^{n}-\pi\mathbb{Z}_{>N_{0}}$ contains a dense subset of $V_{\pi}$.

We will also require the following classic result about the sensitivity of
Linear Programming.

######  Lemma 11 (Sticky face lemma [23]).

If $P$ is a polyhedron in $\mathbb{R}^{n}$, $x_{0}^{*}$ is a point of
$\mathbb{R}^{n}$ and $F$ is the set of maximizers of $\langle
x^{*}_{0},\cdot\rangle$ on $P$ (a face of $P$). Then for any $x^{*}$ close
enough to $x^{*}_{0}$, the maximizers of $\langle x^{*},\cdot\rangle$ on $P$
are just its maximizers on $F$.

###  4.1 Sufficient Condition

In this section, we want to establish the sufficient condition in Theorem 2,
for finitely-generated property of the CG closure. Using the main Theorem 1,
it suffices for us to show the following result.

######  Proposition 4.

If $K$ is a Motzkin-decomposable set in $\mathbb{R}^{n}$ with rational
polyhedral recession cone, then there exists a finite subset
$F\subseteq\mathbb{Z}^{n}$, such that $\left\\{x\in\mathbb{R}^{n}\mid
fx\leq\lfloor\sigma_{K}(f)\rfloor,\forall f\in F\right\\}\subseteq K.$

Before presenting the proof of Proposition 4, we will need the following
auxiliary results. The first lemma can be viewed as an extension of the
_continuity Lemma 1_ in [4] and _sticky face lemma_ 11. Note that unlike
Proposition 4, here we do not assume rational polyhedral recession cone.

######  Lemma 12.

Let $K$ be a Motzkin-decomposable set with polyhedral recession cone, and $F$
is a $\pi$-face of $K$. For any $\delta>0,$ let $F_{\delta}:=\\{x\in
K\mid\exists\ x^{\prime}\in F\text{ s.t. }\|x-x^{\prime}\|\leq\delta\\}.$ Then
there exists $\epsilon>0$, such that for any $\pi^{\prime}$ with
$\|\pi^{\prime}-\pi\|<\epsilon,\sigma_{K}(\pi^{\prime})=\sigma_{F_{\delta}}(\pi^{\prime})$.

###### Proof.

By assumption, since $K$ is Motzkin-decomposable with polyhedral recession
cone, then we write $K=C+\operatorname{cone}(R)$ for a compact convex set $C$
and a finite set of extreme rays $R$. Let $F=\\{x\in K\mid\pi x=\pi_{0}\\}$ be
the $\pi$-face of $K$ and $\pi x=\pi_{0}$ is a supporting hyperplane
($\pi_{0}<\infty$), we know that $\pi r\leq 0$ for any $r\in R$, and
$R_{0}:=\\{r\in R\mid\pi r=0\\}$ is the set of extreme rays of $F$. Clearly
$R_{0}$ is also the set of extreme rays of $F_{\delta}$.

We prove the statement of this lemma by contradiction: there exists a
convergent sequence $\pi^{i}\rightarrow\pi$ and
$\sigma_{K}(\pi^{i})>\sigma_{F_{\delta}}(\pi^{i})$. Note that here
$\sigma_{F_{\delta}}(\pi^{i})<\infty$, which implies $\pi^{i}r\leq 0$ for any
$r\in R_{0}$. By definition of $R_{0}$, we know that for any $r\in R\setminus
R_{0}$, there is $\pi r<0$. Here $R\setminus R_{0}$ is a finite set, hence for
any $\pi^{i}$ close enough to $\pi$, we also have $\pi^{i}r<0$ for any $r\in
R\setminus R_{0}$. Therefore, for any $\pi^{i}$ close enough to $\pi$, there
is $\pi^{i}r\leq 0$ for any $r\in R$. W.l.o.g., we can assume that for our
sequence $\\{\pi^{i}\\}_{i\geq 1},\pi^{i}r\leq 0$ for any $r\in R$ and $i\geq
1$. From $\sigma_{K}(\pi^{i})>\sigma_{F_{\delta}}(\pi^{i})$ for any $i\geq 1$,
we know there must exist $x^{i}\in K\setminus F_{\delta}$, such that
$\pi^{i}x^{i}>\sigma_{F_{\delta}}(\pi^{i})=\max_{x\in F_{\delta}\cap
C}\pi^{i}x$. From our above assumption that $\pi^{i}r\leq 0$ for any $r\in R$,
here we can further assume that $x^{i}\in C\setminus F_{\delta}$. Since
$x^{i}\in C$ which is a compact set, by Bolzano-Weierstrass theorem, there is
a convergent subsequence of $\\{x^{i}\\}_{i\geq 1}$. W.l.o.g. we still assume
the convergent subsequence of $\\{x^{i}\\}_{i\geq 1}$ is itself, and
$x^{i}\rightarrow x^{*}\in C$. Note that $x^{i}\notin F_{\delta}$, so we have
$x^{*}\notin F$. Therefore, from $\pi^{i}x^{i}>\max_{x\in F_{\delta}\cap
C}\pi^{i}x$, we have:

$\pi
x^{*}=\lim_{i\rightarrow\infty}\pi^{i}x^{i}\geq\lim_{i\rightarrow\infty}\max_{x\in
F_{\delta}\cap C}\pi^{i}x=\max_{x\in F_{\delta}\cap C}\pi x=\pi_{0}.$

Since $\pi x=\pi_{0}$ is a supporting hyperplane of $K$, we obtain that $\pi
x^{*}=\pi_{0}$ and $x^{*}\in F$, which gives the contradiction. ∎

Next we present the key lemma for establishing the proof of Proposition 4.

######  Lemma 13.

Let $K$ be a Motzkin-decomposable set with rational polyhedral recession cone.
For any $\pi$-face $F$ of $K$, if $F^{\prime}$ is finitely-generated, then
there exists a rational polyhedron $P_{\pi}$ obtained from finitely many CG
cuts of $K$ and $\epsilon_{\pi}>0$, such that for any $\pi^{\prime}$ with
$\|\pi^{\prime}-\pi\|<\epsilon_{\pi},\pi^{\prime}x\leq\sigma_{K}(\pi^{\prime})$
is valid to $P_{\pi}$.

###### Proof.

Let $K=C+\operatorname{cone}(R)$, where $C$ is a compact convex set and $R$ is
a finite set of rational extreme rays of $K$. Denote $u:=\max_{x\in
C}\|x\|<\infty$. Here we can find a multiplier $\kappa>0$, such that
$(\alpha,\alpha_{0}):=\kappa(\pi,\sigma_{K}(\pi))$ with
$\alpha_{0}\in\mathbb{Z}$. In the following discussion, we simply denote the
supporting hyperplane $\pi x=\sigma_{K}(\pi)$ of $K$ as $\alpha x=\alpha_{0}$.

By assumption that $F^{\prime}$ is finitely-generated, we can denote
$F^{\prime}=\\{x\in\mathbb{R}^{n}\mid
gx\leq\lfloor\sigma_{F}(g)\rfloor,\forall g\in G\\}$, with
$g\in\mathbb{Z}^{n},\forall g\in G$. Here w.l.o.g. we assume that $0\in G$,
since $0x\leq\lfloor\sigma_{F}(0)\rfloor$ trivially holds.

Pick a small positive number

$\delta<\min_{g\in G}\frac{1+\lfloor\sigma_{F}(g)\rfloor-\sigma_{F}(g)}{2},$

and choose a neighborhood of $F$:

$\bar{F}:=\\{x\in K\mid\exists\ x^{\prime}\in F\text{ s.t.
}\|x-x^{\prime}\|\leq\frac{\delta}{\max_{g\in G}\|g\|}\\}.$

By Lemma 12, we know there exists a positive number $\epsilon_{0}>0$, such
that for any $\alpha^{\prime}$ with $\|\alpha^{\prime}-\alpha\|<\epsilon_{0}$,
there is $\sigma_{K}(\alpha^{\prime})=\sigma_{\bar{F}}(\alpha^{\prime})$.
Furthermore, there is a large enough integer number $N_{0}$, such that for any
positive integer $m\geq N_{0}$ and any vector $c$ with
$\|c-m\alpha\|\leq\frac{\delta}{u}$, we have
$\|\frac{c+g}{\|c+g\|}-\frac{\alpha}{\|\alpha\|}\|\leq\frac{\epsilon_{0}}{\|\alpha\|}$
for any $g\in G$, which is
$\|(c+g)\frac{\|\alpha\|}{\|c+g\|}-\alpha\|\leq\epsilon_{0}$.

By Lemma 10, $\mathbb{Z}^{n}-\alpha\mathbb{Z}_{>N_{0}}$ contains a dense
subset of $V_{\alpha}$, so we can find some
$c^{i}-m_{i}\alpha,\lambda_{i}\in[0,1]$ for $i\in[k]$ with
$\sum_{i=1}^{k}\lambda_{i}=1$, such that

$\sum_{i\in[k]}\lambda_{i}(c^{i}-m_{i}\alpha)=0,\|c^{i}-m_{i}\alpha\|\leq\frac{\delta}{u},\quad
c^{i}\in\mathbb{Z}^{n},m_{i}\in\mathbb{N}_{>N_{0}},c^{i}-m_{i}\alpha\in
V_{\alpha}.$ (6)

  * Claim 1. For any $x\in\bar{F}$ and $v\in V_{\alpha},vx\leq\|v\|u$.

  * Proof of claim.  Let $R_{0}:=\\{r\in R\mid\alpha r=0\\}$ denote the set of extreme rays of the face $F$. Then obviously $R_{0}$ is also the set of extreme rays of the set $\bar{F}$. Since $\alpha\in\ker(R_{0})$, where $\ker(R_{0})$ is a rational linear subspace because $R$ is assumed to be a finite set of rational vectors, hence from Lemma 9, we know $V_{\alpha}\subseteq\ker(R_{0})$. This implies that, for any $v\in V_{\alpha}$ and $x=y+r\in C+R_{0}$, there is $vx=vy\leq\|v\|u$. $\hfill\diamond$

Therefore, for any $x\in\bar{F},i\in[k]$ and $g\in G$, we have

$\displaystyle\begin{split}(c^{i}+g)x&=gx+m_{i}\alpha
x+(c^{i}-m_{i}\alpha)x\\\
&\leq\sigma_{F}(g)+\delta+m_{i}\alpha_{0}+\delta.\end{split}$ (7)

Here for any $x\in\bar{F},gx\leq\sigma_{F}(g)+\delta$ is from the definition
of $\bar{F}$, and $(c^{i}-m_{i}\alpha)x\leq\delta$ is from the last claim and
the fact that $c^{i}-m_{i}\alpha\in V_{\alpha}$ and
$\|c^{i}-m_{i}\alpha\|\leq\frac{\delta}{u}$. According to our construction of
$N_{0}$ and $\epsilon_{0}$, we know that
$\sigma_{K}((c^{i}+g)\frac{\|\alpha\|}{\|c^{i}+g\|})=\sigma_{\bar{F}}((c^{i}+g)\frac{\|\alpha\|}{\|c^{i}+g\|})$,
for any $i\in[k]$. Hence:

$\sigma_{K}(c^{i}+g)=\sigma_{\bar{F}}(c^{i}+g)\leq\sigma_{F}(g)+m_{i}\alpha_{0}+2\delta.$

Here the last inequality is from (7). This implies that

$(c^{i}+g)x\leq\lfloor\sigma_{F}(g)+m_{i}\alpha_{0}+2\delta\rfloor=\lfloor\sigma_{F}(g)\rfloor+m_{i}\alpha_{0}$

is a CG cut of $K$, for any $i\in[k]$ and $g\in G$. Here the last equality is
because $\delta$ is assumed to be less than $\min_{g\in
G}\frac{1+\lfloor\sigma_{F}(g)\rfloor-\sigma_{F}(g)}{2}$, and
$m_{i},\alpha_{0}\in\mathbb{Z}$. Now we denote

$P_{\pi}:=\\{x\in\mathbb{R}^{n}\mid(c^{i}+g)x\leq\lfloor\sigma_{F}(g)\rfloor+m_{i}\alpha_{0},\forall
i\in[k],g\in G\\}.$ (8)

Here $P_{\pi}$ is a rational polyhedron which is obtained from finitely-many
CG cuts of $K$.

  * Claim 2. $\alpha x\leq\alpha_{0}$ is valid to $P_{\pi}$, and $\\{x\in P_{\pi}\mid\alpha x=\alpha_{0}\\}\subseteq F$.

  * Proof of claim.  For any $g\in G$, by definition of $P_{\pi}$, we know that inequality $(\sum_{i\in[k]}\lambda_{i}c^{i}+g)x\leq\lfloor\sigma_{F}(g)\rfloor+\sum_{i\in[k]}\lambda_{i}m_{i}\alpha_{0}$ is valid to $P_{\pi}$. By (6), such inequality is just $(\gamma\alpha+g)x\leq\lfloor\sigma_{F}(g)\rfloor+\gamma\alpha_{0}$, where we denote $\gamma:=\sum_{i\in[k]}\lambda_{i}m_{i}$. By assumption that $0\in G$, we know $\alpha x\leq\alpha_{0}$ is valid to $P_{\pi}$. Moreover, there is

$\displaystyle\\{x\in P_{\pi}\mid\alpha x=\alpha_{0}\\}$
$\displaystyle\subseteq\\{x\in\mathbb{R}^{n}\mid\alpha
x=\alpha_{0},(\gamma\alpha+g)x\leq\lfloor\sigma_{F}(g)\rfloor+\gamma\alpha_{0},\forall
g\in G\\}$ $\displaystyle\subseteq\\{x\in\mathbb{R}^{n}\mid
gx\leq\lfloor\sigma_{F}(g)\rfloor,\forall g\in G\\}$
$\displaystyle=F^{\prime}\subseteq F.$

Hence this claim holds. $\hfill\diamond$

Lastly, we want to show that, for $\alpha^{\prime}$ close enough to
$\alpha,\alpha^{\prime}x\leq\sigma_{K}(\alpha^{\prime})$ will always be valid
to $P_{\pi}$. Denote $F_{\pi}$ to be the $\alpha$-face of $P_{\pi}$, and let
$\sigma:=\alpha x$ for any arbitrary $x\in F_{\pi}$. Here $F_{\pi}=\\{x\in
P_{\pi}\mid\alpha x=\sigma\\}$. By the sticky face lemma 11, for polyhedron
$P_{\pi}$, we know there exists $\epsilon_{1}>0$, such that when
$\|\alpha^{\prime}-\alpha\|<\epsilon_{1}$,
$\sigma_{P_{\pi}}(\alpha^{\prime})=\sigma_{F_{\pi}}(\alpha^{\prime})$. It
suffices for us to show, for $\alpha^{\prime}$ close enough to $\alpha$ there
is $\sigma_{F_{\pi}}(\alpha^{\prime})\leq\sigma_{K}(\alpha^{\prime})$, because
this will imply that
$\sigma_{P_{\pi}}(\alpha^{\prime})\leq\sigma_{K}(\alpha^{\prime})$, meaning
$\alpha^{\prime}x\leq\sigma_{K}(\alpha^{\prime})$ is also valid to $P_{\pi}$.
Note that Claim 4.1 tells that $\alpha x\leq\alpha_{0}$ is valid to $P_{\pi}$,
we have $\sigma\leq\alpha_{0}$. Next we argue by two cases:

  1. 1.

_Case $\sigma=\alpha_{0}$:_ In this case, $F_{\pi}=\\{x\in P_{\pi}\mid\alpha
x=\alpha_{0}\\}$. By Claim 4.1, there is $F_{\pi}\subseteq F\subseteq K$,
which implies that
$\sigma_{F_{\pi}}(\alpha^{\prime})\leq\sigma_{K}(\alpha^{\prime})$. Hence in
this case, when $\alpha^{\prime}$ is close enough to
$\alpha,\sigma_{P_{\pi}}(\alpha^{\prime})=\sigma_{F_{\pi}}(\alpha^{\prime})\leq\sigma_{K}(\alpha^{\prime})$,
completing the proof.

  2. 2.

_Case $\sigma<\alpha_{0}$:_ We decompose the face $F_{\pi}$ as:
$F_{\pi}=\operatorname{conv}(E_{\pi})+\operatorname{cone}(R_{\pi})$, where
$E_{\pi}$ and $R_{\pi}$ denote the set of extreme points and extreme rays of
$F_{\pi}$ respectively. Arbitrarily pick $r\in R_{\pi}$, it is also an extreme
ray of polyhedron $P_{\pi}$. By the definition (8) of $P_{\pi}$, we know
$(c^{i}+g)r\leq 0$ for any $i\in[k]$ and $g\in G$. Since $r$ is an extreme ray
of face $F_{\pi}=\\{x\in P_{\pi}\mid\alpha x=\sigma\\}$, we also have $\alpha
r=0$. By (6), we know there must exist some $i^{\prime}\in[k]$, such that
$c^{i^{\prime}}r\geq 0$. Combined with the fact that $(c^{i^{\prime}}+g)r\leq
0$ for any $g\in G$, we have: $gr\leq 0,\ \forall g\in G$. Recall that
$F^{\prime}=\\{x\in\mathbb{R}^{n}\mid
gx\leq\lfloor\sigma_{F}(g)\rfloor,\forall g\in G\\}$, hence $r$ is also a ray
of $F^{\prime}$, which is contained in $K$. This implies that, for any
$\alpha^{\prime}$, if $\sigma_{F_{\pi}}(\alpha^{\prime})=\infty$, then
$\sigma_{K}(\alpha^{\prime})=\infty$. Therefore, we only have to show, for any
$\alpha^{\prime}$ close enough to $\alpha$ and
$\sigma_{F_{\pi}}(\alpha^{\prime})<\infty$, then
$\alpha^{\prime}x\leq\sigma_{K}(\alpha^{\prime})$ is valid to $P_{\pi}$. For
any $\alpha^{\prime}$ close enough to $\alpha$ with
$\sigma_{F_{\pi}}(\alpha^{\prime})<\infty$, there is

$\sigma_{F_{\pi}}(\alpha^{\prime})=\max_{x\in
E_{\pi}}\alpha^{\prime}x\leq\max_{x\in E_{\pi}}\alpha
x+\frac{\alpha_{0}-\sigma}{2}=\frac{\sigma+\alpha_{0}}{2}.$

Here the second inequality is because,
$\sigma_{E_{\pi}}(\alpha^{\prime})\rightarrow\sigma_{E_{\pi}}(\alpha)$ as
$\alpha^{\prime}\rightarrow\alpha$. Moreover, arbitrarily pick a point
$x^{*}\in F$, when
$\|\alpha^{\prime}-\alpha\|<\frac{\alpha_{0}-\sigma}{2\|x^{*}\|}$, there is

$\alpha^{\prime}x^{*}=\alpha
x^{*}+(\alpha^{\prime}-\alpha)x^{*}\geq\alpha_{0}-\|\alpha^{\prime}-\alpha\|\cdot\|x^{*}\|>\frac{\sigma+\alpha_{0}}{2}.$

Hence,
$\sigma_{K}(\alpha^{\prime})>\frac{\sigma+\alpha_{0}}{2}\geq\sigma_{F_{\pi}}(\alpha^{\prime})$
when $\alpha^{\prime}$ is sufficiently close to $\alpha$. This concludes the
proof for this case.

Therefore, we have shown that, there exists a small constant
$\epsilon_{\alpha}>0$, such that for any $\alpha^{\prime}$ with
$\|\alpha^{\prime}-\alpha\|<\epsilon_{\alpha},\alpha^{\prime}x\leq\sigma_{K}(\alpha^{\prime})$
is always valid to $P_{\pi}$. Note that $\alpha=\kappa\pi$ and
$\sigma_{K}(\kappa\pi^{\prime})=\kappa\sigma_{K}(\pi^{\prime})$, by picking
$\epsilon_{\pi}:=\frac{\epsilon_{\alpha}}{\kappa}$, we conclude the proof. ∎

Now we have all the tools needed to verify Proposition 4.

###### Proof of Proposition 4.

Denote $K=C+\operatorname{cone}(R)$, where $C$ is a compact convex set and $R$
is a finite set of rational extreme rays of $K$. The proof proceeds via
induction on the dimension of $K$. By inductive hypothesis, this proposition
holds for proper faces of $K$. Further from Theorem 1, we know that the CG
closure of any proper face of $K$ is finitely-generated. Let

$\Pi:=\\{\pi\in\mathbb{R}^{n}\mid\|\pi\|=1,\pi r\leq 0\ \forall r\in R\\}.$

Since a closed convex set can be exactly given by intersecting all of its
supporting half-spaces, there is $K=\\{x\in\mathbb{R}^{n}\mid\pi
x\leq\sigma_{K}(\pi),\forall\pi\in\Pi\\}$. For any $\pi\in\Pi$, since the CG
closure of any proper face of $K$ is finitely-generated, by Lemma 13, we know
there exists a rational polyhedron $P_{\pi}$ obtained from finitely many CG
cuts of $K$ and a positive number $\epsilon_{\pi}$, such that for any
$\pi^{\prime}$ with
$\|\pi^{\prime}-\pi\|<\epsilon_{\pi},\pi^{\prime}x\leq\sigma_{K}(\pi^{\prime})$
will be valid to $P_{\pi}$. Hence we obtain an open cover
$\\{O_{\epsilon_{\pi}}(\pi)\\}_{\pi\in\Pi}$ for $\Pi$. Because $\Pi$ is a
compact set, as a consequence, there exists a finite subset
$\bar{\Pi}\subseteq\Pi$ with
$\Pi\subseteq\\{O_{\epsilon_{\pi}}(\pi)\\}_{\pi\in\bar{\Pi}}$. Consider
polyhedron

$P:=\bigcap_{\pi\in\bar{\Pi}}P_{\pi}.$ (9)

Here we know that $P$ is also obtained from finitely many CG cuts of $K$.
Moreover, for any supporting half-space
$\pi^{\prime}x\leq\sigma_{K}(\pi^{\prime})$ of $K$, since
$\pi^{\prime}\in\Pi\subseteq\\{O_{\epsilon_{\pi}}(\pi)\\}_{\pi\in\bar{\Pi}}$,
we know there exists $\pi^{\prime\prime}\in\bar{\Pi}$ such that
$\pi^{\prime}\in O_{\epsilon_{\pi^{\prime\prime}}}(\pi^{\prime\prime})$. Hence
$\pi^{\prime}x\leq\sigma_{K}(\pi^{\prime})$ is valid to
$P_{\pi^{\prime\prime}}$, which contains $P$. In other words, we have shown
that, for any supporting half-space of $K$, this half-space also contains $P$.
Therefore, our constructed $P$ in (9) is contained in $K$, and we complete the
proof. ∎

###  4.2 Proof of Theorem 2

To show the necessary condition for the rational polyhedrality of $K^{\prime}$
in Theorem 2, we will need the following easy lemma.

######  Lemma 14.

For a closed convex set $K$,
$\operatorname{rec}(K)=\operatorname{rec}(K^{\prime})$.

###### Proof.

Since $K^{\prime}\subseteq K$, it suffices to show:
$\operatorname{rec}(K)\subseteq\operatorname{rec}(K^{\prime})$. Arbitrarily
pick $r\in\operatorname{rec}(K)$, denote $C_{r}:=\\{c\in\mathbb{Z}^{n}\mid
c\cdot r\leq 0\\}$. For any $c\in\mathbb{Z}^{n}\setminus C_{r}$, since $c\cdot
r>0$, we know $\sigma_{K}(c)=\infty$. Therefore, $K^{\prime}=\bigcap_{c\in
C_{r}}\\{x\in\mathbb{R}^{n}\mid cx\leq\lfloor\sigma_{K}(c)\rfloor\\}.$ Since
$c\cdot r\leq 0$ for any $c\in C_{r}$, we obtain
$r\in\operatorname{rec}(K^{\prime})$. By the arbitrariness of
$r\in\operatorname{rec}(K)$, we conclude the proof of
$\operatorname{rec}(K)\subseteq\operatorname{rec}(K^{\prime})$. ∎

Now we are ready to prove Theorem 2.

###### Proof of Theorem 2.

Let $K$ be a Motzkin-decomposable set. First, assume $\operatorname{rec}(K)$
is a rational polyhedral cone. Then by Proposition 4 and Theorem 1, we know
that $K^{\prime}$ is finitely-generated. Now assume that $K^{\prime}$ is a
finitely-generated. Then $K^{\prime}$ is also a rational polyhedron, which has
rational polyhedral recession cone. By Lemma 14, we obtain that $K$ also has
rational polyhedral recession cone. ∎

When $K$ is further assumed to contain integer points in its interior, we have
the following necessary condition for
$\operatorname{conv}(K\cap\mathbb{Z}^{n})$ to be a rational polyhedron.

######  Proposition 5 (Theorem 6 [11]).

Let $K$ be a closed convex set in $\mathbb{R}^{n}$. If
$\operatorname{int}(K)\cap\mathbb{Z}^{n}\neq\emptyset$ and
$\operatorname{conv}(K\cap\mathbb{Z}^{n})$ is a polyhedron, then
$\operatorname{rec}(K)$ is a rational polyhedral cone.

From the last proposition and Theorem 2, we obtain Corollary 1 as an immediate
corollary.

###### Proof of Corollary 1.

Let $K$ be a Motzkin-decomposable set which contains integer points in its
interior. First, assume $\operatorname{conv}(K\cap\mathbb{Z}^{n})$ is a
polyhedron. Then by Proposition 5, we know that $K$ has rational polyhedral
recession cone. From Theorem 2, we obtain that $K^{\prime}$ is a rational
polyhedron. Now, assuming $K^{\prime}$ is a rational polyhedron. By the fact
that $K^{\prime}\cap\mathbb{Z}^{n}=K\cap\mathbb{Z}^{n}$, we know
$\operatorname{conv}(K\cap\mathbb{Z}^{n})=\operatorname{conv}(K^{\prime}\cap\mathbb{Z}^{n})$,
which is a rational polyhedron. ∎

For closed convex sets which are not Motzkin-decomposable, as we have seen
from Example 1 and Example 2, the integer hull of $K_{1}$ and $K_{2}$ are both
polyhedral, while $K^{\prime}_{1}$ is non-polyhedral, and $K^{\prime}_{2}$ is
polyhedral. The fact that $K_{1}$ is congruent with $K_{2}$ suggests that for
more general closed convex set, the relationship between its integer hull and
its CG closure is more subtle. Moreover, we should further remark that, the
additional condition that
$\operatorname{int}(K)\cap\mathbb{Z}^{n}\neq\emptyset$ is not artificial.

######  Example 3.

Let $K=\\{x\in\mathbb{R}^{2}\mid\sqrt{2}x_{1}-x_{2}=0\\}$, which is a straight
line with irrational slope. Then $K\cap\mathbb{Z}^{2}=\\{0\\}$, and its
integer hull is a singleton (also a polyhedron). However, $K^{\prime}=K$ which
is an irrational polyhedron.

## References

  * [1] Gennadiy Averkov.  On finitely generated closures in the theory of cutting planes.  Discrete Optim., 9(4):209–215, 2012.
  * [2] Alexander Barvinok.  A course in convexity, volume 54.  American Mathematical Soc., 2002.
  * [3] Alexander Bockmayr, Friedrich Eisenbrand, Mark Hartmann, and Andreas S Schulz.  On the chvátal rank of polytopes in the 0/1 cube.  Discrete Applied Mathematics, 98(1-2):21–27, 1999.
  * [4] Gábor Braun and Sebastian Pokutta.  A short proof for the polyhedrality of the chvátal–gomory closure of a compact convex set.  Operations Research Letters, 42(5):307–310, 2014.
  * [5] Václav Chvátal.  Edmonds polytopes and a hierarchy of combinatorial problems.  Discrete Mathematics, 4(4):305–337, 1973.
  * [6] Václav Chvátal, William Cook, and Mark Hartmann.  On cutting-plane proofs in combinatorial optimization.  Linear Algebra Appl., 114/115:455–499, 1989.
  * [7] William Cook, Jean Fonlupt, and Alexander Schrijver.  An integer analogue of caratheodory’s theorem.  Journal of Combinatorial Theory, Series B, 40(1):63–70, 1986.
  * [8] Daniel Dadush, Santanu S Dey, and Juan Pablo Vielma.  The chvátal-gomory closure of a strictly convex body.  Mathematics of Operations Research, 36(2):227–239, 2011.
  * [9] Daniel Dadush, Santanu S Dey, and Juan Pablo Vielma.  On the chvátal–gomory closure of a compact convex set.  Mathematical Programming, 145(1-2):327–348, 2014.
  * [10] Alberto Del Pia, Dion Gijswijt, Jeff Linderoth, and Haoran Zhu.  Integer packing sets form a well-quasi-ordering.  Oper. Res. Lett., 49(2):226–230, 2021.
  * [11] Santanu S Dey and Diego A Morán R.  Some properties of convex hulls of integer points contained in general convex sets.  Math. Program., 141(1-2, Ser. A):507–526, 2013.
  * [12] Santanu S Dey and Juan Pablo Vielma.  The chvátal-gomory closure of an ellipsoid is a polyhedron.  In International Conference on Integer Programming and Combinatorial Optimization, pages 327–340. Springer, 2010.
  * [13] Leonard Eugene Dickson.  Finiteness of the odd perfect and primitive abundant numbers with n distinct prime factors.  American Journal of Mathematics, 35(4):413–422, 1913.
  * [14] Juliane Dunkel and Andreas S Schulz.  The gomory-chvátal closure of a nonrational polytope is a rational polytope.  Mathematics of Operations Research, 38(1):63–91, 2013.
  * [15] Matteo Fischetti and Andrea Lodi.  Optimizing over the first Chvátal closure.  Math. Program., 110(1, Ser. B):3–20, 2007.
  * [16] Miguel A Goberna.  Linear semi-infinite optimization.  Mathematical Methods in Practice 2, 1998.
  * [17] Miguel A Goberna, Enrique González, Juan Enrique Martínez-Legaz, and Maxim I Todorov.  Motzkin decomposition of closed convex sets.  Journal of mathematical analysis and applications, 364(1):209–221, 2010.
  * [18] Ralph E Gomory.  Outline of an algorithm for integer solutions to linear programs.  Bull. Amer. Math. Soc., 64:275–278, 1958.
  * [19] Farhad Hüsseinov.  A note on the closedness of the convex hull and its applications.  Journal of Convex Analysis, 6(2):387–393, 1999.
  * [20] Alfredo N Iusem, Juan Enrique Martinez-Legaz, and Maxim I Todorov.  Motzkin predecomposable sets.  Journal of Global Optimization, 60(4):635–647, 2014.
  * [21] Victor Klee.  Extremal structure of convex sets.  Archiv der Mathematik, 8(3):234–240, 1957.
  * [22] Leopold Kronecker.  Näherungsweise ganzzahlige auflösung linearer gleichungen.  1884\.
  * [23] Stephen M Robinson.  A short proof of the sticky face lemma.  Mathematical Programming, 168(1-2):5–9, 2018.
  * [24] Alexander Schrijver.  On cutting planes.  Combinatorics, 79:291–296, 1980.
  * [25] Alexander Schrijver.  Theory of linear and integer programming.  John Wiley & Sons, 1998.
  * [26] Milan Studenỳ.  Convex cones in finite-dimensional real vector spaces.  Kybernetika, 29(2):180–200, 1993.
  * [27] Hermann Weyl.  Über die gleichverteilung von zahlen mod. eins.  Mathematische Annalen, 77(3):313–352, 1916.
  * [28] Haoran Zhu.  Characterization of the cutting-plane closure, 2021.  https://arxiv.org/abs/1911.12943.

## Appendices

###  C Proof of Proposition 1 and Corollaries

We will require the next extended Farkas’ lemma for the proof of Proposition
1.

######  Lemma 15 (Extended Farkas’ lemma, Corollary 3.1.2 [16]).

The inequality $ax\geq b$ is a consequence of the consistent system
$\\{a_{t}x\geq b_{t},t\in T\\}$ if and only if
$(a,b)\in\operatorname{cl}\operatorname{cone}(\\{(a_{t},b_{t})\ \forall t\in
T,(0,\ldots,0,-1)\\})$.

###### Proof of Proposition 1.

Consider the linear system $\\{\omega\cdot(x,-1)\ \forall\omega\in\Omega\\}$.
Since $\mathscr{I}(\Omega)$ is essentially the feasible region given by this
linear system which is also non-empty, we know that linear system
$\\{\omega\cdot(x,-1)\ \forall\omega\in\Omega\\}$ is consistent. By extended
Farkas’ lemma 15 and the assumption that $(0,\ldots,0,1)\in\Omega$, we obtain
$\alpha x\leq\beta$ is valid to $\mathscr{I}(\Omega)$ if and only if
$(\alpha,\beta)\in\operatorname{cl}\operatorname{cone}(\Omega)$. ∎

###### Proof of Corollary 2.

By definition, $\mathscr{I}(\Omega)$ is finitely-generated if there exists a
finite subset $\bar{\Omega}\subseteq\Omega$ with
$\mathscr{I}(\bar{\Omega})=\mathscr{I}(\Omega)$. It suffices to show: for any
finite subset $\bar{\Omega}\subseteq\Omega$,
$\mathscr{I}(\bar{\Omega})=\mathscr{I}(\Omega)$ if and only if
$\operatorname{cone}(\bar{\Omega})=\operatorname{cl}\operatorname{cone}(\Omega)$.
Note that $\mathscr{I}(\bar{\Omega})=\mathscr{I}(\Omega)$ is equivalent of
saying: any inequality $\alpha x\leq\beta$ is valid to
$\mathscr{I}(\bar{\Omega})$ if and only if it is also valid to
$\mathscr{I}(\Omega)$. By Proposition 1, that is further equivalent of saying:
$(\alpha,\beta)\in\operatorname{cone}(\bar{\Omega})$ if and only if
$(\alpha,\beta)\in\operatorname{cl}\operatorname{cone}(\Omega)$. Thus we
complete the proof. ∎

###  D Proof of Lemma 5

First, we present some well-known results in convex geometry that will be
needed.

######  Lemma 16 (Supporting Hyperplane Theorem for pointed cone).

Let $K\subseteq\mathbb{R}^{n}$ be a closed convex pointed cone. Then there is
$h\in\mathbb{R}^{n}$ such that if $x\in K$ and $x\neq 0$, then $h^{T}x>0$.

###### Proof.

Since $K$ is pointed, we know the polar cone $K^{\circ}$ is full-dimensional.
So we can find an interior point $x^{*}\in K^{\circ}$, which has $x^{*}\cdot
x<0$ for all $x\in K$. By picking $h=-x^{*}$ we complete the proof. ∎

######  Lemma 17 (Lemma 2.4 in [19], Theorem 3.5 [21]).

Let $S$ be a non-empty closed set in $\mathbb{R}^{n}$. Then, every extreme
point of $\operatorname{cl}\operatorname{conv}(S)$ belongs to $S$.

Now we are ready to verify Lemma 5.

###### Proof of Lemma 5.

From Lemma 16, we can find a supporting hyperplane $hx=0$ such that
$h\omega>0$ for all $\omega\neq
0\in\operatorname{cl}\operatorname{cone}(\Omega)$. Denote the normalized
version of $\Omega$:
$\Omega^{\prime}=\\{\frac{\omega}{h\cdot\omega}\mid\omega\in\Omega\\}$, which
is well-defined since $0\notin\Omega$, and for all $\omega\neq 0\in\Omega$
there is $h\cdot\omega>0$.

  * Claim 3. $\\{x\in\mathbb{R}^{n}\mid hx=1\\}\cap\operatorname{cl}\operatorname{cone}(\Omega)=\operatorname{cl}\operatorname{conv}(\Omega^{\prime})$.

  * Proof of claim.  First, we show $\\{x\in\mathbb{R}^{n}\mid hx=1\\}\cap\operatorname{cl}\operatorname{cone}(\Omega)\subseteq\operatorname{cl}\operatorname{conv}(\Omega^{\prime})$. Arbitrarily pick $\alpha^{*}$ such that $h\alpha^{*}=1$, and there exists $\\{\alpha^{i}\\}\subseteq\operatorname{cone}(\Omega)$ such that $\alpha^{i}\rightarrow\alpha^{*}$. Denote $\beta^{i}:=\frac{\alpha^{i}}{h\alpha^{i}}$. Since $\alpha^{i}\rightarrow\alpha^{*},h\alpha^{*}=1$, we know $h\alpha^{i}\rightarrow 1$. Hence we also have $\beta^{i}\rightarrow\alpha^{*}$, and here $\beta^{i}\in\\{x\in\mathbb{R}^{n}\mid hx=1\\}\cap\operatorname{cone}(\Omega)$. In the following, we show: $\\{x\in\mathbb{R}^{n}\mid hx=1\\}\cap\operatorname{cone}(\Omega)\subseteq\operatorname{conv}(\Omega^{\prime})$, which will imply that $\alpha^{*}\in\operatorname{cl}\operatorname{conv}(\Omega^{\prime})$ since $\beta^{i}\rightarrow\alpha^{*}$ and $\beta^{i}\in\\{x\in\mathbb{R}^{n}\mid hx=1\\}\cap\operatorname{cone}(\Omega)$. According to the arbitrariness of $\alpha^{*}\in\\{x\in\mathbb{R}^{n}\mid hx=1\\}\cap\operatorname{cl}\operatorname{cone}(\Omega)$, this will complete the proof of $\\{x\in\mathbb{R}^{n}\mid hx=1\\}\cap\operatorname{cl}\operatorname{cone}(\Omega)\subseteq\operatorname{cl}\operatorname{conv}(\Omega^{\prime})$.

Pick $\beta\in\\{x\in\mathbb{R}^{n}\mid
hx=1\\}\cap\operatorname{cone}(\Omega),$ we can write it as:
$\beta=\sum_{i=1}^{k}\lambda_{i}b^{i}$ for some
$\lambda_{i}>0,b^{i}\in\Omega,i\in[k],k\in\mathbb{N}$. Here because
$\beta\in\\{x\in\mathbb{R}^{n}\mid hx=1\\}$, we know
$\sum_{i=1}^{k}\lambda_{i}hb^{i}=1$. Therefore, we can also write $\beta$ as:
$\beta=\sum_{i=1}^{k}(\lambda_{i}hb^{i})\cdot\frac{b^{i}}{hb^{i}},\text{ here
}\frac{b^{i}}{hb^{i}}\in\Omega^{\prime},\ \sum_{i=1}^{k}\lambda_{i}hb^{i}=1.$
We get $\beta\in\operatorname{conv}(\Omega^{\prime})$, which concludes
$\\{x\in\mathbb{R}^{n}\mid
hx=1\\}\cap\operatorname{cone}(\Omega)\subseteq\operatorname{conv}(\Omega^{\prime})$.

Lastly, we show the other direction $\\{x\in\mathbb{R}^{n}\mid
hx=1\\}\cap\operatorname{cl}\operatorname{cone}(\Omega)\supseteq\operatorname{cl}\operatorname{conv}(\Omega^{\prime})$.
By definition, $\Omega^{\prime}\subseteq\\{x\in\mathbb{R}^{n}\mid hx=1\\}$,
which implies
$\operatorname{cl}\operatorname{conv}(\Omega^{\prime})\subseteq\\{x\in\mathbb{R}^{n}\mid
hx=1\\}$. On the other hand, clearly
$\Omega^{\prime}\subseteq\operatorname{cone}(\Omega)$, so
$\operatorname{cl}\operatorname{conv}(\Omega^{\prime})\subseteq\operatorname{cl}\operatorname{cone}(\Omega)$,
and we complete the proof for this claim. $\hfill\diamond$

Given an extreme ray $r\in\operatorname{cl}\operatorname{cone}(\Omega)$,
w.l.o.g. we assume $hr=1$. Then $r\in\Omega$ iff $r\in\Omega^{\prime}$. From
the above claim, we also know
$r\in\operatorname{cl}\operatorname{conv}(\Omega^{\prime})$. Lastly, we want
to show that $r$ is an extreme point of
$\operatorname{cl}\operatorname{conv}(\Omega^{\prime})$. Assume
$r=\sum_{i=1}^{k}\lambda_{i}a^{i}$ for
$\lambda_{i}>0,\sum_{i=1}^{k}\lambda_{i}=1$ and $r\neq
a^{i}\in\operatorname{cl}\operatorname{conv}(\Omega^{\prime})$. From the
definition of $\Omega^{\prime}$, we also have
$ha^{i}=1,a^{i}\in\operatorname{cl}\operatorname{cone}(\Omega)$. According to
the extreme ray assumption of $r$, while it can be written as the conical
combination (convex combination is also conical combination) of other points
in $\operatorname{cl}\operatorname{cone}(\Omega)$, we know there exists
$\gamma_{i}>0$ such that $a^{i}=\gamma_{i}r$. Since $hr=ha^{i}=1$, we have
$\gamma_{i}=1$, meaning $a^{i}=r$, which contradict to the assumption that
$r\neq a^{i}$. So for any extreme ray
$r\in\operatorname{cl}\operatorname{cone}(\Omega)$ with $hr=1$, $r$ is an
extreme point of $\operatorname{cl}\operatorname{conv}(\Omega^{\prime})$.
Since
$\operatorname{cl}\operatorname{conv}(\Omega^{\prime})=\operatorname{cl}\operatorname{conv}(\operatorname{cl}({\Omega^{\prime}}))$,
so $r$ is an extreme point of
$\operatorname{cl}\operatorname{conv}(\operatorname{cl}({\Omega^{\prime}}))$.
By Lemma 17, we obtain that $r\in\operatorname{cl}({\Omega^{\prime}})$. By
definition of $\Omega^{\prime}$, it implies that either $r\in(\Omega)_{+}$, or
there exists different $\\{r^{i}\\}\subseteq\Omega$ such that
$r^{i}\xrightarrow{c}r$. ∎

###  E Proof of Lemma 10

The next lemma says, the rational linear subspace $V_{\pi}$ defined in
Definition 2 can be characterized by any linear basis of
$\\{1,\pi_{1},\ldots,\pi_{n}\\}$ over $\mathbb{Q}$. Let $e^{1},\ldots,e^{n}$
denote the canonical basis of $\mathbb{Z}^{n}$.

######  Lemma 18.

Let $\\{1,\pi_{i}\text{ for }i\in I\\}$ be a linear basis of
$\\{1,\pi_{1},\ldots,\pi_{n}\\}$ over $\mathbb{Q}$, with
$\pi_{j}=q_{j,0}+\sum_{i\in I}q_{j,i}\pi_{i}\ \forall j\notin I$, here
$q_{j,i}\in\mathbb{Q}\ \forall i\in\\{0\\}\cup I,j\notin I.$ Then
$V_{\pi}=\\{x\in\mathbb{R}^{n}\mid x_{j}=\sum_{i\in I}q_{j,i}x_{i}\ \forall
j\notin I\\}$.

###### Proof.

Denote $L:=\\{x\in\mathbb{R}^{n}\mid x_{j}=\sum_{i\in I}q_{j,i}x_{i},j\notin
I\\}$. First, we show that $V_{\pi}\supseteq L$. For any
$\alpha\in\mathbb{Q}^{n}$ such that $\alpha^{T}\pi\in\mathbb{Q}$, since
$\pi_{j}=q_{j,0}+\sum_{i\in I}q_{j,i}\pi_{i}$ for any $j\notin I$, we have:
$\alpha^{T}\pi=\sum_{i\in I}\alpha_{i}\pi_{i}+\sum_{j\notin
I}\alpha_{j}(q_{j,0}+\sum_{i\in I}q_{j,i}\pi_{i})=\sum_{j\notin
I}\alpha_{j}q_{j,0}+\sum_{i\in I}(\alpha_{i}+\sum_{j\notin
I}\alpha_{j}q_{j,i})\pi_{i}\in\mathbb{Q}.$ Since
$\alpha\in\mathbb{Q}^{n},q_{j,i}\in\mathbb{Q}$, and $\\{1,\pi_{i}\text{ for
}i\in I\\}$ are linearly independent over $\mathbb{Q}$, hence we obtain that
$\alpha_{i}+\sum_{j\notin I}\alpha_{j}q_{j,i}=0$ for any $i\in I$. For any
$x\in L$, by definition of $L$, we have $\alpha^{T}x=\sum_{i\in
I}(\alpha_{i}+\sum_{j\notin I}\alpha_{j}q_{j,i})x_{i}$, which is simply 0.
Therefore, we have shown $V_{\pi}\supseteq L$. Next, we show $L\supseteq
V_{\pi}$. For any $j\notin I$, define $\alpha^{j}:=e^{j}-\sum_{i\in
I}q_{j,i}e^{i}$. Then easy to verify that, $(\alpha^{j})^{T}\pi\in\mathbb{Q}$.
So for any $x\in V_{\pi}$ and $j\notin I$, there is $(\alpha^{j})^{T}x=0$.
This is simply saying, for any $j\notin I,x_{j}=\sum_{i\in I}q_{j,i}x_{i}$,
which implies that $L\supseteq V_{\pi}$. ∎

###### Proof of Lemma 10.

W.l.o.g. we assume that a linear basis of $\\{1,\pi_{1},\ldots,\pi_{n}\\}$
over $\mathbb{Q}$ is $\\{1,\pi_{1},\ldots,\pi_{k}\\}$. Let
$\pi_{j}=q_{j,0}+\sum_{i=1}^{k}q_{j,i}\pi_{i}$ for any $j>k$, here
$q_{j,i}\in\mathbb{Q}\ \forall i\in\\{0\\}\cup[k],j>k.$ By Lemma 18, we know
$V_{\pi}=\\{x\in\mathbb{R}^{n}\mid x_{j}=\sum_{i=1}^{k}q_{j,i}x_{i},j>k\\}$.
When $k=n$ then $V_{\pi}=\mathbb{R}^{n}$, and the statement of this lemma is a
special case of Weyl’s criterion. We reduce the general case to this one.

The following elements lie in $\\{x\in\mathbb{R}^{n}\mid
x_{j}=\sum_{i=1}^{k}q_{j,i}x_{i},j>k\\}$, which is $V_{\pi}$:

$\tilde{e}^{i}:=e^{i}+\sum_{j=k+1}^{n}q_{j,i}e^{j}\ \forall i\leq
k,\quad\quad\tilde{\pi}=\pi-\sum_{j=k+1}^{n}q_{j,0}e^{j}.$

By Weyl’s criterion,
$\mathbb{Z}^{k}+(\pi_{1},\ldots,\pi_{k})\mathbb{Z}_{>N_{0}}$ is dense in
$\mathbb{R}^{k}$. We reformulate this for $V$ via the projection to the first
$k$ coordinates, which is an isomorphism between $V$ and $\mathbb{R}^{k}$: a
dense subset of $V_{\pi}$ is
$\sum_{i=1}^{k}\mathbb{Z}\tilde{e}^{i}+\tilde{\pi}\mathbb{Z}_{>N_{0}}$, which
is a subset of $\mathbb{Z}^{n}+\pi\mathbb{Z}_{>N_{0}}$. This completes the
proof. ∎