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

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.14396v1 [math.OC] 14 Aug 2026

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 [3]. 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

1.1

The Identity-Slack Question

Consider the linearly constrained three-block convex program min

x1 ,x2 ,x3

θ1 (x1 ) + θ2 (x2 ) + θ3 (x3 )

s.t. A1 x1 + A2 x2 + A3 x3 = b, ∗

(1.1)

Codes, certificates, prompts, and workspace manifests are available at https://github.com/ConanXu-math/iden tity-slack-admm-cycle-certificate. † We would like to express our sincere gratitude to Professor Bingsheng He for encouraging me to explore the problem addressed in this paper using AI, and for the in-depth discussions we had throughout the process, from which we have benefited immensely. ‡ School of Mathematical Sciences, East China Normal University, Shanghai 200241, P.R. China. § Key Laboratory of Mathematics and Engineering Applications (MoE) and School of Mathematical Sciences, East China Normal University, Shanghai 200241, P.R. China.

1

where, for i = 1, 2, 3, xi ∈ Rni , Ai ∈ Rm×ni , b ∈ Rm , and θi : Rni → (−∞, +∞] is proper, closed, and convex. Block constraints may be absorbed into θi through indicator functions, and the solution set is assumed nonempty. Although two-block ADMM is convergent under standard assumptions [3, 6], direct three-block ADMM can fail for general coefficient matrices. Both the zero-objective feasibility example and the strongly convex example in [5] lack an identity third block. We study the distinct subclass n3 = m, A3 = Im . Typically, this can be considered as the closest case compared with classical two-block problem. This structure usually arises from the inequality-constrained problem min F (x) + G(y)

(1.2)

x,y

s.t. Ax + By ≤ b,

where F : Rnx → (−∞, +∞] and G : Rny → (−∞, +∞] are proper, closed, and convex, A ∈ Rm×nx , B ∈ Rm×ny , and b ∈ Rm . All vector inequalities are understood componentwise, and Rm + := {u ∈ m R : u ≥ 0}. For a nonempty closed convex set C, let ιC denote its indicator: ιC (u) = 0 for u ∈ C and ιC (u) = +∞ otherwise. Introducing a nonnegative slack variable gives min F (x) + G(y) + ιRm (z) +

(1.3)

x,y,z

s.t. Ax + By + z = b.

This is (1.1) with (x1 , x2 , x3 ) = (x, y, z) and (A1 , A2 , A3 ) = (A, B, Im ); the last subproblem is projection onto Rm + . We consider the direct slack-last sweep, rather than a grouped two-block reformulation [14]. For β > 0 and λ ∈ Rm , the augmented Lagrangian function is defined as β ∥r∥2 , r = Ax + By + z − b ∈ Rm . (1.4) 2 Assuming that the subproblems attain solutions, direct three-block ADMM in the order x → y → z → λ is Lβ (x, y, z, λ) = F (x) + G(y) + ιRm (z) − λ⊤ r + +

xk+1 ∈ arg min Lβ (x, y k , z k , λk ),

(1.5a)

y k+1 ∈ arg min Lβ (xk+1 , y, z k , λk ),

(1.5b)

z k+1 ∈ arg min Lβ (xk+1 , y k+1 , z, λk ),

(1.5c)

λk+1 = λk − β(Axk+1 + By k+1 + z k+1 − b).

(1.5d)

x y z

we can employ the normal-cone convention NC (u) = {v : ⟨v, w − u⟩ ≤ 0 for every w ∈ C},

u ∈ C.

With the sign convention in (1.4), a KKT point of (1.3) satisfies A⊤ λ⋆ ∈ ∂F (x⋆ ), Ax⋆ + By ⋆ + z ⋆ = b,

B ⊤ λ⋆ ∈ ∂G(y ⋆ ), z ⋆ ∈ Rm +,

(z ⋆ ). λ⋆ ∈ NRm +

(1.6)

As mentioned above, 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, available multi-block convergence results impose additional regularity or parameter assumptions [4, 17, 18, 19], or modify the iteration by correction, proximal, or back-substitution steps [10, 11, 12, 15]. None of these results establishes convergence from A3 = Im alone, leaving the identity-slack case unresolved: the existing literature gives neither a general convergence proof nor a counterexample for this subclass. Professor Bingsheng He from Nanjing University also mentioned this open problem in his talk [9]. 2

1.2

Main Results

In this paper, we give a negative answer to the above open problem through an AI-assisted research process, i.e., direct three-block ADMM may fail even when the first two blocks are strongly convex quadratics. The main contributions are as follows: • Mathematically. An exact rational period-66 identity-slack counterexample (Theorem 2.1); problem-dependent multiplier-step convergence and the exclusion of any class-uniform relative step (Section 3); and a locally attracting period-23 certificate (Section 4). • AI-assisted research process. We document how human-guided reasoning-and-coding agents contributed to representation discovery, structured counterexample construction, exact certification, and theorem continuation. Floating-point divergence or cycling is treated only as a clue; theorem-level claims require exact certificates. Prompts, workspace records, human interventions, and verification artifacts are archived in Appendix C.

1.3

Paper Organization

Section 2 presents the period-66 counterexample constructed on the Codex (GPT 5.6 Sol) route, together with its analysis and exact certification; Section 3 then studies multiplier relaxation, including when convergence is restored and when it is not. Section 4 presents the period-23 attracting counterexample from the Kimi Code (Kimi K3) route and compares the different discovery mechanisms of the two AI-assisted research routes. Section 5 summarizes the main findings and discusses implications for AI for optimization; the evidence workflow, prompts, interventions, and verification records are collected in Appendix C.

2

A Period-66 Counterexample

This section presents a rational period-66 counterexample and its piecewise-affine certificate. The construction proceeds through four mathematical steps: rejecting fixed-branch instability as insufficient without a realizable projection itinerary; deriving the signed piecewise-affine realization on s = (y, q), q = z + λ (Section 2.3); shifting the search from (Q1 , Q2 ) to resolvents (M, N ) and reachable active-set itineraries; and reconstructing the candidate over Q with exact checks of closure, branch admissibility, the original ADMM iteration, and minimality. AI-assisted process records are collected in Appendix C.

2.1

Problem Data and Main Theorem

Set A = B = I2 , β = 1, and consider min

x,y,z∈R2

1 ⊤ 1 x Q1 x + y ⊤ Q2 y + ιR2+ (z) 2 2

s.t. x + y + z = b̄. Define

M = (Q1 + I2 )−1 ,

N = (Q2 + I2 )−1 .

3

(2.1)

Then algorithm (1.5) becomes xk+1 = M (b̄ − y k − z k + λk ),

(2.2a)

y k+1 = N (b̄ − xk+1 − z k + λk ),   z k+1 = b̄ − xk+1 − y k+1 + λk + ,

(2.2b)

λk+1 = λk − (xk+1 + y k+1 + z k+1 − b̄).

(2.2d)

(2.2c)

Let ε=

1 , 1000

µ=

8957 , 10000

and define

ν=

999 , 1000

d1 = (−1, 20)⊤ ,

d2 = (−1, 10)⊤ ,

d1 d⊤ M = εI2 + (µ − ε) ⊤ 1 , Q1 = M −1 − I2 , d1 d1 d2 d⊤ N = εI2 + (ν − ε) ⊤ 2 , Q2 = N −1 − I2 . d2 d2

(2.3)

(2.4)

To define the right-hand side, prescribe a KKT point. Choose z ⋆ = (0, 1)⊤ , and set

⋆ x⋆ = Q−1 1 λ ,

λ⋆ = (−1, 0)⊤ ,

⋆ y ⋆ = Q−1 2 λ ,

b̄ = x⋆ + y ⋆ + z ⋆ .

(2.5)

By construction, Q1 x⋆ = λ⋆ ,

Q2 y ⋆ = λ⋆ ,

x⋆ + y ⋆ + z ⋆ = b̄,

λ⋆ ∈ NR2+ (z ⋆ ),

so (x⋆ , y ⋆ , z ⋆ , λ⋆ ) satisfies the KKT conditions (1.6). Every entry of Q1 , Q2 , b̄ is rational. Moreover,     1043 1 σ(Q1 ) = 999, , σ(Q2 ) = 999, , (2.6) 8957 999 where σ(Q) denotes the spectrum. Thus Q1 , Q2 ≻ 0. Strong convexity in (x, y) and the constraint determine a unique primal solution, while Q1 x⋆ = λ⋆ fixes the multiplier. Hence the KKT point is unique. All three ADMM subproblems also have unique minimizers, so the iteration is single-valued. Theorem 2.1 (Exact rational period-66 counterexample). For the rational problem (2.1)–(2.5), there is a rational initialization for which the sequence generated by the unmodified direct three-block ADMM (1.5) is bounded, non-KKT, and periodic with minimal period 66. Its strict projection-sign sequence is W = (00)2 (01)64 , (2.7) where the i-th bit is 1 if the corresponding projection input is positive and 0 if it is negative. All 132 projection inequalities are strict with a common margin greater than 10−3 . Therefore an identity third constraint block does not guarantee unconditional global convergence of direct three-block ADMM.

4

2.2

Orbit Geometry

Figure 1 is a decimal visualization of the exact rational sequence in Theorem 2.1. The values q k = z k + λk form a closed loop that does not contain the unique KKT value q ⋆ = (−1, 1). (a) Periodic reduced ADMM iterates

(b) Projection pattern over one period 2.00

2.0

pattern 00 pattern 01

1.75 1.50

1.5

1.0

q2k

q2k

1.25 KKT q ⋆

1.00 0.75

0.5

0.50 65

0.0

0

−2.0

−1.5

first iterate with q2k > 0

0.25

2

0.00

1

−1.0

−0.5

0.0

0

10

20

30

40

50

60

iteration within one period k

q1k

Figure 1: Decimal visualization of the exact rational period-66 sequence. Red squares mark the two 00 iterates; the remaining iterates have pattern 01. The KKT coordinate q ⋆ = (−1, 1) is not on the periodic sequence. Numerically, the dominant 01-branch pair has modulus 1.00018 and angle 0.0951955 ≈ 2π/66, while ρ(T00 ) ≈ 0.97058. Thus 64 near-rotational 01 steps followed by two resetting 00 steps explain the word (00)2 (01)64 . This is only intuition; the proof follows.

2.3

Exact Period Certificate

We now reduce the ADMM iteration to verify the periodic sequence in Theorem 2.1. For quadratic programs, local ADMM behavior and parameter selection can often be reduced to linear or affine iterations after active-set identification [2, 7, 16]. Here we instead compose an entire finite sign itinerary in exact rational arithmetic. Define the orthant-projection input q k+1 = b̄ − xk+1 − y k+1 + λk .

(2.8)

The z- and multiplier updates give z k+1 = [q k+1 ]+ ,

λk+1 = [q k+1 ]− ,

