Facial Reduction and Partial Polyhedrality
Facial Reduction and Partial Polyhedrality
复制标题
DOI：
10.1137/15m1051634
复制
发表时间：
2015-12
期刊：
影响因子：
--
通讯作者：
Bruno F. Lourenço;M. Muramatsu;T. Tsuchiya
中科院分区：
文献类型：
--
作者：
Bruno F. Lourenço;M. Muramatsu;T. Tsuchiya
我们提出了FRA-Poly，这是一种面部还原算法（FRA），用于圆锥线性程序，该程序对锥体中的多面体面部敏感。 FRA和FRA-POLY的主要目标是相同的，即，找到包含可行区域并检测出可能性的最小面孔，但是FRA-Poly可以分别处理多面体约束。当有许多线性不平等约束时，这个想法使我们能够大大减少迭代次数。 FRA-POLY的迭代次数最差的情况数是用“与多面腺的距离”的术语编写的，并且在轻度条件下提供了比FRA更好的界限。特别是，在双重非负锥的情况下，FRA-POLY给出了最坏的情况，而经典的FRA为$ \ Mathcal {o}（o}（n^2）$。我们可能会产生独立的兴趣，这证明了Gordan-Stiemke定理的一种变体，并考虑了一个适当的分离定理，该定理考虑了部分多面的多面性。我们提供了有关最佳面部减少策略的讨论，并迫使FRAS执行许多步骤。我们还提供了一些应用程序。特别是，我们将使用FRA-POLY来改善Liu和Pataki最近在某些出现在弱不可行的问题中的某些仿射子空间的维度上获得的界限。
We present FRA-Poly, 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 FRA-Poly are the same, i.e., finding the minimal face containing the feasible region and detecting infeasibility, but FRA-Poly 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 FRA-poly 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, FRA-Poly gives a worst case bound of $n$ whereas the classical FRA is $\mathcal{O}(n^2)$. Of possible independent interest, we prove a variant of Gordan-Stiemke'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 FRA-poly to improve the bounds recently obtained by Liu and Pataki on the dimension of certain affine subspaces which appear in weakly infeasible problems.