Abstract: We revisit two classical optimization tasks that arise across scientific computing, economics, and network modeling: (1) scaling a symmetric positive definite matrix by a positive diagonal so that all row and column sums are equal to one, and (2) minimizing a convex quadratic function subject to non-negativity constraints. Both problems lend themselves to efficient algorithms based on interior point methods (IPMs), for which the classical self-concordance theory of Nesterov and Nemirovski implies a O(n^(1/2)) worst-case iteration bound in dimension n.
We show that when the input matrix is an M-matrix -- a class that includes graph Laplacians and discretized diffusion operators -- a standard log-barrier IPM equipped with adaptive step size selection solves both problems in only O(n^(1/3)) iterations, with polylogarithmic depth and nearly-linear work per iteration. This provides a notable instance where an IPM provably surpasses the O(n^(1/2)) iteration barrier. As a consequence, we obtain faster solutions for applications including flow diffusion in networks, optimal stopping in Markov chains, load shedding in resistive DC power grids, Leontief market equilibrium computation, and group-constrained portfolio optimization.
Appears in STOC 2025. Full version: arXiv:2504.20619
