CS Paper Radar

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

Kenan Xu, Xiangfeng Wang

cs.AI math.OC ·submitted 2026-08-14 15:36 UTC · v1

Abstract

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.

Comment
34 pages

Closest papers

Nearest neighbours by meaning across the whole index.

Parallelizable Interior-Point ADMM for Block-Structured Nonconvex Programs

cs.LG math.OC ·2026-11-16 ·Zherong Pan
similarity 0.68
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

A Fast and Accurate Algorithm for the $p \to q$ Norm of Sparse Non-Negative Matrices

cs.DS ·2026-11-06 ·Marco Pirazzini, Daniel A. Spielman
similarity 0.58
Abstract · 31 pages, 6 figures

We present an algorithm that computes the $p \to q$ norm of a non-negative matrix with $s$ nonzero entries to accuracy $\varepsilon$ in time $\widetilde{O}(s^{3/2} \log (1/\varepsilon))$, for any $p \ge q \ge 1$. The fastest algorithm previously designed for this problem has running time $\widetilde{O}(s / \varepsilon)$ (Objois and Vladu, 2026), which is slower when high accuracy solutions are desired. Our algorithm employs a surprising application of Laplacian solvers inside an Interior Point Method (IPM). We formulate the problem as a linear optimization problem over a product of power cones, and show that the Newton updates of the IPM can be computed by solving a Laplacian system in a Schur complement after subtracting a rank-2 matrix. We also discuss an implementation of our algorithm, showing that it is practical and it outperforms optimized solvers such as MOSEK by factors of up to $20\times$ on a variety of tasks.

0.31

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

eess.SY math.OC ·2026-10-26 ·Roland Schwan, Thomas Lew, Brian Plancher
similarity 0.56
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.

0.36

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

An Adaptive Multi-Parameter ADMM Algorithm for Embedded MPC

eess.SY math.OC ·2026-09-11 ·Alberto Zaupa, Mikael Johansson
publishedbenchmark similarity 0.54
Abstract · Accepted for publication at CDC 2026

We introduce an adaptive multi-parameter variant of ADMM and prove that it exhibits local superlinear convergence once the set of active constraints has been identified. In simulations, the proposed algorithm consistently outperforms OSQP, a standard ADMM solver, in terms of iteration count. We then implement an MPC solver based on our method and compare its runtime against a broader selection of state-of-the-art algorithms. Evaluations on challenging benchmark problems reveal that our approach delivers competitive performance both in terms of average and worst-case solve times, without being limited to coarse tolerances, as is typically the case for standard ADMM implementations and first-order methods.

0.36

The Mode of Null-A: Compositional Computation of a Generalized Inverse

cs.PL math.NA ·2026-09-29 ·Barak A. Pearlmutter, Jeffrey Mark Siskind
similarity 0.54
Abstract · Submitted to ICLR 2027

We present a novel algorithm for calculating the preimage of an affine space through a product ${J}={J}_{T-1}\cdots{J}_0$ of matrices ${J}_t$ of special form: finding the largest input space $\mathbf{X}$ such that $\mathbf{x}\in\mathbf{X}$ implies ${J}\mathbf{x}\in \mathbf{Y}$, where $\mathbf{Y}$ is a given output affine space. These special matrices arise in AD, where the Jacobians $J$ describing the linearized computation have precisely this structure: the product of a series of linearized primitive numeric operations. This allows us to use the new algorithm to formulate Null-A mode preimage AD, which finds the affine preimage through the Jacobian or Jacobian transpose of a numeric computation. This is a generalization of the inverse AD problem of solving ${J}\acute{\mathbf{x}}^{\ast}=\acute{\mathbf{y}}^{\ast}$ or ${J}^{T}\grave{\mathbf{y}}^{\ast}=\grave{\mathbf{x}}^{\ast}$. The key is to represent affine spaces in a fashion which lends itself to efficient preimage calculation, in a compositional and quasi-local fashion, through a succession of matrices ${J}_t$. Unlike previous methods, Null-A preimage mode AD allows the ${J}_t$ matrices to be non-square, corresponding to a computer program whose number of active variables swells and shrinks during the computation. When ${J}$ is square and the initial affine space is a single point, this finds the conventional inverse. But in the more general case, having the entire affine space provides freedom which can be leveraged in a problem-specific manner. We apply the method to small problems on-CPU where the $J_t$ are linearized scalar unary or binary numeric functions; and to larger problems on-GPU where the $J_t$ are linearized aggregate array operations like convolution and attention.

