Robert Freund, MIT

Geometric Condition Measures for First-Order Methods for Linear Programming: Theory, Re-Scaling, and Computation
Date
Oct 6, 2023, 10:00 am10:30 am
Location
Friend 006

Speakers

Details

Event Description

The primal-dual hybrid gradient method (PDHG) (with restarts and heuristic enhancements) has shown significant success in solving huge-scale LP problems, and our recent research has shown that this success relies on certain geometric condition measures of the LP related to error ratios and sharpness. However, these condition measures may take on extreme values and lead to poor performance both in theory and in practice, which begs the question of whether these geometric condition measures can be improved by applying suitable transformations of the given LP instance? We show in particular how column rescaling can improve these condition measures in theory (and lead to improved performance of PDHG in practice). Our theoretical development leads to guidelines for practical implementation of re-scaling based on ideas from analytic centers. Also, our experiments on LP relaxations of the MIPLIB 2017 dataset demonstrate the impact of rescaling on the actual performance of PDHG. This is joint work with Zikai Xiong.