q k+1 = z k+1 + λk+1 .

(2.9)

For a ∈ R2 , write ([a]+ )i = max{ai , 0}, ([a]− )i = min{ai , 0}, and (|a|)i = |ai | for i = 1, 2. Thus (2.9) shows that the single vector q k+1 uniquely determines both z k+1 and λk+1 . Since z k+1 = ΠR2+ (q k+1 ), the projection optimality condition gives λk+1 = q k+1 − z k+1 ∈ NR2+ (z k+1 ). We index the recurrence after the projection–multiplier update and set sk = ((y k )⊤ , (q k )⊤ )⊤ ∈ R4 . 5

Since z − λ = |q|, the eliminated variables are recovered by z = [q]+ ,

x+ = M (b̄ − y − z + λ) = M (b̄ − y − |q|).

λ = [q]− ,

(2.10)

Define p := b̄ − x+ − z + λ and g := (I2 − M )b̄. Substitution gives the reduced recurrence (2.11a)

p = M y − (I2 − M )|q| + g,

(2.11b)

+

y = N p, +

+

+

+

q = b̄ − x − y + λ = p + z − y = (I2 − N )p + [q]+ .

(2.11c)

Together with (2.10), this recurrence is equivalent to the original ADMM after the first projection– multiplier update. For a strict projection pattern D = diag(1{q1 >0} , 1{q2 >0} ), one has [q]+ = Dq and |q| = SD q, where SD = 2D − I2 . Hence, on the corresponding polyhedral projection region, (2.11) is the affine update s+ = TD s + h,     (2.12) Ng NM −N (I2 − M )SD TD = , h= . (I2 − N )M D − (I2 − N )(I2 − M )SD (I2 − N )g Only two projection patterns are needed: D00 = diag(0, 0) and D01 = diag(0, 1). Write T00 := TD00 and T01 := TD01 , and represent each affine update in homogeneous coordinates by   Tω h Lω = ∈ R5×5 , ω ∈ {00, 01}. (2.13) 0 1 Composing the affine updates in the order prescribed by (2.7) gives   P a 64 2 L01 L00 = . 0 1

(2.14)

Here P ∈ Q4×4 and a ∈ Q4 . Exact rational elimination verifies det(I4 − P) ̸= 0. Hence s66 = s0 has the unique rational solution s0 = (I4 − P)−1 a ∈ Q4 . (2.15) Thus the cycle is an affine fixed point selected by the nonzero offset a, which comes from b̄, rather than a unit-eigenvalue orbit of P or an effect of linear objective terms. Prescribing a branch itinerary and then solving the fixed-point equation of its return map is related to constructive counterexample methodology [8]; the projection admissibility of every step must still be verified here. It remains to verify that the fixed point (2.15) follows the prescribed projection branches. Exact rational iteration of (2.11) gives q1k < 0 (0 ≤ k < 66),

q2k > 0 (2 ≤ k < 66).

(2.16)

1 . 1000

(2.17)

q2k < 0 (k = 0, 1),

More precisely, if δk = 0 for k = 0, 1 and δk = 1 otherwise, then min min{−q1k , (2δk − 1)q2k } >

0≤k<66

Hence every branch is admissible and the orthant projection realizes (00)2 (01)64 . Equation (2.10) recovers the full ADMM sequence. Define x0 = M (b̄ − y 65 − |q 65 |). 6

Together with z 0 = [q 0 ]+ and λ0 = [q 0 ]− , this gives (x0 , y 0 , z 0 , λ0 ) ∈ Q8 , and the step-65 update returns the full state. If the ADMM sequence had a proper subperiod, its projection-sign sequence would be a proper repetition. The only possible repetition factor is two, because the sequence has length 66 and contains exactly two occurrences of 00. Its two length-33 halves, however, contain different numbers of 00 symbols. The first return therefore occurs at step 66. The periodic sequence cannot contain the unique KKT point, which is a fixed point of this single-valued ADMM iteration. It is consequently non-KKT, nonconvergent, and bounded. This proves the theorem. The strict projection margin and nonsingularity of the return equation also make the cycle persist under sufficiently small perturbations of the problem data; see Corollary A.1.

3

Multiplier Relaxation

With the period-66 certificate established, a natural next question is whether a smaller multiplier step restores convergence on the same instance. We kept the rational QP, β, and initialization fixed, and had the Codex route explore only τ . The resulting branch maps, candidate regimes, and certificate proposals were then checked by exact replay; the authors separated the claims into local KKT stability, convergence from the specified initialization, and a problem-dependent class-level extension (Appendix C). Keep the primal penalty β > 0 and replace only the multiplier update by λk+1 = λk − τ (Axk+1 + By k+1 + z k+1 − b),

τ > 0.

(3.1)

The standard method corresponds to τ = β. In the counterexample below β = 1, so the certified choice τ ≈ 1/2 is a substantial multiplier relaxation, not a small perturbation of the standard step. We first state a class-level result and its limitation, and then give sharper ranges for the period-66 instance.

3.1

Small-Step Convergence and Its Limits

The small-dual-step contraction principle is due to Hong and Luo [13, Theorem 3.1 and (3.16)–(3.17)]. Their argument uses primal and dual error bounds obtained under compact-polyhedral assumptions. The contribution needed here is to verify those bounds globally for the noncompact slack-last model under global smooth strong convexity and the full-row-rank condition on [A B]. Thus the next proposition is an assumption-replacement specialization of the Hong–Luo framework, rather than a new general small-step principle. Proposition 3.1 (Hong–Luo-type slack-last specialization). In (1.3), suppose that F : Rnx → R and G : Rny → R are continuously differentiable, respectively µF - and µG -strongly convex, and have LF - and LG -Lipschitz gradients, where µF , µG > 0 and LF , LG < ∞. Assume also that [A B] has full row rank. For every fixed β > 0, there exists a problem-dependent τ̄ > 0 such that, for every 0 < τ < τ̄ , the direct x → y → z → λ iteration with (3.1) converges R-linearly from every finite initialization satisfying z 0 ∈ Rm + to the unique KKT point. Proof. Let u = (x, y, z), let ū(λ) minimize the augmented Lagrangian at fixed λ, and set dβ (λ) = minu Lβ (u; λ). Consider V k = Lβ (uk+1 ; λk ) − dβ (λk ) + dβ (λ⋆ ) − dβ (λk ), and write Sk = ∥uk+1 − uk ∥2 and Rk = ∥∇dβ (λk )∥2 . Combining the Hong–Luo primal–dual gap calculation with the global primal and dual error bounds verified here for the noncompact slack-last 7

model gives finite positive constants γ, C, Cp , Cd , depending only on the problem data and β, such that V k − V k−1 ≤ −(γ − τ C)Sk − τ Rk , V k ≤ Cp Sk + Cd Rk . (3.2) Hence 0 < τ < τ̄ := γ/C implies V k ≤ ρV k−1 ,

ρ = (1 + min{(γ − τ C)/Cp , τ /Cd })−1 < 1.

The iterate error is bounded by a constant multiple of V k , which gives R-linear convergence. The full derivation is given in Appendix A.1. The threshold in Proposition 3.1 cannot be chosen independently of the problem; the obstruction already occurs in the strongly convex quadratic subclass. With ϑ = τ /β, the following result gives a quantitative obstruction. Theorem 3.2 (No problem-independent positive relative-step interval). For every 0<ϑ≤

80 , 119

there is an m = 3 slack-last QP with Q1 , Q2 ≻ 0 and [A B] of full row rank, together with a finite feasible initialization, for which direct x → y → z → λ ADMM with relative multiplier step ϑ generates a bounded nonconvergent sequence. Consequently, there is no ϑ̄ > 0 such that, for every problem in the class, the method converges for every 0 < ϑ < ϑ̄. Proof. Fix ϑ. Appendices A.3 and A.4 construct a continuous one-parameter branch matrix U (α) := p UD (r, α), where D = diag(1, 0, 0) and r = 7ϑ/(80 √ − 7ϑ). The branch is unstable at the degenerate endpoint α = 0, while the other endpoint α = 2 − 1 is strictly stable. Continuity gives an interior αc with ρ(U (αc )) = 1; at this parameter the associated problem is already strongly convex and [A B] has full row rank. Uniqueness of the KKT point excludes the eigenvalue +1, so the remaining unit-circle mode generates a bounded nonconvergent error sequence. Finally, the strict projection margin keeps every sufficiently small perturbation on the same affine branch; the appendix also constructs a feasible initialization and verifies boundedness of the full ADMM orbit. When τ̄ is unavailable, the same global error bounds yield an exact look-ahead backtracking rule with one additional trial primal sweep. We make no model-independent novelty claim for this rule; it is recorded as a consequence of the slack-last bounds rather than a primary contribution. Corollary 3.3 (General adaptive dual step with backtracking). Under the assumptions of Proposition 3.1, write u = (x, y, z), E = [A, B, Im ], and set 1 + max{LF , LG } + β∥E∥2 , λmin (diag(µF I, µG I, 0) + βE ⊤ E) PGλ (u) := u − proxh (u − ∇sλ (u)) , BE (v) := ∥E∥2 κ2p ∥v∥2 , κp :=

where h(u) = ιRm (z) and sλ is the smooth part of Lβ (·; λ), while Gλ denotes one exact x → y → z + Gauss–Seidel primal sweep at fixed multiplier. Fix χ, δ ∈ (0, 1) and τmax > 0. Algorithm 1 accepts a b satisfy trial only when its (b v , D) b τ BE (b v ) ≤ (1 − χ)D. (3.3) Under exact block solves and exact evaluation of the acceptance test, backtracking terminates finitely, the accepted steps have a positive lower bound independent of k, and {(uk+1 , λk )}k≥1 converges globally R-linearly. 8

Algorithm 1 Backtracking dual-step ADMM with an exact trial primal sweep 0 m Require: uinit = (xinit , y init , z init ) with z init ∈ Rm + , λ ∈ R ; χ, δ ∈ (0, 1), τmax > 0 1 init 1: u ← Gλ0 (u ) 2: for k = 1, 2, . . . do 3: rk ← Euk − b 4: for j = 0, 1, 2, . . . do b ← λk−1 − τ rk ; u 5: τ ← τmax δ j ; λ b ← Gλb (uk ) b − Lβ (b b b ← Lβ (uk ; λ) 6: vb ← PGλb (uk ); D u; λ) b then 7: if τ BE (b v ) ≤ (1 − χ)D k k+1 b u 8: (τk , λ , u ) ← (τ, λ, b); exit inner loop 9: else 10: retain (uk , λk−1 ) 11: end if 12: end for 13: end for If set

F (x) = 21 x⊤ Q1 x + c⊤ 1 x,

G(y) = 12 y ⊤ Q2 y + c⊤ 2 y,

K = diag(Q1 , Q2 , 0) + βE ⊤ E,

