Files in this item



application/pdf8026534.pdf (3MB)Restricted to U of Illinois
(no description provided)PDF


Title:Duality and Approximation in Semi-Infinite Programs
Author(s):Karney, Dennis F.
Department / Program:Mathematics
Degree Granting Institution:University of Illinois at Urbana-Champaign
Abstract:Consider the standard semi-infinite 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' (L-HOOK 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 semi-infinite programs.
Issue Date:1980
Description:110 p.
Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 1980.
Other Identifier(s):(UMI)AAI8026534
Date Available in IDEALS:2014-12-14
Date Deposited:1980

This item appears in the following Collection(s)

Item Statistics