CS Paper Radar

GPU-Accelerated Conic Quadratic Programming with Local Linear Convergence under Strict Complementarity

Hongpei Li, Yicheng Huang, Huikang Liu, Dongdong Ge, Yinyu Ye

cs.DC math.OCcs.MS ·submitted 2026-08-10 06:16 UTC · v1
code/datahighly cited

Abstract

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.

Comment
Source code available at https://github.com/Lhongpei/PDHCG

Closest papers

Nearest neighbours by meaning across the whole index.

cuPDQPx: A GPU-Accelerated Restarted Halpern PDHG for Large-Scale Convex Quadratic Programming

cs.MS math.OC ·2026-10-28 ·Haihao Lu, Zedong Peng, Jinwen Yang
similarity 0.77
Abstract

We present cuPDQPx, a GPU-accelerated, factorization-free first-order solver for large-scale convex quadratic programming (QP). Building on the restarted reflected Halpern primal-dual framework of cuPDLPx, we introduce an auxiliary-variable splitting that yields explicit updates without linearizing the quadratic objective or solving inner quadratic subproblems. A preconditioned proximal point interpretation yields both sublinear and linear fixed-point residual convergence guarantees. For practical efficiency, cuPDQPx integrates diagonal preconditioning, step-size selection, adaptive restart, and adaptive primal and quadratic weight updates. cuPDQPx is implemented in C and CUDA with optimized sparse matrix-vector products, kernel fusion, and CUDA Graphs. Numerical experiments on the Maros-Mészáros collection, a convex subset of QPLIB, and synthetic large-scale QPs demonstrate that cuPDQPx has strong numerical performance at both $10^{-4}$ and $10^{-8}$ tolerances.

0.21

First-order smoothed exact-penalty methods for equality-constrained regularized nonconvex optimization

cs.LG math.OC ·2026-11-15 ·Shiji Zuo, Qihang Lin, Wei Liu, Yangyang Xu
theory similarity 0.70
Abstract

We consider regularized nonconvex optimization over a closed convex set $\mathcal{X} \subseteq \mathbb{R}^d$, which involves a convex nonsmooth regularizer $r$ in the objective and $n$ smooth equality constraints. To find a near-KKT point of the problem, we propose a prox-linear first-order method, named as SEPi-Prox, based on a smoothed exact-penalty formulation. At each outer iteration of SEPi-Prox, a strongly convex prox-linear subproblem is formed and solved inexactly to a sufficient accuracy. Under a local non-singularity condition that is weaker than some other commonly used regularity conditions or constraint qualifications, SEPi-Prox finds an $ε$-KKT point within $O(ε^{-2})$ first-order oracle calls, matching the lower bound for unconstrained smooth nonconvex optimization. We employ Nesterov's accelerated proximal-gradient method (APG) and a dual cutting-plane method (DCP) for the prox-linear subproblems. Let $\mathcal{C}_{\mathrm{FO}}$ and $\mathcal{C}_r$ denote the numbers of arithmetic operations of evaluating one first-order oracle and one proximal mapping of $r$ over $\mathcal{X}$, respectively. Then SEPi-Prox requires $\widetilde{O}(\mathcal{C}_{\mathrm{FO}}ε^{-2} + (dn + \mathcal{C}_r)ε^{-5/2})$ and $\widetilde{O}((\mathcal{C}_{\mathrm{FO}} + dn^2 + n\mathcal{C}_r + n^{3.373})ε^{-2})$ total arithmetic operations to produce an $ε$-KKT point, respectively by using APG and DCP as the subsolver. The latter result is preferable when $n$ is small and nearly matches the optimal dependence on $ε$. Numerical experiments on instances of the multi-class Neyman-Pearson classification demonstrate the efficiency of SEPi-Prox with both subsolvers.

0.05

Convex-SKM-Net: Low-Latency Block Halfspace Corrections for Neural Convex Constraint Satisfaction

cs.LG cs.AImath.OC ·2026-10-28 ·Haoyu Zhu, Xiaochen Zhang, Qingchun Hou
benchmarktheory similarity 0.65
Abstract

