Worst-case analysis of restarted primal-dual hybrid gradient on totally unimodular linear programs

Abstract

We analyze restarted PDHG on totally unimodular linear programs. In particular, we show that restarted PDHG finds an $\epsilon$-optimal solution in $O(H{m}_1^{2.5}\sqrt{\text{nnz}(A)}\log (H{m}_2/\epsilon ))$ matrix-vector multiplies where $m_1$ is the number of constraints, $m_2$ the number of variables, $\text{nnz}(A)$ is the number of nonzeros in the constraint matrix, $H$ is the largest absolute coefficient in the right hand side or objective vector, and $\epsilon$ is the distance to optimality of the outputted solution.

10 pages. Fixed a typo in Table 1 caption