Optimization Online


Strong duality in conic linear programming: facial reduction and extended duals

Gabor Pataki(gabor***at***unc.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 )


Download: [PDF]

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