PaperlayerView exact revision on arXiv

Source-linked AI summary

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

arXiv:2608.14396v1math.OCcs.AI

TL;DR

The paper addresses the unresolved convergence question for direct three-block ADMM with an identity third block. It uses AI-assisted piecewise-affine construction and exact certification to produce counterexamples and study multiplier relaxation. The results show bounded nonconvergence at period 66, a locally attracting period-23 certificate, and problem-dependent but not class-uniform relaxation guarantees.

  • Problem

    Existing results provide neither a general convergence proof nor a counterexample for direct three-block ADMM with identity third block.

  • Method

    The paper combines AI-assisted route guidance with piecewise-affine reduction, exact rational construction, active-set itinerary verification, and return-map certification.

  • Results

    Direct three-block ADMM has a bounded non-KKT orbit of minimal period 66, while multiplier relaxation can restore convergence problem-by-problem but no positive relative step works uniformly over the class.

  • Takeaways & Limitations

    An identity third constraint block alone does not guarantee convergence, and relaxation guarantees must be distinguished between fixed instances and the whole problem class.

  • Takeaways & Limitations

    The claims do not establish arbitrary-initial global convergence over the displayed fixed-instance ranges, and several quantitative stability and implementation questions remain open.

Abstract

from arXiv · show

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.

1 The Open Problem

The paper studies whether direct three-block ADMM converges when the third constraint block is the identity, a case not resolved by existing convergence results or counterexamples. It answers negatively by constructing an AI-assisted strongly convex quadratic counterexample and documenting exact certification and related multiplier-relaxation results.

  • Problem Formulation: The studied model uses a slack variable z with identity third block and constraint Ax + By + z = b.The slack is constrained to the nonnegative orthant through an indicator formulation.
  • Algorithm: The direct iteration studied is the slack-last sweep x → y → z → λ, rather than a grouped two-block reformulation.The augmented Lagrangian uses penalty parameter β > 0 and multiplier λ.
  • The Open Problem: The identity-slack subclass has neither a general convergence proof nor a counterexample in the existing literature.Existing multi-block results instead impose additional assumptions or modify the iteration.
  • Main Results: The paper gives a negative answer: direct three-block ADMM may fail even when the first two blocks are strongly convex quadratics.This is presented as the central mathematical result of the paper.
  • Main Results: The contributions include an exact rational period-66 counterexample, problem-dependent multiplier-step convergence, exclusion of any class-uniform relative step, and a locally attracting period-23 certificate.The paper also documents an AI-assisted workflow involving representation discovery, construction, exact certification, and theorem continuation.

2 A Period-66 Counterexample

The paper constructs an exact rational period-66 orbit for direct three-block ADMM by reducing the iteration to piecewise-affine branch dynamics and verifying a realizable projection itinerary. Exact closure, admissibility, and reconstruction checks establish a bounded, non-KKT, nonconvergent cycle that persists under sufficiently small perturbations.

  • Construction: The construction reduces the ADMM iteration to signed piecewise-affine dynamics, searches resolvent parameters and active-set itineraries, and reconstructs candidates over the rationals.The verification checks closure, branch admissibility, the original ADMM iteration, and minimality.
  • Problem Data and Main Theorem: Theorem 2.1 gives a rational initialization whose unmodified direct three-block ADMM orbit is bounded, non-KKT, and periodic with minimal period 66.All projection inequalities are strict with a common margin greater than 10^-3, so the failure is not caused by projection ties.
  • Orbit Reduction: The reduced state uses q = z + λ, and the projection and multiplier updates uniquely determine z and λ from q.On each strict projection region, the recurrence becomes an affine update.
  • Orbit Geometry: Only the projection patterns D00 and D01 are needed, producing the itinerary (00)^2(01)^64 across the 66-step cycle.The decimal visualization marks the two 00 iterates and the remaining 01 iterates; the KKT coordinate q⋆ = (−1, 1) is outside the loop.
  • Exact Period Certificate: Composing the affine updates yields a rational return equation whose nonsingular return map has a unique rational fixed point.The cycle is selected by the nonzero offset from b̄, not by a unit-eigenvalue orbit of the linear return matrix.
  • Exact Period Certificate: Exact iteration verifies every prescribed branch, reconstructs the full ADMM state, and proves first return at step 66.Because the periodic sequence excludes the unique KKT point, the orbit is non-KKT, nonconvergent, and bounded; strict margins and return-map nonsingularity yield perturbation persistence.

