Strong Duality in Conic Linear Programming: Facial Reduction and Extended Duals
By Gábor Pataki. 2013
106 citations recorded by the source corpus.
The facial reduction algorithm (FRA) of Borwein and Wolkowicz and the extended dual of Ramana provide a strong dual for the conic linear program $$\displaystyle{ \sup \,\{\,\langle c,x\rangle \,\vert \,Ax \leq _{K}b\,\} }$$ (P) in the absence of any constraint qualification. The FRA 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 simple and self-contained exposition of facial reduction, of extended duals, and generalize Ramana’s dual: We state a simple FRA and prove its correctness. Building on this algorithm we construct a family of extended duals when K is a nice cone. This class of cones includes the semidefinite cone and other important cones.
Subfields: Computational Mechanics, Computational Theory and Mathematics, Numerical Analysis
View Paper: https://www.semanticscholar.org/paper/7f03c104312f448ca6cfe4c225a22629dd146022
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Computational Theory and Mathematics
In Numerical Analysis
Citations in the corpus
- Open problems in the theory of completely positive and copositive matrices (2015, background): “Facial exposedness of a cone and the related concept of niceness of a cone (see [51]) play a role in optimization, since for nice cones it is possible to design so called facial reduction algorithms (cf. [52] and references therein).”