CounterexampleConstruction: AI-generatedVerification: AI-generatedPipeline-generatedprecheck passjudge pass (gpt-6-luna)

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.

Cyclic exact block minimization can cycle outside the convex separable hypotheses

Statement refuted

The claim that every infinite continuation of the cyclic exact block-minimization update rule for an arbitrary nonconvex, nonseparable extended-real objective converges to one point is false when block minimizers are nonunique and the allowed tie choices vary by update.

Witness

Let $C = {(0, 0), (2, 0), (2, 2), (1, 2), (1, 1), (0, 1)} \subset R^{2}$ and let $F$ be its indicator: $F = 0$ on $C$ and $F = + \infty$ off $C$ . This is a finite, closed but nonconvex, nonseparable domain. Use singleton blocks in the order $x, y$ and start at $(0, 0)$ . Any finite sweep budget follows the corresponding prefix of the periodic tie-selection rule; three sweeps complete one six-update period.

Facts & Assumptions

Given: The objective, blocks and starting point in the Counterexample.

[F1]

Cyclic exact block minimization: at each update the selected coordinate is replaced by any global minimizer of the current coordinate slice.

[F2]

The extended real line $\overline{R} = R \cup {- \infty, + \infty}$ , its order, and the arithmetic that is left undefined: the indicator values $0$ and $+ \infty$ give the extended-real objective and its finite domain.

[F3]

The Euclidean inner product $⟨ x, y ⟩ = \sum_{k < n} x_{k} y_{k}$ on $R^{n}$ and Cauchy-Schwarz $∣ ⟨ x, y ⟩ ∣ \leq ∥ x ∥_{2} ∥ y ∥_{2}$ with its equality case, the triangle inequality for $∥ \cdot ∥_{2}$ , the parallelogram law and polarisation: the Euclidean norm induces the usual metric and satisfies the triangle inequality; Every nonempty finite set of reals has a maximum and a minimum: a nonempty finite set of positive reals has a positive minimum; The metric topology: a set is open when every one of its points has a ball around it inside the set; closed means open complement and Open ball, closed ball and sphere in a metric space: open balls form neighborhoods in which closedness is tested.

Proof

1.1F1F2givenchoose

At $y = 0$ , the feasible $x$ values are $0$ and $2$ , and both minimize the slice with value $0$ ; choose $x = 2$ . At $x = 2$ , the feasible $y$ values are $0$ and $2$ , and both minimize; choose $y = 2$ .

2.1F1F2step 1.1choose

At $y = 2$ , choose $x = 1$ from the two minimizing values $1, 2$ . At $x = 1$ , choose $y = 1$ from the two minimizing values $1, 2$ . At $y = 1$ , choose $x = 0$ from the two minimizing values $0, 1$ . At $x = 0$ , choose $y = 0$ from the two minimizing values $0, 1$ . Thus one six-update cycle returns to $(0, 0)$ , and repeating the same admissible tie choices gives a period-six trajectory.

3.1F1F2F3step 1.1step 2.1algebra

Every point in the trajectory lies in $C$ and has objective $0$ , so every coordinate update described in steps 1.1 and 2.1 is an exact global block minimization. The set $C$ is closed: for any $z \notin C$ , the finitely many distances ${∥ z - c ∥_{2} : c \in C}$ are positive, so [F3] gives a positive minimum $δ$ ; if $∥ w - z ∥_{2} < δ / 2$ , the triangle inequality gives $∥ w - c ∥_{2} \geq ∥ z - c ∥_{2} - ∥ w - z ∥_{2} > δ / 2$ for every $c \in C$ . Thus the open ball of radius $δ / 2$ about $z$ misses $C$ . The set is nonconvex because $(0, 0), (2, 0) \in C$ but their midpoint $(1, 0) \notin C$ . It is not a Cartesian product of its coordinate projections: both projections are ${0, 1, 2}$ , whose product has nine points, whereas $C$ has six. If $F (x, y) = h (x) + k (y)$ for functions $h, k$ taking values in $R \cup {+ \infty}$ , its finite domain consists exactly of pairs where $h$ and $k$ are each finite, hence is a Cartesian product. Thus $F$ is nonseparable.

4.1F1step 1.1step 2.1step 3.1algebra∎

In the infinite continuation of the finite-budget prefixes, the trajectory does not converge: the subsequences at updates $6 m$ and $6 m + 1$ are constantly $(0, 0)$ and $(2, 0)$ , respectively, and those limits differ. Repeating the six admissible choices therefore gives a nonconvergent cyclic exact-minimization trajectory.

Remarks

The example has a nonconvex, nonseparable objective and nonunique block minimizers. It lies outside Cyclic exact block descent has globally optimal accumulation points; the convergence theorem does not assert convergence for this case.

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

37 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

Stephen J. Wright, Coordinate Descent Algorithms, §3.1 (standard reference, not scraped)
P. Tseng, Convergence of a Block Coordinate Descent Method for Nondifferentiable Minimization, §1 (standard reference, not scraped)