University of Illinois Urbana-Champaign

Duality and Approximation in Semi-Infinite Programs

Karney, Dennis F.

This item is only available for download by members of the University of Illinois community. Students, faculty, and staff at the U of I may log in with your NetID and password to view the item. If you are trying to access an Illinois-restricted dissertation or thesis, you can request a copy through your library's Inter-Library Loan office or purchase a copy directly from ProQuest.

Permalink

https://hdl.handle.net/2142/68174

Description

Title
Duality and Approximation in Semi-Infinite Programs
Author(s)
Karney, Dennis F.
Issue Date
1980
Department of Study
Mathematics
Discipline
Mathematics
Degree Granting Institution
University of Illinois at Urbana-Champaign
Degree Name
Ph.D.
Degree Level
Dissertation
Keyword(s)
Mathematics
Language
eng
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.
Graduation Semester
1980
Type of Resource
text
Permalink
http://hdl.handle.net/2142/68174

Owning Collections

Graduate Dissertations and Theses at Illinois PRIMARY
Graduate Theses and Dissertations at Illinois
Dissertations and Theses - Mathematics