Q1 , Q2 ≻ 0,

BK (v) := β −1 v ⊤ (K −1 + 2I + K)v.

Then BK (v) is also an upper bound for ∥E(u − ū(λ))∥2 , so one may replace (3.3) by (3.4)

b τ BK (b v ) ≤ (1 − χ)D,

with the same finite-backtracking and convergence conclusions. The proof of Corollary 3.3 and of this quadratic refinement is given in Appendix A.2.

3.2

Stability of the Period-66 Example

For the rational QP (2.1), set β = 1 and use the six-dimensional essential state w = (y, z, λ) ∈ R6 . On a strict projection branch with mask D, one complete update is affine: (0)

w+ = TD (τ )w + aD (τ ),

(1)

TD (τ ) = TD + τ TD .

(3.5)

Here τ enters only the multiplier block row. The explicit block matrices are given in Appendix A.7. At the unique KKT point, q ⋆ = (−1, 1), so the local branch is D01 . Figure 2 separates the three scopes below.

9

(a) Spectral radius on the strict KKT branch

ρ(T01(1)) > 1

1.000 0.999

ρ(T01(τ))

τc 0.998

τ = 1/2

0.997 0.996 0.995 0.994 0.0

0.2

0.4

0.6

0.8

1.0

multiplier step τ (b) Certified convergence intervals near 1/2 [0.49, 0.51] common H

same initialization [0.5 − 10−10, 0.5 + 10−10] marker not to scale

0.485

0.490

0.495

0.500

0.505

0.510

0.515

multiplier step τ

Figure 2: Certified dual-step ranges for the fixed rational instance: pointwise local attraction on the strict D01 branch, a uniform common-Lyapunov interval, and convergence of the initialization in Theorem 2.1. For H ≻ 0, write

∥e∥H := (e⊤ He)1/2 .

For a fixed τ , we say that the KKT state w⋆ is locally Q-linearly attracting if there exist a neighborhood Uτ of w⋆ , a norm ∥ · ∥τ , and a constant κτ ∈ (0, 1) such that every w0 ∈ Uτ remains in Uτ and satisfies ∥wk+1 − w⋆ ∥τ ≤ κτ ∥wk − w⋆ ∥τ , k ≥ 0. Theorem 3.4 (Dual step length for the period-66 instance). For the rational QP (2.1) and (3.1): 1. there exist a rational matrix H ≻ 0, a radius r > 0, and a constant κ ∈ (0, 1), all independent of τ ∈ [49/100, 51/100], such that ∥w0 − w⋆ ∥H ≤ r

=⇒

∥wk+1 − w⋆ ∥H ≤ κ∥wk − w⋆ ∥H

for every k ≥ 0. In particular, the KKT point is uniformly locally Q-linearly attracting throughout 49 51 ≤τ ≤ ; 100 100 2. the initialization of Theorem 2.1 converges to that KKT point whenever τ−

1 ≤ 10−10 ; 2 10

3. for each fixed τ ∈ (0, 1), the KKT state w⋆ is locally Q-linearly attracting if and only if 0 < τ < τc , where 0.9366061114 < τc < 0.9366061115. Equivalently, T01 (τ ) is Schur stable exactly for 0 < τ < τc . For every fixed τ in this interval, the neighborhood, Lyapunov metric, and contraction factor may depend on τ . Proof. At τ = 1/2, an exact rational Lyapunov equation produces a common metric. Exact endpoint tests and a quadratic chord identity extend contraction to [0.49, 0.51]; strict complementarity supplies a projection-safe neighborhood. For the specified period-66 initialization, an exact 232-step interval enclosure for |τ − 1/2| ≤ 10−10 enters that neighborhood. Finally, exact Schur recursion and a Sturm count identify the unique boundary τc ; inside the strict D01 branch, the resulting Lyapunov metric and the Banach fixed-point theorem give local linear convergence. The exact derivation, polynomial, and verification commands are in Appendices A.8 and A.9. The quantifiers in the three assertions are intentionally different. The first is uniform in τ but local in the initial state; the second concerns only the initial state used in Theorem 2.1; and the third is a pointwise local branch criterion whose metric and neighborhood may depend on τ . Only the second assertion says anything about the former period-66 initialization. None of the three assertions gives arbitrary-initial global convergence over the displayed fixed-instance ranges. Proposition 3.1 has a fourth, class-level quantifier: for every fixed problem satisfying its assumptions, there is a problem-dependent τ̄ that works from every finite initialization.

4

A Period-23 Attracting Cycle

This section presents a separate Kimi Code K3 route that was not supplied with the period-66 candidate or its certificate.

4.1

Exact Period-23 Certificate

The route received the same mathematical question without the Codex matrices, projection word, initialization, certificate, or project-specific route guidance (Appendix C.1). It produced an m = 3 non-KKT sequence of minimal period 23. More strongly, Proposition 4.1 certifies an open invariant ellipsoid of reduced initializations attracted phasewise to that sequence. All 69 projection inputs have common strict margin greater than 1/250, and an exact Lyapunov inequality certifies local attraction. The retained run record and starting condition are summarized in Appendix C. The route reduced each fixed projection branch to an affine map on v = (y, t), t = z + λ, screened projection words with KKT-compatible QP data, and promoted a candidate only after exact rational replay. An exact Lyapunov search then certified local attraction.

11

Consider the rational m = 3 QP with β = 1 and     5/36 1/60 25/97 4/61 1/54 5/83 b =  1/60 5/77 5/91  , b = 1/54 13/92 23/88 , A B 25/97 5/91 11/12 5/83 23/88 53/58     85/93 −1/57 −3/11 99/100 −1/51 −3/47 b x = −1/57 99/100 −5/86 , b y =  −1/51 72/79 −18/65 , Q Q −3/11 −5/86 7/78 −3/47 −18/65 4/43       −2/17 33/98 −31/99 bb = −1/14 ,    b c1 = −33/25 , b c2 = 19/36  . 56/73 −24/55 −11/20

(4.1)

Composing the 23 branch maps of word W23 yields the return map Φper (v) = Mper v + cper (B.2) with exact rational fixed point vb0 ∈ Q6 . The certified projection-sign word is W23 = (+, −, +)5 (−, +, +)7 (−, −, +)2 (−, −, −) (−, −, +)8 .

(4.2)

Proposition 4.1 (Exact period-23 certificate for nearby initializations). For the rational data (4.1), bx , Q b y ≻ 0 and det(A) b det(B) b ̸= 0. The direct iteration (1.5), with β = 1, applied to Q min

x,y,z∈R3

s.t.

1 ⊤b 1 ⊤b x Qx x + b c⊤ c⊤ 1 x + y Qy y + b 2 y + ιR3+ (z) 2 2 b + By b + z = bb, Ax

(4.3)

has the following properties. (i) It has a unique primal–dual KKT point. (ii) Direct ADMM has a non-KKT sequence of minimal period 23. Its strict projection-sign word is (4.2); its exponents denote consecutive repetitions and sum to 23. All 23 × 3 = 69 projection inputs are separated from zero: 1 min |b tki | > . 0≤k<23 1≤i≤3 250 min

(iii) There is a rational matrix P ≻ 0 for which  Ecert := vb0 + e : e⊤ P e <

1 4000



(4.4)

is an open invariant set for the 23-step return map (B.2). Every v 0 ∈ Ecert follows the repeating pattern W23 and converges phasewise to the period-23 sequence. Consequently, the reconstructed ADMM sequence is nonconvergent for every reduced initialization v 0 ∈ Ecert . The proof, together with the reduced branch maps, the return-map construction, and the b and B b are nonsingular, the example invariant-ellipsoid data, is given in Appendix B. Because A converts to an all-identity instance. b and B b are nonsingular, the change of variables Corollary 4.2 (Identity-slack equivalence). Since A b w = By b converts (4.3) into an equivalent rational strongly convex [I3 , I3 , I3 ] identity-slack u = Ax, QP. The transformed Hessians remain positive definite, so Proposition 4.1 yields a locally attracting period-23 counterexample in the all-identity model as well. The change-of-variables formulas defining the equivalent rational all-identity instance are given in Appendix B. 12

Figure 3 summarizes the certified word, projection margin, invariant-ellipsoid slice, and spectrum of the period map. (a) Certified projection pattern

23 = (+, − , + )5 (−, + , + )7 (−, − , + )2 (−, − , − ) (−, − , + )8

t1 t2 t3 0

4

5

11

12

14

phase within one ADMM period k tik > 0 (inactive)

tik < 0 (active)

(c) Certified location of the spectrum of Mper 1.00

slice: Δy = 0, Δt3 = 0

⊤

e Pe < 1/4000

0.75

cycle phase v ̂0 (e = 0)

Δt2

22 k, i

(b) Certified invariant slice of cert 0.005

18

projection margin: min|tik | > 1/250

0.50

0.000

⊤ P − Mper PMper ≻ 0 ⟹ ρ(Mper) < 1

−0.005

Im ξ

0.25 certified interval: |Δt1| < 1/√ 6000

−0.015 −0.010 −0.005 0.000

0.005

0.010

0.00 −0.25

0.015

Δt1

0 (multiplicity 3)

−0.50 −0.75 −1.00 −1.0

−0.5

0.0

0.5

1.0

Re ξ

Figure 3: Kimi period-23 certificate: projection word and margin; invariant-ellipsoid slice; spectrum of Mper .

4.2

Different Discovery Mechanisms of the Two AI-Assisted Routes

This paper compares two research routes that actually occurred and were fully recorded, rather than the intrinsic capabilities of two base models under controlled conditions. To describe the research environment beyond the model, we write a research harness as H = (M, W, T, S, A, G, V ), where M denotes the base model, W the versioned workspace, T the tools, S the prompts, skills, and instructions, A the persistent research artifacts, G the human decision and claim-promotion gates, and V the exact verifiers. Human direction is a control mechanism inside G, not an independent component outside H. A research route is one concrete run of a harness configuration together with the mathematical trajectory it produces. The present H is used only to describe the research process for the identity-slack question in this paper; it does not constitute a general-purpose AI4Math platform. The two routes address the same mathematical problem, but under different harness configurations. The Codex route ran in a long-maintained project workspace with access to accumulated failure records, reduced representations, experiment scripts, and exact certificates, and with iterative human steering. The Kimi route ran in a frozen blind workspace without access to the period-66 candidate, certificate, or project history, and received only a few continue-search instructions. Both routes share the same evidence principles: floating-point trajectories and model-generated derivations nominate candidates only; periodicity claims must pass exact problem validation, strict branch admissibility, raw ADMM replay, period closure, and minimal-period checks; stability claims further require 13

the corresponding Lyapunov, Schur, Sturm, or interval tests. Detailed process dossiers appear in Appendix C. Exploration candidate evidence only

Mathematical brief identity-slack

AI exploration reduction screening

