Optimization Online


On the sufficiency of finite support duals in semi-infinite linear programming

Amitabh Basu(abasu***at***math.ucdavis.edu)
Kipp Martin(kmartin***at***chicagobooth.edu)
Christopher Ryan(chris.ryan***at***chicagobooth.edu)

Abstract: We consider semi-infinite linear programs with countably many constraints indexed by the natural numbers. When the constraint space is the vector space of all real valued sequences, we show the finite support (Haar) dual is equivalent to the algebraic Lagrangian dual of the linear program. This settles a question left open by Anderson and Nash~\cite{anderson-nash}. This result implies that if there is a duality gap between the primal linear program and its finite support dual, then this duality gap cannot be closed by considering the larger space of dual variables that define the algebraic Lagrangian dual. However, if the constraint space corresponds to certain subspaces of all real-valued sequences, there may be a strictly positive duality gap with the finite support dual, but a zero duality gap with the algebraic Lagrangian dual.

Keywords: Semi-infinite linear programs, Langrangian duality

Category 1: Infinite Dimensional Optimization (Semi-infinite Programming )


Download: [PDF]

Entry Submitted: 04/13/2013
Entry Accepted: 04/13/2013
Entry Last Modified: 04/13/2013

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society