CS Paper Radar

Efficient ADMM for Soft-Constrained Quadratic Programs via Generalized Slack Projections

Roland Schwan, Thomas Lew, Brian Plancher

eess.SY math.OC ·submitted 2026-10-26 15:41 UTC · v1

Abstract

Quadratic programs (QPs) are a core building block in many applications. In practice, constraints are often softened with slack variables to guarantee feasibility. The standard approach tackles this by introducing additional decision variables, growing the resulting optimization problem. In this paper, we propose an Alternating Direction Method of Multipliers (ADMM) scheme for a broad class of convex slack penalty functions, including all $\ell_k$-norms, without increasing the problem size. The only change to the ADMM scheme is a modified slack projection function, while the remaining algorithm stays the same. We demonstrate our approach on numerical examples, showing significant speedups, and show its flexibility on an energy optimization problem.

Closest papers

Nearest neighbours by meaning across the whole index.

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.66
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

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.63
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.04

Strengthening AC optimal power flow relaxation through offline bound tightening and linear approximations

eess.SY math.OC ·2026-10-23 ·Xiangxin An, Constance Crozier, Santanu S. Dey
similarity 0.59
Abstract · 15 pages, 4 figures

The alternating-current optimal power flow (ACOPF) problem is fundamental to power system operation and planning, but its nonconvexity makes globally optimal solutions of large-scale instances computationally challenging. Convex relaxations provide tractable lower bounds for assessing solution quality and supporting global optimization, although their effectiveness depends strongly on relaxation strength. This paper proposes an offline convexification and bound tightening framework for constructing strong linear programming (LP) relaxations for families of related ACOPF instances. Rather than repeating the tightening procedure for each instance, we compute variable bounds and second-order cone outer-approximation (SOC-OA) cuts offline using a demand-slack model and reuse them for subsequent instances with the same topology and admissible demand variations. Computational results on PGLib instances show that the fully offline approach achieves an average gap of $4.32\%$, compared with $3.80\%$ for the fully online approach, while achieving an average speedup of approximately $272\times$. The results demonstrate that offline convexification and bound tightening can recover most of the relaxation improvement of online tightening while significantly reducing the computational burden for repeated ACOPF evaluations.

0.32

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

cs.DC math.OCcs.MS ·2026-08-10 ·Hongpei Li, Yicheng Huang, Huikang Liu, Dongdong Ge, Yinyu Ye
code/datahighly cited similarity 0.59
Abstract · Source code available at https://github.com/Lhongpei/PDHCG

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.

0.62

On Partial Optimality in QUBO via Quadratic Posiform Autarkies

cs.DM math.OC ·2026-10-14 ·Lucas Fabian Naumann, Bjoern Andres
similarity 0.57
Abstract · 8 pages, 0 figures

Partially optimal assignments (also called persistencies) allow combinatorial optimization problems to be reduced by fixing a subset of variables to values consistent with at least one optimal solution. For the quadratic unconstrained binary optimization (QUBO) problem, such assignments can be computed efficiently via autarkies of quadratic posiforms. However, the largest autarky domain and thus the number of fixed variables can depend on the specific posiform representation. We show that every quadratic posiform with the greatest possible constant term (the roof-dual bound) yields the largest autarky domain obtainable from any quadratic posiform. By computing such a roof-dual-optimal quadratic posiform and a corresponding autarky with largest domain in polynomial time, one can therefore attain the maximum partial optimality obtainable by quadratic posiform autarkies in polynomial time. This justifies the computation of roof-dual-optimal quadratic posiforms and corresponding autarkies in popular polynomial-time algorithms and establishes that finding additional partial optimality in QUBO requires going beyond autarkies of quadratic posiforms.

0.25

Parallelizable Interior-Point ADMM for Block-Structured Nonconvex Programs

cs.LG math.OC ·2026-11-16 ·Zherong Pan
similarity 0.57
Abstract

Physics simulation is an increasingly important computational primitive for AI, and local--global/ADMM splitting exposes its parallel structure but lacks matching finite-time convergence guarantees. We close this gap with two ADMM variants, Interior-Point ADMM (IP-ADMM), for block-structured nonconvex composite programs with smooth nonlinear inequality and affine constraints. A one-sided finite-activation wall keeps each constraint split state strictly feasible while the original-space infeasibility vanishes, giving closed-form constraint updates, one proximal call per objective block, and one equality-constrained quadratic consensus solve per iteration. \rev{To our knowledge, this makes IP-ADMM the first single-loop method that updates nonconvex inequality constraints locally and in parallel with finite-time convergence guarantees.} Ordinary IP-ADMM attains a CQ-free best-iterate weak-KKT rate of $O(K^{-1/3})$ or a banded Fritz--John rate of $O(K^{-1/4})$, which converts to KKT at $O(K^{-1/4})$ under a uniform constraint qualification; these are nearby-point certificates that reduce to conventional KKT for smooth blocks. A checkpoint variant, IP-ADMM-Ckpt, improves the asymptotic KKT exponent to $O(K^{-1/3})$. We also show how the bounds scale with the objective- and constraint-block counts and the coupling norm.

0.24

AI-Assisted Discovery and Construction of a Counterexample to the Convergence of Three-Block ADMM with the Identity Matrix as its Third Constraint Block

cs.AI math.OC ·2026-08-14 ·Kenan Xu, Xiangfeng Wang
similarity 0.56
Abstract · 34 pages

The alternating direction method of multipliers (ADMM), as a landmark algorithm, has attracted tremendous research attention and extensive practical applications over the past two decades. It is well known that, although the two-block ADMM enjoys well-established theoretical convergence guarantees, its direct extension to the three-block case may fail to converge, as demonstrated by existing counterexamples [5]. However, to the best of our knowledge, the case in which the third constraint block is the identity remains unresolved: the existing literature gives neither a general convergence proof nor a counterexample for this subclass. In this paper, we give a negative answer: direct three-block ADMM may fail even when the first two blocks are strongly convex quadratics. Using Codex with GPT-5.6 Sol, we construct an explicit rational counterexample candidate and verify it along a piecewise-affine reduction path; exact checks show that direct three-block ADMM on this instance produces a bounded nonconvergent orbit of period 66. Within the same Codex workflow, we further guide a study of multiplier relaxation and clarify when convergence can be restored at the fixed-instance and class levels: a problem-dependent small dual step can restore convergence, whereas no positive relative step works uniformly over the whole class. Furthermore, we also test the recent Kimi Code with Kimi K3 model without the Codex candidate or project-specific route guidance; along a different path it produces an exact locally attracting period-23 certificate, convertible to an equivalent all-identity instance. The comparison suggests that different research-harness configurations can shape the mathematical objects explored and the certificates pursued.

0.40

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.56
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