Speaker: Amitabh Basu, Johns Hopkins University
Projection: A Unified Approach to Semi-Infinite Linear Optimization and Duality in Convex Programming
Fourier-Motzkin elimination was invented as an explicit projection algorithm for polyhedra and can be used to encode a lot of information in instances of linear optimization with finitely many constraints.
We extend Fourier-Motzkin elimination to semi-infinite linear programs, i.e., linear optimization problems 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.
This extension of the Fourier-Motzkin elimination procedure yields a new classification of variables that is used to determine the existence of duality gaps. Our approach has interesting applications in finite-dimensional convex optimization, such as completely new proofs of classical sufficient conditions for zero duality like Slater's condition. Time permitting, I will also mention some new insights obtained from this approach into the the structure of semi-infinite linear programs.
Department of Mathematical Sciences
George Mason University
4400 University Drive, MS 3F2
Fairfax, VA 22030-4444
Tel. 703-993-1460, Fax. 703-993-1491