Certification exact verification + human audit

Numerical or symbolic candidate

Exact rational reconstruction

Claim promotion exact gates

Theorem-level claim

Gate failure: revise the search object, candidate, or evidence requirement

Codex route Long-running project workspace; iterative human steering

Kimi route Frozen blind workspace; no Codex candidate or certificate

Figure 4: Candidate-generation and claim-promotion workflow shared by the two AI-assisted research routes. Models may propose representations, search objects, and candidates in the exploration stage, but only conclusions that pass exact verification and a human claim-scope audit enter the final mathematical record. The two routes share the same mathematical question and evidence principles, but use different harness configurations. Search space and construction style. The two routes first differ markedly in their search objects. The Codex route reduced the original ADMM iteration to a piecewise-affine dynamical system and then shifted from searching Hessian data (Q1 , Q2 , b̄) to searching resolvent parameters (M, N ) and a realizable active-set itinerary. Its core object is a switching system formed by distinct projection branches, culminating in the itinerary (00)2 (01)64 . Thus the route is closer to a construction driven by dynamical mechanism: first identify a nearrotation/reset structure, then recover an optimization problem that realizes it. The Kimi route is closer to inverse design of an optimization instance. It jointly searched over KKT-compatible quadratic-program data b B, b Q bx , Q by , b (A, c1 , b c2 ) and a realizable projection itinerary W23 , and used a fixed point of the period return map to construct an ADMM instance with a prescribed dynamical property. State representation and analysis object. The Codex route used the four-dimensional signed piecewise-affine state s = (y, q), q = z + λ, whose main role is to expose active-set switching. The period-66 itinerary can be interpreted as a comparatively long near-rotation phase, followed by a short reset through a few 00 branches. The Kimi route used the six-dimensional projector-aligned state v = (y, t),

t = z + λ, 14

and analyzed the one-period return map Φper (v) = Mper v + cper directly. This representation unifies existence and local stability of the periodic orbit as questions about a return-map fixed point and contraction. Certificate goals and dynamical conclusions. The primary goal of the Codex certificate is a strict existence proof for a non-KKT periodic orbit. Its evidence includes exact period closure, strict branch admissibility, raw ADMM replay, and minimal-period verification. The resulting period-66 counterexample moreover retains the same branch itinerary under small data perturbations. The Kimi certificate further seeks local attraction of the periodic orbit. In addition to period closure and strict projection conditions, it constructs a rational Lyapunov matrix satisfying ⊤ P − Mper P Mper ≻ 0

and an invariant ellipsoid preserved by the return map. Thus period-23 nonconvergence is not the phenomenon of a single special initialization, but occurs on an open set of reduced initializations. Continuation in optimization theory. The Codex route not only produced a counterexample, but also carried the active-set switching instability into multiplier-relaxation analysis: after freezing the problem and initialization and varying only the multiplier step τ , it further studied problemdependent small-step convergence, the impossibility of a class-uniform step, and a fixed-instance local stability boundary. The theoretical emphasis of the Kimi route is instead on return-map contraction and basin stability under reduced-initialization perturbations. Table 1 summarizes the main differences between the two routes in harness configuration, mathematical search objects, and final certificates.

15

Table 1: Comparison of the two realized AI-assisted research routes. Aspect

Codex / GPT-5.6 Sol route

Kimi Code / Kimi K3 route

Harness configuration

Long-running project workspace; project-specific ADMM skill and experiment toolchain; persistent research artifacts; iterative human steering

Frozen blind workspace; generic research skills with shell/Python tools; isolated route state; few continue-search instructions

Main search object

Resolvent parameters (M, N ) and realizable active-set itinerary (00)2 (01)64

KKT-compatible QP data and projection itinerary W23

Reduced state

s = (y, q) ∈ R4 , q = z + λ; direct m = 2 v = (y, t) ∈ R6 , t = z + λ; m = 3 model, all-identity model equivalently convertible to all-identity form

Construction style

Mechanism-driven: state reduction, branch-spectrum analysis, and near-rotation/reset itinerary design

Inverse design: jointly synthesize problem data, projection itinerary, and return-map fixed point

Main certificate

Exact period closure, strict branch checks, raw ADMM replay, and minimal-period verification

Exact period closure, strict projection checks, discrete Lyapunov inequality, and invariant ellipsoid

Dynamical conclusion

Minimal period-66 non-KKT orbit; exposes active-set switching instability

Minimal period-23 locally attracting non-KKT orbit; certified open attracting basin

Robustness type Structural persistence under problem-data perturbations

Basin stability under reduced-initialization perturbations

Theorem continuation

Multiplier relaxation, step-size sensitivity, and class-level step conclusions

Return-map contraction and local attracting-basin certification

Recorded process use

≈ 40 h wall-clock; ≈ 1.704 × 109 recorded tokens

≈ 9 h wall-clock; ≈ 6.327 × 107 recorded tokens

Scope note. The times and token counts in the table record only the process use of two realized runs. Because the routes differ in base model, workspace, tools, accumulated context, token accounting, and human steering, these numbers do not constitute a controlled model-efficiency comparison. Full prompts, workspace manifests, intervention records, and verification commands appear in Appendix C.

The two routes illustrate complementary modes of AI-assisted optimization research. The Codex route emphasizes discovery of a hidden state-space structure and an algorithmic instability mechanism; the Kimi route emphasizes inverse construction of an optimization instance with prescribed dynamical behavior, together with certification of its local stability. These differences are consistent with the respective harness configurations and historical paths, suggesting that persistent workspaces, prior representations, project skills, evidence gates, and human decisions may jointly shape the mathematical space a model actually explores. Nevertheless, the present records cannot uniquely attribute the divergence to the base model, workspace memory, project skills, or human steering alone. Identifying their separate effects would require controlled model–harness ablations under matched tools, budgets, and prompts. Accordingly, the comparison in this paper should be understood as one between two realized model–harness routes, not as a ranking of base-model capabilities. 16

5

Discussion

5.1

What the Results Show

An identity last coefficient matrix does not by itself restore convergence of unmodified direct threeblock ADMM. The period-66 example rules out explanations based on nonconvexity, nonunique block solves, projection ties, or floating-point drift, and its itinerary persists under small data perturbations. b and B, b an The period-23 example adds a certified open attracting basin and, by nonsingularity of A equivalent all-identity [I3 , I3 , I3 ] instance (Corollary 4.2). Multiplier relaxation further shows that a problem-dependent small step can restore convergence, but no positive relative step is class-uniform.

5.2

AI for Optimization: From Problem Solving to Theory Discovery

Broadly, AI for optimization concerns not only using AI to solve a given optimization model, but also using AI in the formation of optimization models, algorithms, and theory. Relative to the object of study, this role can be organized into three interrelated levels. At the problem-solving level, AI may assist formulation and reformulation, variable and constraint decomposition, algorithm and solver selection, initialization, parameter configuration, and runtime diagnosis or intervention. The usual goal is to improve efficiency, robustness, or automation on a fixed problem. At the algorithm-design level, AI may further participate in the design of update rules, relaxation parameters, penalty terms, correction steps, and adaptive strategies. The task is no longer only to execute an existing algorithm, but to diagnose failure modes and propose analyzable modifications suggested by the discovered structure. The multiplier- relaxation results in this paper illustrate this level: after the period-66 counterexample had been certified, the research continued from “why the algorithm fails” to “which part of the update restores stability”, and then distinguished problem-dependent convergent steps, fixed-instance local stability boundaries, and the impossibility of class-uniform guarantees. At the theory-discovery level, AI may participate in mathematical representation discovery, structured instance design, counterexample and extreme-instance construction, theorem conjecture, proof-route search, and exact certificate generation. The present work primarily studies this theoryfacing role. The two routes show that AI can reshape the search space of optimization research in different ways: the Codex route reduced the original ADMM iteration to a low-dimensional signed piecewise-affine system and turned counterexample search into the design of resolvent parameters and reachable active-set itineraries; the Kimi route jointly searched over KKT-compatible problem data and projection itineraries, turning periodic counterexample construction into inverse instance design with prescribed return-map properties. The AI-for-optimization capabilities illustrated here can therefore be summarized in the following stages. Representation discovery. The raw iteration of a complicated optimization algorithm often contains redundant variables, implicit projections, and multilayered dependencies. AI can search for more analysis-friendly state variables, coordinate changes, operator splittings, or piecewise structures, thereby transforming the original problem into a finite-dimensional linear, affine, or operator dynamical system. A change of representation affects not only proof difficulty, but also which mathematical objects can subsequently be searched and certified.

17

Structured construction and inverse design. AI can convert open questions such as “does a counterexample exist?” into construction problems with explicit parameterizations, branch conditions, and algebraic constraints. The goal may be to design an optimization instance on which an algorithm exhibits a prescribed behavior—for example a periodic orbit, boundary stability, slow convergence, active-set switching, or parameter sensitivity. The same capability can also generate stress-test instances and robustness benchmarks, not only theoretical counterexamples. Failure diagnosis and algorithmic intervention. When an algorithm exhibits nonconvergence, oscillation, or numerical instability, AI can help separate sources such as objective geometry, constraint degeneracy, block ordering, active-set switching, or parameter choice. The resulting dynamical structure can then guide algorithmic modifications, including relaxation, damping, proximal regularization, correction steps, and adaptive parameter rules. Counterexample construction is therefore not only a negative result, but also an input to algorithm design. Proof search and exact certification. Numerical experiments and floating-point computation may discover candidates, but they cannot independently carry theorem-level evidence. AI can organize symbolic derivation, branch enumeration, rational reconstruction, interval arithmetic, Lyapunov search, Schur stability tests, and Sturm root counting into a reproducible certification pipeline. In this paper, agents nominated candidate representations, derivations, and certificate designs; period closure, strict branch conditions, raw ADMM replay, and the corresponding stability predicates were supported by independently executable exact checks. Analytic conclusions remain established by the mathematical arguments in the main text and appendices. Theorem continuation. The role of AI can extend beyond “finding an answer” to a single question. After a candidate or theorem has been certified, representations, code, failure records, and proof artifacts in a persistent workspace can be reused to pose neighboring questions—changing a parameter, relaxing an assumption, seeking a boundary case, or establishing an impossibility result. The progression in this paper from the period-66 counterexample to local multiplier-step stability, convergence from a specified initialization, problem-dependent global guarantees, and the impossibility of class-uniform guarantees is an instance of such theorem continuation. The overall process can be summarized as problem formulation −→ representation discovery −→ candidate or algorithm design −→ analysis −→ exact certification −→ theorem or algorithm continuation −→ knowledge reuse. The final reuse step may include distilling effective state reductions, proof templates, certificate structures, and experimental workflows into research skills that can be invoked on other optimization problems. The role of the research harness. These capabilities are not produced by the base model alone; they depend on the research environment in which the model operates. A versioned workspace provides long-term research memory; tools and skills delimit executable operations; persistent artifacts allow earlier results to be reused; exact verifiers prescribe the evidentiary standard by which candidates enter the mathematical record; and human checkpoints control problem choice, claim scope, literature boundaries, and final acceptance. Thus a research harness does more than store research logs: it also shapes the space of representations, candidates, and proofs that a model can explore. 18

