Cover Image

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

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Xiong, Zikai, Freund, Robert Michael
Format:	Preprint
Published:	2023
Subjects:	Optimization and Control
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

On the Relation Between LP Sharpness and Limiting Error Ratio and Complexity Implications for Restarted PDHG
by: Xiong, Zikai, et al.
Published: (2023)

High-Probability Polynomial-Time Complexity of Restarted PDHG for Linear Programming
by: Xiong, Zikai
Published: (2025)

Accessible Complexity Bounds for Restarted PDHG on Linear Programs with a Unique Optimizer
by: Xiong, Zikai
Published: (2024)

The Role of Level-Set Geometry on the Performance of PDHG for Conic Linear Optimization
by: Xiong, Zikai, et al.
Published: (2024)

A New Crossover Algorithm for LP Inspired by the Spiral Dynamic of PDHG
by: Liu, Tianhao, et al.
Published: (2024)

Restarted Halpern PDHG for Linear Programming
by: Lu, Haihao, et al.
Published: (2024)

Using Taylor-Approximated Gradients to Improve the Frank-Wolfe Method for Empirical Risk Minimization
by: Xiong, Zikai, et al.
Published: (2022)

Connecting Max-entropy With Computational Geometry, LP And SDP
by: Lasserre, Jean B
Published: (2026)

An LP-Based Approach for Bilinear Saddle Point Problem with Instance-dependent Guarantee and Noisy Feedback
by: Jiang, Jiashuo, et al.
Published: (2026)

LP Relaxations for Routing and Wavelength Assignment with Partial Path Protection: Formulations and Computations
by: Yang, Xianyan, et al.
Published: (2025)

Presolving for GPU-Accelerated First-Order LP Solvers
by: Cederberg, Daniel, et al.
Published: (2026)

Concurrent Crossover for PDHG
by: Rothberg, Edward
Published: (2025)

Data-driven approximation of regions of attraction via an LP-based selection of PWA Lyapunov functions
by: Khattabi, Oumayma, et al.
Published: (2026)

Efficient LP warmstarting for linear modifications of the constraint matrix
by: Derval, Guillaume, et al.
Published: (2025)

Backing PDHG into a Corner
by: Rothberg, Edward
Published: (2025)

Batched First-Order Methods for Parallel LP Solving in MIP
by: Blin, Nicolas, et al.
Published: (2026)

Global relaxation-based LP-Newton method for multiple hyperparameter selection in support vector classification with feature selection
by: Qian, Yaru, et al.
Published: (2023)

Hybridizing PDHG and Interior-Point Methods
by: Rothberg, Edward
Published: (2026)

Enhanced PDHG for Linear Programming with Online Preconditioning
by: Lu, Haihao, et al.
Published: (2025)

LP-Based Algorithms for Scheduling in a Quantum Switch
by: Srikant, R.
Published: (2026)

Function-free Optimization via Comparison Oracles
by: Scheinberg, Katya, et al.
Published: (2026)

A Lyapunov Analysis of Accelerated PDHG Algorithms
by: Zeng, Xueying, et al.
Published: (2024)

Competitive Equilibrium for Chores: from Dual Eisenberg-Gale to a Fast, Greedy, LP-based Algorithm
by: Chaudhury, Bhaskar Ray, et al.
Published: (2024)

A compact implementation of a recently proposed strongly polynomial-time algorithm for the general LP problem
by: Awoniyi, Samuel
Published: (2025)

Monitoring the Convergence Speed of PDHG to Find Better Primal and Dual Step Sizes
by: Fercoq, Olivier
Published: (2024)

Understanding the PDHG Algorithm via High-Resolution Differential Equations
by: Li, Bowen, et al.
Published: (2024)

Decentralized Concurrent Learning with Coordinated Momentum and Restart
by: Ochoa, Daniel E., et al.
Published: (2024)

Predict-then-Calibrate: A New Perspective of Robust Contextual LP
by: Sun, Chunlin, et al.
Published: (2023)

An Adaptive Parameter-free and Projection-free Restarting Level Set Method for Constrained Convex Optimization Under the Error Bound Condition
by: Lin, Qihang, et al.
Published: (2020)

The Integrality Gap of the Traveling Salesman Problem is $4/3$ if the LP Solution Has at Most $n+6$ Non-zero Components
by: Villa, Tullio, et al.
Published: (2025)

PDHG-Unrolled Learning-to-Optimize Method for Large-Scale Linear Programming
by: Li, Bingheng, et al.
Published: (2024)

Adaptive Acceleration Without Strong Convexity Priors Or Restarts
by: Cavalcanti, Joao V., et al.
Published: (2025)

A Technical Note on the Implementation and Use of PDCS
by: Lin, Zhenwei, et al.
Published: (2026)

Restarted contractive operators to learn at equilibrium
by: Davy, Leo, et al.
Published: (2025)

Time-Discretized Simulation of Vehicle Platoons for Safety Analysis with Guaranteed Error Bounds
by: Chen, Yuhao, et al.
Published: (2025)

Robust Accelerated Dynamics for Subnetwork Bilinear Zero-Sum Games with Distributed Restarting
by: Li, Weijian, et al.
Published: (2025)

Restart-Free (Accelerated) Gradient Sliding Methods for Strongly Convex Composite Optimization
by: Wu, Xinming, et al.
Published: (2026)

Neural Risk Limiting Dispatch in Power Networks: Formulation and Generalization Guarantees
by: Chen, Ge, et al.
Published: (2024)

Accelerating Low-Frequency Convergence for Limited-Angle DBT via Two-Channel Fidelity in PDHG
by: Iyadomi, Taro, et al.
Published: (2026)

Effective rates for continuous-time quasi-Fejér monotone dynamical systems
by: Freund, Anton, et al.
Published: (2026)