Optimization Online


Facial reduction algorithms for conic optimization problems

Hayato Waki (hayato.waki***at***jsb.cs.uec.ac.jp)
Masakazu Muramatsu (muramatu***at***cs.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

  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 Programming Society