This paper presents one case study of that research pattern on the identity-slack ADMM question. It does not prove that the same capabilities already transfer reliably to other optimization domains, nor can it separate the causal contributions of the base model, workspace memory, project skills, and human steering from the difference between the two routes. Future work in AI for optimization may further explore Lyapunov-function construction, error-bound discovery, splitting design, adaptive update rules, extreme-instance generation, and reusable proof patterns, and may evaluate transferability through frozen workspaces, matched tool budgets, and controlled ablation experiments.

5.3

Limits and Outlook

Several mathematical questions remain open. First, it is still unclear whether the two-dimensional pure-quadratic subclass admits a shorter counterexample whose projection branches are all strictly admissible. Second, quantitative conditions excluding active-set switching instability are still needed, as is a sharper characterization of the exact global multiplier-step range for a fixed problem. Finiteprecision computation, inexact block solves, alternative block update orders, nonorthant cone constraints, and more general nonsmooth models also require further analysis. The present certificates rely mainly on exact rational arithmetic, finite symbolic derivation, and independently executable algebraic and spectral checks; they have not yet been fully translated into formal proofs inside a proof assistant. A natural next step is to encode the critical ingredients— period closure, branch admissibility, Lyapunov inequalities, and Schur–Sturm tests—in Lean, Isabelle, or another formal verification system, thereby narrowing the gap between computer-assisted certificates and fully formalized proofs. On the AI-evaluation side, this paper compares two realized model–harness routes rather than base-model capabilities under controlled conditions. Future studies should use frozen workspaces, preregistered success criteria, matched tool and compute budgets, and controlled human or model baselines. Systematic ablations of the base model, workspace memory, project-specific skills, persistent research artifacts, and human steering are also needed to identify each component’s contribution to representation discovery, candidate construction, certificate design, and theorem continuation. Another important question is whether the state-reduction, structured-search, and exact-certification patterns developed here transfer to Douglas–Rachford splitting, primal–dual splitting, and other operator splitting methods, rather than merely rediscovering or reproducing the ADMM examples of this paper.

References [1] Heinz H. Bauschke and Patrick L. Combettes, Convex analysis and monotone operator theory in Hilbert spaces, 2 ed., CMS Books in Mathematics, Springer, Cham, 2017. [2] Daniel Boley, Local linear convergence of the alternating direction method of multipliers on quadratic or linear programs, SIAM Journal on Optimization 23 (2013), no. 4, 2183–2207. [3] Stephen Boyd, Neal Parikh, Eric Chu, Borja Peleato, and Jonathan Eckstein, Distributed optimization and statistical learning via the alternating direction method of multipliers, Foundations and Trends in Machine Learning 3 (2011), no. 1, 1–122. [4] Xingju Cai, Deren Han, and Xiaoming Yuan, On the convergence of the direct extension of ADMM for three-block separable convex minimization models with one strongly convex function, Computational Optimization and Applications 66 (2017), no. 1, 39–73.

19

[5] Caihua Chen, Bingsheng He, Yinyu Ye, and Xiaoming Yuan, The direct extension of ADMM for multi-block convex minimization problems is not necessarily convergent, Mathematical Programming 155 (2016), no. 1–2, 57–79. [6] Jonathan Eckstein and Dimitri P. Bertsekas, On the Douglas–Rachford splitting method and the proximal point algorithm for maximal monotone operators, Mathematical Programming 55 (1992), no. 1–3, 293–318. [7] Euhanna Ghadimi, André Teixeira, Iman Shames, and Mikael Johansson, Optimal parameter selection for the alternating direction method of multipliers (ADMM): Quadratic problems, IEEE Transactions on Automatic Control 60 (2015), no. 3, 644–658. [8] Baptiste Goujaud, Aymeric Dieuleveut, and Adrien Taylor, Counter-examples in first-order optimization: A constructive approach, IEEE Control Systems Letters 7 (2023), 2485–2490. [9] Bingsheng He, My Talks 19(V), http://maths.nju.edu.cn/~hebma/. [10] Bingsheng He, Min Tao, and Xiaoming Yuan, Alternating direction method with gaussian back substitution for separable convex programming, SIAM Journal on Optimization 22 (2012), no. 2, 313–340. [11] Bingsheng He, Shengjie Xu, and Xiaoming Yuan, Extensions of ADMM for separable convex optimization problems with linear equality or inequality constraints, Handbook of Numerical Analysis, vol. 24, Elsevier, 2023, pp. 511–557. [12] Bingsheng He and Xiaoming Yuan, A class of ADMM-based algorithms for three-block separable convex programming, Computational Optimization and Applications 70 (2018), no. 3, 791–826. [13] Mingyi Hong and Zhi-Quan Luo, On the linear convergence of the alternating direction method of multipliers, Mathematical Programming 162 (2017), no. 1–2, 165–199. [14] Thomas Lew, Marcus Greiff, John Subosits, and Brian Plancher, Solving quadratic programs with slack variables via ADMM without increasing the problem size, European Journal of Control (2026), 101557. [15] Min Li, Defeng Sun, and Kim-Chuan Toh, A convergent 3-block semi-proximal ADMM for convex minimization problems with one strongly convex block, Asia-Pacific Journal of Operational Research 32 (2015), no. 4, 1550024. [16] Jingwei Liang, Jalal Fadili, and Gabriel Peyré, Local convergence properties of Douglas–Rachford and alternating direction method of multipliers, Journal of Optimization Theory and Applications 172 (2017), no. 3, 874–913. [17] Tianyi Lin, Shiqian Ma, and Shuzhong Zhang, On the global linear convergence of the ADMM with multiblock variables, SIAM Journal on Optimization 25 (2015), no. 3, 1478–1497. [18] Tianyi Lin, Shiqian Ma, and Shuzhong Zhang, Global convergence of unmodified 3-block ADMM for a class of convex minimization problems, Journal of Scientific Computing 76 (2018), no. 1, 69–88. [19] Min Tao and Xiaoming Yuan, Convergence analysis of the direct extension of ADMM for multiple-block separable convex minimization, Advances in Computational Mathematics 44 (2018), no. 3, 773–813.

A

Multiplier-Relaxation Proofs

A.1

Proof of Proposition 3.1

Proof. Write u = (x, y, z) and E = [A, B, Im ]. Decompose the augmented Lagrangian as Lβ (u; λ) = sλ (u) + h(u), where sλ (u) := F (x) + G(y) − λ⊤ (Eu − b) +

20

β ∥Eu − b∥2 , 2

h(u) := ιRm (z). +

Set dβ (λ) = min Lβ (u; λ). u

We first verify uniqueness of the KKT point. Full row rank of [A B] implies strict feasibility: for any z > 0, the equation [A B](x, y) = b − z is solvable. Strong convexity gives a unique primal solution. In the present multiplier convention, the unaugmented negative dual objective is ϕ0 (λ) = F ∗ (A⊤ λ) + G∗ (B ⊤ λ) − b⊤ λ + ιRm (λ). − Standard conjugacy results imply that an L-smooth convex function has a 1/L-strongly convex conjugate [1]. Hence F ∗ and G∗ are 1/LF - and 1/LG -strongly convex, respectively. Consequently,   AA⊤ BB ⊤ m0 = λmin + > 0, LF LG where strict positivity follows from the full-row-rank assumption. The multiplier is therefore unique. We next establish the global primal error bound at fixed multiplier. Set Kµ = diag(µF I, µG I, 0) + βE ⊤ E,

µp = λmin (Kµ ) > 0,

Lp = max{LF , LG } + β∥E∥2 . For all u, v, ⟨∇sλ (u) − ∇sλ (v), u − v⟩ ≥ (u − v)⊤ Kµ (u − v) ≥ µp ∥u − v∥2 , ∥∇sλ (u) − ∇sλ (v)∥ ≤ Lp ∥u − v∥. Let ū = ū(λ) denote the unique minimizer of Lβ (·; λ), and set
p = proxh u − ∇sλ (u) , r = u − p = PGλ (u). Proximal optimality gives r − ∇sλ (u) ∈ ∂h(p),

−∇sλ (ū) ∈ ∂h(ū).

By monotonicity of ∂h, ⟨∇sλ (u) − ∇sλ (ū), p − ū⟩ ≤ ⟨r, p − ū⟩. Using the µp -strong monotonicity and Lp -Lipschitz continuity of ∇sλ , we obtain µp ∥u − ū∥2 ≤ ⟨∇sλ (u) − ∇sλ (ū), u − ū⟩ = ⟨∇sλ (u) − ∇sλ (ū), p − ū⟩ + ⟨∇sλ (u) − ∇sλ (ū), r⟩ ≤ ⟨r, p − ū⟩ + Lp ∥u − ū∥ ∥r∥ ≤ (1 + Lp )∥u − ū∥ ∥r∥. Therefore ∥u − ū(λ)∥ ≤ κp ∥ PGλ (u)∥,

κp =

1 + Lp , µp

globally, with a constant independent of λ. Exact x → y → z block minimization gives γ=

 1 min λmin (µF I + βA⊤ A), λmin (µG I + βB ⊤ B), β > 0 2

and Lβ (uk ; λk ) − Lβ (uk+1 ; λk ) ≥ γ∥uk+1 − uk ∥2 . Let ax = LF + β∥A⊤ A∥,

ay = LG + β∥B ⊤ B∥,

σ 2 = a2x + β 2 ∥B ⊤ A∥2 + a2y + β 2 ∥A∥2 + β 2 ∥B∥2 + (β + 2)2 .

21

For ∆x = xk − xk+1 , ∆y = y k − y k+1 , and ∆z = z k − z k+1 , write the three blocks of PGλk (uk ) as (PGx,k , PGy,k , PGz,k ). The block optimality conditions and nonexpansiveness of the orthant projection then give ∥ PGx,k ∥ ≤ ax ∥∆x∥, ∥ PGy,k ∥ ≤ β∥B ⊤ A∥∥∆x∥ + ay ∥∆y∥, ∥ PGz,k ∥ ≤ β∥A∥∥∆x∥ + β∥B∥∥∆y∥ + (β + 2)∥∆z∥. Consequently, ∥ PGλk (uk )∥ ≤ σ∥uk+1 − uk ∥. For the x, y blocks this uses only global Lipschitz continuity of ∇F, ∇G; for z, it compares the projection fixed-point identities at the current point and the block minimizer. Completing the square in the quadratic penalty and applying Fenchel duality gives the explicit Moreauenvelope representation   1 −dβ (λ) = minm ϕ0 (η) + ∥η − λ∥2 . (A.1) η∈R 2β Since ϕ0 is m0 -strongly convex, its Moreau envelope in (A.1) is strongly convex with modulus md =

