It is shown that PDHG converges eventually (R-)linearly whenever the limiting KKT point satisfies either strict complementarity or primal--dual nondegeneracy, and numerical experiments support the theory and identify difficult SDP instances where PDHG struggles to reach high accuracy.
Abstract
Primal-dual first-order methods are widely used for large-scale semidefinite programming (SDP), but their ability to compute highly accurate solutions is not well explained by global convergence theory alone. We study the local convergence of the primal-dual hybrid gradient (PDHG) method applied to a standard primal--dual SDP pair. We show that PDHG converges eventually (R-)linearly whenever the limiting KKT point satisfies either strict complementarity or primal--dual nondegeneracy. The proof views PDHG as a preconditioned proximal point method for the KKT inclusion and combines its descent inequality with a local error bound. Under strict complementarity, the error bound follows from the local spectral geometry of the positive semidefinite cone; under primal-dual nondegeneracy, it follows from strong regularity of the KKT mapping. We also give a simple SDP instance where both regularity conditions fail and PDHG can converge only sublinearly. This contrasts with linear programming, where PDHG admits a local linear convergence regime even for degenerate instances. Numerical experiments support the theory and identify difficult SDP instances where PDHG struggles to reach high accuracy.
It is shown that strict complementarity, together with a quadratic facial-violation property of the associated complementary faces, implies uniform quadratic growth of both the primal and dual augmented Lagrangians near a strictly complementary solution, and the local equivalence of three regularity conditions is proved.
In this paper, we study a Tikhonov-regularized mixed-order primal--dual dynamical system with implicit Hessian damping for linearly constrained convex optimization problems in finite-dimensional Euclidean spaces, where the primal equation is second order and incorporates the viscous damping term \(\delta\sqrt{\varepsilon(t)}\,\dot x(t)\), whereas the multiplier equation remains first order. By constructing a new class of energy functions, for a general Tikhonov regularization coefficient \(\varepsilon(t)\), we prove the strong convergence of the primal trajectory and derive fast convergence rates under the same parameter assumptions, without imposing any eventual inside/outside-ball condition. More precisely, the primal trajectory converges to the minimum-norm solution, and the multiplier converges to a compatible KKT multiplier, while the convergence rates of the Lagrangian gap, feasibility violation, and objective residual are \(o(\varepsilon(t))\), and the convergence rate of the velocity norm is \(o(\sqrt{\varepsilon(t)})\). For the critical case \(\varepsilon(t)=c/t^2\), in which the damping coefficient \(\delta\sqrt{\varepsilon(t)}\) reduces to \(\delta\sqrt{c}/t\), we establish the sharper convergence rates \(o(t^{-2})\) for the Lagrangian gap, feasibility violation, and objective residual, together with \(o(t^{-1})\) for the velocity norm, which improve the corresponding \(O(t^{-2})\) and \(O(t^{-1})\) decay estimates obtained in the related literature. Most importantly, when the proposed dynamical system is specialized to the finite-dimensional unconstrained setting, our analysis answers the open question on strong convergence in this critical regime posed by Attouch and L\'aszl\'o [Math. Methods Oper. Res., 99 (2024), pp.~307--347].
It is shown that any first-order method guaranteeing a bound on the primal objective gap f(x_N)-f(x_\star) assuming only a bound on $\|x_0-x_\star\|$ actually has a stronger guarantee on an explicit, computable primal-dual gap at the same rate.
A primal--dual interior-point method for nonsymmetric conic optimization based on a conjugate-free scaling matrix obtained from a single-secant BFGS update of the primal barrier Hessian, which attains an iteration bound of $\mathcal{O}(\sqrt{\nu}\log(1/\varepsilon)$ and is competitive with QICS, a specialized solver for conic models arising in quantum information.
We present PDHCG-CQP, a GPU-accelerated first-order solver for large-scale conic convex quadratic programming. PDHCG-CQP supports affine constraints and Cartesian products of nonnegative, second-order, rotated second-order, exponential, and three-dimensional power cones. At its core is a restarted averaged primal-dual hybrid gradient (PDHG) method, whose primal update is computed inexactly by solving a conic quadratic proximal subproblem with projected gradient iterations. We establish local linear convergence of the restarted averaged scheme with both exact and inexact primal proximal evaluations under a uniform local quadratic-growth condition on the smoothed primal-dual gap. We further show that this condition holds under strict complementarity by exploiting a rotated second-order-cone lifting together with local primal and dual regularity conditions. Our C/CUDA implementation combines matrix-free linear algebra, batched cone projections, adaptive inner solves, reflected-Halpern acceleration, and fully device-resident KKT residual computations. It also supports multi-GPU execution through a two-dimensional partitioning of the problem data. Extensive experiments on standard and large-scale quadratic programming (QP), convex quadratically constrained quadratic programming (QCQP), second-order cone programming (SOCP), and quasilinear Fisher equilibrium benchmarks demonstrate that PDHCG-CQP achieves state-of-the-art robustness among first-order solvers while scaling efficiently to 8 GPUs and instances with up to $4.4\times10^8$ stored primal coordinates. PDHCG-CQP is open source and available at https://github.com/Lhongpei/PDHCG.
Hongpei Li, Yicheng Huang, Huikang Liu et al.· 2 citations
We consider convex optimization with nonlinear inequality constraints and develop a primal--dual multiplier framework that is consistent in continuous and discrete time. We first propose continuous-time dynamics with Nesterov-type vanishing damping $\alpha/t$, together with suitable extrapolations of the dual variable and the nonlinear constraint mapping. Under convexity assumptions and $\alpha\geq3$, we establish $\mathcal O(t^{-2})$ convergence rates for both nonlinear feasibility and the objective residual. We then derive an inexact accelerated primal--dual algorithm through a compatible discretization of a perturbed version of the dynamics. For composite convex objectives, a weighted summability condition on the primal inexactness yields the $\mathcal O(k^{-2})$ rates for feasibility and the objective residual, thereby matching the accelerated rates of their continuous-time counterparts. To the best of our knowledge, this is the first Nesterov-type primal--dual multiplier framework for convex optimization with nonlinear inequality constraints.
Xin He· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
