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.
Abstract
Operator-splitting methods such as the primal-dual hybrid gradient method (PDHG) and the alternating direction method of multipliers (ADMM) often exhibit linear convergence on conic programs, although general theory guarantees only sublinear rates. We identify two geometric conditions -- strict complementarity and quadratic facial violation -- that explain this local behavior: under these conditions, PDHG and ADMM converge linearly to an optimal solution when initialized sufficiently close to the converging strictly complementary solution. We establish this result through a unified and verifiable primal-dual error-bound framework. First, we show 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. Second, we prove the local equivalence of three regularity conditions: uniform quadratic growth of the augmented Lagrangians, quadratic growth of a localized smoothed primal-dual gap, and metric subregularity of the saddle-point mapping. This equivalence clarifies the relationship among previously proposed conditions for local linear convergence. Third, using a unified formulation, we give a concise analysis showing that these equivalent conditions yield local linear convergence of PDHG and ADMM. We verify the quadratic facial-violation property for standard polyhedral and symmetric cones, as well as relevant faces of exponential and power cones, and show that it is preserved under Cartesian products. We also obtain an improved local rate using a restarted Halpern scheme. Finally, we extend the framework to convex composite optimization through a quadratic subdifferential-violation condition, which generalizes the quadratic facial-violation.
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
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.
In this paper, we study dual semismooth Newton (SSN) methods for degenerate polyhedral projection problems, where generalized Jacobians of the dual residual may remain singular even arbitrarily close to the solution set. Rather than regularizing these singular systems, we exploit the nonuniqueness of the dual representation. We introduce a primal--dual lifted projection-equivalent set that always possesses extreme points without additional structural assumptions on the polyhedron, and show that its extreme-point geometry identifies dual representatives at which nonsingular generalized Jacobians of the dual residual can be constructed. This geometry is further linked to a full-column-rank condition and a generalized weak strict Robinson constraint qualification, showing that the regularity required by the Newton step can be recovered rather than imposed \emph{a priori}. We also establish displacement bounds that connect representative selection throughout the algorithm with the local Newton mechanism. Building on this variational framework, we develop an inexact dual SSN method with local superlinear convergence and a globalized version combining monotone representative selection with a Wolfe line search. The resulting method is globally convergent and eventually recovers the fast local rate. Numerical experiments on regularized optimal transport, battery-scheduling feasibility restoration, and occupation-measure projection demonstrate its robustness in highly degenerate settings.
This work develops a regularization analysis of non-accelerated and accelerated primal-dual methods for solving linear inverse problems in the presence of noisy data. We investigate a Condat-V\~u algorithm and an accelerated primal-dual hybrid gradient method in Hilbert spaces, with focus on quantifying the effect of data perturbations on the reconstruction error. For the non-accelerated scheme, we derive error estimates in terms of Bregman distances, whereas for the accelerated scheme we establish error estimates in norm. The study accommodates a general class of convex data fidelities satisfying suitable perturbation conditions, which are verified explicitly for equality constrained and Morozov regularization. For the non-accelerated method, the analysis is further extended to Banach spaces, taking into account non-Euclidean geometries and including a particular non-reflexive setting tailored to nonnegative solution reconstruction. The results recover known behavior in classical settings while extending the regularization analysis to these more general frameworks. Numerical experiments with representative regularizers, including sparsity and entropic models, support the theoretical findings and illustrate practical performance under noise.
Diana-Elena Mirciu, Martin Benning, Elena Resmerita· 0 citations
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.
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.