m0 >0 1 + βm0

and has 1/β-Lipschitz gradient [1]. It follows that ∥λ − λ⋆ ∥ ≤ m−1 d ∥∇dβ (λ)∥, Define

∇dβ (λ) = b − E ū(λ).

∆kp = Lβ (uk+1 ; λk ) − dβ (λk ), ∆kd = dβ (λ⋆ ) − dβ (λk ), V k = ∆kp + ∆kd .

The gap calculation of Hong and Luo [13, Theorem 3.1, Lemma 3.1, and (3.16)–(3.17)], in the present sign convention, yields V k − V k−1 ≤ −a∥uk+1 − uk ∥2 − τ ∥∇dβ (λk )∥2 , Thus a > 0 whenever 0<τ <

a = γ − τ ∥E∥2 κ2p σ 2 .

γ . ∥E∥2 κ2p σ 2

The cost-to-go estimate on the noncompact orthant can be verified directly. Set ∆x = xk − xk+1 , ∆y = y k − y k+1 , and ∆z = z k − z k+1 , and define   0 A⊤ B A⊤ ∥HGS ∥2 0 B⊤ , HGS = β 0 Cp = . 2µp 0 0 0 The three exact block optimality conditions, including the normal-cone condition for z, give   −βA⊤ (B∆y + ∆z)  ∈ ∂u Lβ (uk+1 ; λk ). −βB ⊤ ∆z wk+1 =  0 Uniform µp -strong convexity at fixed multiplier therefore yields ∆kp ≤

∥wk+1 ∥2 ≤ Cp ∥uk+1 − uk ∥2 . 2µp

22

Moreover, qβ = −dβ is md -strongly convex and 1/β-smooth, so one may take Cd =

1 , 2βm2d

∆kd ≤ Cd ∥∇dβ (λk )∥2 .

These constants are independent of k, λk , and the dual step. Consequently, ρ = (1 + η)−1 ∈ (0, 1)

η = min{a/Cp , τ /Cd } > 0, imply V k − V k−1 ≤ −ηV k ,

V k ≤ ρV k−1 .

Finally, strong convexity and Lipschitz continuity of the fixed-multiplier minimizer give ∥uk+1 − ū(λk )∥2 ≤ 2∆kp /µp , ∥λk − λ⋆ ∥2 ≤ 2∆kd /md , ∥ū(λk ) − u⋆ ∥ ≤ (∥E∥/µp )∥λk − λ⋆ ∥. Hence there is a constant C > 0 for which ∥(uk+1 , λk ) − (u⋆ , λ⋆ )∥ ≤ Cρk/2 . The assumption z 0 ∈ Rm + in Proposition 3.1 ensures that the initial augmented-Lagrangian value is finite. The z-update then preserves z k ∈ Rm + for every k ≥ 0. The compact-polyhedral assumption in the original Hong–Luo theorem is not invoked directly here: the global smooth strongly convex structure above replaces the error bounds for which that assumption is used. Accordingly, the inherited component is the gap-contraction architecture; the model-specific component proved here is the verification of the required global bounds and explicit constants on the noncompact slack-last class.

A.2

Backtracking Rule

This appendix proves Corollary 3.3 and the quadratic refinement stated in Section 3.

Proof of Corollary 3.3. Fix an arbitrary candidate τ , and abbreviate its trial values by b λ = λ,

u = uk ,

u+ = u b,

Let

D = Lβ (u; λ) − Lβ (u+ ; λ).

e = u − ū(λ), v = PGλ (u).

The global primal error bound in Proposition 3.1 directly gives ∥Ee∥2 ≤ ∥E∥2 ∥e∥2 ≤ ∥E∥2 κ2p ∥v∥2 = BE (v).

(A.2)

The trial decrease can be evaluated from the block optimality conditions, without subtracting two nearby + + augmented-Lagrangian values. After the initial primal sweep, z, z + ∈ Rm + . If ∆x = x − x , ∆y = y − y , and q = b − Ax+ − By + + λ/β,

z + = [q]+ ,

and if DF (a, c) = F (a) − F (c) − ⟨∇F (c), a − c⟩ with DG defined analogously, cancellation of the first-order terms in the block optimality conditions gives D = DF (x, x+ ) + β2 ∥A∆x∥2 + DG (y, y + ) + β2 ∥B∆y∥2 + β2

2

+

2

(A.3)

∥z − q∥ − ∥z − q∥ .

23

Exact block minimization gives uniform γ, σ > 0 such that D ≥ γ∥u+ − u∥2 ,

∥v∥ ≤ σ∥u+ − u∥.

Consequently every 0 < τ ≤ τsafe,E :=

(1 − χ)γ ∥E∥2 κ2p σ 2

satisfies (3.3). A geometric search starting from τmax therefore terminates and accepts τk ≥ τ E := min{τmax , δτsafe,E } > 0. For the accepted sequence, set Dk = Lβ (uk ; λk ) − Lβ (uk+1 ; λk ). With ūk = arg minu Lβ (u; λk ), rk = Euk − b, r̄k = E ūk − b, and dk = dβ (λk ), direct expansion gives V k − V k−1 = −Dk + τk ∥rk ∥2 − 2(dk − dk−1 ). Concavity of dβ and λk−1 − λk = τk rk imply dk − dk−1 ≥ τk ⟨r̄k , rk ⟩. Completing the square yields V k − V k−1 ≤ τk ∥E(uk − ūk )∥2 − Dk − τk ∥∇dβ (λk )∥2 .

(A.4)

Equations (3.3) and (A.2) imply V k − V k−1 ≤ −χDk − τk ∥∇dβ (λk )∥2 . The proof of Proposition 3.1 explicitly constructs step-sequence-independent constants Cp , Cd > 0 such that ∆kp ≤ (Cp /γ)Dk ,

∆kd ≤ Cd ∥∇dβ (λk )∥2 .

Using τk ≥ τ E gives k

V ≤ (1 + η)

−1

V

k−1

 ,

η = min

χγ τ E , Cp Cd

 > 0.

(A.5)

This closes the proof for the general smooth strongly convex class.

Quadratic weighted refinement. If F, G are the strongly convex quadratics stated in the main text, set K = diag(Q1 , Q2 , 0) + βE ⊤ E,

p = proxh (u − ∇sλ (u)) = u − v.

Proximal optimality and monotonicity of ∂h give e⊤ Ke + ∥v∥2 ≤ e⊤ (I + K)v. Cauchy–Schwarz in the K-metric, together with K ⪰ βE ⊤ E, yields q √ e⊤ (I + K)v ≤ e⊤ Ke v ⊤ (K −1 + 2I + K)v, ∥Ee∥2 ≤

1 ⊤ 1 e Ke ≤ v ⊤ (K −1 + 2I + K)v = BK (v). β β

(A.6)

This step uses the quadratic identity ∇sλ (u) − ∇sλ (ū) = Ke. The majorant can be evaluated without forming K −1 . For v = (vx , vy , vz ), ⊤ v ⊤ K −1 v = (vx − A⊤ vz )⊤ Q−1 1 (vx − A vz ) ⊤ −1 + (vy − B ⊤ vz )⊤ Q−1 ∥vz ∥2 , 2 (vy − B vz ) + β

v ⊤ Kv = vx⊤ Q1 vx + vy⊤ Q2 vy + β∥Avx + Bvy + vz ∥2 .

24

(A.7) (A.8)

Thus two pre-factorized solves with Q1 and Q2 suffice. The two Bregman terms in (A.3) reduce to 12 ∥∆x∥2Q1 and 12 ∥∆y∥2Q2 . Set 1 cK = max (ξ + ξ −1 + 2). β ξ∈σ(K) Since BK (v) ≤ cK ∥v∥2 , every 0 < τ ≤ τsafe,K :=

(1 − χ)γ cK σ 2

satisfies (3.4), and geometric backtracking accepts τk ≥ τ K := min{τmax , δτsafe,K } > 0. Replacing (3.3)–(A.2) by (3.4)–(A.6) in (A.4) gives the same contraction, with τ K in place of τ E . b must use the same trial The trial-point evaluation order is essential: the trial residual vb and decrease D dual iterate. If a candidate step is rejected, both trial iterates must be discarded, and the next candidate must be constructed from the same (uk , λk−1 ). The theorem assumes exact solves of the block subproblems and exact evaluation of the acceptance test; the strict margin needed for a finite-precision acceptance decision requires separate analysis.

A.3

Proof of Theorem 3.2

Proof. It suffices to take β = 1. For a prescribed 0 < ϑ ≤ 80/119, set r 7ϑ ∈ (0, 1/4], u = (1, r, 0)⊤ , v = (1, 3r/5, 4r/5)⊤ , r= 80 − 7ϑ and define PA = √ For α ∈ [0, 2 − 1], let

uu⊤ , 1 + r2

PB =

vv ⊤ . 1 + r2

2α 1 − α2 , t = , 1 + α2 1 + α2 Aα = tPA + s(I − PA ), Q1,α = s2 PA + t2 (I − PA ), s=

Q2,α = s2 PB + t2 (I − PB ).

Bα = tPB + s(I − PB ),

⊤ Then Q1,α + A⊤ α Aα = Q2,α + Bα Bα = I. For α > 0, both Hessians are positive definite and Aα , Bα are nonsingular. Take

x⋆ = y ⋆ = 0, and set

b = z⋆,

z ⋆ = (1, 0, 0)⊤ , ⋆ c1 = A⊤ αλ ,

λ⋆ = (0, −1, −1)⊤ , c2 = Bα⊤ λ⋆ .

This is the unique strictly complementary KKT point. Fix D = diag(1, 0, 0). The exact Schur recursion in Appendix A.4 proves ρ(UD (r, 0)) > 1, At α =

√ 2 − 1,

ϑ=

√ Aα = Bα = I/ 2,

80r2 . 7(1 + r2 )

Q1,α = Q2,α = I/2, 25

and the coordinates decouple. The scalar characteristic polynomials for a positive-slack and a zero-slack coordinate are 1 (2ζ − 1)2 (ζ + ϑ − 1), 4

 ζ 2 4ζ + (3ϑ − 5)ζ + 1 − ϑ . 4

Write p(ζ) = 4ζ 2 + (3ϑ − 5)ζ + 1 − ϑ. The Jury inequalities for this quadratic factor are 4 > |1 − ϑ|,

p(−1) = 10 − 4ϑ > 0,

p(1) = 2ϑ > 0,