3 Multiplier Relaxation

The paper studies whether multiplier relaxation can restore convergence for direct three-block ADMM, distinguishing fixed-instance behavior from guarantees uniform over the problem class. It proves problem-dependent small-step convergence, rules out any positive class-uniform relative-step interval, and gives sharper local and initialization-specific results for the period-66 instance.

  • 3.1 Small-Step Convergence and Its Limits: A problem-dependent threshold τ̄ > 0 guarantees global R-linear convergence from every finite feasible initialization for each fixed problem satisfying the stated strong-convexity and rank assumptions.The threshold depends on the problem data and β; the result specializes the Hong–Luo framework to the slack-last model.
  • 3.1 Small-Step Convergence and Its Limits: No positive relative-step interval works uniformly over the whole class: for every fixed relative step, a strongly convex slack-last QP can produce a bounded nonconvergent sequence.The obstruction already occurs with three blocks, positive-definite Q1 and Q2, and full row rank of [A B].
  • 3.1 Small-Step Convergence and Its Limits: A backtracking rule with one additional trial primal sweep obtains finitely terminating step selection and globally R-linearly convergent iterates under exact block solves and exact acceptance tests.The accepted steps have a positive lower bound independent of the iteration index.
  • 3.2 Stability of the Period-66 Example: The KKT point is uniformly locally Q-linearly attracting for τ ∈ [0.49, 0.51] under a common rational Lyapunov metric independent of τ.This interval concerns local attraction, whereas convergence of the specified period-66 initialization is a separate assertion.
  • 3.2 Stability of the Period-66 Example: For the period-66 instance, the initialization from Theorem 2.1 converges when τ is sufficiently below 1, while local attraction on the strict D01 branch holds pointwise up to τc.The certified boundary satisfies 0.9366061114 < τc < 0.9366061115.

4 A Period-23 Attracting Cycle

A separate Kimi Code K3 route produced an exact, locally attracting period-23 non-KKT cycle without access to the Codex candidate or project-specific guidance. The certificate extends to an equivalent all-identity model and illustrates a discovery path distinct from Codex’s dynamical construction.

  • Exact Period-23 Certificate: Period 23 is the certified minimal period of a non-KKT direct-ADMM sequence for the rational instance.The sequence has a unique primal–dual KKT point.
  • Exact Period-23 Certificate: All 69 projection inputs have a common strict margin greater than 1/250.The margin supports strict branch admissibility throughout the cycle.
  • Different Discovery Mechanisms: The Kimi route reduced fixed projection branches to affine maps, searched KKT-compatible QP data, and promoted candidates after exact rational replay and Lyapunov certification.Its construction is closer to inverse design, whereas the Codex route searched a switching-system representation and realizable itineraries.
  • Exact Period-23 Certificate: An open invariant ellipsoid of reduced initializations converges phasewise to the period-23 sequence, so nonconvergence occurs on an open set rather than one initialization.The return map is certified by an exact Lyapunov inequality.
  • Exact Period-23 Certificate: Because the first two coefficient matrices are nonsingular, a change of variables converts the example into an equivalent rational strongly convex [I3, I3, I3] identity-slack QP.The transformed Hessians remain positive definite.
  • Different Discovery Mechanisms: The two routes shared evidence principles but differed in workspaces, tools, accumulated context, and human steering.Their records therefore compare realized model–harness routes rather than isolated base-model capabilities.

5 Discussion

