Linear Optimization

High-Probability Polynomial-Time Complexity of Restarted PDHG for Linear Programming

Categories Linear Programming Tags , , ,

The restarted primal-dual hybrid gradient method (rPDHG) is a first-order method recently known for its computational effectiveness in solving linear programming (LP) problems. Despite its impressive practical performance, the theoretical iteration bounds for rPDHG can be exponentially poor. To investigate this gap from a probabilistic perspective, we show that rPDHG achieves polynomial-time complexity in a … Read more

Computing Weak Counterfactual Explanations for Linear Optimization: A New Class of Bilevel Models and a Tailored Penalty Alternating Direction Method

Categories Energy, Nonlinear Optimization, Optimization in Data Science Tags , , , ,

In recent years, significant attention has been devoted to the issue of explainability in automated decision-making tools. The idea is to explain the outcome of a model by presenting a certain change in the input of the model so that the outcome changes significantly. In this paper, we study this question for linear optimization problems … Read more

Accessible Complexity Bounds for Restarted PDHG on Linear Programs with a Unique Optimizer

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 \(O\left(\kappa\Phi\cdot\ln\left(\frac{\kappa\Phi\|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 \(\Phi\) … Read more

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

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

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

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

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

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