How do you prove that $\{ Ax \mid x \geq 0 \}$ is closed?

We denote by $a_i \in \mathbb R^m$, $i = 1, \ldots, n$ the columns of $A$. By a conic variant of Carathéodory's theorem, each conic combination of $\{a_i\}$ can be written as a conic combination of a linearly independent subset of $\{a_i\}$. Since there are only finitely many linearly independent subsets of $\{a_i\}$, it is sufficient to prove the claim for matrices $A$ which have full column rank (i.e., all columns are linearly independent). But in this case, the claim is easy to establish.


Here is an alternative approach. I wish I could give proper attribution – I am fairly certain I learned this in the context of some nonlinear programming coursework, but it's been so long ago, my memory is fuzzy. Someone on the faculty at either Cornell or MIT in the early 90's showed me this, or at least gave me a hint. :-)

The approach relies on the following fact: any linear optimization problem (with finitely many variables and constraints) that has a finite optimal value attains that optimal value, i.e., it has at least one optimal solution. There are many ways of proving this fact, but there is one approach that does not rely on any convex analysis, and thus using this fact would not lead us to a circular argument. (For those of you curious, this is a classic argument in linear programming: (1) Any feasible linear program (LP) can be reformulated as an equivalent LP in standard form; (2) Any feasible LP in standard form is amenable to the Simplex algorithm; (3) If the above LP is not unbounded, and an anticycling pivoting rule is used, the Simplex method will terminate finitely and produce an optimal solution; this solution of the standard form LP can then be easily transformed into an optimal solution of the original LP.)

So, suppose $y$ is a limit point of the set in question, and consider the following optimization problem: $$ \inf_{x} \|y-Ax\|_\infty\text{ subject to } x\ge 0. $$ (Here, $\|\cdot\|_\infty$ denotes the $\infty$-norm.) This optimization problem is clearly feasible (e.g., $x=0$ is a feasible solution), and its optimal value is $0$, since there exists a sequence of feasible solutions $\{x^k\}_k$ such that $\lim_{k\rightarrow\infty}Ax^k=y$.

As written, this optimization problem is not an LP, but can be reformulated as an equivalent LP using well-known reformulation "tricks." Therefore, we can conclude that the problem has an optimal solution, to wit, a point $x\ge 0$ such that $\|y-Ax\|_\infty=0$, or $y=Ax$, as desired.


The cone $C=\{y\colon Ax=y,x\ge 0\}$ is finitely generated (by finitely many columns of $A$) and convex. By Minkowsky-Weyl theorem (en easy proof via Fourier-Motzkin eliminations can be found here, Theorem 1) it is a polyhedral cone, that is, $C=\{y\colon By\le 0\}$. From the last representation it is clear that $C$ is closed as an intersection of closed half-spaces.