Copertina

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

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autore principale:	Xiong, Zikai
Natura:	Preprint
Pubblicazione:	2025
Soggetti:	Optimization and Control
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

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

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

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

Computational Guarantees for Restarted PDHG for LP based on "Limiting Error Ratios" and LP Sharpness
di: Xiong, Zikai, et al.
Pubblicazione: (2023)

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

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

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

Concurrent Crossover for PDHG
di: Rothberg, Edward
Pubblicazione: (2025)

Backing PDHG into a Corner
di: Rothberg, Edward
Pubblicazione: (2025)

Hybridizing PDHG and Interior-Point Methods
di: Rothberg, Edward
Pubblicazione: (2026)

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

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

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

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

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

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

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

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

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

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

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

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

Negative Curvature Methods with High-Probability Complexity Guarantees for Stochastic Nonconvex Optimization
di: Berahas, Albert S., et al.
Pubblicazione: (2026)

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

Complexity of Bilevel Linear Programming with a Single Upper-Level Variable
di: Sugishita, Nagisa, et al.
Pubblicazione: (2025)

A Sequential Quadratic Programming Method with High Probability Complexity Bounds for Nonlinear Equality Constrained Stochastic Optimization
di: Berahas, Albert S., et al.
Pubblicazione: (2023)

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

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

Dynamic Programming in Probability Spaces via Optimal Transport
di: Terpin, Antonio, et al.
Pubblicazione: (2023)

Stochastic Adaptive Optimization with Unreliable Inputs: A Unified Framework for High-Probability Complexity Analysis
di: Scheinberg, Katya, et al.
Pubblicazione: (2025)

Robust Accelerated Adaptive Search: High-Probability Complexity Bounds under Bounded-Moment Stochastic Oracles
di: Zhang, Shunzhi, et al.
Pubblicazione: (2026)

Biquadratic Cauchy Tensors and Spherical Biquadratic Polynomial Programming
di: Chen, Haibin, et al.
Pubblicazione: (2026)

Polynomial Optimization Relaxations for Generalized Semi-Infinite Programs
di: Hu, Xiaomeng, et al.
Pubblicazione: (2023)

A Quadratic Programming Algorithm with $O(n^3)$ Time Complexity
di: Wu, Liang, et al.
Pubblicazione: (2025)

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

Maximizing Reach-Avoid Probabilities for Linear Stochastic Systems via Control Architectures
di: Schmid, Niklas, et al.
Pubblicazione: (2026)

On the Design of Rational Polynomial State Feedback Controllers
di: Newton, Matthew, et al.
Pubblicazione: (2025)

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

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

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