CounterexampleConstruction: Literature-sourcedVerification: AI-adaptedPipeline-generatedprecheck pass

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

The direct three-block ADMM extension can diverge

Statement

Use three scalar blocks, zero objectives, $ρ = 1$ , and the homogeneous constraint $A x = 0$ with $A = (\begin{array}{ccc} 1 & 1 & 1 \\ 1 & 1 & 2 \\ 1 & 2 & 2 \end{array}) .$ The sequential three-block recurrence of Naive sequential three-block ADMM has a rational initial state for which its iterates are unbounded, although the unique primal-dual solution is zero and every block subproblem is attained uniquely.

Facts & Assumptions

Given: The three-block ADMM recurrence, the displayed matrix, zero objectives, $ρ = 1$ , and exact real arithmetic.

[A1]

The objectives are zero, $ρ = 1$ , and all three block minimizers are exact.

[F1]

Naive sequential three-block ADMM: each scalar block minimizes one half the squared current residual and the scaled multiplier is updated by adding the final residual.

[F2]

Schur reduction preserves strict unit-disk root location: for monic $p$ with $∣ p (0) ∣ < 1$ , strict unit-disk stability of $p$ implies strict stability of its normalized Schur reduction.

[F3]

A complex polynomial of degree $n$ has exactly $n$ roots counted with multiplicity: a degree- $d$ complex polynomial factors into $d$ linear factors, counted with multiplicity.

[F4]

For every finite-dimensional space, $σ_{F} (T)$ is exactly the set of roots in $F$ of $χ_{T}$ and Eigenvalues, eigenvectors, eigenspaces $E_{λ} (T) = \ker (T - λ I)$ , and the spectrum $σ_{F} (T)$ of an endomorphism: a root of the characteristic polynomial of a finite-dimensional complex endomorphism is an eigenvalue, so its eigenspace contains a nonzero vector.

Proof

1.1A1F1givenalgebra

Write the columns of $A$ as $a_{1} = (1, 1, 1)^{T}$ , $a_{2} = (1, 1, 2)^{T}$ , $a_{3} = (1, 2, 2)^{T}$ . Their squared norms are $3, 6, 9$ , so every scalar block subproblem has a strictly positive quadratic coefficient and a unique attained minimizer. Also $d e t A = - 1$ , so $A x = 0$ has only $x = 0$ . The dual function is $d (y) = i n f_{x} ⟨ y, A x ⟩$ : it is $0$ when $A^{T} y = 0$ and $- \infty$ otherwise. Since $A$ is invertible, $A^{T} y = 0$ only for $y = 0$ , so the dual optimum is unique.

1.2A1F1givenalgebra

For state $s^{k} = (x_{2}^{k}, x_{3}^{k}, u_{1}^{k}, u_{2}^{k}, u_{3}^{k})^{T}$ , exact differentiation of the three scalar subproblems gives $x_{1}^{k + 1} = - \frac{a_{1}^{T} (u^{k} + a_{2} x_{2}^{k} + a_{3} x_{3}^{k})}{3}$ , $x_{2}^{k + 1} = - \frac{a_{2}^{T} (u^{k} + a_{1} x_{1}^{k + 1} + a_{3} x_{3}^{k})}{6}$ , and $x_{3}^{k + 1} = - \frac{a_{3}^{T} (u^{k} + a_{1} x_{1}^{k + 1} + a_{2} x_{2}^{k + 1})}{9}$ . Substitute these into $u^{k + 1} = u^{k} + a_{1} x_{1}^{k + 1} + a_{2} x_{2}^{k + 1} + a_{3} x_{3}^{k + 1}$ ; exact rational simplification gives $s^{k + 1} = M s^{k}$ with $M = \frac{1}{162} (\begin{array}{ccccc} 144 & - 9 & 9 & 9 & - 18 \\ 8 & 157 & 5 & - 13 & 8 \\ - 64 & - 122 & 122 & - 58 & - 64 \\ - 56 & 35 & - 35 & 91 & - 56 \\ 88 & 26 & - 26 & - 62 & 88 \end{array}) .$ The vector $v = (0, 0, 1, 1, 1)^{T}$ satisfies $M v = 0$ . Exact rational matrix multiplication gives $p_{1} = tr (M) = \frac{301}{81}$ , $p_{2} = tr (M^{2}) = \frac{20860}{6561}$ , $p_{3} = tr (M^{3}) = \frac{2588159}{1062882}$ , and $p_{4} = tr (M^{4}) = \frac{132553799}{86093442}$ . Newton's identities $e_{1} = p_{1}$ , $e_{2} = (p_{1}^{2} - p_{2}) / 2$ , $e_{3} = (p_{3} - e_{1} p_{2} + e_{2} p_{1}) / 3$ , and $e_{4} = (- p_{4} + e_{1} p_{3} - e_{2} p_{2} + e_{3} p_{1}) / 4$ give $e_{1} = 301 / 81$ , $e_{2} = 287 / 54$ , $e_{3} = 280 / 81$ , $e_{4} = 70 / 81$ ; $M v = 0$ gives $e_{5} = \det M = 0$ . Therefore $\det (λ I - M) = λ q (λ)$ , where $q (λ) = λ^{4} - \frac{301}{81} λ^{3} + \frac{287}{54} λ^{2} - \frac{280}{81} λ + \frac{70}{81}$ .

