  


Infeasibility detection with primaldual hybrid gradient for largescale linear programming
David Applegate(dapplegategoogle.com) Abstract: We study the problem of detecting infeasibility of largescale linear programming problems using the primaldual hybrid gradient method (PDHG) of Chambolle and Pock (2011). The literature on PDHG has mostly focused on settings where the problem at hand is assumed to be feasible. When the problem is not feasible, the iterates of the algorithm do not converge. In this scenario, we show that the iterates diverge at a controlled rate towards a welldefined ray. The direction of this ray is known as the infimal displacement vector $v$. The first contribution of our work is to prove that this vector recovers certificates of primal and dual infeasibility whenever they exist. Based on this fact, we propose a simple way to extract approximate infeasibility certificates from the iterates of PDHG. We study three different sequences that converge to the infimal displacement vector: the difference of iterates, the normalized iterates, and the normalized average. All of them are easy to compute, and thus the approach is suitable for largescale problems. Our second contribution is to establish tight convergence rates for these sequences. We demonstrate that the normalized iterates and the normalized average achieve a convergence rate of $O\left(\frac{1}{k}\right)$, improving over the known rate of $O\left(\frac{1}{\sqrt{k}}\right)$. This rate is general and applies to any fixedpoint iteration of a nonexpansive operator. Thus, it is a result of independent interest since it covers a broad family of algorithms, including, for example, ADMM, and can be applied settings beyond linear programming, such as quadratic and semidefinite programming. Further, in the case of linear programming we show that, under nondegeneracy assumptions, the iterates of PDHG identify the active set of an auxiliary feasible problem in finite time, which ensures that the difference of iterates exhibits eventual linear convergence to the infimal displacement vector. Numerical experiments on \emph{Netlib} dataset of infeasible LP instances verify our theoretical results. Keywords: Infeasibility detection, linear programming, first order methods, largescale Category 1: Linear, Cone and Semidefinite Programming (Linear Programming ) Category 2: Convex and Nonsmooth Optimization (Convex Optimization ) Citation: Download: [PDF] Entry Submitted: 03/02/2021 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  