m
Projection: A Unified Approach to Semi-Infinite Linear Programs
and Duality in Convex Programming
Amitabh Basu
Kipp Martin
q , Christopher Thomas Ryan
(N
Vh '• April 11, 2013
Or
<
O ■ Abstract
u
ctf
s
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
^J , 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.
m ,
5 ■ Contents
1 Introduction
2 Fourier-Motzkin elimination [5|
3 Solvability and duality theory using projection
3.1 The projected system
3.2 Primal results
d i 3.2.1 Primal feasibility
3.2.2 Primal boundedness
3.2.3 Primal solvability
3.3 Dual results
3.3.1 Dual feasibility
3.3.2 Dual boundedness
3.3.3 Dual solvability
3.3.4 Zero duality gap and strong duality . . .
3.4 Summary of primal and dual results
3.5 Tidy semi-infinite linear programs
3.6 Finite linear programs
Feasible sequences and regular duality of semi-infinite linear programs [26|
1
5 Application: Conic linear programs
5.1 Zero duality gap via boundedness
5.2 Regular duality for conic programs
5.3 Zero duality gap via Slater's condition
6 Application: Convex programs
7 Application: Generalized Farkas' Theorem
8 Application: Further results for semi-infinite linear programs
8.1 Additional sufficient conditions for zero duality gap
8.2 Finite approximation results
30
31
31
9 Conclusion [40|
1 Introduction
Duality is an important theoretical and practical topic in optimization. In order to better
understand the structure of an optimization problem (called the primal), and design solution
algorithms, it is often useful to consider its dual (or duals). A key determinant of the usefulness
of the dual is the duality gap which is the difference between the optimal value of a primal and
the optimal value of the dual. Establishing that the primal and dual have zero duality gap is
particularly desirable and is a subject of intense study throughout the field of optimization.
Linear programming is a perfect example. Every linear program has a well-understood dual
with the simple property that when the primal is feasible with bounded optimal value, there is
zero duality gap. Moreover, optimal solutions to both the primal and dual are guaranteed to
exist. For more general problems, additional conditions are needed to establish zero duality gap
and the existence of an optimal solution.
Much research has focused on sufficient conditions for zero duality gap. Possibly the most
well-known sufficient condition for zero duality gap is the Slater condition for convex program-
ming. Slater's condition states that when the feasible region of the primal convex program
has an interior point (sometimes called a Slater point) there is zero duality gap. "Slater-like"
conditions are also prevalent in conic programming, where the existence of interior points to the
dual conic program guarantees a zero duality gap (see for instance, Gartner and Matousek Q).
Less well-known is the duality theory of semi-infinite linear programs. These are linear opti-
mization problems with a finite number of variables and possibly infinitely many constraints.
In this paper we use this theory to understand the duality of both convex and conic programs.
In semi-infinite linear programming, a variety of sufficient conditions for zero duality gap have
been introduced (see for example, Anderson and Nash [l(, Charnes, Cooper and Kortanek [2|],
Duffin and Karlovitz [6[, Goberna and Lopez [9|, and Karney [1Q(). We provide an alternate
and unifying approach to duality in semi-infinite linear pro gram s.
We extend Fourier-Motzkin elimination (projection) [7], [ll| to semi-infinite systems of lin-
ear inequalities as a method to study duality. Taking the dictum expressed by Duffin and
Karlovitz [6( of "the desirability of omitting topological considerations" to its logical conclusion,
the method of projection is purely algebraic. It is simply the aggregation of pairs of linear
inequalities using nonnegative multipliers. Applying Fourier-Motzkin elimination to a semi-
infinite linear program reveals important properties about the semi-infinite linear program that
can only be obtained through this elimination (or projection) process. In particular, Fourier-
Motzkin elimination reveals the existence of what the authors term "dirty" variables. Dirty
variables are necessary for the existence of a duality gap. The dirty variable characterization
also has important implications for finite dimensional problems. For example, sufficient con-
ditions for a zero duality gap in a finite-dimensional convex optimization problem, such as
existence of a Slater point, are reduced to guaranteeing that there are no dirty variables in an
appropriately defined semi-infinite linear program.
The extension of Fourier-Motzkin elimination to semi-infinite linear programs involves sub-
tleties that do not arise in standard Fourier-Motzkin theory where the number of inequalities is
finite. Sections [5] and [3] provide a cogent framework for analyzing semi- infinite linear programs.
Applying projection leads to new characterizations of important properties for primal-dual pairs
of semi-infinite programs such as zero duality gap, feasibility and boundedness, and solvability.
These results have implications for finite-dimensional conic linear programs and convex opti-
mization. See Section [5] and Section [6j respectively. Applications of the results from Section [3]
to the generalized Farkas' theorem and additional sufficient conditions for zero duality gap in
semi-infinite linear programs are in Section [7] and Section [H respectively. Concluding remarks
are in Section [9]
We begin with a brief notation review and a summary of our results.
Notation
Let Y be a vector space. The algebraic dual of Y, denoted Y', is the set of linear functionals
with domain Y. Let tp £ Y' . The evaluation of i\) at y is denoted by (y, if>); that is, (y, ip) = ip(y).
Let P be a convex cone in Y. A convex cone P is pointed if and only if P n — P = {0}. A
pointed convex cone P in Y defines a vector space ordering >p of Y, with y >zp y' if y — y' G P-
The dual cone of P is P' — {ip £ Y : (y, ip) > for all y £ P}. Elements of P' are called positive
linear functionals in Y. A cone P is reflexive if P" = P under the natural embedding of Y c -> Y".
Let A be a linear mapping from vector space X to vector space Y. The algebraic adjoint
A' : Y' ->■ X' is defined by A'{ip) = ipoA and satisfies (x, A'(ip)) = (A(x),ip) where ip £ Y' and
x£X.
Given any set /, R 7 denotes the vector space of real- valued functions u with domain /, i.e.,
u : I — > K. For u £ R 1 the support of u is the set supp(u) = {i £ I : u(i) / 0}. The subspace
R( 7 ) are those functions in R 7 with finite support. Let > denote the standard vector space
ordering on R 7 . That is, u > v if and only if u(i) > v(i) for all i £ I. The subspace M^ 7 ^
inherits this ordering. Let K^_ (resp. MS ) denote the pointed cone of u £ K 7 (resp. u £ M.\ )
with u > 0. Using the standard embedding of R*- 7 -* into (R 7 )' for u £ R 7 and v £ M.^\ write
(u,v) — X)j£/ u(i)v(i). The latter sum is well-defined since v has finite support.
For all h £ I, define a function e h £ R 7 by e h (i) = 1 if h = i, and e h (i) — if h ^ i for all
i £ I. When / = {1, 2, . . . , n}, R 7 is R™ and e 1 , e 2 , ...e™ correspond to the standard unit vectors
ofR".
The optimal value of optimization problem (*) is denoted by v(*).
Our results
The main topic of study is the semi-infinite program
inf^eR- c x ,„ ,
s-t. Efc=i o*(*)a;* > &(*) iori£l [ ^^>
where / is an arbitrary (potentially infinite) index set, c £ R™, and b,a k el' for k = 1, . . . , n,
and its finite support dual
SU P J2iei b ( i ) v ( i )
s.t. E,-e/O fc (*)v(«) =c fe for fc = l,...,n (FDSILP)
u el! 7 '.
Our main results on this primal-dual pair are summarized in Table Q] (see page(33]). These include
a sufficient condition for primal solvability (Theorem 13. 10[) and characterizations of both dual
solvability (Theorem 13. 20p and zero duality gap (Theorem I3.21| . Here, zero duality gap means
t> pLPl) = ?; (|FDSILPI) when pEP) is feasible.
We identify a special class of semi-infinite linear programs, termed tidy semi-infinite linear
programs, where zero duality gap is guaranteed to hold (Theorem 13. 24|) . The name tidy comes
from the fact that the Fourier-Motzkin elimination procedure eliminates (or "cleans up" ) all
primal decision variables. In our terminology, there are no "dirty" decision variables.
Theorem ET241 If (jSILPj) is feasible and tidy then
(i) (ISlLPl) is solvable,
(ii) (jFDSILPp is feasible and bounded,
(iii) there is a zero duality gap for the primal-dual pair (jSILPp and (|FDSILP[) .
In particular, the method of projection is used to prove a result due to Duffin and Karlovitz [6]
on duality gaps for semi-infinite linear programs with bounded feasible regions by showing such
semi- infinite linear programs are tidy (Theorem 13.251 establishes a slightly more general result).
A number of sufficient conditions for zero duality gap in semi-infinite linear programs due
to Karney [10( also follow directly from our results in Section [3) This is shown in Section [8]
Applications in Convex Optimization
The theory of tidy semi-infinite linear programs is leveraged to establish important duality
results in conic and convex programming. In conic programming the standard primal is
s.t. A(x) hp d v '
where X and Y are vector spaces, A : X — > Y is a linear mapping, d £ Y, P is a pointed convex
cone in Y and (f> is a linear functional on X. The standard dual (also a conic program) is
SUp^gy, (d, V>)
s.t. A'(i/j) = (j) (ConLPD)
ip£P'.
We study a semi-infinite linear program that is equivalent to (ConLP) and use the method of
projection to give a new proof of the following well-known duality result for conic programs.
Theorem l5.12l (Slater's theorem for conic programs). Let X and Y be finite-dimensional vector
spaces, and let P be reflexive. Assume the primal conic program (jConLPp is feasible. Suppose
there exists ip* 6 int(P') with A'(tp*) = c. Then the primal-dual pair (|ConLPI) - (IConLPDp has
a zero duality gap. Moreover, the primal is solvable.
Our proof uses the interior point ip* to construct a set of constraints that show the asso-
ciated semi-infinite linear program is tidy. Thus, zero duality gap and primal solvability are
established in a transparent "algebraic" manner. Alternate proofs (see for instance Gartner and
Matousek [8j) are based on a intermediate result called regular duality, a core theorem in its own
right. According to regular duality, the primal optimal value corresponds to limiting values of
sequences of points in the dual space, which are dual feasible in a limiting sense. Regular duality
is also established in this paper as a consequence of our method of projection (Theorem 15. 10|) .
but this intermediate step is unnecessary in our proof of Theorem 15.121
In addition, we prove Theorem 15.81 below. A more restricted version of this result is known
in the classical conic programming literature (see for example Duffin [5j). Our result is obtained
with a completely new proof using projection techniques.
'-xewt n
/(*)
s.t.
9i{x)
X
> o
e
for i =
= 1
Theorem 15.81 (Zero duality gap via boundedness) . Let X be finite-dimensional. If P is re-
flexive and there exists a scalar 7 such the set {x : A(x) <^p d and (x, </>) < 7} is nonempty and
bounded, then there is no duality gap for the primal-dual pair (IConLPp - ljConLPPp .
In particular, conic programs with bounded feasible regions always have zero duality gaps.
Next, consider the following general convex program
..,p (CP)
where /(x) and gi(x) for i = 1, . . . ,p are concave functions, and f2 is a closed, convex set. Define
the Lagrangian function L(X) := max{/(x) + X)f=i ^i9i( x ) '■ x S ^}- The Lagrangian dual is
inf L(X). (LD)
A>0
Slater's condition is a key result in finite-dimensional convex programming.
Theorem 16.41 (Slater's theorem for convex programs). Suppose the convex program (|CP[)
is feasible and bounded. Moreover, suppose there exists x* € ft such that gi(x*) > for all
i = 1, . . . , p. Then there is zero duality gap between the convex program (1CP[) and its Lagrangian
dual (jLDp . Moreover, there exists A* > such that v (ILDp = L(X*), i.e., the Lagrangian dual is
solvable.
Our proof uses the fact that the Slater point x* corresponds to a useful constraint in the
semi-infinite linear program representing the Lagrangian dual. The structure of this constraint
implies the boundedness of the feasible region for a fixed objective value. By Theorem 13.251
this implies zero duality gap and dual solvability. As in the case of conic programs, the result
is established in a transparent "algebraic" manner using the method of projection.
Beyond these results in conic and convex programming, the method of projection is used to
elegantly prove several foundational results for semi-infinite linear programs. In the process, new
structural insights are given. These results include finite approximability of semi-infinite linear
programs (see our Theorem [83] that generalizes Theorem 2.1 in Karney [l0|) and the generalized
Farkas' theorem for infinite systems of linear inequalities (see our Theorem 17.11 and Theorem
3.1 in Goberna and Lopez [9|]). Goberna and Lopez use the latter result as the main tool for
deriving their own set of necessary and sufficient conditions for zero duality in semi- infinite linear
programs. Thus, our methodology can, in principle, be used as an alternate starting point to
derive their results.
2 Fourier-Motzkin elimination
In this section we extend Fourier-Motzkin elimination to semi-infinite linear systems. For
background on Fourier-Motzkin elimination applied to finite linear systems see Fourier [7J,
Motzkin [llj, and Williams [12j. In this section, Fourier-Motzkin elimination elimination is
used to characterize the feasibility and boundedness of semi-infinite systems of linear inequal-
ities. In addition, useful properties are shown about the Fourier-Motzkin multipliers which
appear while aggregating constraints. These properties prove critical in our approach to duality
theory.
Consider the semi-infinite linear system
a 1 (i)x 1 +a 2 (i)x 2 H h a n {i)x n > b(i) for i e I (2.1)
where I is an arbitrary index set. Denote the set of (xi, . . . ,x n ) G M" that satisfy these
inequalities by T. The projection of T into the subspace of R™ spanned by {e J }" = 2 i s
P{T;x 1 ):={{x 2l x 3 ,...,x n )eR n - 1 : 3 Xl G R s.t. (a*, a*, . . . ,i„) G T}. (2.2)
Under certain conditions, the projection P(T; Xi) is characterized by aggregating inequalities in
the original system. Define the sets
n+(k)
H-{k)
H (k)
= {i G I | a k (i) > 0}
= {i G I J a k (i) < 0} (2.3)
= {i£l\ a k (i) =0}
based on the coefficients of variable Xk in (I2.1J) .
For now, assume %+(l) and 'H-(l) are both nonempty. As in the finite case, eliminate
variable x\ by adding all possible pairs of inequalities with one inequality in H+(l) and the
other from %_(1). Since there are potentially infinitely many constraints this may involve
aggregating an infinite number of pairs. The resulting system is
fe=2
a k {i)x k > b(i) for i G U {1) (2.4)
Ef4M-4^W-T?) ^ for P G^(l)and,G^(l). (2.5)
Denote the set of (x 2 , . . . , x n ) G M™ _1 that satisfy the constraints in (|2.4I) - (I2.5|) by FM(T; X\).
Remark 2.1. One way to view the inequalities (|2.5p is the following : pick a pair (p,q) of
inequalities with p G H+(l) and q G H_(l). Then form a new constraint by multiplying the
first constraint by a u -, , multiplying the second constraint by — a u \ , and adding them together.
This "eliminates" x\ from this pair of constraints. Of course, one can achieve this by choosing
any common multiple of u , and — rW as the multipliers prior to adding them together, and
achieve a "scaled" inequality describing the same halfspace (with x\ "eliminated"). <
A key result is that the inequalities in (I2.4l) - (|2.5p describe the projected set P(T; x%).
Theorem 2.2. If U+{1) and H-(l) arc both nonempty, then P{T;xi) = FM(T;xi).
Proof. Since H+(l) and H_(l) are both nonempty,
{X2,X 3 , . . . ,x n ) G P(T;xi)
<^> 3xi G R such that a}{i)x\ + a?{i)x2 + ■ ■ ■ + a n (i)x n > b(i) for i G /
{Sfc=2 a k (i)xk > b(i) Vi G "Ho and
Si > ^y - EL2 fr^j^fe, Vp G "H+(l) and
/ EL2 a fe (*)^fe > &(*) Vi G Ho and 1
<& (X2,x 3 ,...,x n ) €FM(T;xi).
Note that the second to last equivalence holds because both T-L + (l) and H- (1) are nonempty. D
Equally as important to our theory is how "dual information" is accrued during the process
of elimination. The following result captures the essence of this idea.
Corollary 2.3. If H+(l) and H-(l) are both nonempty, then there exists an index set I and
u h £ W + ' for h £ I such that the projection P{T;x\) is
P(T; xi) = {{x 2 , ■ • • , X„) | a 2 (/i)a;2 H h o"(/i)x„ > 6(fe) for fe £ 1}
where b, a 2 , . . . , a n £ M 7 are given by
(i) o(fe) = (o, u h ) for all feel,
(ii) a k (h) = (a k , u h ) for all k = 2, . . . ,n and feel,
(iii) (a 1 ,?/) =0 for all fee/.
Proof. By Theorem |2~2I P(T;xi) = FM(T;Xi). Show that FM(T;xi) has the required repre-
sentation. Since %+(l) and %-(l) are both nonempty, take J = Hq(1) U ("H + (l) x %_{!)). For
each fe e %o(l), take u h e M^ as the function with value 1 at fe and otherwise. For each
h = (p, q) £ U+(l) x H-(l), take u h £ R^ as the function u h : I -> R defined by
[ s4l' when J =p
uh (*) = S ^^T?!' wheni = q
[ 0, otherwise.
Now define 6, a 2 , . . . , a" using the equations from (i) and (ii) in the statement of the corollary.
The proof is then complete by observing that FM(T;xi) = {(x2, ■ ■ ■ ,x n ) | a 2 (h)x2 + ••• +
a n (h)x n > o(fe) for fe £ 1} with these definitions. □
Below is a formal statement of Fourier- Motzkin elimination, which applies the above proce-
dure sequentially for each variable.
FOURIER-MOTZKIN ELIMINATION PROCEDURE
Input: A semi-infinite linear inequality system
a}{i)xi + a 2 (i)x-2 H h a n (i)x n > b(i) for i £ I.
Output: A semi- infinite linear inequality system
a\h)xi + h l+1 {h)x i+1 + --- + a n (h)x n > o(fe) for fe £ I. (2.6)
The variables xi, . . . ,x n form a subset of the variables of the input system relabeled according to
a permutation ir : {1, . . . , n} — > {1, . . . , n}. We allow £ e {1, . . . , n,n + 1} , interpreting £ — n + 1
to mean that the left-hand side is zero. We also output a set of vectors {u h £ R + : h £ I}.
Procedure:
1. Initialization: D «- {1, . . . , n}, I <- I, a k <- a fc for all fc e D, 6 <— 6, and j <— 1. For
each fe e J = I, set w' 1 <— e ft .
2. Elimination: While (j < n) do:
a. Define the sets H+ij), H-(J) and Ho(j) as follows.
H+(j):={h£l\V(h)>0}
H-(j)
H (j)
b. If H+(j) + and H-(j) + do:
= {fee/ | a J (h) <0}
= {feel | aJ'(fe) = 0}
(i) Set I <- Uo(j) U [H+V) x H-(j)} and V <- V \ {j}.
(ii) For each k £T> define a k : I ->■ R by
_ / a fc (ft) for ft € «o(i)
° ( } " I Sg " Si *- ft = ( P , q ) e H + (j) x «.(,■)
(iii) For each h £ I, define u h £ R+ ) by
u' 1 := < j ,.,, j
for ft £ Ha(j)
(v) Define 6 : J -> R by
b(h) for ft 6 -Ho(i)
6(g)
s j (p) a j (?)
(iv) For each k £ V, set a k <— a fc . For each h £ I, set u' 1 «— a
^L__HsL i orh = (p, q )£H + U)xH-U)
6(ft)
and set b
<-&.
end do.
c.
WH+(j)\JH.
-t?) =
d.
j <- i + i-
end do.
then set £>^£>\{j}.
3. Output formatting: Upon termination X> is either empty or, for some I £ {1, . . . , n},
can be written T> = {d\, . . . , d„_£ + i} where <i € {1, . . . , n) with di < dj for z < j. Let
T> = {1, . . . ,n} \ V — {di, . . . 7 di-i} where di £ {1, ...,n} and di < dj for i < j. In
other words, I — 1 variables were eliminated and the rest n — £ + 1 variables indexed by
the indices in T> are not eliminated.
a. If I? = 0, output the system
> fe(ft) for ft e I.
b. Else if £> ^ 0, reassign the indices in T> by dj ■<— t — 1 + i for % = 1, . . . , n — •£ + 1. If T>
is nonempty, reassign the indices in T> by di <— i for i = 1 , . . . , £ — 1. This defines the
permutation n described in the output. Now, construct the system
a e (h)xi + d e+1 (h)x i+1 + ...+ a n (h)x n > b(h) for h £ I.
Definition 2.4 (Clean and dirty variables). At the end of the Fourier- Motzkin procedure, the
variables x\, . . . ,xi-i are called clean variables and the variables xi,...,x n are called dirty
variables. Thus, a dirty variable is one that the Fourier-Motzkin procedure could not eliminate
and a clean variable is one that the procedure could eliminate.
Definition 2.5 (Canonical form). A semi-infinite linear system (|2.1[) is said to be in canonical
form if the permutation n output by the Fourier-Motzkin elimination is the identity permutation.
Lemma 2.6. For every semi-infinite linear system, there exists a permutation of the variables
that puts it into canonical form. Moreover, if you apply the Fourier-Motzkin procedure to the
original system and to the permuted system, they result in the same system of inequalities in
the output.
Proof. The permutation output by the Fourier-Motzkin procedure is one such desired permu-
tation. □
Remark 2.7. In light of Lemma I2l)| we assume without loss, that semi-infinite linear systems
are always given in canonical form before applying the Fourier-Motzkin elimination procedure.
There may exist multiple permutations of the variables which put a given semi-infinite system
into canonical form. Moreover, two different permutations may lead to systems in canonical
form with a different number of clean and dirty variables. For our purposes, this will not make
a difference and any permutation that puts the semi-infinite system into a canonical form will
suffice.
Definition 2.8. The finite support element, u h for every h £ I, that is generated by the Fourier-
Motzkin elimination procedure is called a Fourier-Motzkin elimination multiplier, or simply a
multiplier.
The key property of the Fourier-Motzkin elimination procedure is that it characterizes geo-
metric projections. For £ < n define
P(T;xi,...,xe-i) := {(xe,...,x n ) £ M. n ~ e+1 : 3xi, . . . ,xt-i s.t. (xi,...,xt-i,xt, .. . ,x n ) £ T}.
Theorem 2.9. Apply the Fourier-Motzkin elimination procedure with input inequality system
(|2.1j) to produce output system (|2.6[) . For all h £ I, the finite-support multipliers u h £ W +
generated by the Fourier-Motzkin procedure satisfy
(i) b(h) = (b,u h ),
(ii) a k (h) = (a k , u h ) for all k = £, . . . , n, and
(iii) (a k , u h ) = for all k = 1, . . . ,£ - 1.
In addition, if not all variables are eliminated, and in the output system (|2.6[) £ < n, then
P(T; xi, . . . , a*_i) = {(x e , . . . , x n ) | (EH) holds}.
Proof. If I = 1, then only Step 2d. of the Fourier-Motzkin elimination procedure is executed
and the original system remains unchanged so I = /, a k — a k , k = 1, . . . ,n and b = b. Based
on the initialization step, u h = e h for h £ I and (i)-(iii) follow. If £ > 2, since the system is in
canonical form, the result follows from recursively applying Corollary 12.31 □
Corollary 2.10 (Clean projection). Let (|2.1[) be a semi-infinite linear system and let 1 < M <
min{£,n} where £ is the index of the first dirty variable in the output system (|2.6j) . After the
while loop in Step 2 of the Fourier-Motzkin elimination procedure iterates M times, we have
the following intermediate system (recall (|2.ip is assumed to be in canonical form)
a M+l (h)x M +i + a M+2 {h)x M +2 + ■■■ + a n {i)x n > b{h) for he I. (2.7)
Then
P(T;xi, ■ . .,x M ) = {{xm+i, ...,x n ) | (HZ} holds}.
Proof. Follows from a finite number of applications of Corollary 12.31 □
Partition the index set / in (12.6p . into two sets H\ := {h £ I : a k (h) = for all k £ {£,..., n}
and H 2 := I\ H x . Rewrite §XM as
> b(h) for h £ H x (2.8)
a e (h)x e + a l+1 (h)x e+l + ---+a n (h)x n > b(h) for h £ H 2 . (2.9)
If H 2 — (that is, £ = n + 1), then system (|2.8p - (|2.9l) is a clean system. Otherwise, if H 2 ^ 0,
(|2.8p - (|2.9p is a dirty system. In a dirty system, for any k £ {£,... ,n}, either a k (h) > for all
h £ H 2 , or a k (h) < for all h £ H 2 . Moreover, YZ=i \a k {h)\>0 for h £ H 2 .
9
Definition 2.11. Given a dirty system (|2.8l) - (|2.9p and a real number 5 > 0, let x(5;£) denote
the tuple (xg, . . . , x n ) where for each k £ {£,..., n}, x k = S if a fc (/i) > for all /i S H2 and
Sfe = —(5 otherwise. Let xu{5;£) denote the fcth entry of x(S;£).
Remark 2.12. When / is a finite set, the concept of a dirty variable is unnecessary. In the finite
case, there is always a value of S such that x(5, £) is a feasible solution to (|2.9|) . It is therefore
legitimate to drop the constraints indexed by H2 from further consideration. Therefore, when
implementing the Fourier-Motzkin procedure in the finite case, if variable Xk is dirty, then one
would drop all the constraints h for which a k (h) > (or a k (h) < 0). <i
Theorem 2.13 (Feasibility). Applying Fourier-Motzkin elimination to (|2.1j) results in sys-
tem (|2.8[) - (I2.9[) . If H2 7^ then the system is feasible (i.e. T is nonempty) if and only if
(i) b(h) < for all h E H u and
(ii) sup heHa Hh)/Y2=l \a k (h)\ < 00.
Moreover, if H2 = then L is nonempty if and only if (i) holds.
Proof. If H2 =/= 0, then L is nonempty if and only if P(T; x\, . . . , Xt—i) is nonempty. By The-
orem El P(T; xx,..., xt-!) is defined by I^M~^M- Therefore, it suffices to show ([2~8l) - ([2~9l)
has a feasible solution if and only if conditions i) and ii) hold.
(=>) Assume X£, . . . ,x n be a feasible solution to (|2.8I) - (I2.9|) . Let S = max{|S£|, |x£+i|, . . . , \x n \}.
First, all inequalities in Hi are satisfied and this gives condition i). Moreover, for all h E H2,
Hh) < El= e a k (h)x k < J2 n k=e\a k (h)\\x k \ < «(E*=< l«*W|). This implies for every h e H 2 ,
Kfy/Y^k^i \® k (h)\ < S < 00 and this gives condition ii).
(<==) Assume i) and ii) hold. By ii) there exits a S > maxjOjSup^g^ b(h)/Y^k=e \& k (h)\}-
Show that x(6;£) is a feasible solution to (|2.8 p -(|2.9 p . It suffices to show (|2.9p . since (|2TS|) is
implied by condition i). For any h e H 2 , Y^k=i a k (h)xk(S;£) = 5i^l =l \a k (h)\) > b(h), where
the last inequality follows from the fact that S > sup heff2 b{h)/Y^k=i l» (fo)|. Thus, x(8;£) is a
feasible solution.
Now consider the case H2 = 0- If the inequalities in the original system hold (that is, T 7^ 0)
then the inequalities > b(h) for h £ Hi must also hold, since these inequalities are consequences
of the original system. Thus, (i) holds. Conversely, suppose b(h) < for all h € Hi. Now, just
before x n is eliminated in the Fourier-Motzkin elimination procedure (x n must be eliminated
since H2 = 0) the system stored in the algorithm (after a scaling as stated in Remark 1 2. 1 [1 is
> b{h) for h E U (n) (2.10)
x n > b{ti) for ti € H+(n) (2.11)
-x n > b{h") for h" E H-(n). (2.12)
When x n is eliminated, system (|2~8l) - (l2J|) is derived with b(h) = b{h') + b{h") where h = (h' , h")
for h! E Ti+(n) and h" E H-(n). By hypothesis, b(h) < for all h E Hi and this implies
b{h') < —b(h"). Then there exists an x n such that b(h') < x n < —b{h") for all h! E H+(n) and
h" E H-{n) and this x n that satisfies (|2~TT|) and ([2~T2|) . Note that ((2lB holds by hypothesis
since 'Ho(") Q Hi. Thus, (|2.10p - (|2.12p is a feasible system. By Corollary 12.101 this system
is the projection P(T; x±, . . . , x n -i)- Thus, P(T; xi, . . . , x n -i) is nonempty and therefore T is
nonempty. □
Remark 2.14. In the proof of Theorem 2.8 it was shown that when T is nonempty and
n
5 > max{0. sup b(h)/ V \a k (h)\},
heH 2 k=i
the tuple x(S;£) as defined in Definition 12. Ill is feasible to (|2.8p ~ (|2.9p and thus can be extended
to a feasible vector in T. This fact is used in later development. <
10
We next characterize the boundedness of the feasible set T.
Theorem 2.15 (Boundedness). If T is a bounded set, then applying Fourier-Motzkin elimina-
tion to the system ([2TTJ1 that defines T, gives the system (|2~g)) - (l23)) with H 2 = fit-
Proof. Prove the contrapositive and assume Hi is nonempty. This implies the existence of dirty
variables. Since r ^ 0, sup^ eHa b{h)/Y!Jk=i I^COI < °o by Theorem 12. 131 For any
(5>max{0. sup b(h)/ V \a k {h)\},
heH 2 k=g
x(S;£) is feasible for the system (|2.8|) - ()2.9[) by Remark 12.141 The components of x(S;£) be-
come arbitrarily large in absolute value as (5 — > oo. Since (|2.8|) - (|2.9j) describes the projection
P(T; xi, . . . , X n ) there are feasible solutions for T which take arbitrarily large values in the com-
ponents xe, . . • , x n . This contradicts the fact that T is bounded. □
Example 2.16. The opposite implication in Theorem 12.151 does not hold in general. For
example, consider the linear system —x\ — £2 > 0, x\ + x-i > 0. The feasible region is the
unbounded line x\ + x 2 = 0; but H2 is empty when applying the Fourier-Motzkin elimination
procedure because the output is the degenerate system > 0. <
Theorem 12 . 1 71 below provides a very useful property about Fourier-Motzkin elimination mul-
tipliers that plays a pivotal role in establishing duality results in Section [3.31
Theorem 2.17. Applying Fourier-Motzkin elimination to (|2. 1[) gives (|2.6|) . Let u £ R + such
that (a k , u) = for k — 1, . . . , M with £ — 1 < M < n. Then, there exists a nonempty finite
index set I C I such that for all h £ I the Fourier-Motzkin multipliers u h satisfy (a k , u h ) =
for k = 1, . . . , M. Moreover, there exist scalars A^ > for h 6 / so that u = J2hei^ huh -
Proof. Proceed by induction on n. First prove the inductive step on n and then the n = 1 step.
Assume the result is true for an n — 1 variable system and show that this implies the result is
true for an n variable system. Apply Fourier-Motzkin elimination to the n — 1 variable system
a 1 (a)x 1 + tt 2 («)z 2 H \-a n (i)x n ~i > b(i) for i £ I, (2.13)
obtained by dropping the last column in system (|2.1[) . The result is
a in - 1 {h)x in _ 1 +a <? — 1+1 (/i)a; £ „_ 1+ i + --- + a"" 1 (^)a;„_i >b(h) for h £ I (2.14)
where £ n -i denotes the first index of the dirty variables in the Fourier-Motzkin elimination
output. There are two cases to consider.
Case 1: M < n. Variable £ — 1 is the last clean variable in (12.11) . The assumption that M < n,
together with the theorem hypothesis that £ — 1 < M, implies £ — 1 < n so the last clean
variable in (|2.ip is strictly less than variable n. Then the last clean variable in (J2.13I) is the
same as the last clean variable in (|2.1|) . This implies Fourier-Motzkin elimination applied to
both systems yields identical multiplier vectors. Invoke the induction hypothesis for the n — 1
variable system (|2.13p . Denote by M„_i the value of M and £ n -i the value of £ when the
induction hypothesis is applied to (|2.13[) . Since £ — 1 < M < n and the last clean variable
for (|2.ip is the same as the last clean variable for (|2.13[) . it is valid to set M„_i = M and
£ n —\ — 1 =1—1. Because Fourier-Motzkin elimination applied to both systems yields identical
multiplier vectors, the induction hypothesis implies that the Fourier-Motzkin multipliers also
satisfy the requirements of the theorem for the n variable system.
Case 2: M — n. In this case (a k ,u) = for k = l,...,n. Therefore it is valid to apply the
induction hypothesis to the n—1 variable system (|2. 13[) with M n _i = n—1 and £ n -i = min{£, n}.
11
Then there exists a finite index set {1, . . . ,t} = I C I and multipliers w 3 such that (a k , w 3 ) =
for all k = 1, . . . , n — 1 and j = 1, . . . , t and scalars ay > such that
u = V =1 a.,w J . (2-15)
The multipliers w 3 , j = 1, . . . ,t, are used to show that column n is clean in (|2.1j) and that u is
a nonnegative combination of multipliers that result from eliminating this last column n.
By Theorem 12.91 the scalars (a™, to 7 ) are among the coefficients on x n before that variable
is processed when Fourier- Motzkin elimination is applied to (|2.1[) . Either
(i) (a n ,wJ)=Oforj = l,...,t
or
(ii) there exists j + ,j~ G {l,...,t} such that (a n ,w 3 ) > and {a n ,w^ } < 0.
Conditions (i) and (ii) are exhaustive since = (a n ,u) = X) 7 =i ay (a™, w 3 ) for ay > and so
if (a n , w j ) > for j = 1, . . . , t (similiarly (a n , w j ) < for j = 1, . . . , t) then (a n , w 3 ) = for
j = l,...,t.
If (i) holds, and {a n ,w j } = for j = 1, . . . , t, then {a k ,w j ) = for j = 1, . . . , t, k = 1, . . . , n;
thus w J for j = l,...,t are Fourier- Motzkin multipliers when Fourier- Motzkin is applied to
(|2.1[) . and u — Ylj=i &j w:j ancl Case 2 is proved.
If (ii) holds then x n is a clean variable with respect to the system produced during the
Fourier-Motzkin procedure before variable x n is processed: it has both a positive coefficient
(a n ,wi } > and a negative coefficient (a n , w 3 } < 0.
Define three sets J+, J~ and J° where j e J + if (a™, w- 7 } > 0, j e J - if (a™,u; J ) < and
j G J° if (a™, w J ) = 0. In case (ii) both J + and J~ are nonempty. As discussed in case (i), for
j G J°, w J is already a Fourier-Motzkin multiplier which satisfies (a k , w-*) = for k — 1, . . . , M
and so they meet the specifications of the theorem. Now consider the w J for j G J + and
j G J~. Each pair of (j + ,j~) G J + x J - yields a final Fourier-Motzkin multiplier which is
a conic combination of w J and u^ . In order to simplify the analysis, normalize the w J so
that {a n ,w^) = 1 for j G J + and (a n ,w J } = — 1 for j G J~. Let a^ be the multipliers after
the corresponding scaling of ay for j G J + U J - . With this scaling, from Step 2.b.(iii) of the
Fourier-Motzkin procedure, the u J J = lip + w J for all (j + ,j~) G J + X J~ are among the
Fourier-Motzkin elimination multipliers for the full system. It suffices to show that there exists
multipliers Oj+j- such that
3GJ° j+£J+j-£J-
and
(a fc X' +r ) = (o fc ,iy J ' + +w J_ ) =0for k = 1,...,M. (2.17)
Condition |2~T7j) follows since (a k , w 3 ) = for k = 1, . . . , M - 1 and (a", w? + ) = -(a n ,w r ) = 1
for all j + G J + and j~ G J - .
To establish (J2.16J) consider a transportation linear program with supply nodes indexed by
J + and demand nodes indexed by J~ . Each supply node j G J + has supply ay. Each demand
node j G J - has demand — ay. Since
= (o",«) = (a™, X! "^ + E a J wJ ) = E «i<a n .^'> = E a J " E a ^'
jeJ° jeJ+uJ- jeJ+uJ- jgj+ j&J-
total supply is equal to total demand. Therefore the transportation problem has a feasible
solution Oj+j- which is the flow from supply node j + to demand node j~ . This feasible flow
12
satisfies
2 ®j + ,j- = a j+: for j + £ J +
E 9 3 + >j- = a i-i for J~ e J ~
and so
E E Vj-« 3+j " = E E e j+d -{^ + + w r)
j+eJ+j-eJ- j+£J+j-£J-
= E E 0,+j-v i+ + E E ^-^
j+eJ+j-eJ- j+eJ+j-e.J-
= y, otj+w 3 + 2, chj-w j .
i+eJ+ reJ-
Combining this with ([2"T5]) yields (I^TOl) .
Next, consider the base case n = 1. By hypothesis, this forces A/ = 1, i.e., (a 1 ,!!) — 0. If
the coefficient of xi is zero for all the constraints indexed by supp(u), then the Fourier-Motzkin
procedure initialization step gives multiplers w 3 — e° , j € supp(w). Thenu = J2jesupn(u)^(j) w ^ ■
Otherwise, if variable x\ has nonzero coefficients in the system indexed by supp(w), it follows
that variable x\ has both positive and coefficients in this system, since u is nonegative and
(a 1 ,!!). Define the usual multiplier vector for each pair of positive and negative coefficients.
Again, assume without the loss, the rows are scaled such that the positive coefficients are 1
and the negative coefficients -1. Create a transportation problem as above where each node has
supply of Tij if j corresponds to a row with +1, or demand —Tij corresponds to a row with a -1.
Solving this transportation problem, and using the same logic as before, gives the coefficients
9j+j-i to be used on the multiplier vectors u 3 ,J in order to generate u. This completes the
proof. □
3 Solvability and duality theory using projection
3.1 The projected system
The semi-infinite linear program
inf^eR^ c T x
s.t. a l {i)xi + a 2 (i)x2 + ■ ■ ■ + a n (i)x n > b(i) for i G /
(SILP)
is the primal problem. Reformulate (|SILP|) as
inf z (3.1)
s.t. — c\X\ — C2X2 — ■ ■ ■ — c n x n + z > (3-2)
a l {i)xi +a 2 (i)x 2 H ha n (i)x„ > b(i) for i e I. (3.3)
Let A C K™ +1 denote the set of (x\ 1 . . . , x n , z) that satisfy (|3.2l) - (|3.3p . Consider z as the (n + l)st
variable and constraint (|3.2p as the 0th constraint in the system.
Remark 3.1. This formulation allows for v (jSILPI) = +00 or v (|SILP[) = — 00. The former arises
when the feasible region is empty. The latter signifies that the primal is unbounded. <
13
Applying Fourier-Motzkin elimination procedure to the input system (|3.2[) - (|3.3|) gives the
output system (|2.6p . rewritten as
> b(h), heh
h l {h)x e + a e+1 (h)x e+1 + --- + a n (h)x n > b{h), heh r ~ 4 ,
z > 1(h), heh ' '
a e (h)x( + a l+1 (h)xi + i + ■ ■ ■ + a n (h)x n + z > b(h), heh
where h, h, h and h are disjoint with I = hU ■ ■ ■ U h. Note that z can never be eliminated,
so system (|3.4[) is always dirty and I3U/4 ^ 0. This formatting also assumes that every time a
constraint involving z was aggregated, a multiplier of 1 is used. This can always be achieved by
Remark 12.11 It is possible that all other variables can be eliminated when h = h = (that is,
I = n + 1). By construction, | J2l=e a k ( h )\ > ° for all heh^h-
By Theorem l2.9( system (|3.4|l describes the projection P(A; X\, ■ ■ ■ , xi-i) (recall the assump-
tion that the system of inequalities (|3.2|) - (|3.3I) is in canonical form). Therefore, to solve (|SILP|)
it suffices to consider the optimization problem
miz,xe,...,x n z , .
s.t. daai. { '
A further step (Lemma l3.7p is to examine the geometric projection of A onto the z-variable space
in terms of the data from the output system (|3.4|) . It is easier to characterize the boundedness
and solvability of (|SILP|) in this one-dimensional space.
3.2 Primal results
3.2.1 Primal feasibility
Feasibility of (jSILPI) is determined by looking at the constraints indexed by ii, h,h and h.
Theorem 3.2 (Primal Feasibility). (|SILP|) is feasible if and only if
(i) b(h) < for all heh, (hi) sup b(h) < 00,
heh
(ll) SUp ^^j i-fc/.M < °°' ( 1V ) SU P ^n i~fc/ M i , t < °°-
heh \,h=l \ a W\ heh \,h=l \ a Wl + 1
Proof. The result follows directly from applying Theorem 12.131 to the dirty system (|3.4I) with
H x = h and H 2 = h U h U h- □
Remark 3.3. Some readers may hnd it counter-intuitive that primal feasibility involves consid-
eration of constraints involving z (those indexed by h and -Z4), a variable that does not appear
in the initial description (|3.3() of the feasible region. However, this is indeed the case since
during Fourier-Motzkin elimination the constraints involving only x\, . . . ,x n can be mixed with
constraints involving z in such a way that careful consideration of all four types of constraints
(those indexed by h through h) is necessary. Example 13.41 below demonstrates this.
Alternatively, one could apply Fourier-Motzkin elimination to (j2.ll) and obtain (|2.8p - (|2.9l) .
By Theorem l2.13l the conditions for feasibility are
(i) b(h) < for all h e H u
(ii) su PheJfa 6(/0/£L<|fi*(>0l<<x>-
The key point is that the inequalities indexed by Hi and H2 in (|2.8[) - (|2.9p are not identical to
the inequalities indexed by h and h in (|3.4[) .
14
Example 3.4. Consider the following instance of (ISILP[)
inf xi
X2 > i fori = 1,2,... (3.6)
xi > (3.7)
-xi + x 3 > (3.8)
xi -x 3 > -1. (3.9)
The two sets of interest are: r = {iel 3 : flU) - (|3T9|)} and A = {(x, z) e T : -x 2 + z > 0} .
Applying Fourier-Motzkin elimination to the inequalities describing T gives
> -1
X2 _ i for i = 1, 2, . . .
£3 > 0.
and £2 is a dirty variable. Applying Fourier-Motzkin elimination to the inequalities describing
A gives
> -1
X 3 >
z > i for i = 1,2,...
and X2 is now a clean variable. Note that \H.2\ — oo but I-Z2I = 1- <
Corollarv l3 .51 below states some consequences of primal feasibility for (SILP) which are useful
later. The proof is analogous to the proof of Theorem 12. 131 First introduce the function
oj(S) := sup {1(h)- 5^2 \a k (h)\} (3.10)
heh k=t
that is used throughout the paper. Note uj can take values in the extended reals. If I4 = then
uj(5) = —00, and u>(5) can diverge to +00. Observe a; is a nonincreasing function of <5 since
ElUI« fc (MI>o.
Corollary 3.5. If (jSILPj) is feasible then
n x ~ b (h)
(l) 62 ■= SUp =5 fc < OO,
heh luk=i\ a W\
(ii) S3 :— sup b(h) < 00,
heh
(iii) lim u(S) < 00,
(iv) (x(5;£),z) s P(A;xi, . . . , a^-i) for all J, z S M such that <5 > max {0,^2} and z >
max{<53,o;(i5)}. Moreover, by conditions i), ii) and iii) above, at least one such pair (5,z)
of real number exists.
Proof. Conditions i)— ii) follow immediately from Theorem 13.21 Condition iii) follows from the
claim below and condition iv) of Theorem 13.21
Claim 3.6. sup =^j — ,,,.,,,, ; : < 00 ^=> lim u(6) < CO.
hehT, k= e\a k (h)\ + l a-
-?Cv.
15
Proof of Claim\KE (==►) Let 6 = sup /lG/4 b(h)/(J2k=e l a *COI + 1) < 00. This implies 6 >
b(h)/(J2l=i\a k (h)\ + 1) for every h G J 4 . Rearranging, ^(Efc=^ I 6 * CO I + x ) > &C0> which
implies 5 > 6(/i) - 8{Y2=i |5*C0I) for all h G J 4 . Thus, 5 > sup{6(ft) - 8{Y2=i |5*C0I) :
/i G 14} = w(£). Thus, 00 > J > u>(8) and since w(<5) is a nonincreasing function, this yields
limbec u(S) < 00.
(<=) Since lim^oo u>{6) < 00 and u>{6) is a nonincreasing function, there exists 8 < 00 such
that i5 > u>{6). The reasoning is as follows: lim^oo u>(8) < 00 implies there exists a 8 such
that w(<5) = c < 00. Take (5 > max{<5, c}. Since w(<5) is nonincreasing in 8, u>(6) < lj(8) =
c < 8. Now, because 6 > oj(S) it follows 5 > sup{b(h) — <5(Efc=£ \a k (h)\) : h G h}. Hence,
8 > b(h) - 5{YTk = i \a k {h)\) for all h G h- Rearranging, 6 > b(h)/{Y2=i \a k {h)\ + 1) for every
h G h and so 00 > 8 > sup he/4 b{h)/{J2k=i I^COI + X )- D
Prove condition iv) in the statement of the corollary by verifying that the constraints indexed
by Ii,l2,h and I4 are satisfied by (x(S;£),z) G P(A;xi, . . . ,X£-i) when 8 > maxjO,^} and
z > ms,x{53,Lj(S)}. Since 62,63 and lims^<x>uj(8) are all finite, and ui(S) is a nonincreasing
function, there exists at least one such pair (8, z) of real numbers.
Since (|SILP[) is feasible, the constraints in I\ are satisfied by condition i) in Theorem 13.21
By definition, 8 2 > b{h)/'}^k = i> |ofcCOI for all h G h, which implies SJ^^e l^fcCOl > b(h) for all
h G I-i- Since J2k=£^k(h)xk(8;£) = 8J2k=£ l^fcCOl by construction of x(S;£), (x(S;£),z) satisfies
the constraints indexed by I<z in (I3.4[) .
Since z > 63, all the constraints indexed by I3 are satisfied. Finally, since z > w(<5),
2 > sup heIi {b(h) - ^El-=f |a fc (/i)|} and so for all h G I4, 2 + Efc=£ a k (h)xk(8;£) = z +
(5Efc=^ l a CO I ^ i(/i)- Conclude (#(5; ^), z)) satisfies the constraints indexed by I4, and therefore
feasible to (pT3|) . Thus, (x(<5; f), z)) G P(A; a*, . . . , xi) by TheoremEU D
3.2.2 Primal boundedness
To establish boundedness and solvability, we start by giving a characterization of the closure of
the projection of the feasible region described by (|3.4[) onto the z- variable space.
Lemma 3.7. Assume (jSILPj) is feasible and applying Fourier-Motzkin elimination to (|3.2|l - (|3.3|l
gives p.4|) . Let P(A; x\, . . . , x n ) denote the projection of A into the z-variable space. Then, the
closure of P(A; a?i, . . . , x n ) is given by the system of inequalities
z > sup b(h) (3.11)
z > lim u(S). (3.12)
5
^^
Proof. Since (jSILPj) is feasible, conditions ii) and iii) in Corollary 13.51 imply that sup^ e j b(h) <
00 and lim^oo lo(S) < 00. Let 82 and 83 be as defined in i)— ii) of Corollarv l3.5l
First, suppose z satisfies (|3.11l) - (|3.12l) and show z G cl(P(A; x\, . . . ,x n )). Consider the
following two exhaustive cases.
Case 1: z > lim^oo u>(8). Since u(8) is nonincreasing in 8, there exists 8 G M. such that z > lo{8).
Choose 8 > max{0, 5, 82}- By (|3.1ip . z > sup^ G/3 b(h) = 83. Also, z > uj(S) > u(6) since uj(S)
is nonincreasing. Thus, (x(8;£),z) satisfies the hypotheses of condition iv) of Corollary 13.51
Therefore (x(5; £), z) G P(A; Xi, . . . , xi—i) and this implies z G P(A; x\, ■ . ■ , x n ).
Case 2: z = lim < 5_>. 00 u>(8). Since uj(8) nonincreasing in (5, there exists a sequence of real numbers
(^m)mGN such that for every m G N, 8 m > max{0, ^2} and z m := w{8 m ) — > z. Since U)(S) is
nonincreasing and z satisfies (|3.11|) . z m — uj(8 m ) > lim^^oo U)(S) = z > swp hGl b(h). Hence
z m > max{<53, uj{8 m )} and by Corollary I3.5f iv). (x(5 m ;£),z m ) G P(A; X\, . . . , xt-i). Therefore
Z m G P(A; Xi, . . . , x n ) and z m — > z. This implies z G cl(P(A; Xi, . . . , x n )).
16
Conversely, let z € cl(P(A;xi, . . . , x n )) and show z satisfies (|3.11[) and p. 121) . Since z £
cl(P(A; x±, . . . , x n )) there exists a sequence z m £ P(A; £1, . . . , x n ) where z m — > z. Since z m £
P(A; xi,..., X n ) there exists an x m — (x™, . . . , X™) such that (x m 7 z m ) satisfies the constraints
of system (|3.4j) . This implies z m > swp hel3 b(h). Since z m — > z, conclude z > sup^ G/ b{h).
Also, since (x m ,z m ) satisfies (|3.4p . z m > sup AeJ4 {6(/i) — S&=^ a ' £ (' l ) x ™}- Letting 8 m =
max k =t,...,n \xf\ gives z r _ n > sup heU {b(h)-Y%=ia k (h)x%} > sup heU {b(h)-S m J2k=e 1^0)1} =
w(<5 m ). Thus, z m > uj(S m ) > lim^^oo lo(5) for all m, where the last inequality holds since U)(5)
is nonincreasing. Since z m — >■ z, conclude z > lim,5_j. 00 u>{6). Hence z is a feasible solution to
system (|3~TTj) - (|3~T2l) . D
By Lemma [X71 if (jSILPI) is feasible, then its optimal value is found by solving the optimiza-
tion problem
s.t! dS3U - (EU. (3 - 13)
This follows because the optimal value of a continuous objective function over a convex feasible
region is the same the optimal value of that objective when optimized over the closure of the
region. The next two results follow directly from this observation.
Lemma 3.8. If (jSILPp is feasible then p (|SILPp = max{ sup^ e/3 ^(/i^lim^oo ui(S)}.
Theorem 3.9 (Primal boundedness). A feasible (|SILP[) is bounded if and only if Ij, ^ or
lim^oo ui(5) > -oo.
Proof. By contrapositive in both directions. By Lemma 13.81 ?; (|SILP[) = — oo if and only if
max{sup^ e/3 6(/i),lim,5_j. 00 oj(S)} — — oo if and only if sup^g^ b(h) = — oo and lim^oo ui(5) =
— oo. Note that sup^g^ b(h) = — oo if and only if I3 = 0. D
3.2.3 Primal solvability
An instance of (|SILP[) is solvable if the infimum value of its objective is attained. Note that
an optimal solution « (|SILP[) may exist to (|3.13[) even though an optimal solution to (|SILP[)
does not exist (see for instance Example 13.111 below) . This is due to the fact that (|3.13|) is an
optimization problem over the closure of the projection P(A; Xi, . . . , x n ), and hence an optimal
solution to p.5[) may exist in the closure but not the projection itself. Thus, the solution may
not "lift" to an optimal solution of (jSILPI) . A sufficient condition for when this "lifting" can
occur is given in Theorem 13. 101
Theorem 3.10 (Primal solvability). If (|SILP|) is feasible and sup^ G/ b(h) > lim^oo w(<5), then
(ISILPj) has an optimal solution with value v (|SILP|I = sup he/3 b(h).
Proof. Let z* = ^ (|SILP|) . Since (|SILP|) is feasible, by part (ii) of Corollary |33] it follows that
00 > sup he/a b{h) > lim^oo ui(5). Moreover, by Lemma [3. 8[ z* = sup he/3 b(h). Let 82 be as
defined in Corollary 13.51 Since uj(S) is a nonincreasing function, there exists 5* > maxjO,^}
such that u>(6*) < sup h&1 b(h) = z* . Then, (x(S*;£), z*) satisfies the hypotheses of condition
iv) in Corollary 13.51 and so (x(S*;£), z*) £ P(A; xi , . . . , x n ), showing that there exists a feasible
point (xi, . . .,x n ,z) in A where z = z* . Thus there is a feasible point for (|SILP[) with value
z* =t; (fSlTPl . □
In light of the previous result, an immediate question is whether primal solvability holds when
lim^oo u}(5) = sup^gr b(h). The following two examples demonstrate that such problems can
be either solvable or not solvable.
17
Example 3.11. Consider the following instance of (|SILP[)
inf x\
xi + ^x 2 > ji + \ for t > 1 (3.14)
xi > 0.
Applying Fourier-Motzkin elimination to
-xi + z >
xi + yiX 2 > F + 7 for i > 1 (3.15)
Xi
yields (by eliminating Xx)
'2
> 7^ + 7
> o
Z
Z
>
>
1 -1- 1
F + 7
0.
^■0:2 + z > 4 + t for i > 1
(3.16)
The only -Z3 constraint is z > so sup/j G/3 b(h) = 0. Show that for S > 3/2,
w (5 ) = SU p{^ + I-^}=sup{^ + i} = 2 ^ iy .
4>1 t>l >- J v ;
When <5 > 1 and t ^ 0, the function ^ ^ ' + | is concave and quadratic in j. The supremum
is achieved by t* = —2(1 — 5). When S > 3/2, t* > 1 and substituting the optimal value of t*
into ( ~ 2 - + j gives jr^zj)- Clearly, lim^oo uj(S) = = sup /ie/3 b(h) and so by Lemma [3781 the
optimal value is 0.
However, for z = the system p,16[) has no possible feasible assignment for x%. Indeed,
for any proposed x 2 take t > x 2 . This implies -mX 2 + 0<\<j2+j, which means (x 2 ,0) is
infeasible to (|3.16[) and the primal is not solvable. <
Example 3.12. Consider the following instance of (|SILP|)
inf x\
x\ >
-x 2 > -1
x\ — jx 2 > for i = 3, 4, . . .
Applying Fourier-Motzkin elimination to
-xx +z >
xx >
-x 2 > -1
x\ — \x 2 > for i = 3, 4, . . .
yields (after projecting out x\)
-x 2 > -1
z >
--x 2 + >z > fori = 3,4,...
Observe 7 3 = {1} and sup /lG/3 b(h) = 0. Note
uj(6) = sup {b(h)- 5 ^ \a k {h)\ : he/ 4 }
= sixp{0-6/h : /i = 3,4,...} = 0.
Thus, lim^^oo w(#) = = sup,^/ 6(/i). By Lemma I3~51 this implies v (|SILPI) = and this value
is obtained for the feasible solution xx = x 2 = and the primal is solvable. <
18
3.3 Dual results
The next step is to develop a duality theory for (ISILP|) using Fourier-Motzkin elimination. The
standard dual problem in the semi- infinite linear programming literature (see for instance [2|)
is the finite support (Haar) dual introduced in Section Q] and reproduced here for convenience.
su p EiGi^M*)
s.t. £ lS / afc (*M*) =c fc for ft = l,...,n (FDSILP)
v e R ( + }
In this section, we characterize when (IFDSILPI) is feasible, bounded, and solvable. Later
in Section 13.3.41 we characterize when there is zero duality gap between (jSILPI) and (jFDSILPI) ;
that is, « (ISILPl) = v (IFDSILPI) .
As in the case of the primal, allow ^ (jFDSILPp to take on values in the extended reals.
(|FDSILP|) is unbounded when JFDSILPp = oo. When v (jFDSILPI) = -co, the problem is
infeasible.
In the remainder of this section, assume Fourier-Motzkin elimination has been applied to
(|3.2[) - (|3.3p yielding Q3.4p . Our attention turns to the multipliers generated in Step 2.b.(iii) of
the Fourier-Motzkin elimination procedure. These multipliers generate solutions to (jFDSILPp .
First a small, but important, distinction. The multipliers u h generating (J3.4I) are real-valued
functions defined on the set {0} U I where the inequality (|3.2p has index 0. However, solutions
to (IFDSILPp are real- valued functions defined only on /. Thus, it is useful to work with the
restriction v h : I — > M. of u h to /. That is, v h (i) — u h (i) for i E I. Conversely, given a function
v : I — > M. and a real number vq, let u — {vq,v) denote the extension of v onto the index set
{0} U I where u(0) = vq and u(i) = v(i) for all i € I. Lemma T3. 131 gives basic properties of v h
that are used later.
Lemma 3.13. If Fourier-Motzkin elimination is applied to (|3.2)) - (j3.3[) yielding (|3.4p . then
(i) for every h E h U h U I 3 U h, b(h) = (b, v h ).
(ii) for h £ I\, u h (0) = and v h is a recession direction for the feasible region of (jFDSILPp .
(iii) for h e I 2 , u h (Q) = and v h satisfies J^iei a k (i)v h (i) = for k = 1,...,£- 1, and
J2 igI a k (i)v h (i) = a k (h) for k = £, . . . , n.
(iv) for h S I3, u h (Q) = 1 and v h is a feasible solution to (IFDSILPp . and
(v) for h e I4, u h (0) = 1 and v h satisfies Ejei ak {i) vh (i) — Ck = fox k = 1, ...,£— 1, and
Eigj a k {i)v h {i) - c fe = h k {h) for k = £ , . . . , n.
Proof. We establish parts Q, (jil]) and ([Iv]) only. The other parts are seen analogously.
(Q) By TheoremUS for all h: b{h) = ((0,b),u h ) = (b,v h ).
(pi]) The constraints indexed by I\ do not involve z and so the multipliers u h for h € I\ must
have u h (0) = 0. By Theorem ESfii) , for Ii e I b = ((-c fc , a' ),?/' 1 ) = (a' £ ,'y' 1 ) for all
fc = l,...,n. This implies w' 1 satisfies ^2 ie j a k (i)v h (i) = 0. In addition, u h > implies
v h > and w^ is a recession direction for the feasible region of (jFDSILPp .
(pv|) The constraints indexed by -Z3 must involve z and so the multipliers u h for h £ I3 must have
m' i (0) > 0. Assume u h (0) — 1, which is without loss by Remark [2~T1 By Theorem 12. 9f ii).
for h € h, = ((-c k ,a k ),u h ) = -c k + (a k ,v h ) for all fc = l,...,n. This implies v h
satisfies the equality constraints of (jFDSILPp . In addition, u h > implies v h > and v h
is a feasible solution to (jFDSILPp . D
19
3.3.1 Dual feasibility
The next two subsections relate dual feasibility and boundedness to properties of the projected
system (|3.4|) . Theorem 12 . 1 71 and Lemma T3. 131 plav pivotal roles in the proofs.
Theorem 3.14 (Dual Feasibility). (jFDSILPjl is feasible if and only if 7 3 ^ 0.
Proof. (=>) If (|FDSILP|) is feasible, there is a TJ > with hnite support such that J2 ieI ak {i)v% —
Ck,k — 1, . . . , n and this implies ((— Ck, a k ), (1, v)) = 0, k = 1, . . . , n. Then, by applying The-
orem [2TT7] to p.2p ~ p.3l) with M = n, there exists an index set /c (I 1 U 1%) and multipliers
11
h
{0} U I ->■ R for h G I such that
(1,S) = ^TAftV 1
/is/
= 2 X h u h + y, x ^ h
heinh hemi 3
heinh heinii
where Ah > for all h G I and v h is the restriction of u h onto I. The third equality follows
from Lemma [3.131pl|) and ([Iv])- Now, the 1 in the first component of (l,v) implies that In I3
cannot be empty, and hence -Z3 cannot be empty.
(<=) Take any u h with h G I3. By Lemma [3~T3lfiv]) , w' 1 is a feasible solution to (|FDSILP|) . D
3.3.2 Dual boundedness
To characterize dual boundedess, first establish weak duality.
Lemma 3.15 (Weak Duality). Suppose b(h) < for all h G I\. If v is a feasible dual solution
to problem (|FDSILP|) then
(i) there exists an h G ^3 such that b(h) > (b,v),
(ii) (b,v) is a lower bound on the optimal solution value of (|SILP[) .
Proof. Applying Theorem 12 . 1 71 as in the proof of Theorem 13. 141 implies there exists an index set
I C Ii U I3 such that
(1,15) = ]T A /l (0, U /l )+ ]T A A (1,A
heinii heini 3
Reasoning about the components of (1, v) separately gives,
v= Y X *v h + J2 X h v h (3.17)
heinii h£ini 3
and 1 = J2heTni Xfl - L emma I3-I3f i) and the hypothesis b(h) < for all h G I\ imply {b, v h ) <
for all heh. Thus, (|3"T7|) gives (b,v) < J2heim 3 x h{b,v h ) < (b,v h ) = b(h) for some h G Inh,
where the second inequality follows because the Aft, for h G I3 are nonnegative and sum to 1.
This implies i). Now ii) follows immediately from Lemma 13.81 □
Theorem 3.16 (Dual boundedness). Suppose (jFDSILPp is feasible. Then (jFDSILPI) is bounded
if and only if
(i) b(h) < for all h € h and
20
(ii) sup /ie/3 b(h) < oo.
Proof. (<=) By contrapositive. Suppose (|FDSILP|) is unbounded and show that if condition i)
holds, then ii) does not hold. Assume b(h) < for all h € I\. Since (jFDSILPj) is unbounded, for
every M € N there exists a feasible Vm with (b, Vm) > -W- By Lemma \3. 151 there exists some
h M e I3 such that 6(/im) > (Mm) > Af. Thus, sup/, e7a 6(ft) > 6(/im) > M for all MeN and
this implies sup he/3 6(/i) = 00. Therefore, (ii) does not hold.
(=>) By contrapositive. Assume condition i) does not hold. Thus, there exists h* 6 I\
such that b(h*) > and by Lemma f3.13f ii). (a k ,v h ) = for all k = 1, . . . ,n. Now, consider
any v feasible to (|FDSILP|) . which exists since (|FDSILP[) is feasible. Then, v + Xv h is also
feasible for all A > 0. Now, the objective value for these feasible solutions equal (b, v + \v h } =
(b, v) + \(b,v h ). Since (b,v h ) = b{h*) > 0, letting A — > 00, yields unbounded values for the
objective value of (jFDSILPp .
Next assume condition ii) does not hold. This implies there is a sequence of {/i m }meN in ^3
such that, by Lemma l3.13f ih (b, v hm ) — b(h m ) — > 00. By Lemma 15. 13f iii). each v hm is a feasible
solution to (|FDSILPj) and thus (|FDSILP|) is unbounded. □
Remark 3.17. Observe that there are two distinct ways for a feasible (|FDSILP[) to be un-
bounded. The hrst is when there there is a recession direction to the feasible region that drives
the objective value to +00. From Lemma 13. 13tfTT|) every h S I\ yields a recession direction v .
In addition, if b(h) > then (b, v h ) > and so moving within the feasible region along recession
direction v drives the objective to +00. This argument was given in full detail in the proof of
Theorem 13.161
Contrary to our intuition from finite dimensions, the second way (|FDSILP[) may have an
unbounded objective value can occur when the feasible region itself is bounded. This happens
when there are no recession directions and sup^ G j b(h) — 00. This occurs when ([FDSILPp has
a sequence of feasible solutions whose values converge to +00. Consider the following example
inf x\
s.t. X\ > i for ieN
with finite support dual
sup y iv(i)
s.t. 5^w(t) = 1
v(i) > for i € N
The feasible region of the finite support dual is bounded (note that < v(i) < 1 for all i)
and there is no recession direction. However, the problem is still unbounded. Consider the
sequence of feasible extreme point solutions e m . Clearly, sup^^^^ 5Z ieN ie m (i) = m — > oo.
Thus (jFDSILPp is unbounded.
Fourier- Motzkin elimination can identify which of the conditions of Theorem l3.16l are violated
and result in an unbounded problem. Applying Fourier-Motzkin elimination to the system
-xi+z >
x\ > i for i = 1, 2
1 ^1 ■
yields (after eliminating X\)
z > i for i = 1, 2, . . . .
Thus, I\ = so there are no recession directions, but I 3 — {1, 2, . . . } and sup he/ b(h) = 00. <
21
3.3.3 Dual solvability
To characterize dual solvability, begin with a characterization of the optimal dual value.
Theorem 3.18. If b(h) < for all h e h then « (IFDSILP|1 = sup, lG/3 ~b(h).
Proof. By Lemma r3.15l ii). for every dual feasible solution v there exists an ft e ^ with b(h) >
(b,v). Hence, snp he j 3 b{h) > (b,v) for all feasible v. This implies sup hel3 b(h) > u (|FDSILPp .
Conversely, by Lemma r3.13l iii). every h G I3 yields a v h with v h feasible to (|FDSILPp and b(h) =
(b,v h ). Hence b(h) = (b,v h ) < JFDSILPp for all h e I 3 . Thus, sup fte/3 b(h) < f flFDSILPp and
the result follows. □
Corollary 3.19. If either (|5lLPl) is feasible or (jFDSILPI) is feasible and bounded, then JFDSILPp
su Pfte/ 3 ~ b ( h )-
Proof. If (tSlLP|) is feasible, then by Theorem Ej^ii) b(h) < for all h E h. The result follows
from Theorem [3Tl If (jFDSILPp is feasible and bounded then by Theorem E^i) b(h) < for
all h £ I\. Once again, the result follows from Theorem 13. 181 □
Theorem 3.20 (Dual solvability). (|FDSILPp has an optimal solution if and only if
(i) b(h) < for all h € h, and
(ii) sup /ie/j b(h) is realized for at least one h £ I3.
Proof. (=*>) Let v* be an optimal solution to (jFDSILPI) with optimal value t> (|FDSiLPj) =
(6, v*). This implies (jFDSILPp is both feasible and bounded. By TheoremEjili) , b{h) < for all
h e Ii, establishing condition (i). Apply Lemma f3.15lT i) and conclude there exists a v h for some
h* e h with {b, v h *) > (b ,v*) = i; (|FDSILPj) . By Lem ma EHi v| , v h " is feasible to (jFDSILPp
and (b,v h ") < JFDSILPI) . Hence b(h*) = (b,v h ') = JFDSILPI) = sup he/a b(h), where the hrst
equality holds from Lemma [3.13lj i|) , the second equality holds from the arguments in the previous
two sentences, and the third equality holds from Corollary 13.191 Thus, b(h*) = sup^ e/3 b(h),
establishing condition (ii).
(<=) By hypothesis there is an h* E I3 such that sup^ e/3 b(h) = b(h*) < 00. The fact that I3 is
nonempty implies (|FDSILP|) is feasible by Theorem [Ol Thus, by Theorem [3~TC1 (jFDSILPp is
bounded. Since (jFDSILPp is feasible and bounded, by Corollarv l3"T9l sup,, c h b(h) = t; (|FDSILPp .
Moreover, Lemma f3 . 1 3 K |T|) and ([rv]) imply that b(h*) = (b,v h ) and v h is a feasible solution to
(jFDSILPp . Putting this together, t> (|FDSILPp = sup heh b{h) = b(h*) = (b,v h ") and v h * is an
optimal solution to (jFDSILPp . D
3.3.4 Zero duality gap and strong duality
The primal-dual pair (|SILP[) and (jFDSILPI) has a zero duality gap if (jSILPp is feasible and
^ (ISlLTj) = JFDSILP I).
Theorem 3.21 (Zero Duality Gap). There is a zero duality gap for the primal-dual pair (|SILPp
and (IFDSILPp if and only if
(i) (ISILPl) is feasible,
(ii) sup he/3 b(h) > liras^ao uj(S).
Proof. (=$■) Assume zero duality gap. Condition (i) holds by definition of zero duality gap.
Since (ISlLPl) is feasible, by Corollary EH
sup b(h) = JFDSILPP = « (JSILPJ) = maxjsup b(h), lim w(S)} > lim w{5),
heh hei 3 5 ^°° 5 ^°°
22
where the third equality holds by Lemma I3~51 Thus condition ii) holds.
(<=) Now assume conditions (i) and (ii) hold. By i) (|SILP[) is feasible. By Lemma [37
v (|SILP[) = max{sup fte j 6(/s), limj^oo w(5)} = sup heI b(h), where the second equality follows
from condition ii). Also, Corollary [37X91 implies « (|FDSILPp = sup heh b(h). Thus, i> ([SILPp =
t; (|FDSILP|) and there is a zero duality gap. D
Combining solvability and duality, strong duality holds if there is a zero duality gap and
there is an optimal solution to (jSILPp and ([FDSILPp . Putting several previous results together
gives Theorem l3.22l
Theorem 3.22 (Strong Duality). Strong duality holds for the primal-dual pair (|SILP[) and
(IFDSILPI) if
(i) pLPl) is feasible,
(ii) s\ip heh b(h) >liui S ^ oc uj(S) ,
(iii) sup hGl3 b{h) is realized for at least one h € I3.
Conversely, if strong duality holds for the primal-dual pair (|SILP[) and (jFDSILPp then (i) and
(iii) hold as well as
(ii') sup^ e/3 b(h) > Um 5 _j. 0O w((5).
Proof. Suppose conditions (i) to (iii) hold. Conditions (i) and (ii) imply primal solvability via
Theorem 03 Since (jSILPJ) is feasible, by Theorem O^i) , b(h) < for all h € I x . Combined
with condition (iii) dual solvability follows from Theorem 13.201 Conditions (i) and (ii) imply
the sufficient conditions for zero duality gap given in Theorem 13.211 and the duality gap is zero.
Conversely, suppose strong duality holds. Then there is a zero duality gap and so Theo-
rem [2211 (i) and (ii') hold. Theorem I3.20f ii) implies condition (iii). □
In the example below strong duality holds but condition ii) in Theorem 13.221 is not satisfied.
Example 3.23 (Example 13. 121 revisited). In this example the primal is solvable with objective
value u (|SILPp = 0. Recall also that sup he/3 b(h) — is attained since ^3 is a singleton. This
implies it is dual solvable and there is zero duality gap. This problem satisfies strong duality.
However, swp hGl b(h) = lim^oo oj(S). Therefore condition (ii) in Theorem 13.221 is not satisfied,
but condition (ii') is satisfied. <i
3.4 Summary of primal and dual results
Table Q] summarizes the main results of this section. For brevity in displaying conditions, define
S := swp heIa b(h) and L := lim5_ > . 00 a;((5).
Result
Sets involved
Characterization
Primal feasibility (Thm[375|)
Primal boundedness (Thm[379|
Primal solvability* (Thm[3T0|)
Conditions i)-iv) of Theorem 13.21
Primal feas. and (-Z3 7^ OR L > —00)
Primal feasible and S > L
Dual feasibility (Thm[3T4[)
Dual boundedness (Thml3.16p
Dual solvability (Thml3.20p
h
Dual feas., 1(h) < for all h G I\, S < 00
b(h) < for all h € I\, sup defining S realized
Zero dualitv gap (Thm 13.211)
h,h
S > L and Primal feasible
Table 1: Summary of results from Section^ All results are characteriza-
tions except primal solvability, where a sufficient conditions is given.
23
The next two subsections illustrate insights that are gained by applying the results in Table [T]
to two special cases of (|SILP[) .
3.5 Tidy semi-infinite linear programs
An instance of (jSILPI) is tidy if, after applying Fourier- Motzkin elimination to (|3.2p - (13.3[) . z is
the only dirty variable remaining. Tidy semi-infinite linear programs play a fundamental role in
applications of our theory in later sections. The key properties of tidy systems are summarized
in the following theorem.
Theorem 3.24 (Tidy semi-infinite linear programs). If (|SILP[) is feasible and tidy then
(i) [(SlLTI) is solvable,
(ii) (jFDSILPj) is feasible and bounded,
(iii) there is a zero duality gap for the primal-dual pair (jSILPI) and (|FDSILP[) .
Proof. Since (jSILPj) is tidy, I 2 = h = 0- Since z cannot be eliminated, I4 = implies I3 7^ 0. In
addition, Zj = means u>(5) = — 00 for all 5 and \iuig^ 00 u;(S) = —00. Moreover, since I3 7^ it
follows that sup/jgj b(h) > —00. Then, sup he/3 b{h) > lim^oo w(<5) and Theorem 13.101 implies
the primal is solvable. This establishes (i).
Since I 3 ^, (|FDSILP|> is feasible by Theorem 13.141 Since the primal is feasible, Theo-
rem I3.2( i) and (ii) imply that the dual is bounded via Theorem 13.161 This establishes (ii) .
Since the primal is feasible and sup^ G/ b(h) > lim,5_j. 00 u(S), Theorem 13 . 2 1 1 implies that there
is a zero duality gap. This establishes (iii). □
The following result provides a sufficient condition for the tidiness of a semi-infinite linear
program.
Theorem 3.25 (Bounded System). If there exists a 7 £ R such that the system
-C1X1 - c 2 x 2 c„x„ > -7 , .
a 1 (i)x 1 + a 2 (i)x 2 -\ \-a n (i)x n > b(i) for i £ I \ ■ )
is feasible and bounded then (|SILP[) is feasible and tidy. In particular, if the set of solutions
(xi, . . . , x n ) that satisfy (|3.18[) is feasible and bounded for some 7 £ R, then (|SILP[) is solvable
and there is zero duality gap.
Proof. Let T 7 denote the set of those x £ R™ that satisfy (|3.18[) . Observe that the columns
in systems (|3. 18|) and (|3.2|) - (j3.3|l are identical for variables xi,...,x„. This means if x^ is
eliminated when Fourier-Motzkin elimination is applied to one system, it will be eliminated in
exactly the same order in the other. In particular, at each step of the elimination process, the sets
T-io(k), T-L+(k) and 7-1- (k) are identical for the two systems. By hypothesis, T 7 is non-empty and
bounded so Theorem l2 . 1 51 guarantees that applying Fourier-Motzkin elimination to (13.18)) results
in a clean system. Thus, variables xi, . . . , x n are eliminated during the procedure and so those
variables are eliminated when applying Fourier-Motzkin elimination to (|2.8l) - (|2.9p . Thus, (ISILP|)
is tidy. Since T 7 is non-empty, (|SILP[) is feasible and tidy and the hypotheses of Theorem 13.241
are met. Then by Theorem 13.241 (|SILP[) is solvable and there is a zero duality gap for the
primal-dual pair (ISlLP] and (jFDSILPj) . □
24
3.6 Finite linear programs
Another special case is a semi-infinite linear program with finitely many constraints, i.e. a finite
linear program, or just a linear program. Finite linear programs are a special case of (jSILPj)
and our analysis applies directly.
For finite linear programs, ii, I2, I3 and I4 are always finite sets. This simplifies the charac-
terizations in Table [1] since the supremums arc taken over finite sets. Take, for example, primal
feasibility (Theorem I3.2[) . Conditions ii)-iv) always hold from the finiteness of I-x , I3 and I4
respectively. Thus to determine primal feasibility it suffices to check if b(h) < for all h € I\.
This result is well known (see for instance, Motzkin |ll|).
As another example, strong duality holds for a finite linear program when the primal is
feasible and bounded. Our framework recovers this result.
Theorem 3.26 (Finite Case). If / is a finite index set and (|SILP[) is feasible and bounded,
then strong duality holds for the primal-dual pair (|SILP[) and (jFDSILPp .
Proof. Show that conditions (i)-(iii) of Theorem l3.22l hold. By hypothesis (|SILP|) is feasible and
bounded so i) holds. When / is a finite set, I4 has finite cardinality so lim^oo ui(6) = — 00.
Combining this with the hypothesis that the primal is bounded implies ^3 7^ by Theorem 13.91
Thus condition (ii) in Theorem 13.221 holds. Finally, (iii) holds since I3 is finite whenever / is
finite. □
Beyond this, the analysis of this section reveals important differences between a finite linear
programs and a semi-infinite linear program. Consider the following well-known facts about
finite linear programs:
(i) if the primal is infeasible then the dual must be either infeasible or unbounded, and
(ii) if the primal has a finite optimal objective value, then the dual must be feasible and
bounded with the same objective value (that is, strong duality always holds).
The following two examples demonstrate that (i) and (ii) need not hold for general semi-
infinite linear programs.
Example 3.27. Consider the following problem
inf x\
-%2 > 1 for i = 1,2, ...
1
xi > 0.
This problem is infeasible since for any X2, there exists sufficiently large i such that ix2 < 1.
Add the constraint — x\ + z > 0, apply Fourier-Motzkin elimination and project out the
clean variable X\ to get the following system.
-X2 > 1 for i = 1,2, ...
1
z > 0,
In this system I\ = I4 = and -Z3 is a singleton. This implies that sup fte/ b(h) is achieved and
the dual is solvable. <
Example 3.28 (Example 13.111 revisited). In Example 13.111 the primal problem has a finite
optimal value of 0. This optimal value remains greater than or equal to zero even without
the non-negativity constraint on x\ in (|3. 14|) . This is because uj(S) still equals 4 /g 1 _ 1 i and
lim ( 5_>. 0O uj(5) = 0. Then by Lemma 13. 8[ the optimal primal value is greater than or equal to
25
zero. However, the finite support dual of this semi-infinite linear program is infeasible. The
objective coefficient of x-i in the primal is and the coefficient of xi is strictly positive in the
constraints. This implies that the only possible dual element satisfying the dual constraint
corresponding to %% is u = 0; however, the objective coefficient of x\ is 1 and this dual vector
does not satisfy the dual constraint corresponding to x\. Alternatively, the infeasibility of the
dual follows from Theorem 13.141 because in this case I3 = f/j. <
4 Feasible sequences and regular duality of semi-infinite
linear programs
When ^3 is empty in Q3.4p . there is no a feasible solution to (jFDSILPI) as shown in Theorem l3.14t
Nevertheless, if the primal problem has optimal solution value z* , we show there is a sequence
{h m } £ I4 for m E N with the desirable property that for all k = 1, . . . ,n, a k (h m ) converges
to zero and b{h m ) converges to z* as m — » 00. In Theorem 14.31 it is shown that there is a
sequence of finite support elements with nice limiting properties, and whose objective values
converges to the primal optimal value. The terminology for this phenomenon, standard in conic
programming, is introduced next. The concepts date back to Duffin [4|.
A sequence v m E R^, m EN of finite support elements is a, feasible sequence for (|FDSILP[) if
v m > for all m E N, and for every k = 1, . . . ,n, lim m _ >00 (^ £i a k (i)v m (i)) = c k . For a feasible
sequence {v m ) me tq, its value is defined by value((w m ) mG N) '■— limsup m _ yoo Yliel b{i)v m {i). For
a given (jFDSILPp , its limit value (a.k.a. subvalue) is
sup{value((w m ) me N) | (v m ) m eN is a feasible sequence for (jFDSILPj) }.
Since any feasible solution v E R^ to (jFDSILPp naturally corresponds to a feasible sequence
(where every element in the sequence is v), the limit value of (|FDSILPj) is greater than or equal
to its optimal value. We prove a remarkable theorem (Theorem 14.31 below) relating the limit
value of (|FDSILP|) and the optimal value of the primal (jSILPj) .
Lemma 4.1 (Weak Duality-II). Let x be a feasible solution to the primal (ISILPp and let
(w m )mGN be a feasible sequence for (JFDSILPP . Then c T x > va.\ue((v m ) me ^) .
Proof. Since a; is a feasible solution to the primal (jSILPP , a 1 (i)xi + . . . + a n (i)x n > b(i) for every
i E I. For each v m , since v m {i) > for all i E /, v m (i)a 1 (i)xi + ...+ v m (i)a n {i)x n > b{i)v m (i)
for every i E I. Therefore, summing over all the indices i E I, gives (X)iej v m (ija 1 (i))xi + • • • +
(EiGi v m {i)a n {i))x n > J2 ie i b{i)v m {i) for all m E N. Thus,
c 1 x 1 + ... + c n x n = lim m ^ oc [(X; 4e/ v m (i)a 1 (i))x 1 -\ \- {Y /teI v m (i)a n {i))x
= ]im S np m ^ 00 fy: iGl v m (i)a l (i))x 1 + ■■■ + fc ieI v m (i)a n {i))x n ]
> Hmsup m ^ oc [J2 ieI b{i)v m (i)}
= value((u m ) mGN ),
where the first equality follows from the definition of feasible sequence. □
The following lemma is required for the main result of the section (Theorem l4.3p . Applying
Fourier-Motzkin elimination on (jSILPP gives (|3.4p . Recall the function ui(8) = sup{6(/i) —
8Ht=t \ &k ( h )\ ■ h ^h} defined in (I3~TU1) .
Lemma 4.2. Suppose lim^^oo U)(8) — d such that —00 < d < 00. Then there exists a sequence
of indices h m in Z4 such that such that linim^oo b(h m ) = d and \\m m ^ toa a k (h m ) = for all
k =£,..., n. Moreover, b(h m ) > d for all m EN.
26
Proof. Since ui(8) is a nonincreasing function of 8, w(<5) > d for all 8. Therefore, d < sup{b(h) —
8 Y^k=t l" fe (^)l : h G I-i} f° r every 8. Let I C I 4 be such that for all h £ I, b(h) < d. Show that
it is sufficient to consider indices in 7 4 \ /. Given any 8 > 0, 6(ft) — <!>2~Zfc=f I® Wl < d f° r a U
fee/. Since d < sup{b(h) -8J2k=t I^WI : ^ e Mi S iven <* > °>
n n
suv{b(h)-8j2\a h (h)\ : ft G I 4 } = sup{6(ft) - £^) |a fc (ft)| ■h£h\I}.
k=e k=l
Thus, ui(8) = sup{6(ft) -8Y2=i \a k ( h )\ : h£l 4 \I} for all 8 > 0._
First show that there exists a sequence of indices h m £ I4 \ I such that a k (h m ) — > for
all k = £, . . . ,n. Begin by showing that inf{Y^k=e \® k (h)\ ■ h E I 4 \ 1} = Q. This implies that
there is a sequence h m £ Ii\I such that lim m _ i . 00 'Y^u—t \d k (h m )\ = which in turn implies that
lim m _ i . 00 a (h m ) = for all k = £, . . . , n. Suppose to the contrary that inf{X]fc = £ |5. fc (fe)| : ft £
I4 \ 1} = /3 > 0. Since u>(8) is nonincreasing and lim^oo ui(8) — d < 00, there exists <5 > such
that w(8) < 00. Observe that d = lim^oo ui{8) = lim^oo oj(8 + 8). Then, for every 8 > 0,
n
u>(8 + 8) = sup{b{h) -(8 + 8)^2 |5* COI : heh\I}
k=e
n n
= sup{b(h)-8^2\a k (h)\-8^2\a k {h)\ : hel 4 \l}
k=£ k=£
n
< sup{b(h) ~ SJ2 \a k W\ ~ 8/3 : h£h\I}
k=l
= sup{6(ft) -6^2 \d k (h)\ : h£l 4 \I}-S/3
= oj(S) - 8/3.
k=t
Therefore, d — lim^-yoo u>{8 + 8) < lim,5^j. 00 (a;((5) — 8(3) = —00, since /? > and w(<5) < 00. This
contradicts —oo<d. Thus j3 = and there is a sequence ft m £ I4 \ I such that a k (h m ) — ► for
all fc = £, . . . , n.
Now show there is a subsequence of b{h m ) that converges to d. Since lim^oo w((5) = d, there
is a sequence (J p ) p gn such that <5 p > and oj(S p ) < d + - for all peN. It was shown above
that the sequence h m £ I4, \ I is such that limm^oo Ylk=e l° fc (ftm)| — 0. This implies that for
every p £ N there is an m p £ N such that for all m > m p , 8 P Y^l = i \d k {h m )\ < -. Thus, one
can extract a subsequence (ft m »)peN of (/i m )m£N such that <5 P Sfe=£ l^ fe (^"i p )| < - for all p £ N.
Then
n
d + - > u(S v ) = sup{b(h) - 8 P V |& fc (/i)| : ft G Ii \ /}
y k=l.
n
> b(h mp )-S P Y,\a k (h mp )\.
k=l
The second inequality, along with 8 P Y^k=i \o- k {h m )\ < hi and the fact that h mp G I 4 \I implies
b{h mp ) > d, gives d + - > b(h„ lp ) > d and b(h mp ),p G N is the desired subsequence. □
Theorem 4.3 (Regular duality of semi- infinite linear programs). If (|SILP[) has an optimal
primal value z*, where —00 < z* < 00, then the limit value d of (|FDSILP[) is finite and z* = d.
27
Proof. By Lemma l3.81 z* = max{sup{6(/i) : h G i3},]im,5_ > . 00 w(<5)}. If 2* = sup{6(/i) : h £ 13},
then by Theorem 13.211 there is a zero duality gap, i.e., z* — d* where d* is the optimal value
of (|FDSILP|) . From Lemma |4~T1 d < z*, so z* = d* implies d < d*. By definition of limit value,
d > d*. Therefore, d* =d = z*.
In the other case when z* = lim ( 5_ ) . 00 a;((5), by Lemma 14.21 there is a sequence h m £ I4 such
that \iui m ^oo b(h m ) — z* and lim m _ ! . 00 d k (h m ) = for all k = ■£, . . . ,n. By Lemma 13.131 there
exist v hm G M^ for each m G N such that -c k + T,ieiV hm (i)a k (i) = for k = 1, . . . ,£ -
1, ~Ck +J2iei vhm ( i ) ak ( i ) = a k (h m ) for k = £,..., n, and J2ieiH i ) v>lm ( i ) = K^m)- Since
limm^oo d k (h m ) — for all fc = £, . . . , n, and limm^oo b(h m ) = z* , «''"*, m G N is a feasible
sequence with value z*. Thus, d > z*. Again, from Lemma \4. 11 d < z* , so z* = d. □
5 Application: Conic linear programs
Recall the definition of (|ConLPI) in Section [T] and its standard dual (jConLPDI) . They are
reproduced here for convenience. The conic primal is
infxe f { ?!*L a ( ConLp )
s.t. A(x) hp d '
where X and Y are vector spaces, A : X — ¥ Y is a linear mapping, d G Y, P is a pointed convex
cone in Y and is a linear functional on X . The conic dual is
sup^y, (d,ip)
s.t. A'(ip) = </> (ConLPD)
V>gP'.
Let F = {1 e I -^(aO hp d} denote the feasible region of (|ConLP[) . In our development, it
is convenient to assume that the algebraic adjoint A' of linear map A is surjective (in order to
apply the Open Mapping Theorem). Lemmas I5.1H5.3I and Remark 15.41 show this assumption
can be made without loss of generality. For any linear map T defined on X, let ker(T) = {x G
X : T(x) = 0} denote the kernel of T.
Lemma 5.1. Given a linear mapping A : X — s> Y, ker(A) — {0} if and only if A' is surjective.
Proof. (=>) If kci(A) = {0}, then A is one-to-one and there is a linear map A^ 1 : Im(A) — > X.
Let 4> be an arbitrary linear functional in X'. Show there exists a linear functional ip £ Y' such
that (f) — -A'CVO- Define the linear functional <f> o A" 1 on Im(A) and let ip be any extension of
this linear functional from Im(A) to Y. Thus rp G Y'. Show <f> — A'(ip). For any x £ X,
(x,A'(tp)) = (A(x),ip) = {<p o A~ 1 )(A(x)) = (f>(x) = {x,4>). The second equality follows since
A(x) G Im(A).
(<=) Consider x G X such that A(x) = 0. Show that for every </> G X' , (x, </>) — 0. This
would imply that x = 0. Since A 1 is surjective, for every <j> G X' there exists i/ief such that
A'(tp) = (/>. Thus, (x, (f>) = (x, A'(ip)) = (A(x), V) = (0, V) =0. □
Lemma 5.2. If (|ConLP[) is feasible and bounded, then ker(yl) C ker(</>).
Proof. Prove the contrapositive and assume that there is an r G kei(A) \ ker(0). Without loss
of generality assume (r, (f>) < (otherwise make the argument with — r). Let x be a feasible
solution to (IConLP[) . i.e., A(x) >p d. Since r G ker(A), A(x + Xr) ^p d for all A > 0. But since
(r, 4>) < 0, (x + Xr, 4>) — ^ —00 as A — > 00, contradicting the boundedness of (IConLP[) . D
28
Lemma 5.3. Let X be a finite-dimensional space, so that orthogonal complements of subspaces
are well-defined. Let </> = ^IhcifA) 1 - be the linear functional on ker(A) 1 - defined by the restriction
of <j> to ker( J 4) ± . Similarly, let A = A\ kcT r A \± denote the restriction of the linear map A. Consider
the optimization problem
m fxGker(A)^ {x,4>) (r i\
s.t. A{x) hp d. [ °- L>
If (|ConLP|) is feasible and bounded, the optimal value of (jConLPj) equals the optimal value
of (|5.1|) . Moreover, if O is the set of optimal primal solutions for (JConLPj) . and O is the set of
optimal primal solutions for (|5.ip . then O = O + ker(A).
Proof. Since (jConLPI) is feasible and bounded, kei(A) C ker(</>) by Lemma 15.21 For any x
feasible to (|ConLP[) . let r G ker(A) and x G ker(A) 1 - such that x — x + r. Since ker(y4) C ker(<j>),
(r, (f)) — 0. Thus, (x, <j>) = (x+r,(f>) = (x, <j>) = (x, </>), the last equality follows since x G ker(A) ± .
Similarly, A(x) — A(x) = A(x + r) = A{x) ^p d. Thus, x is a feasible solution to (|5.ip with the
same objective value as {x,(f>). D
Remark 5.4. By Lemma [5. 31 when (JConLPI) is feasible and bounded, it suffices to consider
a restricted optimization problem like (|5.1|) . Note that ker(^4) = {0}. Thus, without loss of
generality, it is valid to assume that for an instance of a feasible and bounded (JConLPj) in a
finite-dimensional space X, the linear map A has zero kernel, i.e., it is one-to-one. This implies
that A' is surjective by Lemma 15.11 <
Construct the following primal-dual pair of semi-infinite linear programs in the case where
X is finite-dimensional and the cone P is reflexive. Recall that a cone P is reflexive if P" = P
under the natural embedding of Y c -¥ Y". The significance of this property will become apparent
in Theorem 15.51 The primal semi- infinite linear program is
s.t. a 1 {^)x 1 +a 2 (iP)x 2 + --- + a n (iP)x n >b{ijj) for all ip 6 P' l^orioii.rj
where X is isomorphic to l n with respect to a basis e 1 , . . . , e™ and c € M. n represents the linear
functional <fi G X' (also using the isomorphism of X' and W 1 ). In (jConSILPI) . the elements
a j eR p 'j = l,...,n and b G R p ' , are defined by a j (ip) := (A{e^),ijj) and b(ip) := (d,ip). The
finite support dual of (|ConSILP|) is
su PEv-eP' 6 (^) w (V')
s -t- J2i,eP' ak W v W = c fe forfc=l,...,n (ConFDSILP)
v e K^ p,) .
The close connection of this primal-dual pair to the conic pair (|ConLPjl - (|ConLPDjl is shown in
Theorem 15.51 and Theorem 15.71
Theorem 5.5 (Primal correspondence). Assume P is reflexive and X is finite-dimensional. Let
e 1 , . . . , e™ be the basis of X used to define (jConSILPp and (|ConFDSILPj) . Then, ^ (jConLPp =
f (jConSILPp . Moreover, the set of feasible solutions to (IConLPp is isomorphic to the set of
feasible solutions to (JConSILPp under this basis.
Proof. Since X is isomorphic to R™ with respect to the basis e 1 , . . . , e n and c £ R" represents
the linear functional £ X' the objective functions of both problems are identical (under this
isomorphism). The result follows if the feasible regions of both problems are isomorphic under
this same mapping.
Let F denote the feasible region of (ConLP) and F denote the feasible region of (ConSILP).
Show F is isomorphic to F under the basis e 1 , . . . , e™. First show that if x = x\e l + . . .+x n e n G F
29
then (xi, . . . , x n ) £ F. If X £ F, then A(x) hp d. Therefore, A(x) — <i G P and so for all ip £ P',
((A(x) — d),i/j) > 0. Writing A(x) = X)?=i XjA{e?) and using the linearity of ip, it follows that
(xi,...,x„) 6 F.
Next show that if (xi , . . . , x n ) eF, then x = xie 1 + . . . + x n e n G F. Show the contrapositive,
i.e. if x fL F then (xi, . . . ,x n ) f: P. If x €" F, then A(x) — d ^ P and since P is reflexive,
A(x) — d f: P" (under the natural embedding of Y <-t Y"). Therefore, there exists i/igP' such
that ((A(x) — d), ip) < 0. Again, using the linearity of ip it follows that (xi, . . . , x„) f- F. D
Remark 5.6. The condition that P is reflexive naturally holds in many important special cases
of conic programming. Once such case is when X and Y are finite dimensional spaces and P
is a closed, pointed cone in Y. Then P is easily seen to be reflexive. This case includes lin-
ear programming, semi-definite programming (SDPs) and copositive programming. The above
reformulation as a semi-infinite linear program works for any such instance. <
Theorem 5.7 (Dual Correspondence). Assume P is reflexive and X is finite-dimensional. Let
e 1 , . . . , e™ be the basis of X used to define (JConSILPj) and (|ConFDSILP|> . Then, i; (|ConLPD|) =
i> (|ConFDSILP|) . Moreover, there exists maps T : P' -> R^P and f : R^P ->■ P' such that if
ip G P' is a feasible solution to (|ConLPD[) then T(ip) is a feasible solution to (|ConFDSILP[) .
Conversely, if v € M.( p ' is a feasible solution to (|ConFDSILP[) then T(v) is a feasible solution
to IjConLPDjI .
Proof. It suffices to construct maps T and T which satisfy the following properties.
(i) (e k ,A'(ip*)) = T,4,eP' ak W T ^*)W> for ever y ^* e p ' and a11 fc = 1, •■-,"■
(ii) (d, </;*} = £^ p , &(VW)(V0, for every ^ G P'.
(iii) E^ e p'« fe (V')"('0) = (e k ,A'(f(v))}, for every t> G M. ( f" > and all fc = 1,. . . ,n.
( iv ) E^p> KV>)<#) = (d,r(t;)), for every v G R^°.
The map T is defined as follows. For any ip* G P', T(ip*) is the finite support element v* G
R( p ' where the only non-zero component of v* is 1 and corresponds to ip* . For any k G
{l,...,ri}, ^ e p,a k {ip)v*(ip) = a k {iP*) = (A(e k ),iP*) = (e k , A' (ip*)) and (i) is satisfied. Also,
X^eP' b(ip)v*(ip) = b(ip*) = (d,ip*) and (ii) is satisfied.
The map T is defined as follows. For any v* G M^ p ', T(v*) — X^eP' v*(ip)ip where the sum
is well-defined because v* has finite support. Since v* has nonnegative entries, T(v*) G P'. Now,
Y.^P^ k {iP)v*{iP) = E^ 6 P'^(e*)^>f*W = (^(e^E^^'WW = (A{e k ) 7 f{v*)) =
(e k ,A'(f(v*)) and (iii) is satisfied. Also, £, 0eP , 6(V>)«*(V) - E^P'R WW = <d»£* e j» U *(W)
{d,T(v*)) and (iv) is satisfied. □
5.1 Zero duality gap via boundedness
We prove Theorem 15.81 in this section. A more restricted version of this result is known in the
classical conic programming literature (see for example Duffin [5J). Our result is obtained with
a completely new proof using projection techniques.
Theorem 5.8 (Zero duality gap via boundedness). Let X be finite-dimensional. If P is re-
flexive and there exists a scalar 7 such the set {x : A(x) ^p d and (x, <p) < 7} is nonempty and
bounded, then there is no duality gap for the primal-dual pair (IConLP[) - (|ConLPDp .
Proof. By Theorem 15.51 the primal optimal value of (jConLPI) is equal to the optimal value
of the (IConSILPp . By Theorem 13.251 there is a zero duality gap between the primal dual
pair (JConSILPj) - (|ConFDSILPJ) . Finally, from Theorem O the optimal value of (|ConFDSILPp
is equal to the optimal value of (|ConLPD|) . □
30
Corollary 5.9. Scmi-dcfinitc programs (SDPs) and copositive programs with nonempty, bounded
feasible regions have zero duality gap.
5.2 Regular duality for conic programs
We now prove a central result of conic programming, known as regular duality, using the machin-
ery of FM elimination. First, some notions from conic programming (see Chapter 4 of Gartner
and Matousek [8| for more details). A sequence (ip m ) m &i> is called a feasible sequence for the
dual program (IConLPPp if ip m £ P' for all m £ N and
lim A\i> m ) = (/).
m— >-oo
The value of a feasible sequence (ip m )men is (d, (0> m )meN) = hm sup m ^ oc (of, ip m ). The limit
value (a.k.a. subvalue) of the dual program (IConLPDj) is
sup{(d, (i/i m ) m6 N) | {ip m )m£fi is a feasible sequence for (|ConLPD|) }.
A simple proof of regular duality for conic programs is easily obtained using projection (see
Theorem 4.7.3 in Gartner and Matousek [8| for the more standard proof technique).
Theorem 5.10 (Regular duality for conic programs). Assume X is finite-dimensional and P
is reflexive. If the primal conic program (IConLPp is feasible and has a finite optimal value z* ,
then the dual program (jConLPPp has a finite limit value d and z* = d.
Proof. By Theorem 15. 51 the optimal value of (|ConSILPj) is equal to z* and z* is finite since the
optimal value of (|ConLPp is finite. By Theorem l4.31 the limit value of (|ConFDSILP[) equals the
optimal value of (|ConSILP[) . By Theorem 15.71 every feasible sequence (V' m )meN for (JConLPPp
maps to a feasible sequence (T(-0 m )) mG N for (jConFPSILPp . Similarly, every feasible sequence
(u m ) meN for (IConFDSILPp maps to a feasible sequence (T(u m )) mGN for (jConLPPp . Thus, the
limit value d of (JConLPPp is equal z*, the limit value of (|ConFDSILP|) . □
5.3 Zero duality gap via Slater's condition
Assume throughout this section X and Y are finite-dimensional spaces, and P is reflexive (note
that any closed cone is reflexive because Y is finite-dimensional). As before, identify X with R".
Let B(x,e) C M. n denote the open ball of radius e with center x £ M. n . Identify the objective
linear functional <p £ X' with the vector c £ M. n .
Lemma 5.11. Assume A' : Y' — >• X' is surjective and there exists ip* £ int(P') with A'(ip*) = c.
Then there exists e > and -0 £ P', such that for all c £ B(c,e), c T x > (d,tp) is a constraint
in (IGonSlLPP .
Proof. For each ip £ P', the constraint in (jConSILPp corresponding to ip is X)?=i x j (Aie^), ip) >
(d,ijj). The left hand side of the inequality is the same as X) 7 -=i x j( e ^ ^'(V 1 )} = (^j A'(ip)).
Since A' is a linear map between finite-dimensional spaces, it is continuous and by assumption,
surjective. By the Open Mapping theorem, A' maps open sets to open sets. Since tp* £ int(P')
there exists an open ball B* C P' containing ip* . Thus, A'(B*) is an open set containing c.
Therefore, there exists an e > such that B(c,e) C A'(B*). Thus, for every c £ B(c,e), there
exists ^ £ B* such that A'fy) = c. Since all -0 £ B* C P' give constraints (x,A'(ip)) >
(d,ip) in (JConSILPp . for every c £ B(c,e) there is the constraint c T x = (x : A'{}p)) > (d,-ip)
in (IConSILPD . □
Theorem 5.12 (Slater's theorem for conic programs). If the primal conic program (jConLPp is
feasible and there exists ip* £ int(P') with A'(ip*) = c, then there is a zero duality gap for the
primal dual pair (JConLPp - (IConLPPp . Moreover, the primal is solvable.
31
Proof. By hypothesis, there exists ip* £ int(P') with A'(ip*) = c so the dual conic pro-
gram (jConLPDp is feasible. Since (IConLPp is also feasible by hypothesis, feasibility of (|ConLPPp
implies (IConLPp is both feasible and bounded. Then by Remark 15.41 it is valid to assume A' is
surjective.
Claim 5.13. The variables x\, . . . ,x n remain clean when Fourier-Motzkin elimination is applied
to (IConSILPI) .
Proof. Since A'(ip*) — c, there is a constraint c T x > (d,ip*) in the system (|ConSILP[) . The
constraint — c T x + z > is also present when Fourier-Motzkin elimination is performed on a
semi-infinite linear program. By Lemma 15. Ill there exists e > such that every c £ B(c, e)
gives a constraint c T x > b' in (JConSILPp . Thus, for any S < e, both (c + 5e 3 ) T x > lP + and
(c-SeP)x > b 3 _ are constraints for every j = 1, . . . , n, (where b J + and b J _ are some real numbers).
Case 1: Cj = for all j = 1, . . . , k. In this case the constraints are %Xj > b J + and — # Xj > iP_
in the system. During Fourier-Motzkin, for each j — 1, ...,n, the constraints ^Xj > b\ and
— %Xj > bi_ remain in the system until variable Xj is reached. This makes all variables x±, . . . , x n
clean throughout the Fourier-Motzkin procedure.
Case 2: Cj ^ for some j = 1, . . . , k. Relabel the variables and assume that c\ ^ 0. Thus, the
coefficient of x\ in — c T x + z > has opposite sign to the coefficient of x\ in the constraints
(c + Se^) 1 x > b J + and (c — Se-*) X > b J _ for j — 2, . . . , n. Thefefore x\ is clean, and when x\ is
eliminated, the constraint — c T x + z > is aggregated with the constraints (c + 8e^) T x > b J +
and (c — 8e?yx > lP_, for each j = 2, . . . ,n. This leaves the constraints Sxj + z > b 3 + and
— Sxj + z > b 3 _ in the system for j — 2, . . . ,n, after x\ is eliminated. As in Case 1, these
constraints remain in the system variable until Xj is reached. This makes all variables x±, . . . ,x n
clean throughout the Fourier-Motzkin procedure. □
Since variables xi, ■ . ■ , x n are clean throughout the Fourier-Motzkin procedure, and (JConSILPp
is feasible (since (|ConLPp is feasible), the problem is feasible and tidy and by Theorcm l3.24l there
is a zero duality gap between the pair (|ConSILPp - (|ConFDSILPp . and ([ConSILPp is solvable. By
Thcorcms l5.5l and l5.7[ this implies that there is zero duality gap for the pair (|ConLPp - (|ConLPDp .
and the primal (jConLPp is solvable. □
Remark 5.14. Since the dual conic program (IConLPDp is also a conic program, one can
consider (jConLPDp as a primal conic program. In this case the dual is (|ConLPp . By Theo-
rem I5.12[ there is a zero duality gap between this primal-dual pair if there is a point x* such
that A(x*) — d £ int(P). Moreover, the dual is solvable. <
6 Application: Convex programs
Recall the convex program (|CP|) and its Lagrangian dual (jLDp introduced in Section [TJ They
are reproduced below for convenience. The primal is
maxxeun f(x)
s.t. gi(x) > tori = l,...,p (CP)
X £ il
where f{x) and gi(x), i = 1, . . . ,p are concave functions, and Q is a closed, convex set. The
dual is
inf L(X) (LP)
A>0
32
where L is the Lagrangian function
p
L(X) := max{/(x) + TJ Xigi(x) : x G Q}.
8=1
Construct a semi-infinite linear program which is shown in Theorem l6.1l to have the same optimal
value as the Lagrangian dual (|LD[) . This semi- infinite linear program is
inf a
s.t. cr - X)-Li *i9i(x) > f(x) for i £ fi (CP-SILP)
'a > 0.
Construct the finite support dual for (|CP-SILP[) . There are two sets of constraints in (ICP-SILP[) .
There are typically an uncountable number of constraints indexed by x 6 Q and a finite number
of nonnegativity, A > 0, constraints indexed by {1, ... ,p}. Thus, the finite support dual elements
belong to R(nu{i,. ..,?})_ The finite support dual defined over (u,v) G R (n) x W is
(CP-FDSILP) sup Y^ u(x)f(x) (6.1)
xen
s.t. ^2u(x) = 1 (6.2)
- y^ u(x)gj(x) +Vj = for i=l,..., p (6.3)
xen
(u,v) G tfxR p + . (6.4)
Recall v(CP) is the optimal value of (jC"Pj) . u(LD) is the optimal value of (|LDl) , v(CP-SILP) is
the optimal value of (|CP-SILPI) and v(CP-FDSILP) is the optimal value of ([6TI ]) -([6T1 ]) .
Theorem 6.1. u(LD) = u(CP-SILP). Moreover, (ICP-SILPp is solvable if and only if there
exists A* > such that L(\*) — infx>o L(X).
Proof. First show w(LD) > v(CP-SILP). If, for every A > 0, L(X) _= oo then u(LD) =00
and the result is immediate. Else, consider any A > such that L(X) < oo. Set a — L(X).
Then (er,A) is a feasible solution to (|CP-SILP[) with the same objective value as L(X). Thus,
L(X) > v(CP-SILP). Since A > was chosen arbitrarily, inf A > £(A) > v (CP-SILP).
Now show w(CP-SILP) > u(LD). If (JCP-SILPJ) is infeasible thenu(CP-SILP) = oo and
the result is immediate. Otherwise, consider any feasible solution (a, A) to (|CP-SILPp . Then
a > L(X) and thus a > infA>o^(A). Since a is the objective value of this feasible solution to
(|CP-SILPp . the optimal value of (|CP-SILP[) is greater than or equal to inf^o L(X).
The second part follows from very similar arguments. □
Theorem 6.2. v(CP) = w(CP-FDSILP).
Proof. First show v(CP) > w(CP-FDSILP). If JCHD-flHD is infeasible, then u(CP-FDSILP) =
— oo and the result is immediate. Assume (|6.2I) - (|6.4I) has feasible solution (u,v). Let x —
y^ r£ Q xu(x). This sum is well-defined because u has finite support. Show x is feasible to (|CP[) .
First, since Q is convex, by (|6.2|) x G ft. By ()6.3j) . — J2 x en u(x)gi(x) +Ui = for all i = 1, . . . 7 p.
Since vi > 0, J2 x en u{x)gi(x) > 0. By (|6.2j) and concavity of gi, g%{x) — gi(J2 x en x ^( x )) -
J2xen u(x)gi(x) > for all z = 1, . . . ,p. Thus the constraints of JCPj are satisfied. Since / is
concave, f(x) — fiYlxetl xu(x)) > X^xen u(x)f(x) which is the objective value of (u, v) in (|6.1[) .
Now show that w(CP-FDSILP) > u(CP). If (JCPj) is infeasible, then w(CP) = -oo and the
result is immediate. Otherwise, consider any feasible solution x to (|CPp . Let u G M. + ' be
33
defined by u(x) — 1 and u(x) = for all x ^ x. Define v £ M. p by Vi = gi(x). Since x is feasible
to (|CPI) . v £ R?_. Thus, (u,v) is a feasible solution to (|6.1[) . The objective value of (u, u) in
(|6.ip is /(#) which is the objective value x in (|CPp . D
Remark 6.3. Theorems 16.11 and 16.21 imply
v(CP-SILP) = u(LD) > u(CP) = u(CP-FDSILP)
where the inequality follows from weak duality of the Lagrangian dual (or the weak duality of
semi-infinite linear programs as discussed in Section [3]). <
Theorem 6.4 (Slater's theorem for convex programs). Assume the convex program (|CP[) is
feasible and bounded, i.e., — oo < u(CP) < oo and there exists x* £ Q such that gi(x*) >
for alii = 1, . . . ,p. Then there is a zero duality gap between the convex program (|CP[) and its
Lagrangian dual (|LD[) and there exists A* > such that u(LD) = L(X*), i.e., the Lagrangian
dual is solvable.
Proof. Write the semi- infinite linear program defined by system (|CP-SILP[) as in Section [5]
z - a >
* - E*=i Aiflfi(aO ^ /O) for z eft (6-5)
A, > for i = 1, . . . , p.
Without loss of generality, assume that f(x) is bounded above on Vt. It is valid to replace the
objective function f(x), by the concave function f(x) = min{/(x), B}, where B is an upper
bound on v(CP). Such a bound exists by hypothesis. Therefore, z = a = B, A = is a feasible
solution to (|6.5p . Let 7 be any value of z that is feasible in (|6.5p and show
7 - a >
<7-£*=iAiSi(aO > /(*) for a; eft (6.6)
Aj > for i = 1, . . . ,p
is bounded. By hypothesis, (jCPp has a Slater point x* . Consider the sub-system of (|6.6p
7-0- >
v-i:U*i9i(x*) > /(»*) (6-7)
Ai > for z = 1, . . . ,p.
Since x* is a Slater point, g%{x*) > 0, i = 1, . . . ,p; which together with <r < 7 implies
< A, < (7 - /(a*))Ms*) fori = l,...,p,
which in turn implies /(a;*) < ct < 7 and the set of feasible solutions to (|6.7p is bounded.
Since (|6.7p is a sub-system of (|6.6p . the set of feasible solutions to (|6.6p is bounded. Then
by Theorem GE2H u(CP-SILP) = w(CP-FDSILP) and (|CP-SILPp is solvable. By Remark O
v(CP) — w(LD). Moreover, since (jCP-SILPp is solvable, by Theorem 16.11 there exists A* such
that v(LD) = L(X*). D
The following example demonstrates that it is possible to identify a zero duality gap with
techniques of this paper, even when a Slater condition fails.
Example 6.5. Consider the convex optimization problem
max xeR n
s.t. l-x\-xl>0 (6.8)
-l + si > 0.
34
The feasible region is the singleton {(1, 0)} and so no Slater point exists, however there is a zero
duality gap. For this instance, (|CP-SILPp is
inf a
s.t. a + \i(x\ + x\ - I) + \ 2 {l - xi) > for x G
A 0.
(6.9)
Setting (cr, Ai,A2) = (0,0,0) shows that this semi-inhnite linear program (|SILP[) is feasible.
Notice also that the right-hand function b : K™ — > M, is the zero function. Applying Fourier-
Motzkin elimination to (|6.9j) gives b(h) = for all h and this implies sup ?ie/3 b(h) = 0. Also, for
any S > 0,
;(<*) = sup { b(h) -Sy"\5, k (h)\ } = sup { -iV |5 fc (^)l ? < 0.
fc=f
fc=£
Then sup Ae j 3 b(h) > lim^oo u(d) and by Theorem 13.211 there is a zero duality gap between
(|6.9[) and its finite support dual. By Theorem 16.11 and 16.21 this implies there is a zero duality
gap between (|6.8|) and its Lagrangian dual. <
7 Application: Generalized Farkas' Theorem
In this section, Fourier-Motzkin elimination is used to prove the generalized Farkas' theorem.
Consider a closed convex set given as the intersection of (possibly infinitely many) halfspaces
P = {xeW n \ a 1 (i)x 1 H h a n (i)x„ > b(i) for i e I},
(7.1)
where / is any index set, a 1 ,..., a™ and b are elements of R 7 . An inequality c T x > d is a
consequence of the system of inequalities a 1 (i)xi + . . . a n (i)x n > b(i), i G / if c T x > d for every
x G P. If P = 0, then every inequality is a consequence the inequalities a 1 (i)xi + . . . a n (i)x n >
6(i), i G /. Let a 1 denote the vector in R n given by a 1 — (a 1 (i), . . . , a n (i)) T . The notation n is
used to denote the n-dimensional vector of zeros.
Theorem 7.1 (Generalized Farkas' Theorem, see Theorem 3.1 in Goberna and Lopez [9|]). The
inequality c T x > d is a consequence of (a l ) T x > b(i) for all i G /, if and only if at least one of
the following holds:
(i)
Gel
0„
a'
b(i)
G/
(ii)
0„
1
Gel
a'
b(i)
iel
Proof. First show that the condition is sufficient. Assume (0) holds. If
tor in cone
cl I cone
such that each
(
[
1
a
"
\\
-1
)
bd)
I
0„
a 1
I
-1
)
b
® .
; i £ I > I , then j T x > S for every x G P. Since
&
belongs to cone
, there exists a sequence lim
j->oo
"
7
8
is any vec-
\ Since
c
d
G
Si
c
i
o„
-1
6(f)
; i £ I
Thus, (7 J ) T x-(5 J ' >
35
for every j and every x G P and linij_). 0o (('y ,J ') a: — 5 3 ) = c T x — d > for every x G P. Thus
c T a; > d is a consequence. Now assume that ((u]) above holds. Then, by the same reasoning,
0n x > 1 is satisfied for all x G P. This implies P = and then any inequality c T a; > d is a
consequence.
For the other direction, assume c T x > d is a consequence. There are two cases, depending
on whether P is empty or not.
Case 1: P — 0. Apply the Fourier-Motzkin elimination procedure to the constraints that define
P in (|7.1I) and obtain the system (|2.8I) - (|2.9I) with the corresponding index sets H\ and Hi- Since
P = 0, by Theorem [2T3] either b(h) > for some h* 6 fli, or sup{6(/i)/ ELf l« fc (MI : /- 6
i?2J = oo. Consider these two cases in turn:
Case la: b(h*) > for some h* € Hi. By Theorem l2~9l there exists u' 1 ' G R+
, n and (6, u } > 0. Using the multiplers
with finite
h*
support such that {a 3 ,u ) = for all j = 1
for the constraints corresponding to the non-zero elements in u h to aggregate constraints, gives
<&,-,
')
0„
1
G cone
b(i)
iel
Condition (fnl) in the statement of the theorem is satisfied.
Case lb: sup^g-- b(h)/y]2_( \a k (h)\ = oo. This implies that there is a sequence h m G -H2,
m = 1, 2, . . . such that b(h m )/ Ylk=£ \ ak (hm)\ > m. This implies b(h m ) > for all m. Rearrang-
ing the terms, gives
lim
The above limit implies
EL« l« fe (^
HKn)
a k (h m )
= 0.
lim
=
for fc = £, ^ + 1, . . . , n. By Theorem 12.91 there exists u m G
p(-)
with finite support such that
{a 3 , u h ™) = for j = 1, . . . ,£ - 1, (a-', u h ™} = a- (Tim) for j =£,..., n and (6, u h ™} = 6(/i m ).
Since b(h m ) > 0, (a J
and (b, jTjp-r) = 1. Since limm-n*,
y* m \ = n for all i = 1 t - 1 (a- 7 ' -" hm \ = il^il f or j = P n
---—-/ u ior an j !,...,« i, [a , -^-y; ------- ior j t,...,ra
, n, this gives a sequence of points in
--------- = 0forj = l,
0„
1
b(h
that converges to
and condition ([n]) holds.
Case J?: P ^ 0. Consider the semi-infinite linear program
inf^e
c T a;
s.t. a 1 (i)xi+a 2 (i)x 2 -\ + a n (i)x n > o(i), for i G I.
(7.2)
If P ^ 0, the semi-infinite linear program defined by (|7.2j) is feasible, i.e., z* < oo. Since
c T x > d is a consequence, (|7.2|) is bounded, i.e., z* > d > — oo. Reformulate as in (I3.ip ~ p.3p
and apply Fourier-Motzkin elimination and obtain the system (|3.4p with the corresponding index
sets 2i,i2,^3 and 14. Then by Lemma 13.81 the primal optimal value is
maxjsup 6(/i), lim lu(S)}.
hei 3 s ^°°
Again consider two cases :
Case 2a: z* — sup fte - b{h). This implies that for any fixed e > there is an h* G I3
such that b(h*) > z* — e > d — e. Since h* G I3, Lemma l3.131pv|) implies that there ex-
ists v h " G
W such that {a 3 ,v h ") = Cj and b(h*) = (M H *) > d
Thus,
c
d-e
36
cone
-1
a"
b(i)
iel
where the multiplier for
is b(h*) - (d - e). Since
this is true for any e > 0,
G cl cone
0„
-1
a'
b(i)
i€l
and condition Q of the theorem holds.
Case 2b: z* — lim,5_ ! . 00 a;((5). Since — oo < z* < oo, by Lemma 14.21 there exists a sub-
sequence of indices h m ,m — 1,2,... such that h m G I4, a k (h m ) —>■ for all k = £,..,, n,
b{h m ) -> z* and b(h m ) > z* for all m e N. Let 5 m G M™ be defined by (5 m ) fe = for
k = 1, . . . ,£ - 1 and (a m )fc = a k (h. m ) for k = £,... ,n. By Lemma [3TT3t jvj) . for each m G N,
a m = a m — c, for some a m G coneda 1 }^/). Renaming b(h m ) — b rn , gives
a'
b„
and
Since a r '
G cone
a
b n
- c
d
b(i)
+ (b m - d)
i€l
0„
as m —s- 00,
a'" - c
+ (6m - d)
o„
-1
a"
+ (b m - d)
+ (b m - d)
0,,
•1
Now b m > d because 6 m = b(h m ) > z* > d. Therefore
0„
, G cl I cone
d J v
and condition O of the theorem holds.
-1
a'
b(i)
c
d
c
d
iel
a
8 Application: Further results for semi-infinite linear pro-
grams
8.1 Additional sufficient conditions for zero duality gap
By looking at the recession cone of p,18[) it is possible gain further insights and discover useful
sufficient conditions for zero duality gaps in general semi-infinite linear programs. We show
results first discovered by Karney [Kf follow directly and easily from our methods. The recession
cone of (|3.18[) is defined by the system
- CiXx - c 2 x 2 - ■ ■ ■ - c n x n > (8.1)
a l (i)x 1 +a 2 (i)x 2 -\ \-a n (i)x n > for i G I. (8.2)
Applying Fourier-Motzkin elimination to (|8.1[) - (|8.2j) gives
> for h € Hi (8.3)
d e (h)x e + d e+1 (h)x i+1 +--- + a n (h)x„ > for h G H 2 . (8.4)
37
Following the notation conventions of Karney [10j, K denotes the recession cone of (|SILP[) .
given by the inequalities (|8.2|l and N denotes the null space of the objective function vector c.
Lemma 8.1. If H2 is nonempty in (|8.4[) . then there exists a ray r G K." satisfying (|8.ip - (|8.2
with at least one of the inequalities in (|8.1|) - (|8.2j) satisfied strictly.
Proof. If H-2 is nonempty, there is a k > £ such that a k (h) is nonzero for at least one h G H^-
Since Xk is a dirty variable, the nonzero a k (h) are of the same sign for all h G i?2- If the a (h)
are all nonnegative, then set x k = 1 and Xi — for i 7^ k; if the 5 (/i) are all nonpositive, then set
Xk = —1 and Xi = for i ^ k. This solution to (I8.3[l - (|8.4p satisfies at least one of the inequalities
in (|8.3p - (|8.4l) strictly. Since this is the projection of some r satisfying (|8.ip - (|8.2[) . this r must
satisfy at least one inequality in (|8.ip - (|8.2p strictly, since all inequalities in (|8.3p - (|8.4p are conic
combinations of inequalities in (|8.1l) - (|8.2p . D
Theorem 8.2. If (|SILPI) is feasible and K n N is a subspace, then u (|SILPp = « (|FDSILPp .
Proof. Case 1: H2 in (|8.4[) is empty. Observe that the columns in systems (|8.ip - (|8.2p and (13.21) -
(|3.3p are identical for variables x\, . . . ,x n . This means if Xk is eliminated when Fourier-Motzkin
elimination is applied to one system, it is eliminated in the other system. Since H2 in (|8.4|) is
empty, ([SILPJ) is tidy. Then by Theorem [32! v pLPl = u (|FDSILP|) .
Case 2: H2 in (|8.4p is not empty. If H2 is not empty, by Lemma 18. 1[ there exists r satis-
fving (J8.ip - (l8.2p such that at least one of the inequalities in (|8.1l) - (|8.2p is satisfied strictly. If
c T r < and r G K, then u ljSILPp = —00. Therefore (jFDSILPp is infeasible by weak duality and
ufJEEEJ = ^FPSILPp = -00. If c T r = then the constraint (|8~1~T) is tight at r and so r G N.
Then r G KP\N which is a subspace by hypothesis. Then — r G KON. This implies r G Kn—K.
But this means that r satisfies all inequalities in (|8.2[) at equality and this contradicts the fact
established for this case that at least one inequality in (|8.1l) - (l8.2p is strict. □
8.2 Finite approximation results
Consider an instance of (|SILP[) and the corresponding finite support dual (jFDSILPp . For any
subset J C. I, define SILP(J) as the semi- infinite linear program with only the constraints
indexed by J and the same objective function, and v(J) the optimal value of SILP(J). For
example, if J is a finite subset of /, SILP( J) is a finite linear program.
Theorem 8.3. If (ISILPp is feasible, then w(FDSILP) = sup{w(J) : J is a finite subset of /}.
Proof. First show w(FDSILP) < sup{u(J) : J is a finite subset of /}. By hypothesis, (jSILPjl
is feasible and this implies by Corollary 13.191 that u(FDSILP) = svp hel3 b(h). Therefore, for
every e > 0, there exists h* G I3 such that w(FDSILP) -e < b(h*). By Lemma I3~T3T[ iv |) .
there exists v h " G M^ 7 ^ with support J* such that b(h*) = (b,v h ") = J2ieJ' b{i)v h *(i), and
J2ie.J' ak (i) vh (i) = Cfc. Since (ISILPp is feasible, SILP(J*) is feasible; let x be any feasible
solution to this finite LP. Thus,
T-
C X
En -
k—l C-kXk
= ELi(E JGJ .« fc (*K*(*)K
- T.ieATZ^ k {i)x k )v h '{i)
= b(h*).
Since this holds for any feasible solution to SILP(J*), v(J*) > b(h*) > w(FDSILP) - e.
Thus, for every e > 0, there exists a finite J* C I such that v(J*) > w(FDSILP) — e. Hence,
u(FDSILP) < sup{w(J) : J is a finite subset of I}.
38
Next show that w(FDSILP) > sup{v(J) : J is a finite subset of /}. Consider any finite
J* C I. It suffices to show that u(FDSILP) > v(J*). If v(J*) = -oo, then the result is
immediate. So assume v(J*) > — oo. Then SILP(J*) is bounded. Since (|SILP[) is feasible by
hypothesis, SILP(J*) is also feasible. Then by Theorem 13.261 there exists v* G R such that
T, ieJ , b(i)v*(i) = v(J*) and £ ieJ . a k (i)v*(i) = c fe . Defi ne g £ R^ by t>(i) = v*(i) for j <= J*
and v(i) — for i ^ J* . Thus, u is a feasible solution to (|FDSILP|) with objective value v(J*).
Therefore, w(FDSILP) > v(J*). D
Theorem 18.31 is used to prove a series of results by Karney [10( . Consider a semi-infinite
linear program with countably many constraints, i.e., I = N. For every n£N, let P n denote the
finite linear program formed using the constraints indexed by {1, . . . , n} and the same objective
function. Let v(P n ) denote its optimal value.
Corollary 8.4. If (jSlLPJ) is feasible with I = N, then lim^oc v(P n ) = w(FDSILP).
Proof. Since {1, . . . , n} is a finite subset of /, v(P n ) < sup{v(J) : J is a finite subset of /} =
u(FDSILP) < oo where the equality follows from Theorem 18.31 and the "<" follows from
weak duality since (jSILPp is feasible. Since v(P n ) is a nondecreasing sequence of real num-
bers bounded above, linin^oo v(P n ) exists and ]xm n ->. 00 v(P n ) < u(FDSILP). Next prove that
lim.n-j.oo v(P n ) > w(FDSILP). Observe that for any finite subset J* C I there exists n* G N
such that J* C {1, . . . ,n*} and this implies v{P n *) > v(J*). Thus, lim„_ i . 00 v{P n ) > sup{v(J) :
J is a finite subset of /} = v(FDSILP) where the equality follows from Theorem 18.31 □
Corollary 8.5 (Karney [13 Theorem 2.1). If the feasible region of (|SILP|) with I == N is
nonempty and bounded, then \im n ^ QO v(P n ) = i; (jSILPp .
Proof. This follows from Theorem 13.251 and Corollary 18.41 □
Corollary 8.6 (Karney [10( Theorem 2.4). If (|SILP|) with I = N is feasible and the zero vector
is the unique solution to the system (|8.1j) - ()8.2|) . then linin^oo v(P n ) — -u (|SILP|) .
Proof. If the zero vector is the unique solution to the system (|8.1j) - (|8.2j) . then the recession cone
of (|3.18j) is {0} and (|3.18j) is bounded for any value of 7 such that (|3.18j) is feasible (such a 7 exists
because (jSILPjl is feasible). The result then follows from Theorem l3.25l and Corollarv l8.4l □
Corollary 8.7 (Karney [l(| Theorem 2.5). Assume (|SILP|) with I = N is feasible and let r be
a ray satisfying (|8.ip - (|8.2|) . If r is not an element of the null space TV, then lim„^oo v(P n ) =
v tiSTLPl = -00.
Proof. If r £ K and r £ N, then c T r < 0. This implies ^ (jSlLP]) = -00 and (jFDSILPp is
infeasible by weak duality. Then f (jSILPp = i' (|FDSILPp = — 00 and the result follows from
Corollary 111 □
Corollary 8.8 (Karney [10] Theorem 2.6). If (jSILPp is feasible and KC\ N is a linear subspace,
then lim^oo v(P n ) = ^ (|SILP|) .
Proof. This follows from Theorem [5?2l and Corollary [5^41 D
39
9 Conclusion
This paper explores two related themes. The first is how the powerful extension of Fourier-
Motzkin elimination to semi-infinite systems of linear inequalities is used to prove and provide
insights about duality theory for semi- infinite linear programs. This was the topic of Section [3]
where projection is used to characterize feasibility, boundedness, solvability and the duality
gap between primal and dual semi-infinite linear programs. In Sections [7] and [5] we established
connections between our approach and the duality theories of Goberna and Lopez [9( and Kar-
ney [10J respectively. In particular, we prove the generalized Farkas' theorem in Section [Jj a
result which forms the basis of most of Goberna and Lopez's arguments. Hence, in principle,
their work can be obtained from the Fourier- Motzkin approach. In Section |8l we explicitly show
how Karney's results follow directly from the Fourier-Motzkin approach. This underscores our
claim that projection is a universal and unifying approach to the study of semi-infinite linear
programming.
The second theme is that semi-infinite linear programming has implications for finite dimen-
sional convex optimization. Sections [5] and [5] illustrate how both well-known and lesser-known
duality results in conic and convex programming are special cases of semi-infinite linear pro-
gramming duality.
The connection between semi-infinite linear programming and convex optimization is made
clear by the method of projection. Fourier-Motzkin elimination is purely algebraic. It is simply
the aggregation of pairs of linear inequalities using nonnegative multipliers. The key insight
is that topological conditions common in duality theory of finite-dimensional convex optimiza-
tion are implied by the algebraic conditions for solvability and duality in semi-infinite linear
programming via projection.
Both themes, and the connections between them, deserve further exploration. Regarding the
first, it might be fruitful to further explore the connections between our characterization of zero
duality gap and the characterization presented in Theorem 8.2 of Goberna and Lopez [9(]. Gob-
erna and Lopez's approach is topological and based on separating hyperplane theory, whereas
our approach is purely algebraic. Our proof of the generalized Farkas' theorem (see our Theo-
rem [7j] and Theorem 3.1 in Goberna and Lopez |9j) provides a useful starting point for further
exploration.
Regarding the second theme, there are at least two avenues for further research. First, all
the duality results for finite-dimensional convex optimization considered here were derived by
showing the associated semi-infinite linear program was tidy. Recall that when (jSILPj) is tidy,
lim^oo (jj(6) = — oo. This condition (along with primal feasibility) suffices to establish primal
solvability (Theorem 13. 10|) and zero duality gap (Theorem I3.21|) . However, tidiness is far from
necessary, as demonstrated in Examples 13.121 and 16.51 Exploring how to translate more subtle
sufficient conditions for zero duality gap arising from finite values for lim5_ > . 00 ui(S) into the
language of finite dimensional convex optimization could prove fruitful.
A second avenue is to examine algorithmic approaches to solving convex programs from
the viewpoint of semi-infinite programming. As an example, Wolfe [13j proposed a method for
solving (|CP|) using column generation. See also Dantzig [3| . The restricted master of Dantzig
and Wolfe corresponds to a modified (CP-FDSILP) containing a finite subset of columns. At
each step of the Dantzig and Wolfe algorithm, a column with a negative reduced cost is added
to the current restricted master. This results in a new restricted master with one more column.
Dantzig [3] proves that the optimal value of the restricted master converges to the optimal value
of the convex program (ICP[) as the number of iterations (columns in the restricted master)
goes to infinity. In other words, once the number of columns becomes infinite, it is possible
to recover the optimal value of the convex program. It would be an interesting project to see
if an alternate proof of Dantzig's result, and possibly further insight into his algorithm, derive
from a deeper understanding of the semi-infinite linear programs (CP-SILP) and (CP-FDSILP)
40
associated with the convex program (|CP|) .
This paper has not addressed the algorithmic aspects of Fourier-Motzkin elimination applied
to semi-infinite linear programs. Obviously, when applied to semi-infinite linear programs,
Fourier-Motzkin elimination is not a finite process. However, if the functions b, a k G M. 1 for
k = 1, . . . , n could be characterized in a reasonably simple format, then symbolic elimination
might be possible. This is another avenue of research.
References
[1] E.J. Anderson and P. Nash. Linear programming in infinite- dimensional spaces: theory
and applications. Wiley, 1987.
[2] A. Charnes, WW Cooper, and K. Kortanek. Duality in semi-infinite programs and some
works of Haar and Caratheodory. Management Science, 9(2):209-228, 1963.
[3] G. B. Dantzig. Linear Programming and Extensions. Princeton University Press, Princeton,
NJ, 1963.
[4] R.J. Duffin. Infinite programs. In H. W. Kuhn and A. W. Tucker, editors, Linear In-
equalities and Related Systems, pages 157-170. Princeton University Press, Princeton, NJ,
1956.
[5] R.J. Duffin. Clark's theorem on linear programs holds for convex programs. Proceedings of
the National Academy of Sciences, 75(4):1624-1626, 1978.
[6] R.J. Duffin and L.A. Karlovitz. An infinite linear program with a duality gap. Management
Science, 12:122-134, 1965.
[7] J. B. J. Fourier. Solution d'une question particuliere du calcul des inegalites. Oeuvres II
Pans, pages 317-328, 1826.
[8] B. Gartner and J. Matousek. Approximation Algorithms and Semi-Definite Programming.
Springer- Verlag, 2012.
[9] M.A. Goberna and M.A. Lopez. Linear semi-infinite optimization. John Wiley & Sons
Chichester, 1998.
[10] D. F. Karney. Duality gaps in semi-infinite linear programming - an approximation prob-
lem. Mathematical Programming, 20:129-143, 1981.
[11] T. S. Motzkin. Beitrage zur Theorie der Linearen Ungleichungen. PhD thesis, University
of Besel, Jerusalem, 1936.
[12] H. P. Williams. Fourier's method of linear programming and its dual. The American
Mathematical Monthly, 93:681-695, 1986.
[13] P. Wolfe. Methods of nonlinear programming. In J. Abadie, editor, Nonlinear Programming,
pages 100-142. John Wiley and Sons, New York, NY, 1967.
41