2.1A1step 1.2algebracases

For $z = e^{i t}$ , direct expansion gives $Im (e^{- 2 i t} q (e^{i t})) = \frac{\sin t (22 \cos t - 21)}{81}$ . If this vanishes because $\sin t = 0$ , substitution gives $q (1) = 1 / 162$ and $q (- 1) = 775 / 54$ , both nonzero. Otherwise $\cos t = 21 / 22$ , and substitution into the real part gives $Re (e^{- 2 i t} q (e^{i t})) = 19 / 19602 \neq 0$ . Thus $q$ has no unit-circle zero.

3.1A1F2F3step 2.1contradictionalgebra

Suppose every zero of $q$ lies inside the unit disk. By [F2], its normalized Schur reduction is the stable monic cubic $q_{1} (z) = z^{3} - \frac{4781}{1661} z^{2} + \frac{861}{302} z - \frac{1610}{1661}$ . Since $∣ q_{1} (0) ∣ = 1610 / 1661 < 1$ , another application gives the stable monic quadratic $q_{2} (z) = z^{2} - \frac{317086}{166821} z + \frac{336511}{333642}$ . By [F3], $q_{2}$ factors as $(z - ζ_{1}) (z - ζ_{2})$ over $C$ , with both roots inside the unit disk by the reductions. Its constant term is $ζ_{1} ζ_{2}$ , so $∣ q_{2} (0) ∣ = ∣ ζ_{1} ∣ ∣ ζ_{2} ∣ < 1$ , contradicting $q_{2} (0) = 336511 / 333642 > 1$ . Therefore not all zeros of $q$ lie inside. The coefficients of $q_{1}, q_{2}$ follow by substituting into $(p - p (0) p^{#}) / (z (1 - p (0)^{2}))$ and collecting powers.

4.1A1F3F4step 1.2step 2.1step 3.1contradictionalgebra∎

By [F3], $q$ has four roots counted with multiplicity. Steps 2.1 and 3.1 show that none is on the unit circle and not all are inside, so some root $λ$ satisfies $∣ λ ∣ > 1$ . Since $\det (λ I - M) = λ q (λ) = 0$ by step 1.2, [F4] gives a nonzero complex vector $v$ with $M v = λ v$ . Suppose each of the five standard basis vectors $e_{j} \in Q^{5}$ had a bounded orbit under $M$ . Then every column of $M^{k}$ would be uniformly bounded in $k$ , and since there are only five columns, every entry would be bounded by one common constant $C$ . Choose $i$ with $v_{i} \neq 0$ . The finite-sum triangle inequality would give $∣ (M^{k} v)_{i} ∣ \leq C \sum_{j} ∣ v_{j} ∣$ for every $k$ , but $M^{k} v = λ^{k} v$ makes $∣ (M^{k} v)_{i} ∣ = ∣ λ ∣^{k} ∣ v_{i} ∣ \to \infty$ , a contradiction. Hence at least one standard basis vector has an unbounded orbit. Taking $s^{0} = e_{j}$ for that index and $x_{1}^{0} = 0$ gives a rational initial state with unbounded iterates; each subproblem remains uniquely attained as shown in step 1.1.

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

18 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

Caihua Chen, Bingsheng He, Yinyu Ye, and Xiaoming Yuan, The direct extension of ADMM for multi-block convex minimization problems is not necessarily convergent, Theorem 3.1 and §§3.1–3.2 (standard reference, not scraped)
Stephen Boyd, Neal Parikh, Eric Chu, Borja Peleato, and Jonathan Eckstein, Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers, §3 (standard reference, not scraped)