so this endpoint is strictly Schur stable throughout the stated interval. √ By continuity, some αc ∈ (0, 2 − 1) satisfies ρ(UD (r, αc )) = 1. The corresponding problem remains strongly convex and full row rank. The branch cannot have eigenvalue +1: a sufficiently small perturbation along its eigenvector would remain in the strict affine branch and create a second ADMM fixed point, contradicting uniqueness of the KKT point. The unit-circle eigenvalue is therefore −1 or a nonreal conjugate pair. Choose a genuine eigenmode: a real eigenvector for −1, or the real invariant subspace spanned by the real and imaginary parts of a complex eigenvector. For a nonzero e in that mode, {UD (r, αc )k e} alternates or rotates. It is therefore bounded but nonconvergent. Scaling e below the strict KKT projection margin keeps every iterate in the same branch, so the branch orbit is a bounded nonconvergent raw ADMM orbit. Because the unit-circle eigenvalue is nonzero, the two inactive components of the z-part of e vanish; taking e still smaller preserves the positive active component and gives z 0 ∈ R3+ . Since Aαc is nonsingular, set 0 0 x0 = A−1 αc (b − Bαc y − z ). Then Aαc x0 + Bαc y 0 + z 0 = b, so the initial state is fully feasible. The stored x0 does not enter the right-hand side of the next x-subproblem and therefore does not alter the (y, z, λ) orbit above. Each subsequent x-update is an affine function of that bounded reduced state, so the full (x, y, z, λ) orbit is bounded as well.

A.4

Uniform-Step Obstruction

⊤ For e = (δy, δz, δλ), RA = Aα A⊤ α , and RB = Bα Bα , define

Yy = Bα⊤ RA Bα ,

Yz = −Bα⊤ (I − RA ),

Yλ = Bα⊤ (I − RA ),

Cy = (I − RB )RA Bα , Cz = RA − RB RA + RB , Cλ = I − RA − RB + RB RA . On a fixed projection mask D, the full error matrix is   Yy Yz Yλ . DCy DCz DCλ UD (r, α) =  ϑ(I − D)Cy ϑ(I − D)Cz (1 − ϑ)I + ϑ(I − D)Cλ For completeness, we recall the real Schur recursion used below. Let pj (ζ) =

dj X

p♯j (ζ) := ζ dj pj (ζ −1 ),

aj,ℓ ζ dj −ℓ ,

ℓ=0

where aj,0 and aj,dj are respectively the leading and constant coefficients of pj . Define ∆j := a2j,0 − a2j,dj 26

and, whenever ∆j > 0, pj+1 (ζ) :=

aj,0 pj (ζ) − aj,dj p♯j (ζ) ζ

.

A necessary Schur–Cohn condition is that ∆j > 0 at every recursion stage. Consequently, once the preceding recursions are well defined, a negative ∆j certifies that the original polynomial has a zero outside the unit disk. At α = 0, D = diag(1, 0, 0), and ϑ = 80r2 /[7(1 + r2 )], remove the four zero roots and the root 1 − ϑ from the characteristic polynomial. The first three exact Schur deltas of the remaining quartic satisfy ∆0 > 0,

∆1 > 0,

∆2 < 0

(0 < r ≤ 1/4),

where, after positive factors are removed, the signs of ∆1 and ∆2 are determined by −h1 (r), h2 (r),

h1 (r) = 1205r8 + 1977r6 − 4643r4 − 7385r2 − 2450, h2 (r) = 14530r10 + 57137r8 − 131931r6 − 449323r4 − 329735r2 − 82950.

For 0 < r ≤ 1, and

h1 (r) ≤ −1461r4 − 7385r2 − 2450 < 0, h2 (r) ≤ −60264r6 − 449323r4 − 329735r2 − 82950 < 0.

Thus the signs are strict and a root lies outside the unit disk. The exact polynomial, factorization, and endpoint Jury checks are regenerated by python python/verify_universal_step_obstruction.py –check

from the GitHub certificate repository root. The underlying exact script is python/analyze_identity_slack_universal_step_obstruction.py.

A.5

Period-66 Verification

From the GitHub certificate repository https://github.com/ConanXu-math/identity-slack-admm-cycle-certificate run python python/verify_certificate_pair.py. One-shot acceptance of both frozen certificates is python python/verify_all.py. The command invokes separately implemented four- and six-dimensional rational replays and verifies strong convexity, the unique KKT point, every ADMM update, 66-step closure, all 132 strict projection inequalities, and minimality of the period.

27

A.6

Perturbation Robustness

Corollary A.1 (Persistence under data perturbations). Let S2++ denote the cone of real 2 × 2 symmetric positive-definite matrices. With A = B = I2 , β = 1, and the update order x → y → z → λ fixed, there is an open neighborhood of (Q1 , Q2 , b̄) in S2++ × S2++ × R2 such that each resulting problem has a non-KKT periodic ADMM sequence of minimal period 66, with the same projection-sign sequence and every projection inequality strict. Proof. For the fixed projection-sign sequence, P and a in (2.14) depend analytically on the problem data. The period system remains nonsingular near the displayed instance, so (I4 − P)−1 a and its 66 reduced iterates vary continuously. The signs in (2.17) have a positive common margin and remain strict under sufficiently small perturbations. The primitive word is unchanged.

A.7

Relaxed Branch Map

Set β = 1,

M = (Q1 + I2 )−1 ,

N = (Q2 + I2 )−1 ,

I = I2 ,

and use the six-dimensional essential state w = (y, z, λ) ∈ R6 . Eliminating x+ from the primal updates gives Cy = (I − N )M,

Cz = N + (I − N )M,

and

Cλ = (I − N )(I − M ),

q + = Cy y + Cz z + Cλ λ + d.

For a strict projection mask
D = diag 1{q+ >0} , 1{q+ >0} , 1

2

z + = Dq + ,

the identity x+ + y + + z + − b̄ = λ − q + + z + yields λ+ = (1 − τ )λ + τ (I − D)q + . Thus the matrices in (3.5) are 

 N M −N (I − M ) N (I − M ) (0) DCz DCλ  , TD = DCy 0 0 I   0 0 0 (1) , 0 0 0 TD =  (I − D)Cy (I − D)Cz (I − D)Cλ − I and

   N (I − M )b̄ 0 . +τ Dd 0 aD (τ ) =  0 (I − D)d 

This also shows directly that τ affects only the multiplier block row.

28

d = Cλ b̄,

A.8

Proof of Theorem 3.4 (0)

(1)

Proof. Set T0 := T01 , T1 := T01 , and T (τ ) = T01 (τ ) = T0 + τ T1 . Define ΦH (τ ) = H − T (τ )⊤ HT (τ ). If τ = ητ− + (1 − η)τ+ , direct expansion gives ΦH (τ ) − ηΦH (τ− ) − (1 − η)ΦH (τ+ ) = η(1 − η)(τ+ − τ− )2 T1⊤ HT1 ⪰ 0.

(A.9)

At τ = 1/2, let H ∈ Q6×6 solve H − T01 (1/2)⊤ HT01 (1/2) = I6 . Exact Sylvester tests give H ≻ 0, ΦH (49/100) ≻ 0, and ΦH (51/100) ≻ 0. Equation (A.9) therefore gives uniform contraction throughout [49/100, 51/100]. Strict complementarity places a sufficiently small closed H-ellipsoid around the KKT point entirely inside the D01 projection region, proving the first assertion. For the initialization in Theorem 2.1, a 232-step rational componentwise enclosure is propagated uniformly on |τ − 1/2| ≤ 10−10 . Every projection sign remains strict, and the entire enclosure at step 232 lies in the preceding projection-safe ellipsoid. The first assertion then proves convergence. For the third assertion, exact factorization of the D01 -branch characteristic polynomial, followed by a real Schur recursion and a Sturm root count, reduces the stability boundary to the unique root in (0, 1) of pstab in (A.10); exact endpoint evaluation gives the stated bracket. If 0 < τ < τc , Schur stability gives the unique Hτ ≻ 0 satisfying Hτ − T01 (τ )⊤ Hτ T01 (τ ) = I6 . In the induced norm there is a κτ < 1 such that ∥T01 (τ )e∥Hτ ≤ κτ ∥e∥Hτ . Since q ⋆ = (−1, 1) is in the interior of the strict branch, a sufficiently small closed Hτ -ellipsoid is invariant under the full projected map. Therefore ∥wk+1 − w⋆ ∥Hτ ≤ κτ ∥wk − w⋆ ∥Hτ , so w⋆ is locally Q-linearly attracting. Conversely, suppose that τc ≤ τ < 1. Since w⋆ lies in the interior of the strict D01 branch, the full projected map agrees with its affine branch map on a neighborhood of w⋆ . Local Q-linear attraction on that neighborhood would imply an induced norm in which the linear part T01 (τ ) has operator norm strictly smaller than one, and hence ρ(T01 (τ )) < 1. This contradicts ρ(T01 (τ )) ≥ 1. Thus the KKT point is not locally Q-linearly attracting for τc ≤ τ < 1.

A.9

Verification of Theorem 3.4

The dual-step certificate is verified by python python/certify_relaxed_multiplier_interval_theory.py. It re-derives the essential-state projection-region matrices from the original updates, checks the endpoint Sylvester minors and chord identity, propagates the exact 232-step finite-entry enclosure, and performs the Schur–Sturm boundary test. The boundary polynomial is pstab (τ ) = 111794210406295556649228900462157733493 τ 3 + 23105776975281816108275814441284422085171521 τ 2 − 244157339715898821440243649673959463071543521 τ + 208410060660460340386576638889814578828638507. 29

(A.10)

An exact Sturm count gives one root of pstab in (0, 1), and rational endpoint evaluation gives the bracket in Theorem 3.4.

B

Period-23 Certificate

This appendix records the reduced branch maps, the return-map construction, the proofs, and the invariant-ellipsoid data for the exact m = 3 period-23 certificate stated in Section 4.1 (Proposition 4.1). It is a fixed-QP initialization result and does not assert robustness to perturbations of the problem data.

B.1

Branch Map

Record the state immediately after the z- and multiplier updates. With β = 1, set t = z + λ,

v = (y, t) ∈ R6 ,

St = [ 03×3 I3 ],

so that t = St v. The projection identity gives z = [t]+ and λ = [t]− ; thus v determines (z, λ) and the next ADMM step. Each strict projection branch is determined by σ(t) := (sgn t1 , sgn t2 , sgn t3 ) ∈ {−, +}3 . On a fixed branch the projection is linear, and eliminating the x- and z-updates gives Rσ ∈ Q6×6 ,

Φσ (v) = Rσ v + rσ ,

rσ ∈ Q6 .

For quadratic objectives F (x) = 12 x⊤ Qx x + c⊤ 1 x, set

G(y) = 21 y ⊤ Qy y + c⊤ 2 y,

Kx = (Qx + A⊤ A)−1 ,

