A primal-dual algorithm for solving polyhedral conic systems with a finite-precision machine (Q2784423)

This paper describes a primal-dual interior-point algorithm that determines which one of two alternative systems: \(Ax=0\), \(x\geq 0\) and \(A^Ty\leq 0\) \((A\in \mathbb{R}^{m\times n})\) is strictly feasible, provided that this pair of systems is well-posed. Furthermore, when the second one is strictly feasible, the algorithm returns a strict solution \(y\); when the first system is strictly feasible, the algorithm returns a strict forward-approximate solution \(x\). The algorithm works with finite-precision arithmetic. The amount of precision required is adjusted as the algorithm progresses and remains bounded by a measure of well-posedness \(C(A)\) of the pair of systems of constraints. The algorithm halts in at most \(((m+n)^{1/2} (\log(C(A))+ |\log \gamma|))\) interior-point iterations, where \(\gamma\in (0,1)\) is a parameter specifying the desired degree of accuracy of the forward-approximate solution for the first system. If the feasible system is the second one, the term \(|\log \gamma|\) in the above expression can be dropped.