  


Facial Reduction and Partial Polyhedrality
Bruno F. Lourenco (lourencomist.i.utokyo.ac.jp) Abstract: We present FRAPoly, a facial reduction algorithm (FRA) for conic linear programs that is sensitive to the presence of polyhedral faces in the cone. The main goals of FRA and FRAPoly are the same, i.e., finding the minimal face containing the feasible region and detecting infeasibility, but FRAPoly treats polyhedral constraints separately. This idea enables us to reduce the number of iterations drastically when there are many linear inequality constraints. The worst case number of iterations for FRApoly is written in the terms of a "distance to polyhedrality" quantity and provides better bounds than FRA under mild conditions. In particular, in the case of the doubly nonnegative cone, FRAPoly gives an worst case bound proportional to O(n) whereas the classical FRA is O(n^2). Of possible independent interest, we prove a variant of GordanStiemke's Theorem and a proper separation theorem that takes into account partial polyhedrality. We provide a discussion on the optimal facial reduction strategy and an instance that forces FRAs to perform many steps. We also present a few applications. In particular, we will use FRApoly to improve the bounds recently obtained by Liu and Pataki on the dimension of certain affine subspaces which appear in weakly infeasible problems. Keywords: facial reduction, partial polyhedrality, weak infeasibility, doubly nonnegative cone Category 1: Linear, Cone and Semidefinite Programming Citation: Download: [PDF] Entry Submitted: 11/29/2015 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  