- Strong duality in conic linear programming: facial reduction and extended duals Gabor Pataki(gaborunc.edu) Abstract: The facial reduction algorithm of Borwein and Wolkowicz and the extended dual of Ramana provide a strong dual for the conic linear program (P) \sup { | Ax \leq_K b} in the absence of any constraint qualification. The facial reduction algorithm solves a sequence of auxiliary optimization problems to obtain such a dual. Ramana's dual is applicable when (P) is a semidefinite program (SDP) and is an explicit SDP itself. Ramana, Tuncel, and Wolkowicz showed that these approaches are closely related; in particular, they proved the correctness of Ramana's dual using certificates from a facial reduction algorithm. Here we give a clear and self-contained exposition of facial reduction, of extended duals, and generalize Ramana's dual: -- we state a simple facial reduction algorithm and prove its correctness; and -- building on this algorithm we construct a family of extended duals when $K$ is a {\em nice} cone. This class of cones includes the semidefinite cone and other important cones. Keywords: Conic linear programming; minimal cone; semidefinite progr amming; facial reduction; extended duals; nice cones Category 1: Linear, Cone and Semidefinite Programming Category 2: Linear, Cone and Semidefinite Programming (Semi-definite Programming ) Category 3: Convex and Nonsmooth Optimization (Convex Optimization ) Citation: Download: [PDF]Entry Submitted: 02/13/2013Entry Accepted: 02/13/2013Entry Last Modified: 02/13/2013Modify/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 Optimization Online is supported by the Mathematical Optmization Society.