  


Projection: A Unified Approach to SemiInfinite Linear Programs and Duality in Convex Programming
Amitabh Basu(abasumath.ucdavis.edu) Abstract: FourierMotzkin elimination is a projection algorithm for solving finite linear programs. We extend FourierMotzkin elimination to semiinfinite linear programs which are linear programs with finitely many variables and infinitely many constraints. Applying projection leads to new characterizations of important properties for primaldual pairs of semiinfinite programs such as zero duality gap, feasibility, boundedness, and solvability. Extending the FourierMotzkin elimination procedure to semiinfinite 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 finitedimensional 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: Semiinfinite linear programs, convex optimization, conic programs, FourierMotzkin elimination, duality Category 1: Infinite Dimensional Optimization (Semiinfinite Programming ) Category 2: Convex and Nonsmooth Optimization (Convex Optimization ) Category 3: Linear, Cone and Semidefinite Programming Citation: Download: [PDF] Entry Submitted: 04/05/2013 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  