The results show that identity-slack structure alone does not ensure convergence, while multiplier relaxation can restore convergence only in problem-dependent ways. The discussion presents AI assistance as a research process spanning representation discovery, construction, intervention, and exact certification, while emphasizing unresolved mathematical and evaluation limits.

  • What the Results Show: An identity third constraint block does not by itself restore convergence of unmodified direct three-block ADMM.The paper reports a period-66 counterexample and an equivalent all-identity period-23 example.
  • What the Results Show: A problem-dependent small multiplier step can restore convergence, but no positive relative step works uniformly across the whole class.The discussion distinguishes fixed-instance stability from class-level guarantees.
  • AI for Optimization: AI assistance spans representation discovery, structured instance construction, failure diagnosis, algorithmic intervention, and exact proof certification.The paper frames these as connected levels from solving fixed problems to discovering theory.
  • AI for Optimization: Persistent workspaces, tools, artifacts, verifiers, and human checkpoints shape how candidates are explored and promoted into the mathematical record.The harness is presented as part of the research environment rather than a capability of the base model alone.
  • Limits and Outlook: The mathematical outlook includes shorter strictly admissible cycles, sharper active-set and multiplier-step conditions, and analysis beyond exact rational arithmetic.Additional boundaries include finite precision, inexact solves, alternative update orders, and broader nonsmooth models.
  • Limits and Outlook: The route comparison cannot isolate the effects of model, workspace, tools, prompts, persistent memory, or human steering.Controlled ablations with matched budgets and conditions are needed before making capability claims.

A.1 Proof of Proposition 3.1

The proof establishes global contraction for direct three-block ADMM on a smooth strongly convex slack-last class under a sufficiently small dual step. It combines fixed-multiplier primal bounds, dual cost-to-go estimates, and explicit constants, with a quadratic refinement and exact-evaluation assumptions.

  • Global Bounds: The proof establishes unique primal and multiplier solutions using full row rank and strong convexity.Strict positivity of the relevant dual curvature yields multiplier uniqueness.
  • Global Bounds: A fixed-multiplier strongly convex augmented Lagrangian provides a global primal error bound with constants independent of the multiplier.The curvature is represented through Kµ and µp = λmin(Kµ) > 0.
  • Contraction Argument: The proof combines block optimality, projection nonexpansiveness, and Moreau-envelope structure to control primal and dual changes.The resulting cost-to-go argument supplies contraction ingredients on the noncompact orthant.
  • Contraction Argument: A sufficient convergence range is 0 < τ < γ ∥E∥2κ2pσ2.The contraction factor is built from η = min{a/Cp, τ/Cd} > 0 and ρ = (1 + η)−1 ∈(0, 1).
  • Conclusion: The resulting theorem closes the proof for the general smooth strongly convex class with step-sequence-independent constants.The inherited architecture is gap contraction; the class-specific work verifies global bounds on the noncompact slack-last setting.
  • Quadratic Refinement: For quadratic objectives, the proof replaces general curvature estimates with a K-metric identity and evaluates the majorant using pre-factorized Q1 and Q2 solves.The quadratic refinement yields the same contraction with τK replacing τE.
  • Backtracking Assumptions: The geometric backtracking argument terminates and accepts a step, but assumes exact block solves and exact acceptance-test evaluation.Finite-precision acceptance under the required strict margin needs separate analysis.

A.3 Proof of Theorem 3.2

The proof establishes instability through exact branch analysis and constructs a bounded, nonconvergent orbit by selecting a unit-circle eigenmode while preserving strict projection conditions.

  • For 0 < ϑ ≤ 80/119, the selected endpoint is strictly Schur stable throughout the stated interval.
  • The constructed problem has positive-definite Hessians, nonsingular constraint matrices, and a unique strictly complementary KKT point.
  • On the fixed projection mask D = diag(1, 0, 0), exact Schur recursion yields a negative second delta, certifying a root outside the unit disk.
  • A unit-circle eigenvalue must be −1 or a nonreal conjugate pair, producing an alternating or rotating bounded nonconvergent branch orbit.
  • Scaling the eigenmode preserves the strict KKT projection margin, while feasibility and affine x-updates extend boundedness to the full (x, y, z, λ) orbit.

A.6 Perturbation Robustness

