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

## See other formats

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