Linear Optimization

Accessible Theoretical Complexity of the Restarted Primal-Dual Hybrid Gradient Method for Linear Programs with Unique Optima

  • Zikai Xiong
    • Categories Convex Optimization, Linear Programming, Nonsmooth Optimization Tags , , ,

    \(\) The restarted primal-dual hybrid gradient method (rPDHG) has recently emerged as an important tool for solving large-scale linear programs (LPs). For LPs with unique optima, we present an iteration bound of \(\widetilde{O}\left(\kappa\Phi\cdot\ln\left(\frac{\|w^*\|}{\varepsilon}\right)\right)\), where \(\varepsilon\) is the target tolerance, \(\kappa\) is the standard matrix condition number, \(\|w^*\|\) is the norm of the optimal solution, and … Read more

    The Role of Level-Set Geometry on the Performance of PDHG for Conic Linear Optimization

  • Zikai Xiong
  • Robert M. Freund
    • Categories Convex Optimization, Linear Programming, Linear, Cone and Semidefinite Programming Tags , , , , ,

    We consider solving huge-scale instances of (convex) conic linear optimization problems, at the scale where matrix-factorization-free methods are attractive or necessary. The restarted primal-dual hybrid gradient method (rPDHG) — with heuristic enhancements and GPU implementation — has been very successful in solving huge-scale linear programming (LP) problems; however its application to more general conic convex … Read more

    Counterfactual Explanations for Linear Optimization

  • Jannis Kurtz
  • Ş. İlker Birbil
  • Dick den Hertog
    • Categories Applications - OR and Management Sciences, Linear Programming Tags , , ,

    The concept of counterfactual explanations (CE) has emerged as one of the important concepts to understand the inner workings of complex AI systems. In this paper, we translate the idea of CEs to linear optimization and propose, motivate, and analyze three different types of CEs: strong, weak, and relative. While deriving strong and weak CEs … Read more

    Computational Guarantees for Restarted PDHG for LP based on “Limiting Error Ratios” and LP Sharpness

  • Zikai Xiong
  • Robert M. Freund
    • Categories Convex Optimization, Linear Programming, Linear, Cone and Semidefinite Programming Tags , , , , , , ,

    In recent years, there has been growing interest in solving linear optimization problems – or more simply “LP” – using first-order methods in order to avoid the costly matrix factorizations of traditional methods for huge-scale LP instances. The restarted primal-dual hybrid gradient method (PDHG) – together with some heuristic techniques – has emerged as a … Read more

    On the Relation Between LP Sharpness and Limiting Error Ratio and Complexity Implications for Restarted PDHG

  • Zikai Xiong
  • Robert M. Freund
    • Categories Convex Optimization, Linear Programming, Linear, Cone and Semidefinite Programming Tags , , , , , , ,

    There has been a recent surge in development of first-order methods (FOMs) for solving huge-scale linear programming (LP) problems. The attractiveness of FOMs for LP stems in part from the fact that they avoid costly matrix factorization computation. However, the efficiency of FOMs is significantly influenced – both in theory and in practice – by … Read more

    Efficient Use of Quantum Linear System Algorithms in Interior Point Methods for Linear Optimization

  • Mohammadhossein Mohammadisiahroudi
  • Ramin Fakhimi
  • Tamás Terlaky
    • Categories Linear Programming Tags , , ,

    Quantum computing has attracted significant interest in the optimization community because it potentially can solve classes of optimization problems faster than conventional supercomputers. Several researchers proposed quantum computing methods, especially Quantum Interior Point Methods (QIPMs), to solve convex optimization problems, such as Linear Optimization, Semidefinite Optimization, and Second-order Cone Optimization problems. Most of them have … Read more