The period-66 construction is robust to sufficiently small perturbations of the quadratic data and right-hand side, because its branch itinerary and strict inequalities persist locally.

  • There is an open neighborhood of the displayed problem data in which every resulting problem has a non-KKT ADMM sequence of minimal period 66.
  • The perturbed sequences retain the same projection-sign sequence, with every projection inequality remaining strict.
  • Analytic dependence of the period system and a positive common margin preserve the 66-step itinerary under sufficiently small perturbations.

A.8 Proof of Theorem 3.4

The proof characterizes multiplier relaxation through the affine branch matrix: a small dual step yields local contraction, whereas steps at or above the stability boundary cannot produce local Q-linear attraction.

  • Exact Sylvester tests establish contraction throughout τ ∈ [49/100, 51/100] in a suitable H-norm, and a finite 232-step enclosure reaches the contraction ellipsoid.
  • For 0 < τ < τc, Schur stability provides an invariant ellipsoid in which the KKT point is locally Q-linearly attracting.
  • For τc ≤ τ < 1, ρ(T01(τ)) ≥ 1, ruling out local Q-linear attraction of the KKT point.

A.9 Verification of Theorem 3.4

Verification reconstructs the relaxed reduced dynamics from rational QP data, checks exact branch maps and projection behavior, and confirms the stability boundary using Schur–Sturm analysis.

  • The verification script re-derives the essential-state projection-region matrices and checks endpoint Sylvester minors, the chord identity, and a 232-step exact enclosure.
  • Exact factorization, Schur recursion, and Sturm counting reduce the stability boundary to one root of the boundary polynomial in (0, 1).
  • The period-23 certificate uses v = (y, z + λ), whose projection identity determines z and λ and thereby the next ADMM step.
  • On each strict branch, eliminating the x- and z-updates gives a rational affine map Φσ(v) = Rσv + rσ when the QP data are rational.

B.2 Exact Data and Certificate

The certificate constructs a rational period-23 return map, verifies its exact fixed orbit and branch stability, and documents the gated workflow supporting the computational claims.

  • Exact construction: The W23 branch word defines a 23-step piecewise-affine return map whose phase-zero fixed point and phase states are recovered exactly over the rationals.Exact elimination solves the fixed-point system, while the initialization equations recover the rational starting state.
  • Exact verification: Exact replay verifies closure, strict projection consistency, pairwise distinct phase states, and minimal period 23.The certificate also checks positive definiteness, nonsingularity, the unique KKT point, and separation from that point.
  • Stability certificate: Every initialization in the certified ellipsoid follows the same 23 affine branches and converges phasewise to distinct limiting states, so the full sequence does not converge.The return map leaves the ellipsoid invariant because its error contracts and the strict sign margin preserves all projection decisions.
  • Certificate scope: The certified ellipsoid is sufficient rather than maximal, while a one-dimensional slice still provides an interval of certified nonconvergent reduced initializations.The stated slice imposes Δy = 0 and Δt3 = 0, with the quadratic inequality determining the interval.
  • Research workflow: The workflow separates human direction from model-proposed constructions and promotes candidates through gates covering exact data, KKT validity, closure, branch admissibility, replay, period, and audit checks.Exact arithmetic supports G1–G6 where applicable, while G7 audits quantifiers, novelty, and literature scope; model transcripts have no independent evidentiary weight.

C.4 Claim-to-Artifact Map

The claim-to-artifact map links each theorem and proposition to an exact replayable verifier, with a consolidated command checking all period-66 and period-23 claims.

  • Claim-specific verification: The repository maps Theorem 2.1 to the exact certificate-pair verifier and Theorem 3.4 to the relaxed-multiplier interval-theory certificate.Each entry identifies the claim and its corresponding verification command.
  • Claim-specific verification: Theorem 3.2 and Proposition 4.1 are linked to verifiers for the universal-step obstruction and the exact period-23 certificate, respectively.The period-23 verifier checks the certificate associated with Proposition 4.1.
  • Independent artifacts: The one-shot verifier checks the combined 66+23 claims, and these computer-assisted claims rest on exact replays independently of language-model transcripts.The repository presents the first exact replayable certificate as each verification endpoint.
Loading 2608.14396v1…