Fast inference and strict constraint satisfaction are essential for learning-based decision-making. Existing methods often rely on constraint-specific projections or feasible-set parameterizations, while iterative repair can be costly. We introduce Convex-SKM-Net, a convex constraint-satisfaction layer that forms linearization halfspaces from residual and (sub)gradient oracles without constraint-specific inequality projectors. It applies fixed-depth dual projected-gradient descent (dual PGD) to minimum-displacement block problems using GPU-friendly matrix operations. We jointly learn the predictor and a positive-definite mobility, adapting the correction geometry to improve objective quality. We prove convergence of the outer iterates at fixed dual depth and linear convergence in distance under Slater's condition and bounded subgradients. All our test outputs on three second-order-cone model-predictive control (SOC-MPC) horizons and six power-system convex relaxations satisfy a $10^{-3}$ feasibility tolerance. Comparisons with the latest constraint-satisfaction methods show inference speedups of up to $144.3\times$ on SOC-MPC and $7.7\times$ on a convex quadratically constrained quadratic programming (QCQP) benchmark with joint training. On QCQP, the mean objective gap is $0.012\%$, with full test feasibility at $10^{-4}$. Learning mobility reduces the five-seed affine-task mean gap by $22.4\%$ and improves gaps in matched power-system comparisons.

0.10

ALDER: A Single-Loop Augmented-Lagrangian Damped Extragradient Method for Nonconvex--Concave Minimax Problems with Nonlinear Coupled Constraints

cs.LG math.OCstat.ML ·2026-10-31 ·H. Zhang, M. Zhang, Z. Xu, Y. -H. Dai
similarity 0.64
Abstract

ALDER, a single-loop augmented-Lagrangian damped extragradient method, is proposed for smooth nonconvex--concave minimax problems with nonlinear coupled inequality constraints. Within an augmented-Lagrangian framework, ALDER combines prediction--correction steps for the primal variables with explicit projected-and-relaxed multiplier updates in a single loop. The penalty parameter is fixed throughout each run, eliminating inner-loop subproblem solves and iterative penalty updates. We establish uniform boundedness of the relaxed multiplier sequence and, under an extended Mangasarian--Fromovitz constraint qualification, boundedness of the projected output multiplier. Building on these bounds, we show that ALDER finds an $\varepsilon$-KKT point within $\mathcal{O}(\varepsilon^{-7/2})$ complete first-order oracle evaluations in the strongly concave setting and $\mathcal{O}(\varepsilon^{-4})$ in the concave setting. These bounds improve upon the best known complexity bounds for multi-loop algorithms for this problem class, achieved by FAL, by removing a $\log(1/\varepsilon)$ factor, while retaining a single-loop update structure.

0.18

Learned Preconditioning for a Primal-Dual Interior-Point Method

cs.LG math.OC ·2026-09-28 ·Abhinav Madabhushi, Jialin Liu, Minxin Zhang
similarity 0.64
Abstract

Interior-point methods (IPMs) are among the most widely used algorithms for constrained optimization, yet their Newton-based search directions require costly second-order information and large linear-system solves. Learning to optimize offers cheaper updates learned from data, but the singular behavior of logarithmic barriers near constraint boundaries makes IPMs highly sensitive to perturbations, complicating both warm starting and learning reliable updates. We introduce pdLIP, an IPM for smooth nonlinear programs that integrates learned preconditioning with pdProj, an all-shifted primal-dual projected-search IPM. A shared coordinate-wise recurrent network predicts a positive diagonal preconditioner that scales the right-hand side of the reduced Newton system for the primal step, and the remaining slack and multiplier directions are recovered analytically. The learned iterations avoid Hessian evaluations and Newton-system solves, using only first-order and coordinate-wise operations amenable to GPU parallelization. Training is self-supervised, with a loss based on a penalty-barrier merit function and the residual of perturbed optimality conditions, requiring neither target directions nor precomputed solutions. Primal and dual shifts mitigate the barrier's sensitivity to perturbations near constraint boundaries, enabling effective warm starting. Across four classes of 200-dimensional convex and nonconvex constrained problems, pdLIP warm starts reduce pdProj refinement iterations by 63-67% compared with cold starts at the same KKT residual tolerance of $10^{-8}$, with negligible warm-start generation cost relative to the subsequent pdProj solve. Improvements persist on box-constrained QPs with 1000 variables and extend to applications including portfolio optimization, support vector machines, and a nonlinear control example.

0.31

Certified Robustness via Sparse Second-Order Cone Relaxations

