Book chapter
A Perturbation-Based Duality Classification for Max-Flow Min-Cut Problems of Strang and Iri
Mathematical programming with data perturbations, pp.285-303
Marcel Dekker
1998
DOI: 10.1201/9781003072119-13
Abstract
A definitive classification is established for all conceivable and permissible duality states of two slightly different versions (Strang and Iri) of infinite dimensional max–flow min–cut dual optimization problems. The approach builds on three elements: (1) previous work of the first author on duality gaps in max–flow problems under appropriate choices of function spaces, (2) construction of a class of perturbations in infinite convex optimizations germane to max–flow, and (3) a previously published classification theory of duality states defined by combinations of (extended) extremal values of closed convex bifunction dual families and their homogeneous derivant bifunctions.
A definitive classification is established for all conceivable and permissible duality states of two slightly different versions (Strang and Iri) of infinite dimensional max–flow min–cut dual optimization problems. This chapter investigates the properties of asymptotic duality that arise from the closure operation applied to a class of perturbations in general convex programming, typically developed in convex bifunction form. The perturbation approach is applicable to a wide class of convex programming problems, and different problems can give rise to their own classes of perturbations. The chapter defines and establishes existence of all duality states for the function-theoretic construction of infinite max–flow min–cut problems developed by Gilbert Strang and developed by Masao Iri. G. Strang formulated a pair of optimization problems over a Euclidean domain which are closely related to some problems in mechanics principally in plastic limit analysis, see R. Kohn and R. Temam and E. Christiansen.
Details
- Title: Subtitle
- A Perturbation-Based Duality Classification for Max-Flow Min-Cut Problems of Strang and Iri
- Creators
- Ryôhei Nozawa - Sapporo Medical UniversityK. O. Kortanek - University of Iowa
- Contributors
- Anthony V. Fiacco (Editor)
- Resource Type
- Book chapter
- Publication Details
- Mathematical programming with data perturbations, pp.285-303
- DOI
- 10.1201/9781003072119-13
- Publisher
- Marcel Dekker; New York
- Number of pages
- 19
- Alternative title
- Duality Classification for Max-Flow Min-Cut Problems of Strang and Iri
- Language
- English
- Date published
- 1998
- Academic Unit
- Business Analytics
- Record Identifier
- 9984963079202771
Metrics
1 Record Views