Restarted Accelerated Primal-Dual Algorithms with Adaptive Stepsizes for Nonlinear Conic Constrained Convex Optimization
Abstract
We propose restarted accelerated primal-dual algorithms with (non-monotone) backtracking (rAPDB) for convex nonlinear conic programs, with quadratically constrained quadratic programs (QCQPs) as a special case. Unlike linear and quadratic programs, these problems give rise to convex-concave minimax reformulations with non-bilinear coupling terms; therefore, the existing primal-dual methods for bilinear couplings are not applicable. To address this challenge, we build on the accelerated primal-dual method with adaptive stepsize search -- as it adapts to the local curvature -- and develop both fixed-frequency and adaptive restart schemes, incorporating both monotone and non-monotone adaptive step-size search strategies. The resulting algorithms require only first-order information and matrix-vector products, making them suitable for large-scale and GPU-accelerated implementation. Under metric subregularity of the KKT mapping, we prove a quadratic growth property for a self-centered smoothed duality gap and establish global linear convergence of the proposed restarted methods. We also establish sufficient conditions under which the metric subregularity holds even for general nonconvex problems over convex polyhedral cones. These results are new and may be of independent interest. Numerical experiments on random QCQPs and kernel matrix learning instances show that the proposed methods, especially with non-monotone adaptive stepsizes and GPU acceleration, achieve strong practical performance.
Related
- Accelerated Prox-Level Methods for Unknown Piecewise-Smooth Optimization II: Function-constrained Optimization
- Accelerated primal-dual dynamics and algorithms for convex optimization with nonlinear inequality constraints
- cuPDQPx: A GPU-Accelerated Restarted Halpern PDHG for Large-Scale Convex Quadratic Programming
- Projection-Free Multi-level Algorithms for Stochastic Constrained Compositional Optimization
- Accelerating Min-Max Optimization via Power-Law Stepsizes
BibTeX
@misc{aybat2026restarted,
title = {{Restarted Accelerated Primal-Dual Algorithms with Adaptive Stepsizes for Nonlinear Conic Constrained Convex Optimization}},
author = {Necdet Serhat Aybat and Jinxin Wang},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2605.29291},
eprint = {2605.29291},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2605.29291},
}
RIS
TY - UNPB
TI - Restarted Accelerated Primal-Dual Algorithms with Adaptive Stepsizes for Nonlinear Conic Constrained Convex Optimization
AU - Necdet Serhat Aybat
AU - Jinxin Wang
PY - 2026
DA - 2026/09/29
PB - arXiv
DO - 10.48550/arxiv.2605.29291
UR - https://arxiv.org/abs/2605.29291
AB - We propose restarted accelerated primal-dual algorithms with (non-monotone) backtracking (rAPDB) for convex nonlinear conic programs, with quadratically constrained quadratic programs (QCQPs) as a special case. Unlike linear and quadratic programs, these problems give rise to convex-concave minimax reformulations with non-bilinear coupling terms; therefore, the existing primal-dual methods for bilinear couplings are not applicable. To address this challenge, we build on the accelerated primal-dual method with adaptive stepsize search -- as it adapts to the local curvature -- and develop both fixed-frequency and adaptive restart schemes, incorporating both monotone and non-monotone adaptive step-size search strategies. The resulting algorithms require only first-order information and matrix-vector products, making them suitable for large-scale and GPU-accelerated implementation. Under metric subregularity of the KKT mapping, we prove a quadratic growth property for a self-centered smoothed duality gap and establish global linear convergence of the proposed restarted methods. We also establish sufficient conditions under which the metric subregularity holds even for general nonconvex problems over convex polyhedral cones. These results are new and may be of independent interest. Numerical experiments on random QCQPs and kernel matrix learning instances show that the proposed methods, especially with non-monotone adaptive stepsizes and GPU acceleration, achieve strong practical performance.
ER -