Facial reduction algorithms for conic optimization problems

Hayato Waki (hayato.wakijsb.cs.uec.ac.jp)
Masakazu Muramatsu (muramatucs.uec.ac.jp)

Abstract: 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.

Keywords: Facial Reduction, Conic Programming

Category 1: Linear, Cone and Semidefinite Programming (Other )

Category 2: Convex and Nonsmooth Optimization (Convex Optimization )

Category 3: Global Optimization (Theory )

Citation: Technical Report CS-09-01, Department of Computer Science, The University of Electro-Communications

Download: [PDF]

Entry Submitted: 07/30/2009
Entry Accepted: 07/30/2009
Entry Last Modified: 08/14/2009

Modify/Update this entry