To obtain a primal-dual pair of conic programming problems having zero duality gap, two methods have been proposed: the facial reduction algorithm due to Borwein and Wolkowicz [1,2] and the conic expansion method due to Luo, Sturm, and Zhang [5]. We establish a clear relationship between them. Our results show that although the two methods can be regarded as dual to each other, the facial reduction algorithm can produce a finer sequence of faces including the feasible region. We illustrate the facial reduction algorithm in LP, SOCP and an example of SDP. A simple proof of the convergence of the facial reduction algorithm for conic programming is also presented.
Citation
Technical Report CS-09-01, Department of Computer Science, The University of Electro-Communications