(navigation image)
Home American Libraries | Canadian Libraries | Universal Library | Community Texts | Project Gutenberg | Children's Library | Biodiversity Heritage Library | Additional Collections
Search: Advanced Search
Anonymous User (login or join us)
Upload
See other formats

Full text of "Projection: A Unified Approach to Semi-Infinite Linear Programs and Duality in Convex Programming"

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