cs.LG ·2026-10-12 ·Mohammadreza Maleki, Daniel Sadig, Rushendra Sidibomma, Mahyar Fazlyab, Arman Adibi +1 more
benchmark similarity 0.63
Abstract

Certified robustness is critical for deploying neural networks in safety-sensitive settings, but computing exact certificates typically requires solving nonconvex optimization problems. Practical verifiers use convex relaxations: linear programming (LP) relaxations are scalable but often too conservative, whereas semidefinite programming (SDP) relaxations can be substantially tighter but are computationally expensive. We introduce a hierarchy of second-order cone programming (SOCP) relaxations that provide stronger certificates than LP while avoiding the cost of global positive-semidefinite constraints. Our construction combines convex-hull relaxations of ReLU activations, selective McCormick lifting over certified variable bounds, and second-order cone constraints induced by 2-by-2 principal minors. Adding these constraints progressively yields a monotone hierarchy of increasingly tight bounds with a controllable computation-tightness trade-off. On fully connected and convolutional networks on MNIST and CIFAR-10, SOCP-based verification improves certified robust accuracy over LP-based verification and is competitive with alpha,beta-CROWN, while remaining orders of magnitude faster than SDP-based verification. These results position selective second-order constraints as a practical middle ground between scalable LP-based and tight SDP-based certification. Finally, we introduce class-optimized robust evaluation (CORE), which applies tighter relaxations only to target classes not certified by cheaper ones. On the fully connected MNIST benchmark, CORE variants match SDP-cert's certified robust accuracy while reducing average verification time by up to 86.30%.

0.11

B$^3$-PWL: GPU-Batched Branch-and-Bound for Piecewise-Linear Optimization with SOS2 Constraints

cs.DC math.OC ·2026-08-29 ·Yilin Guan, Shuqing Luo, Pingzhi Li, Tianlong Chen, Kaidi Xu
benchmarkcode/datahot direction similarity 0.63
Abstract · 23 pages, 3 figures

Piecewise-linear (PWL) optimization problems arise in many mixed-integer programming (MIP) optimization applications, including portfolio optimization, workforce scheduling, and resource allocation. But solving them to global optimality remains computationally expensive because branch-and-bound repeatedly solves LP relaxation subproblems. Existing solvers are largely CPU-centric, leaving the scalability of modern GPUs underutilized. Few prior GPU-accelerated branch-and-bound either targets neural network which is not suitable for general PWL optimization, or accelerates only auxiliary subroutines such as strong branching heuristics within CPU-centric MIP solvers. To bridge this gap, we propose B$^3$-PWL, a GPU-centric batched branch-and-bound framework for piecewise-linear optimization with Special Ordered Set of type 2 (SOS2) constraints. Our method solves batches of LP relaxation subproblems concurrently on the GPU using a first-order primal-dual solver, enabled by a specialized batched block-tiled sparse matrix kernel. To complement bound computation, we further introduce a unified feasibility search module that combines an SOS2 repair primal heuristic with a batched feasibility pump to rapidly obtain feasible incumbents and improve pruning efficiency. On a benchmark of 43 PWL-MIP instances, B$^3$-PWL achieves a 9.25x geometric-mean speedup over NVIDIA cuOpt while reaching high-quality feasible incumbents on every tested instance. On a public valve-point unit-commitment benchmark, it further outperforms NVIDIA cuOpt and the open-source CPU solvers SCIP and HiGHS, demonstrating the potential of first-order LP methods as the central engine of GPU-accelerated branch-and-bound.

0.42

Primal Acceleration of Newton's Method

cs.AI math.OCcs.LG ·2026-08-21 ·Nikita Doikov
similarity 0.63
Abstract

We develop a new direct accelerated Newton method for minimizing convex functions with Lipschitz continuous Hessian. The algorithm uses only primal variables and performs just one linear solve per iteration. With a simple predetermined choice of parameters, it achieves the global convergence rate of $O(1/k^3)$ in terms of the functional residual. To the best of our knowledge, this is the first second-order method for this problem class attaining this rate while relying solely on one linear system solve per iteration (without solving auxiliary nonlinear regularized subproblems, such as cubic regularization, performing nonlinear parameter searches, or using dual extragradient corrections). Our method can be implemented in a Hessian-free way, using an inexact linear system solver, while preserving the fast global rate. We further extend our construction to arbitrary geometry through Bregman divergence, and to composite optimization problems.

0.11