0.27

Tight Convergence Bounds for the Classical Kaczmarz Method

cs.DS math.OCmath.NA ·2026-09-25 ·Runbo Yu, Jelena Diakonikolas
similarity 0.54
Abstract

The classical method of Kaczmarz, introduced in 1937, is a textbook iterative method for solving linear systems $A x = b.$ Despite its widespread use, particularly in the context of solving inverse problems where it is commonly included in software packages within Matlab, Python, and Julia, the precise characterization of convergence has long been deemed difficult to obtain. While different bounds on convergence rates have been established, they are largely unsatisfying as they cannot explain the classical, cyclic-update method's efficient convergence in practice. In this work, we obtain a tight characterization of convergence of the classical Kaczmarz method, establishing both linear and sublinear convergence bounds. The worst-case tight (i.e., exactly attained by some instances in the considered family) bounds are expressed in terms of a fixed matrix that depends only on $A,$ but are not fully interpretable in terms of the matrix spectrum and row correlations, which had been observed to have an impact on convergence. We thus provide relaxations of these bounds that are fully expressible in terms of matrix row norms, row correlations, rank, and extremal positive singular values. The provided relaxed bounds explain one-cycle convergence in special cases where the matrix rows are all either parallel or orthogonal to each other. We further argue that the dependence on different parameters appearing in the bounds is necessary and within a small constant factor of the best attainable in the worst case. Finally, our bounds explain why the classical cyclic update is faster than the randomized one when matrix rows are weakly correlated, which is often observed in inverse problems where the cyclic method is used.

0.54

4-Block Integer Programming is in FPT

cs.CC ·2026-09-22 ·Martin Koutecký, Alexandra Lassota, Koen Ligthart
similarity 0.54
Abstract · 23 pages, 0 figures

Integer programming is a fundamental and important NP-hard problem. This motivated extensive efforts in studying several tractable subclasses. One of the most important, unresolved complexity questions is the parameterized complexity of 4-block IPs, a natural class characterized by having a diagonal matrix with small blocks after deleting few rows and columns. Over the years, significant progress has been made in improving algorithms for 4-block IPs, but the question whether such IPs can be solved in FPT time, parameterized by the block dimensions and largest matrix coefficient, has remained open. This question is repeatedly highlighted, most recently by Koutecký [IPEC 2025] and by Eisenbrand and Rothvoss [SODA 2026]. We resolve this question in the positive by providing an FPT time algorithm. Our algorithm can optimize non-linear, separable convex objective functions, and can be extended to broader classes of constraint matrices (such as tree-fold or multi-stage) and allows appending few ``global'' columns to it, and it allows coefficients unbounded by the parameters in those columns. It is known that tractability cannot be extended further in any of those directions. The key structural property that we establish is that a function $f\colon\mathbb Z^n\to\mathbb R$ that is integer midpoint convex, i.e., $f(x)\le\tfrac12f(x-p)+\tfrac12f(x+p)$ for all $x,p\in\mathbb Z^n$, can be extended to a convex function on the set $2d\mathbb Z^n\cap L$ if $L$ is a linear subspace of dimension $d$. This closes the gap in a recent work by Ligthart [arXiv 2606.30330, 2026], which allows us to extend the previous algorithm that solves 4-block integer programs with a single global variable to incorporate any parameterized number of global variables. As an example, we apply our algorithm to solve an open problem posed by Boehmer and Koana [ACM Trans. Algorithms, 2024] in Max-Min Fair Matching.

0.40