Files in this item
Files  Description  Format 

application/pdf 8026534.pdf (3MB)  (no description provided) 
Description
Title:  Duality and Approximation in SemiInfinite Programs 
Author(s):  Karney, Dennis F. 
Department / Program:  Mathematics 
Discipline:  Mathematics 
Degree Granting Institution:  University of Illinois at UrbanaChampaign 
Degree:  Ph.D. 
Genre:  Dissertation 
Subject(s):  Mathematics 
Abstract:  Consider the standard semiinfinite linear program P with optimal value MP. For a dual program choose the formal dual program D of Charnes, Cooper and Kortanek with optimal value MD. A straightforward calculation shows that MP (GREATERTHEQ) MD. Numerous examples due to Duffin, Karlovitz, Kortanek, Jeroslow and Rockafellar show that it is possible for MP to be strictly greater than MD. If this occurs, then a duality gap exists between Programs P and D. Let MP(,n) be the optimal value of the primal program subject to only the first n constraints. A classical result of Duffin and Karlovitz states that MP(,n) converges to MP if and only if there is no duality gap between Programs P and D. The starting point of this thesis is the derivation of sufficient conditions for MP(,n) to converge to MP. Let be the objective function of Program P, let N be the null space of and let K(DEGREES) be the recession cone of the feasible region. An examination of the relationship between K(DEGREES) and N yields the following result. THEOREM: If the feasible region of Program P is nonempty and K(DEGREES)(INTERSECT) N is a subspace, then MP(,n) converges to MP. This result implies that a duality gap can occur only when K(DEGREES) (INTERSECT) N is not a subspace. Since K(DEGREES) can be written in the form M+K' where M = K(DEGREES) (INTERSECT) (K(DEGREES)), K' (LHOOK EQ) M('(PERP)) and K' (INTERSECT) (K') = {0}, it follows that a duality gap can occur only when K' (INTERSECT) N (NOT=) {0}. In this case, it is not necessary to decide if a duality gap exists in order to solve Program P. THEOREM. If K' (INTERSECT) N is not zero, then there is a vector d such that the intersection of the nullspace of and K' is zero for all positive (epsilon) less than one. Define a new program, P(,(epsilon)), whose objective function is of the above theorem and whose constraints are the constraints of Program P. Let MP(,(epsilon)) be the optimal value of Program P(,(epsilon)). As (epsilon) tends to zero, the values MP(,(epsilon)) converge to MP. In fact, each Program P(,(epsilon)) has an optimal solution x(,(epsilon)) and the values converge to MP as (epsilon) tends to zero. In summary, when K' (INTERSECT) N is not zero, Program P can be linearly perturbed to a program P(,(epsilon)) which does not have a duality gap and as (epsilon) tends to zero, the values MP(,(epsilon)) converge to MP. In the remainder of the thesis, the theory of recession functions is used to extend the above linear results to convex programs. From these extensions, duality results for the limiting Lagrangian are derived and Clark's theorem is extended to semiinfinite programs. 
Issue Date:  1980 
Type:  Text 
Language:  English 
Description:  110 p. Thesis (Ph.D.)University of Illinois at UrbanaChampaign, 1980. 
URI:  http://hdl.handle.net/2142/68174 
Other Identifier(s):  (UMI)AAI8026534 
Date Available in IDEALS:  20141214 
Date Deposited:  1980 
This item appears in the following Collection(s)

Dissertations and Theses  Mathematics

Graduate Dissertations and Theses at Illinois
Graduate Theses and Dissertations at Illinois