Cover Image

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

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Xiong, Zikai, Freund, Robert M.
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

Computational Guarantees for Restarted PDHG for LP based on "Limiting Error Ratios" and LP Sharpness
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)

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)

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

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

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

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)

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)

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)

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)

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

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

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)

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)

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)

Restarted Primal-Dual Hybrid Conjugate Gradient Method for Large-Scale Quadratic Programming
by: Huang, Yicheng, et al.
Published: (2024)

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

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

Nonlinear conjugate gradient methods: worst-case convergence rates via computer-assisted analyses
by: Gupta, Shuvomoy Das, et al.
Published: (2023)

A Practical GPU-Enhanced Matrix-Free Primal-Dual Method for Large-Scale Conic Programs
by: Lin, Zhenwei, et al.
Published: (2025)

Improved Analysis of Restarted Accelerated Gradient and Augmented Lagrangian Methods via Inexact Proximal Point Frameworks
by: Burns, Matthew X., et al.
Published: (2026)

Anderson Acceleration Without Restart: A Novel Method with $n$-Step Super Quadratic Convergence Rate
by: Ye, Haishan, et al.
Published: (2024)

A Parameter-Free Restart Scheme with Only a Parallelizable $\log\log(1/ε)$ Overhead
by: Wu, Yue, et al.
Published: (2026)

Complexity of Error Bounds for Systems of Linear Inequalities
by: Wei, Zhou, et al.
Published: (2025)

cuPDLP.jl: A GPU Implementation of Restarted Primal-Dual Hybrid Gradient for Linear Programming in Julia
by: Lu, Haihao, et al.
Published: (2023)

Optimal Restart Strategies for Parameter-dependent Optimization Algorithms
by: Schönenberger, Lisa, et al.
Published: (2025)

Learning When to Restart: Nonstationary Newsvendor from Uncensored to Censored Demand
by: Chen, Xin, et al.
Published: (2025)

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

From an Interior Point to a Corner Point: Smart Crossover
by: Ge, Dongdong, et al.
Published: (2021)

Random-Restart Best-Response Dynamics for Large-Scale Integer Programming Games and Their Applications
by: Lee, Hyunwoo, et al.
Published: (2024)