Optimization Online


Projection: A Unified Approach to Semi-Infinite Linear Programs and Duality in Convex Programming

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

Abstract: Fourier-Motzkin elimination is a projection algorithm for solving finite linear programs. We extend Fourier-Motzkin elimination to semi-infinite linear programs which are linear programs with finitely many variables and infinitely many constraints. Applying projection leads to new characterizations of important properties for primal-dual pairs of semi-infinite programs such as zero duality gap, feasibility, boundedness, and solvability. Extending the Fourier-Motzkin elimination procedure to semi-infinite linear programs yields a new classification of variables that is used to determine the existence of duality gaps. In particular, the existence of what the authors term dirty variables can lead to duality gaps. Our approach has interesting applications in finite-dimensional convex optimization. For example, sufficient conditions for a zero duality gap, such as existence of a Slater point, are reduced to guaranteeing that there are no dirty variables. This leads to completely new proofs of such sufficient conditions for zero duality.

Keywords: Semi-infinite linear programs, convex optimization, conic programs, Fourier-Motzkin elimination, duality

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

Category 2: Convex and Nonsmooth Optimization (Convex Optimization )

Category 3: Linear, Cone and Semidefinite Programming


Download: [PDF]

Entry Submitted: 04/05/2013
Entry Accepted: 04/05/2013
Entry Last Modified: 04/05/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