CMP.6:4.4 - Establish what repeated updates imply
Select a progress argument appropriate to the state space and update:
| Available structure | What can be established | What remains to be supplied |
|---|---|---|
| A finite candidate set and strict improvement at every accepted change | No candidate repeats; the procedure reaches a state with no accepted improving change. | A feasible way to find or rule out such changes, and a useful bound on the amount of work. |
| A decreasing nonnegative integer potential | At most its initial value many decreases of at least one. | The potential’s encoded magnitude can be large, and one iteration may be expensive. |
| A contraction or another quantitative convergence relation | A finite error bound after a chosen number of updates. | A way to compute the required update and connect that error to the requested result. |
| A descent estimate with a bounded-below objective | Bounds on accumulated improvement and, under appropriate assumptions, stationarity measures. | Convergence to one point or global optimality requires its own additional conditions. |
Use MATH.20 for the bound and MATH.21 for the convergence construction when needed. If each step improves but there is no useful stopping guarantee, return that limited procedure or change the method. Equal-value moves need their own cycle handling; strict-improvement reasoning does not cover them.