Ky = (Qy + B ⊤ B)−1 , Hx = AKx A⊤ , Hy = BKy B ⊤ ,
Dσ = diag 1{σi =+} , Jσ = 2Dσ − I3 , Eσ = I3 − Dσ , ξ = Kx (A⊤ b − c1 ),

η = Ky (B ⊤ b − c2 − B ⊤ Aξ).

Direct substitution in the x-, y-, and projection–multiplier updates gives     η Ky B ⊤ Hx B Ky B ⊤ (Hx − I3 )Jσ
Rσ = , rσ = . b − Aξ − Bη (I3 − Hy )Hx B Eσ + (I3 − Hy )Hx + Hy Jσ

(B.1)

If the QP data are rational, then every entry of Rσ and rσ is rational.

B.2

Exact Data and Certificate

Apply the reduced map above to the rational instance (4.1) stated in Section 4.1. The resulting strict projection-sign word is W23 in (4.2). Take ω = W23 = (σ0 , . . . , σ22 ). Write the composition of its first j branch maps as Φ(j) ω (v) = Lj v + dj , Lj+1 = Rσj Lj ,

L0 = I6 ,

d0 = 0,

dj+1 = Rσj dj + rσj . 30

The full 23-step return map is therefore
v 23(ℓ+1) = Φper v 23ℓ , (B.2)

Φper (v) := Φ(23) ω (v) = Mper v + cper , Mper := L23 = Rσ22 · · · Rσ0 ,

cper := d23 .

Exact elimination shows that I6 − Mper is nonsingular, so define the phase-zero state by vb0 := (I6 − Mper )−1 cper ∈ Q6 ,

vbj := Lj vb0 + dj

(j = 0, . . . , 22).

The complete exact rational initialization is recovered by b t0 = St vb0 , b x := (Q bx + A b⊤ A) b −1 , K

b0 = [b zb0 = [b t0 ]+ , λ t0 ]− , h i b22 ) − b bx A b⊤ (bb − Bb b y 22 − zb22 + λ x b0 = K c1 .

These equations define the exact rational initialization; the machine certificate stores its expanded numerators and denominators. Proof of Proposition 4.1. For ω = W23 , the recursion above gives the exact rational return map (Mper , cper ) = (L23 , d23 ). Exact rational elimination solves the fixed-point system for vb0 . Exact replay reconstructs every phase state and verifies the pattern, the strict margin, Φper (b v 0 ) = vb0 , and that the 23 phase states are pairwise distinct. Hence the sequence has minimal period 23. b x and Q b y gives a unique primal solution; feasibility determines z, and Positive definiteness of Q b determines λ. Thus the KKT point is unique and is a fixed point of the singlenonsingularity of A valued ADMM map. It cannot belong to the nonconstant period-23 sequence, which is therefore non-KKT. For nearby initializations, the matrix P in Appendix B.3 satisfies ⊤ P − Mper P Mper ≻ 0.

It follows that the error decreases after each complete block of 23 ADMM steps. In particular, every eigenvalue of Mper lies strictly inside the unit disk. The strict sign margin guarantees that every point in Ecert continues to use the same 23 affine branches. The return map sends this ellipsoid into itself, so induction gives the same projection pattern and phasewise convergence for all subsequent returns. The 23 limiting phase points are distinct; hence the full sequence does not converge to a single point. b and w = By. b Nonsingularity of A b and B b makes the change of Proof of Corollary 4.2. Set u = Ax b + By b + z − bb = u + w + z − bb. The transformed variables bijective and preserves the residual Ax objectives are ex = A b−⊤ Q bx A b−1 , Q

ey = B b −⊤ Q by B b −1 , Q

b−⊤ b e c1 = A c1 ,

b −⊤ b e c2 = B c2 ,

ex , Q e y ≻ 0. The x- and y-subproblems are invertible reparameterizations which remain rational with Q of the u- and w-subproblems, while the z- and multiplier updates are unchanged. Starting from b 0 and w0 = By b 0 , the two direct ADMM trajectories correspond step by step. u0 = Ax 31

B.3

Attracting Ellipsoid

Use the partial-composition matrices Lj and the selector St defined in Appendix B.1. Set  2 0 0 0 −1 1 0 2 1 0 −2 2    1 0 1 6 2 −7 7   . P =  0 2 3 −3 3  2 0  −1 −2 −7 −3 16 −13 1 2 7 3 −13 14 

Its leading principal minors are 1,

11 , 4

1,

25 , 8

333 , 32

441 , 32

so P ≻ 0. Exact Sylvester tests also give ⊤ P − Mper P Mper ≻ 0.

For the ith standard basis vector ei ∈ R3 , define 1×6 aji := e⊤ . i St Lj ∈ Q

Thus aji e is the perturbation of the ith projection input at phase j caused by the initial-state error e = v 0 − vb0 . Define the corresponding sign-preserving radius by r̄2 :=

(b tji )2 . 0≤j<23, 1≤i≤3 aji P −1 a⊤ ji min

aji ̸=0

The exact certificate gives r̄2 > 29/100000 > 1/4000; the minimum occurs at phase 14 and coordinate t3 . The P -norm Cauchy–Schwarz inequality therefore preserves all 69 projection signs for ⊤ PM e⊤ P e < 1/4000. Since P − Mper per ≻ 0, the return map leaves Ecert invariant. Induction gives the same branch word and phasewise convergence to the non-KKT sequence. The ellipsoid in (4.4) is sufficient but not claimed maximal. On the slice ∆y = 0, ∆t3 = 0, 3 1 (∆t1 )2 − 3∆t1 ∆t2 + 8(∆t2 )2 < , 2 4000

∆t2 = 0 =⇒ |∆t1 | < √

1 . 6000

Every point in this interval is therefore a certified nonconvergent reduced initialization.

B.4

Reproduction

From the same GitHub certificate repository root, running python python/verify_period23_certificate.py verifies positive definiteness, nonsingularity, the unique KKT point, 23-step closure, 23 distinct phase states, strict projection consistency with margin > 1/250, separation from the KKT point, and the exact Lyapunov inequality for the return matrix. The rational input, verifier, and generated certificate are provided in that repository.

32

C

AI-Assisted Research Records

This appendix records route dossiers, workspace manifests, prompt classes, human interventions, promotion criteria, and the claim-to-artifact map. The accompanying GitHub repository https://github.com/ConanXu-math/identity-slack-admm-cycle-certificate

stores certificates, verifiers, and retained research artifacts. Route dossiers live under provenan ce/routes/\{codex-period66,kimi-period23\}/. The discovery-to-verification workflow is summarized in Figure 4 (Section 4.2). Computer-assisted claims are supported by exact certificates and independently executable verifiers. Analytic claims are established by the proofs in the paper, with symbolic scripts used to check the stated algebraic and spectral predicates where applicable. Language-model transcripts carry no independent evidentiary weight.

C.1

Prompt Records

Archived prompts are classified into three provenance classes: • verbatim historical — retained exactly as issued; • reconstructed — rebuilt from retained transcripts or notes; • retrospective distilled — written after the fact to summarize a stage. No distilled prompt is asserted to be a historical input. Route dossiers and retained prompt artifacts live under provenance/routes/ in the GitHub repository; a consolidated prompt ledger may be archived alongside them. Representative entries (full texts in the GitHub route dossiers): P-K-01 (verbatim_historical), Kimi opening goal; P-C-01 (reconstructed), Codex brief; P-C-02 (retrospective_distilled), τ -only relaxation with explicit quantifier scopes.

C.2

Human Interventions

We distinguish human-specified, AI-proposed, and jointly refined steps. Human direction selected the mathematical question, configured the workspace and tools, set claim scopes, and audited literature; model outputs nominated representations, candidates, and certificate designs. Table 2 records the staged attribution for the Codex route. Attributions are based on the retained transcripts; where a representation emerged during the interaction and cannot be attributed to a single side, it is labeled jointly refined. Typical Codex gates include rejecting fixed-branch instability alone as a counterexample, requiring exact rational closure, and separating KKT-local from class-uniform claims in the τ -extension. The Kimi dossier records the blind opening and subsequent continue-search instructions under the frozen workspace rules. Route dossiers under provenance/routes/ retain the supporting artifacts.

33

Table 2: Recorded stages of the Codex route, with the promotion condition that gated each stage. Stage

Human input

AI output

Promotion condition

Problem setup

Identity-slack question; evidence requirements Request for a certifiable representation

Proof and counterexample route proposals Signed reduced state s = (y, q), q = z + λ (jointly refined) Fixed-branch spectra; near-rotation heuristic

Correct literature boundary Equivalence to raw ADMM

Rational data (2.3)–(2.5) and word (00)2 (01)64

Exact rational closure and strict signs (G1 –G7 ) Quantifier audit and exact certificates

State-space reduction Candidate screening

Period search

Relaxation extension

C.3

Requirement that fixed-branch instability alone is insufficient Requirement of a strict exact counterexample Frozen QP and initialization; vary only τ ; quantifier gates

Parameterized branch maps; candidate step regimes; certificate routes

Projection itinerary must be realizable

Promotion Gates

A candidate becomes a mathematical claim only after passing G1 : exact problem data,

G2 : KKT and subproblem validity,

G3 : exact period closure,

G4 : strict branch admissibility,

G5 : raw ADMM replay,

G6 : minimal-period verification,

G7 : quantifier and literature audit. Gates G1 –G6 are mathematical or computational checks, carried out in exact arithmetic where applicable; G7 is a human audit of quantifiers, novelty, and literature scope. Floating-point orbits and model-generated derivations nominate candidates only. For stability claims, G3 –G6 are replaced by the relevant Lyapunov, Schur, Sturm, or interval predicates. In particular, KKT-local convergence, convergence from a specified initialization, fixed-problem guarantees, and class-uniform guarantees are treated as distinct promotion scopes rather than stylistic qualifications.

C.4

Claim-to-Artifact Map

Verification entry points in the GitHub repository (first exact replayable certificate as endpoint): Claim

Verification command

Theorem 2.1 Theorem 3.4 Theorem 3.2 Proposition 4.1 One-shot acceptance (66+23)

python python/verify_certificate_pair.py python python/certify_relaxed_multiplier_interval_theory.py python python/verify_universal_step_obstruction.py –check python python/verify_period23_certificate.py python python/verify_all.py

The computer-assisted claims listed in the table rest on these exact replays, independently of language-model transcripts.

34

Related documents

• The 2-Dimensional Dual of $ϕ^4$ in AdS$_3$#670484
• The 2-Dimensional Dual of $ϕ^4$ in AdS$_3$#668419
• Using Subproblem Objective Gaps in Inexact Augmented Lagrangian and ADMM Algorithms, with Applications to Stochastic Mixed Integer Programming#652408
• Using Subproblem Objective Gaps in Inexact Augmented Lagrangian and ADMM Algorithms, with Applications to Stochastic Mixed Integer Programming#650955
• Ab Initio Construction of Poincaré and AdS Particle#160792