Author
Listed:
- Zhaonan Qu
(Department of Economics, Stanford University, Stanford, California 94305; and Department of Management Science and Engineering, Stanford University, Stanford, California 94305)
- Wenzhi Gao
(Institute for Computational and Mathematical Engineering (ICME), Stanford University, Stanford, California 94305)
- Oliver Hinder
(Department of Industrial Engineering, University of Pittsburgh, Pittsburgh, Pennsylvania 15213)
- Yinyu Ye
(Department of Management Science and Engineering, Stanford University, Stanford, California 94305)
- Zhengyuan Zhou
(NYU Stern School of Business, New York University, New York, New York 10012)
Abstract
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.
Suggested Citation
Zhaonan Qu & Wenzhi Gao & Oliver Hinder & Yinyu Ye & Zhengyuan Zhou, 2025.
"Optimal Diagonal Preconditioning,"
Operations Research, INFORMS, vol. 73(3), pages 1479-1495, May.
Handle:
RePEc:inm:oropre:v:73:y:2025:i:3:p:1479-1495
DOI: 10.1287/opre.2022.0592
Download full text from publisher
Corrections
All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:oropre:v:73:y:2025:i:3:p:1479-1495. See general information about how to correct material in RePEc.
If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.
We have no bibliographic references for this item. You can help adding them by using this form .
If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.
For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .
Please note that corrections may take a couple of weeks to filter through
the various RePEc services.