  Fourier-Motzkin elimination is a projection algorithm for solving finite
linear programs. We extend Fourier-Motzkin elimination to semi-infinite linear
programs which are linear programs with finitely many variables and infinitely
many constraints. Applying projection leads to new characterizations of
important properties for primal-dual pairs of semi-infinite programs such as
zero duality gap, feasibility, boundedness, and solvability. Extending the
Fourier-Motzkin elimination procedure to semi-infinite linear programs yields a
new classification of variables that is used to determine the existence of
duality gaps. In particular, the existence of what the authors term dirty
variables can lead to duality gaps. Our approach has interesting applications
in finite-dimensional convex optimization. For example, sufficient conditions
for a zero duality gap, such as existence of a Slater point, are reduced to
guaranteeing that there are no dirty variables. This leads to completely new
proofs of such sufficient conditions for zero duality.
