Optimal Diagonal Preconditioning

Preconditioning has long been a staple technique in optimization, often applied to reduce the condition number of a matrix and speed up the convergence of algorithms. Although there are many popular preconditioning techniques in practice, most lack guarantees on reductions in condition number, and the degree to which we can improve over existing heuristic preconditioners remains an important question. In this paper, we study the problem of optimal diagonal preconditioning that achieves maximal reduction in the condition number of any full-rank matrix by scaling its rows and/or columns with positive numbers. We first reformulate the problem as a quasiconvex optimization problem and provide a simple algorithm based on bisection. Then, we develop an interior point algorithm with $O(\log (1/ϵ))$ iteration complexity, where each iteration consists of a Newton update based on the Nesterov-Todd direction. Next, we specialize in one-sided optimal diagonal preconditioning problems and demonstrate that they can be formulated as standard dual semidefinite program (SDP) problems. We then develop efficient customized solvers for the SDP approach and study the empirical performance of our optimal diagonal preconditioning procedures through extensive experiments. Our findings suggest that optimal diagonal preconditioners can significantly improve upon existing heuristics-based diagonal preconditioners at reducing condition numbers, and our SDP approach can find such optimal preconditioners efficiently. We also extend our SDP approach to compute optimal mixtures of heuristic preconditioners, which further improves its scalability and applicability.

Funding: Z. Qu was supported by a Stanford Interdisciplinary Graduate Fellowship; W. Gao was supported in part by the National Natural Science Foundation of China (NSFC) [Grants NSFC-72150001, NSFC-72225009, NSFC-72394360, and NSFC72394365]; O. Hinder was supported by Pitt momentum funds and a Mascaro center for sustainable innovation faculty fellowship; Z. Zhou was supported by NSF Grant CCF [Grant 2312205] and the New York University Research Catalyst Prize.

Supplemental Material: The e-companion is available at https://doi.org/10.1287/opre.2022.0592.