Kemonotonan dan kemaksimalan

Kemonotonan saja belum menjamin bahwa operator mempunyai cukup banyak nilai untuk mendefinisikan langkah implisit pada setiap titik. Sebagai contoh, operator dengan grafik tunggal \(\{(0,0)\}\) monoton, tetapi tidak maksimal, karena grafik itu dapat diperluas menjadi grafik operator nol pada seluruh \(\mathbb{R}^d\).

Teorema Rockafellar memperkuat hasil tersebut: jika \(f\) juga semikontinu bawah, maka \(\partial f\) monoton maksimal. Bab ini memakai teorema itu sebagai hasil dasar, bukan membuktikan kembali argumen pemisahan lengkapnya. Akibat pentingnya ialah kerucut normal dan operator proksimal masuk ke dalam kerangka yang sama.

Ketaksamaan variasional sebagai inklusi monoton

Untuk himpunan konveks tertutup tak kosong \(C\subseteq\mathbb{R}^d\), kerucut normal pada \(x\) didefinisikan oleh \[\begin{equation} \label{orig02:eq:normal-cone} N_C(x)= \begin{cases} \{u:\left\langle u,y-x\right\rangle\leq0\text{ untuk semua }y\in C\},&x\in C,\\ \emptyset,&x\notin C. \end{cases} \end{equation}\] Karena \(N_C=\partial\delta_C\), operator ini monoton maksimal.

Jika \(F=\nabla f\) untuk fungsi konveks terdiferensialkan \(f\), kondisi ini adalah kondisi optimalitas bagi \(\min_{x\in C}f(x)\). Namun, ketaksamaan variasional lebih luas: pemetaan monoton tidak harus merupakan gradien.

Bab ini tidak memakai simpleks sebagai algoritma pemrograman linear. Proyeksi, kerucut normal, dan ketaksamaan variasional di sini berada dalam analisis konveks kontinu dan tidak mengimpor LP/MIP, dualitas atau sensitivitas LP, jaringan, maupun optimisasi diskret dari O018.

Resolven operator monoton maksimal

Untuk \(\gamma>0\), definisikan resolven dan resolven terefleksi \[\begin{equation} \label{orig02:eq:resolvent-definition} J_{\gamma A}=(I+\gamma A)^{-1}, \qquad R_{\gamma A}=2J_{\gamma A}-I. \end{equation}\] Secara apriori, invers tersebut dapat bernilai himpunan atau tidak terdefinisi pada sebagian titik. Untuk operator monoton \(A\), teorema Minty menutup kedua celah itu: di ruang Euclid, \(A\) monoton maksimal jika dan hanya jika \(\operatorname{ran}(I+\gamma A)=\mathbb{R}^d\) untuk setiap \(\gamma>0\).

Metode titik proksimal

Metode titik proksimal menerapkan resolven secara berulang: \[\begin{equation} \label{orig02:eq:ppa} x_{k+1}=J_{\gamma A}x_k, \qquad \gamma>0. \end{equation}\] Ini adalah langkah implisit karena \((x_k-x_{k+1})/\gamma\in Ax_{k+1}\).

Hasil ini menjelaskan kestabilan langkah implisit tanpa mengklaim bahwa \(J_{\gamma A}\) selalu mudah dihitung. Pemisahan operator berguna ketika resolven bagian-bagian operator jauh lebih sederhana daripada resolven jumlahnya.

Pemisahan maju–mundur

Pemetaan tunggal \(B:\mathbb{R}^d\to\mathbb{R}^d\) disebut \(\beta\)-kokorsif jika \[\begin{equation} \label{orig02:eq:cocoercive} \left\langle Bx-By,x-y\right\rangle\geq\beta\left\lVert Bx-By\right\rVert^2 \qquad\text{untuk semua }x,y. \end{equation}\] Kokorsivitas lebih kuat daripada gabungan kemonotonan dan kontinuitas Lipschitz. Gradien fungsi konveks dengan gradien \(L\)-Lipschitz bersifat \(1/L\)-kokorsif.

Untuk \(A\) monoton maksimal dan \(B\) \(\beta\)-kokorsif, definisikan \[\begin{equation} \label{orig02:eq:fb-operator} T_{\mathrm{FB}}=J_{\gamma A}(I-\gamma B), \qquad 0<\gamma<2\beta. \end{equation}\]

Dengan \(A=\partial g\) dan \(B=\nabla f\), pemetaan ini tepat menjadi langkah gradien proksimal yang telah diterjemahkan dari Habring. Nilai tambah bab ini ialah batas operatornya: langkah eksplisit memerlukan struktur seperti kokorsivitas, bukan hanya kemonotonan.

Pemisahan Douglas–Rachford dan limit bayangan

Andaikan \(A\) dan \(B\) monoton maksimal. Definisikan \[\begin{equation} \label{orig02:eq:dr-operator} T_{\mathrm{DR}} =\frac12\bigl(I+R_{\gamma A}R_{\gamma B}\bigr) =I-J_{\gamma B}+J_{\gamma A}(2J_{\gamma B}-I). \end{equation}\] Karena kedua resolven terefleksi tak ekspansif, komposisinya tak ekspansif dan \(T_{\mathrm{DR}}\) tak ekspansif kukuh.

Modul Becker 2 sudah menyediakan bentuk proksimal konkret untuk \(A=\partial f\) dan \(B=\partial g\), berikut penormalan skala serta hubungan primal–dualnya. Bagian ini tidak mengulang materi tersebut; ia menjelaskan mengapa rumus yang sama bekerja untuk operator monoton maksimal yang tidak harus merupakan subdiferensial.

Mengapa kemonotonan saja tidak cukup untuk langkah maju

Ambil \(\omega\neq0\) dan operator linear \[\begin{equation} \label{orig02:eq:skew} S=\omega \begin{pmatrix}0&-1\\1&0\end{pmatrix}. \end{equation}\] Karena \(\left\langle Sh,h\right\rangle=0\) untuk semua \(h\), operator \(S\) monoton. Ia juga monoton maksimal karena \(I+\gamma S\) invertibel untuk setiap \(\gamma>0\). Namun, \(S\) tidak \(\beta\)-kokorsif untuk satu pun \(\beta>0\): ruas kiri ketaksamaan kokorsif selalu nol, sedangkan ruas kanan positif bila \(h\neq0\).

Langkah maju \(x_{k+1}=(I-\gamma S)x_k\) memenuhi \[\begin{equation} \left\lVert x_{k+1}\right\rVert^2=(1+\gamma^2\omega^2)\left\lVert x_k\right\rVert^2, \end{equation}\] sehingga menjauh dari nol untuk \(x_0\neq0\). Sebaliknya, langkah resolven \(x_{k+1}=J_{\gamma S}x_k\) memenuhi \[\begin{equation} \left\lVert x_{k+1}\right\rVert =\frac{1}{\sqrt{1+\gamma^2\omega^2}}\left\lVert x_k\right\rVert. \end{equation}\] Contoh ini memisahkan dengan jelas tiga gagasan: monoton, Lipschitz, dan kokorsif tidak saling dapat dipertukarkan.

Latihan, petunjuk, dan solusi lengkap

Peta asumsi dan batas klaim

Grafik residu inklusi

Tabel data lengkap

Tabel berikut memuat semua baris hasil eksperimen dengan tajuk kolom yang dapat ditelusuri oleh teknologi bantu.

Berkas laboratorium byte-identik

• monotone-splitting-lab.py — 17904 byte; SHA-256 1d13f436644216104036be248ebb3ff0b1a9e45c856aef9229f17a5f26f3e119
• results.json — 13503 byte; SHA-256 bc39d3363f02b904a27245bfe090cbf2153238a5a18ba8bf7cccbe1352672e81
• results.csv — 4228 byte; SHA-256 da8d09cce727c98b408fe719735574977266de1b58f95a742dcb60c5d163e243
• residual.svg — 9538 byte; SHA-256 c7bdeeed813cf36999ae2748362e547fc23de2d5ae15c6131e3fc73edeba6fd5

Daftar berikut diikat oleh ukuran byte dan SHA-256. Pada HTML tautannya mengunduh berkas byte-identik; pada EPUB tautannya menuju representasi lengkap di dalam pembaca, sementara salinan byte-identik tetap termanifestasi.

Kode program Python lengkap

#!/usr/bin/env python3
"""Deterministic open-computation lab for O015 Original-02.

The frozen two-dimensional inclusion combines a strongly monotone linear map
with a nonzero skew part and the subdifferential of the l1 norm.  It compares
forward-backward inside and outside its proved step range with
Douglas-Rachford splitting.  NumPy supplies the open linear solver; an explicit
nine-pattern active-set enumeration supplies an independent reference point.
"""

from __future__ import annotations

import csv
import json
import math
from pathlib import Path

import numpy as np


ROOT = Path(__file__).resolve().parents[2]
OUT_DIR = Path(__file__).resolve().parent
JSON_PATH = OUT_DIR / "results.json"
CSV_PATH = OUT_DIR / "results.csv"
SVG_PATH = OUT_DIR / "residual.svg"

MU = 1.00
OMEGA = 1.50
LAMBDA = 0.25
B_VECTOR = np.array([1.20, -0.70], dtype=np.float64)
X0 = np.array([2.50, -2.00], dtype=np.float64)
Y0 = np.array([2.50, -2.00], dtype=np.float64)
FB_STABLE_GAMMA = 0.40
FB_DIAGNOSTIC_GAMMA = 0.90
DR_GAMMA = 0.70
ITERATIONS = 200
CHECKPOINTS = (0, 1, 2, 5, 10, 20, 40, 80, 120, 200)
SKEW_GAMMA = 0.60
SKEW_STEPS = 30
SKEW_X0 = np.array([1.25, -0.75], dtype=np.float64)

MATRIX = np.array([[MU, -OMEGA], [OMEGA, MU]], dtype=np.float64)
BETA = MU / (MU * MU + OMEGA * OMEGA)
FB_UPPER_BOUND = 2.0 * BETA


def soft_threshold(x: np.ndarray, threshold: float) -> np.ndarray:
    return np.sign(x) * np.maximum(np.abs(x) - threshold, 0.0)


def active_set_reference() -> tuple[np.ndarray, tuple[int, int], np.ndarray]:
    """Enumerate sign/zero patterns and return the unique inclusion solution."""
    candidates: list[tuple[np.ndarray, tuple[int, int], np.ndarray]] = []
    for s0 in (-1, 0, 1):
        for s1 in (-1, 0, 1):
            pattern = (s0, s1)
            active = [index for index, sign in enumerate(pattern) if sign]
            zero = [index for index, sign in enumerate(pattern) if not sign]
            x = np.zeros(2, dtype=np.float64)
            if active:
                block = MATRIX[np.ix_(active, active)]
                rhs = B_VECTOR[active] - LAMBDA * np.array(
                    [pattern[index] for index in active], dtype=np.float64
                )
                x[active] = np.linalg.solve(block, rhs)
            if any(x[index] * pattern[index] <= 1e-12 for index in active):
                continue
            residual = MATRIX @ x - B_VECTOR
            if any(abs(residual[index]) > LAMBDA + 1e-11 for index in zero):
                continue
            if any(
                abs(residual[index] + LAMBDA * pattern[index]) > 1e-10
                for index in active
            ):
                continue
            subgradient = np.empty(2, dtype=np.float64)
            for index in range(2):
                if pattern[index]:
                    subgradient[index] = float(pattern[index])
                else:
                    subgradient[index] = -residual[index] / LAMBDA
            candidates.append((x, pattern, subgradient))
    if len(candidates) != 1:
        raise RuntimeError(f"Expected one active-set solution, found {len(candidates)}")
    return candidates[0]


REFERENCE, REFERENCE_PATTERN, REFERENCE_SUBGRADIENT = active_set_reference()


def fixed_point_residual(x: np.ndarray, gamma: float) -> float:
    mapped = soft_threshold(
        x - gamma * (MATRIX @ x - B_VECTOR), gamma * LAMBDA
    )
    return float(np.linalg.norm(x - mapped))


def inclusion_residual(x: np.ndarray) -> float:
    """Tolerance-adjusted distance from zero to Mx-b + lambda*partial ||x||_1."""
    affine = MATRIX @ x - B_VECTOR
    certificate = np.empty(2, dtype=np.float64)
    for index, value in enumerate(x):
        if value > 1e-12:
            certificate[index] = affine[index] + LAMBDA
        elif value < -1e-12:
            certificate[index] = affine[index] - LAMBDA
        else:
            certificate[index] = math.copysign(
                max(abs(affine[index]) - LAMBDA, 0.0), affine[index]
            )
    return float(np.linalg.norm(certificate))


def observation(method: str, iteration: int, x: np.ndarray, gamma: float) -> dict:
    return {
        "method": method,
        "iteration": iteration,
        "x1": float(x[0]),
        "x2": float(x[1]),
        "norm": float(np.linalg.norm(x)),
        "error_to_reference": float(np.linalg.norm(x - REFERENCE)),
        "fixed_point_residual": fixed_point_residual(x, gamma),
        "inclusion_residual": inclusion_residual(x),
    }


def run_forward_backward(name: str, gamma: float) -> list[dict]:
    x = X0.copy()
    rows = []
    for iteration in range(ITERATIONS + 1):
        if iteration in CHECKPOINTS:
            rows.append(observation(name, iteration, x, gamma))
        if iteration < ITERATIONS:
            x = soft_threshold(
                x - gamma * (MATRIX @ x - B_VECTOR), gamma * LAMBDA
            )
    return rows


def resolvent_linear(v: np.ndarray, gamma: float) -> np.ndarray:
    return np.linalg.solve(
        np.eye(2, dtype=np.float64) + gamma * MATRIX,
        v + gamma * B_VECTOR,
    )


def run_douglas_rachford() -> list[dict]:
    y = Y0.copy()
    rows = []
    for iteration in range(ITERATIONS + 1):
        shadow = soft_threshold(y, DR_GAMMA * LAMBDA)
        if iteration in CHECKPOINTS:
            rows.append(
                observation("douglas_rachford", iteration, shadow, DR_GAMMA)
            )
        if iteration < ITERATIONS:
            reflected = 2.0 * shadow - y
            other = resolvent_linear(reflected, DR_GAMMA)
            y = y + other - shadow
    return rows


def skew_diagnostic() -> dict:
    """Compare exact and numerical contraction factors for the unit rotation."""
    rotation = np.array([[0.0, -1.0], [1.0, 0.0]], dtype=np.float64)
    identity = np.eye(2, dtype=np.float64)
    forward_map = identity - SKEW_GAMMA * rotation
    extragradient_map = (
        (1.0 - SKEW_GAMMA * SKEW_GAMMA) * identity
        - SKEW_GAMMA * rotation
    )
    resolvent_map = np.linalg.inv(identity + SKEW_GAMMA * rotation)
    exact = {
        "forward": math.sqrt(1.0 + SKEW_GAMMA * SKEW_GAMMA),
        "extragradient": math.sqrt(
            1.0 - SKEW_GAMMA * SKEW_GAMMA + SKEW_GAMMA**4
        ),
        "resolvent": 1.0 / math.sqrt(1.0 + SKEW_GAMMA * SKEW_GAMMA),
    }
    maps = {
        "forward": forward_map,
        "extragradient": extragradient_map,
        "resolvent": resolvent_map,
    }
    methods = {}
    initial_norm = float(np.linalg.norm(SKEW_X0))
    for name, operator in maps.items():
        x = SKEW_X0.copy()
        first = operator @ x
        numerical_factor = float(np.linalg.norm(first) / initial_norm)
        for _ in range(SKEW_STEPS):
            x = operator @ x
        methods[name] = {
            "exact_one_step_factor": exact[name],
            "numerical_one_step_factor": numerical_factor,
            "factor_absolute_error": abs(numerical_factor - exact[name]),
            "final_norm": float(np.linalg.norm(x)),
            "exact_final_norm": initial_norm * exact[name] ** SKEW_STEPS,
        }
        if methods[name]["factor_absolute_error"] > 1e-14:
            raise RuntimeError(f"Skew one-step identity failed for {name}")
        if abs(methods[name]["final_norm"] - methods[name]["exact_final_norm"]) > (
            1e-12 * max(1.0, methods[name]["exact_final_norm"])
        ):
            raise RuntimeError(f"Skew multi-step identity failed for {name}")
    if not methods["forward"]["exact_one_step_factor"] > 1.0:
        raise RuntimeError("Frozen skew forward map is not expansive")
    if not methods["extragradient"]["exact_one_step_factor"] < 1.0:
        raise RuntimeError("Frozen skew extragradient map is not contractive")
    if not methods["resolvent"]["exact_one_step_factor"] < 1.0:
        raise RuntimeError("Frozen skew resolvent map is not contractive")
    return {
        "gamma": SKEW_GAMMA,
        "steps": SKEW_STEPS,
        "initial": SKEW_X0.tolist(),
        "initial_norm": initial_norm,
        "methods": methods,
        "interpretation": (
            "For the monotone 1-Lipschitz skew map, the plain forward step "
            "expands while extragradient and the resolvent contract."
        ),
    }


def make_svg(rows: list[dict]) -> str:
    width, height = 900, 520
    left, right, top, bottom = 88, 35, 42, 74
    plot_w = width - left - right
    plot_h = height - top - bottom
    colors = {
        "forward_backward_stable": "#1f77b4",
        "forward_backward_outside_range": "#c03d3e",
        "douglas_rachford": "#2b8a3e",
    }
    labels = {
        "forward_backward_stable": "Maju--mundur: langkah diterima",
        "forward_backward_outside_range": "Maju--mundur: di luar jaminan",
        "douglas_rachford": "Douglas--Rachford",
    }
    grouped = {
        method: [row for row in rows if row["method"] == method]
        for method in colors
    }
    positive = [
        max(float(row["inclusion_residual"]), 1e-16)
        for row in rows
        if math.isfinite(float(row["inclusion_residual"]))
    ]
    log_min = min(-14.0, math.floor(math.log10(min(positive))))
    log_max = max(1.0, math.ceil(math.log10(max(positive))))

    def point(iteration: int, residual: float) -> tuple[float, float]:
        x = left + plot_w * iteration / ITERATIONS
        value = min(max(math.log10(max(residual, 1e-16)), log_min), log_max)
        y = top + plot_h * (log_max - value) / (log_max - log_min)
        return x, y

    parts = [
        '<?xml version="1.0" encoding="UTF-8"?>',
        f'<svg xmlns="http://www.w3.org/2000/svg" width="{width}" height="{height}" viewBox="0 0 {width} {height}" role="img" aria-labelledby="title desc">',
        '<title id="title">Residu inklusi operator monoton</title>',
        '<desc id="desc">Perbandingan residu maju--mundur dengan langkah diterima, langkah di luar jaminan, dan Douglas--Rachford.</desc>',
        '<rect width="100%" height="100%" fill="#ffffff"/>',
        f'<text x="{width/2}" y="24" text-anchor="middle" font-family="Arial, sans-serif" font-size="18" fill="#182235">Residu inklusi terhadap iterasi</text>',
    ]
    for exponent in range(int(log_min), int(log_max) + 1, 2):
        y = point(0, 10.0**exponent)[1]
        parts.append(
            f'<line x1="{left}" x2="{left+plot_w}" y1="{y:.2f}" y2="{y:.2f}" stroke="#d8dee8" stroke-width="1"/>'
        )
        parts.append(
            f'<text x="{left-10}" y="{y+4:.2f}" text-anchor="end" font-family="Arial, sans-serif" font-size="12" fill="#536176">10^{exponent}</text>'
        )
    for iteration in (0, 50, 100, 150, 200):
        x = point(iteration, 1.0)[0]
        parts.append(
            f'<line x1="{x:.2f}" x2="{x:.2f}" y1="{top}" y2="{top+plot_h}" stroke="#eef1f5" stroke-width="1"/>'
        )
        parts.append(
            f'<text x="{x:.2f}" y="{top+plot_h+24}" text-anchor="middle" font-family="Arial, sans-serif" font-size="12" fill="#536176">{iteration}</text>'
        )
    parts.extend(
        [
            f'<line x1="{left}" x2="{left}" y1="{top}" y2="{top+plot_h}" stroke="#182235" stroke-width="1.5"/>',
            f'<line x1="{left}" x2="{left+plot_w}" y1="{top+plot_h}" y2="{top+plot_h}" stroke="#182235" stroke-width="1.5"/>',
            f'<text x="{left+plot_w/2}" y="{height-24}" text-anchor="middle" font-family="Arial, sans-serif" font-size="14" fill="#182235">Iterasi</text>',
            f'<text x="22" y="{top+plot_h/2}" transform="rotate(-90 22 {top+plot_h/2})" text-anchor="middle" font-family="Arial, sans-serif" font-size="14" fill="#182235">Residu inklusi (skala log)</text>',
        ]
    )
    for method, method_rows in grouped.items():
        points = " ".join(
            f'{point(int(row["iteration"]), float(row["inclusion_residual"]))[0]:.2f},{point(int(row["iteration"]), float(row["inclusion_residual"]))[1]:.2f}'
            for row in method_rows
        )
        parts.append(
            f'<polyline points="{points}" fill="none" stroke="{colors[method]}" stroke-width="3" stroke-linejoin="round" stroke-linecap="round"/>'
        )
        for row in method_rows:
            x, y = point(int(row["iteration"]), float(row["inclusion_residual"]))
            parts.append(
                f'<circle cx="{x:.2f}" cy="{y:.2f}" r="3.2" fill="{colors[method]}"/>'
            )
    legend_x, legend_y = left + 18, top + 18
    parts.append(
        f'<rect x="{legend_x-10}" y="{legend_y-15}" width="345" height="82" rx="5" fill="#ffffff" fill-opacity="0.92" stroke="#cbd5e1"/>'
    )
    for index, method in enumerate(colors):
        y = legend_y + 24 * index
        parts.append(
            f'<line x1="{legend_x}" x2="{legend_x+26}" y1="{y}" y2="{y}" stroke="{colors[method]}" stroke-width="3"/>'
        )
        parts.append(
            f'<text x="{legend_x+36}" y="{y+4}" font-family="Arial, sans-serif" font-size="12" fill="#182235">{labels[method]}</text>'
        )
    parts.append("</svg>")
    return "\n".join(parts) + "\n"


def main() -> None:
    if not FB_STABLE_GAMMA < FB_UPPER_BOUND:
        raise RuntimeError("Frozen stable step is outside the proved range")
    if not FB_DIAGNOSTIC_GAMMA > FB_UPPER_BOUND:
        raise RuntimeError("Frozen diagnostic step is not outside the proved range")
    reference_residual = inclusion_residual(REFERENCE)
    if reference_residual > 1e-11:
        raise RuntimeError(f"Active-set reference residual too large: {reference_residual}")

    rows = (
        run_forward_backward("forward_backward_stable", FB_STABLE_GAMMA)
        + run_forward_backward(
            "forward_backward_outside_range", FB_DIAGNOSTIC_GAMMA
        )
        + run_douglas_rachford()
    )
    final = {row["method"]: row for row in rows if row["iteration"] == ITERATIONS}
    if final["forward_backward_stable"]["inclusion_residual"] > 1e-10:
        raise RuntimeError("Stable forward-backward did not reach the frozen tolerance")
    if final["douglas_rachford"]["inclusion_residual"] > 1e-10:
        raise RuntimeError("Douglas-Rachford did not reach the frozen tolerance")
    outside_initial = next(
        row
        for row in rows
        if row["method"] == "forward_backward_outside_range"
        and row["iteration"] == 0
    )
    if not (
        final["forward_backward_outside_range"]["inclusion_residual"]
        > outside_initial["inclusion_residual"]
    ):
        raise RuntimeError("Outside-range diagnostic did not exhibit residual growth")

    resolvent_probe = np.array([0.7, -1.1], dtype=np.float64)
    resolved = resolvent_linear(resolvent_probe, DR_GAMMA)
    resolvent_identity_error = float(
        np.linalg.norm(
            resolved
            + DR_GAMMA * (MATRIX @ resolved - B_VECTOR)
            - resolvent_probe
        )
    )
    if resolvent_identity_error > 1e-12:
        raise RuntimeError("Linear resolvent identity failed")
    skew = skew_diagnostic()

    payload = {
        "schema": "o015-original-02-monotone-splitting-lab-v1",
        "result": "pass",
        "parameters": {
            "mu": MU,
            "omega": OMEGA,
            "lambda": LAMBDA,
            "b": B_VECTOR.tolist(),
            "x0": X0.tolist(),
            "y0": Y0.tolist(),
            "iterations": ITERATIONS,
            "checkpoints": list(CHECKPOINTS),
            "forward_backward_stable_gamma": FB_STABLE_GAMMA,
            "forward_backward_diagnostic_gamma": FB_DIAGNOSTIC_GAMMA,
            "douglas_rachford_gamma": DR_GAMMA,
        },
        "theory": {
            "beta": BETA,
            "forward_backward_upper_bound": FB_UPPER_BOUND,
            "stable_step_inside_open_interval": True,
            "diagnostic_step_outside_proved_interval": True,
        },
        "reference": {
            "method": "complete_active_set_enumeration",
            "pattern": list(REFERENCE_PATTERN),
            "x": REFERENCE.tolist(),
            "subgradient": REFERENCE_SUBGRADIENT.tolist(),
            "inclusion_residual": reference_residual,
        },
        "resolvent_probe": {
            "input": resolvent_probe.tolist(),
            "output": resolved.tolist(),
            "identity_error": resolvent_identity_error,
        },
        "pure_skew_diagnostic": skew,
        "final": final,
        "rows": rows,
        "interpretation": {
            "accepted_methods": [
                "forward_backward_stable",
                "douglas_rachford",
            ],
            "diagnostic_only": "forward_backward_outside_range",
            "claim_boundary": (
                "The outside-range trace is a frozen counterdiagnostic, not a "
                "claim that every step outside the sufficient interval diverges."
            ),
        },
        "dependencies": {
            "python": "standard library",
            "numpy": np.__version__,
        },
        "upstream_contact": False,
    }
    OUT_DIR.mkdir(parents=True, exist_ok=True)
    JSON_PATH.write_text(
        json.dumps(payload, ensure_ascii=False, indent=2, sort_keys=True) + "\n",
        encoding="utf-8",
        newline="\n",
    )
    fieldnames = list(rows[0].keys())
    with CSV_PATH.open("w", encoding="utf-8", newline="") as stream:
        writer = csv.DictWriter(stream, fieldnames=fieldnames, lineterminator="\n")
        writer.writeheader()
        writer.writerows(rows)
    SVG_PATH.write_text(make_svg(rows), encoding="utf-8", newline="\n")
    print(
        json.dumps(
            {
                "result": "pass",
                "beta": BETA,
                "forward_backward_upper_bound": FB_UPPER_BOUND,
                "reference": REFERENCE.tolist(),
                "final_residuals": {
                    method: values["inclusion_residual"]
                    for method, values in final.items()
                },
            },
            sort_keys=True,
        )
    )


if __name__ == "__main__":
    main()

Hasil JSON lengkap

{
  "dependencies": {
    "numpy": "2.4.4",
    "python": "standard library"
  },
  "final": {
    "douglas_rachford": {
      "error_to_reference": 1.8875832159447664e-16,
      "fixed_point_residual": 2.7755575615628914e-16,
      "inclusion_residual": 4.002966042486721e-16,
      "iteration": 200,
      "method": "douglas_rachford",
      "norm": 0.5830951894845302,
      "x1": 0.08461538461538454,
      "x2": -0.5769230769230771
    },
    "forward_backward_outside_range": {
      "error_to_reference": 4.004891561283648e+26,
      "fixed_point_residual": 6.49792884459655e+26,
      "inclusion_residual": 7.219920938440611e+26,
      "iteration": 200,
      "method": "forward_backward_outside_range",
      "norm": 4.004891561283648e+26,
      "x1": -9.882929849502497e+25,
      "x2": 3.8810350930568894e+26
    },
    "forward_backward_stable": {
      "error_to_reference": 3.1780134079895106e-15,
      "fixed_point_residual": 2.401779625492033e-15,
      "inclusion_residual": 5.821000005975887e-15,
      "iteration": 200,
      "method": "forward_backward_stable",
      "norm": 0.5830951894845305,
      "x1": 0.08461538461538787,
      "x2": -0.576923076923077
    }
  },
  "interpretation": {
    "accepted_methods": [
      "forward_backward_stable",
      "douglas_rachford"
    ],
    "claim_boundary": "The outside-range trace is a frozen counterdiagnostic, not a claim that every step outside the sufficient interval diverges.",
    "diagnostic_only": "forward_backward_outside_range"
  },
  "parameters": {
    "b": [
      1.2,
      -0.7
    ],
    "checkpoints": [
      0,
      1,
      2,
      5,
      10,
      20,
      40,
      80,
      120,
      200
    ],
    "douglas_rachford_gamma": 0.7,
    "forward_backward_diagnostic_gamma": 0.9,
    "forward_backward_stable_gamma": 0.4,
    "iterations": 200,
    "lambda": 0.25,
    "mu": 1.0,
    "omega": 1.5,
    "x0": [
      2.5,
      -2.0
    ],
    "y0": [
      2.5,
      -2.0
    ]
  },
  "pure_skew_diagnostic": {
    "gamma": 0.6,
    "initial": [
      1.25,
      -0.75
    ],
    "initial_norm": 1.4577379737113252,
    "interpretation": "For the monotone 1-Lipschitz skew map, the plain forward step expands while extragradient and the resolvent contract.",
    "methods": {
      "extragradient": {
        "exact_final_norm": 0.02868503292055673,
        "exact_one_step_factor": 0.8772684879784524,
        "factor_absolute_error": 0.0,
        "final_norm": 0.028685032920556713,
        "numerical_one_step_factor": 0.8772684879784524
      },
      "forward": {
        "exact_final_norm": 146.81251981799534,
        "exact_one_step_factor": 1.16619037896906,
        "factor_absolute_error": 0.0,
        "final_norm": 146.81251981799582,
        "numerical_one_step_factor": 1.16619037896906
      },
      "resolvent": {
        "exact_final_norm": 0.014474242405445955,
        "exact_one_step_factor": 0.8574929257125443,
        "factor_absolute_error": 2.220446049250313e-16,
        "final_norm": 0.014474242405445915,
        "numerical_one_step_factor": 0.8574929257125441
      }
    },
    "steps": 30
  },
  "reference": {
    "inclusion_residual": 1.1102230246251565e-16,
    "method": "complete_active_set_enumeration",
    "pattern": [
      1,
      -1
    ],
    "subgradient": [
      1.0,
      -1.0
    ],
    "x": [
      0.08461538461538469,
      -0.576923076923077
    ]
  },
  "resolvent_probe": {
    "identity_error": 4.002966042486721e-16,
    "input": [
      0.7,
      -1.1
    ],
    "output": [
      0.23757044458359441,
      -1.0820288040075141
    ]
  },
  "result": "pass",
  "rows": [
    {
      "error_to_reference": 2.8034319626541264,
      "fixed_point_residual": 2.0215835377248204,
      "inclusion_residual": 5.05395884431205,
      "iteration": 0,
      "method": "forward_backward_stable",
      "norm": 3.2015621187164243,
      "x1": 2.5,
      "x2": -2.0
    },
    {
      "error_to_reference": 2.378790901665414,
      "fixed_point_residual": 1.5279057562559282,
      "inclusion_residual": 4.288426284780933,
      "iteration": 1,
      "method": "forward_backward_stable",
      "norm": 2.959189078109069,
      "x1": 0.68,
      "x2": -2.88
    },
    {
      "error_to_reference": 1.9246763564098446,
      "fixed_point_residual": 1.2964710255150327,
      "inclusion_residual": 3.2411775637875815,
      "iteration": 2,
      "method": "forward_backward_stable",
      "norm": 2.4313485969724704,
      "x1": -0.74,
      "x2": -2.316
    },
    {
      "error_to_reference": 0.6490542485346841,
      "fixed_point_residual": 0.46803967472991015,
      "inclusion_residual": 1.4614116829312678,
      "iteration": 5,
      "method": "forward_backward_stable",
      "norm": 0.0665920000000002,
      "x1": -0.0,
      "x2": 0.0665920000000002
    },
    {
      "error_to_reference": 0.2417683009574272,
      "fixed_point_residual": 0.14136031027200002,
      "inclusion_residual": 0.35340077568000017,
      "iteration": 10,
      "method": "forward_backward_stable",
      "norm": 0.8034007756800001,
      "x1": 0.0,
      "x2": -0.8034007756800001
    },
    {
      "error_to_reference": 0.02273956068284884,
      "fixed_point_residual": 0.016397730404707232,
      "inclusion_residual": 0.04099432601176812,
      "iteration": 20,
      "method": "forward_backward_stable",
      "norm": 0.5803122231695571,
      "x1": 0.061875967999999976,
      "x2": -0.5770040216012856
    },
    {
      "error_to_reference": 0.0008513478319503896,
      "fixed_point_residual": 0.0006139156522705296,
      "inclusion_residual": 0.0015347891306762313,
      "iteration": 40,
      "method": "forward_backward_stable",
      "norm": 0.5832163418546286,
      "x1": 0.0854667270535843,
      "x2": -0.5769200464302164
    },
    {
      "error_to_reference": 1.1933201195565088e-06,
      "fixed_point_residual": 8.605153759058425e-07,
      "inclusion_residual": 2.151288439710652e-06,
      "iteration": 80,
      "method": "forward_backward_stable",
      "norm": 0.5830953584494807,
      "x1": 0.08461657792794391,
      "x2": -0.5769230726752853
    },
    {
      "error_to_reference": 1.6726569660632432e-09,
      "fixed_point_residual": 1.2061701768457911e-09,
      "inclusion_residual": 3.0154253724902848e-09,
      "iteration": 120,
      "method": "forward_backward_stable",
      "norm": 0.5830951897213638,
      "x1": 0.08461538628803106,
      "x2": -0.5769230769171229
    },
    {
      "error_to_reference": 3.1780134079895106e-15,
      "fixed_point_residual": 2.401779625492033e-15,
      "inclusion_residual": 5.821000005975887e-15,
      "iteration": 200,
      "method": "forward_backward_stable",
      "norm": 0.5830951894845305,
      "x1": 0.08461538461538787,
      "x2": -0.576923076923077
    },
    {
      "error_to_reference": 2.8034319626541264,
      "fixed_point_residual": 4.148062800874644,
      "inclusion_residual": 5.05395884431205,
      "iteration": 0,
      "method": "forward_backward_outside_range",
      "norm": 3.2015621187164243,
      "x1": 2.5,
      "x2": -2.0
    },
    {
      "error_to_reference": 3.6184093934298724,
      "fixed_point_residual": 5.242403915428493,
      "inclusion_residual": 6.239141066685381,
      "iteration": 1,
      "method": "forward_backward_outside_range",
      "norm": 4.141427893854968,
      "x1": -1.145,
      "x2": -3.98
    },
    {
      "error_to_reference": 4.354836962085509,
      "fixed_point_residual": 6.7562350887092615,
      "inclusion_residual": 7.885150039195511,
      "iteration": 2,
      "method": "forward_backward_outside_range",
      "norm": 4.192732857278173,
      "x1": -4.182499999999999,
      "x2": 0.29274999999999995
    },
    {
      "error_to_reference": 9.98541387533172,
      "fixed_point_residual": 15.826250825263434,
      "inclusion_residual": 18.001460867119047,
      "iteration": 5,
      "method": "forward_backward_outside_range",
      "norm": 10.563470288735333,
      "x1": 0.18739346875000037,
      "x2": -10.561808
    },
    {
      "error_to_reference": 42.02461566400635,
      "fixed_point_residual": 67.8580890355725,
      "inclusion_residual": 75.88240964986971,
      "iteration": 10,
      "method": "forward_backward_outside_range",
      "norm": 42.14445125335256,
      "x1": -39.451837669007126,
      "x2": -14.822525965047928
    },
    {
      "error_to_reference": 849.0555869955879,
      "fixed_point_residual": 1377.5910545842958,
      "inclusion_residual": 1531.098125152578,
      "iteration": 20,
      "method": "forward_backward_outside_range",
      "norm": 848.5877268267457,
      "x1": 402.4422505581068,
      "x2": 747.0885925288309
    },
    {
      "error_to_reference": 362303.871523797,
      "fixed_point_residual": 587837.1595466494,
      "inclusion_residual": 653152.8605182628,
      "iteration": 40,
      "method": "forward_backward_outside_range",
      "norm": 362303.48226164863,
      "x1": -301992.0606033278,
      "x2": 200161.4563083331
    },
    {
      "error_to_reference": 66062006837.49017,
      "fixed_point_residual": 107185478855.24078,
      "inclusion_residual": 119094976506.31174,
      "iteration": 80,
      "method": "forward_backward_outside_range",
      "norm": 66062006837.9523,
      "x1": 47456243914.1256,
      "x2": -45957520179.19019
    },
    {
      "error_to_reference": 1.2045682971348158e+16,
      "fixed_point_residual": 1.954409742053064e+16,
      "inclusion_residual": 2.17156638005896e+16,
      "iteration": 120,
      "method": "forward_backward_outside_range",
      "norm": 1.2045682971348158e+16,
      "x1": -6973546010449878.0,
      "x2": 9821819296157182.0
    },
    {
      "error_to_reference": 4.004891561283648e+26,
      "fixed_point_residual": 6.49792884459655e+26,
      "inclusion_residual": 7.219920938440611e+26,
      "iteration": 200,
      "method": "forward_backward_outside_range",
      "norm": 4.004891561283648e+26,
      "x1": -9.882929849502497e+25,
      "x2": 3.8810350930568894e+26
    },
    {
      "error_to_reference": 2.564569989446424,
      "fixed_point_residual": 2.9293818673911396,
      "inclusion_residual": 4.623344298232611,
      "iteration": 0,
      "method": "douglas_rachford",
      "norm": 2.9557148035627523,
      "x1": 2.325,
      "x2": -1.825
    },
    {
      "error_to_reference": 1.2834888300639757,
      "fixed_point_residual": 1.271073151629751,
      "inclusion_residual": 2.3138423941404755,
      "iteration": 1,
      "method": "douglas_rachford",
      "norm": 1.8401832148580914,
      "x1": 0.7103318722604886,
      "x2": -1.6975579211020664
    },
    {
      "error_to_reference": 0.6423468977949716,
      "fixed_point_residual": 0.5672530458990993,
      "inclusion_residual": 1.1580073383174985,
      "iteration": 2,
      "method": "douglas_rachford",
      "norm": 1.21994766146663,
      "x1": 0.05632520117361578,
      "x2": -1.2186466954908017
    },
    {
      "error_to_reference": 0.09697222070248318,
      "fixed_point_residual": 0.12237340991344488,
      "inclusion_residual": 0.17481915701920683,
      "iteration": 5,
      "method": "douglas_rachford",
      "norm": 0.6242923525599455,
      "x1": 0.0,
      "x2": -0.6242923525599455
    },
    {
      "error_to_reference": 0.003987314578375228,
      "fixed_point_residual": 0.005031763507307906,
      "inclusion_residual": 0.007188233581868407,
      "iteration": 10,
      "method": "douglas_rachford",
      "norm": 0.5800860572060366,
      "x1": 0.08675954580797979,
      "x2": -0.5735613436904881
    },
    {
      "error_to_reference": 3.930573090358453e-06,
      "fixed_point_residual": 4.960158986575774e-06,
      "inclusion_residual": 7.085941409434631e-06,
      "iteration": 20,
      "method": "douglas_rachford",
      "norm": 0.5830912615802498,
      "x1": 0.08461467133432576,
      "x2": -0.5769192116113238
    },
    {
      "error_to_reference": 3.81962062324116e-12,
      "fixed_point_residual": 4.820196128874869e-12,
      "inclusion_residual": 6.885867582289481e-12,
      "iteration": 40,
      "method": "douglas_rachford",
      "norm": 0.5830951894844023,
      "x1": 0.08461538461158907,
      "x2": -0.5769230769235045
    },
    {
      "error_to_reference": 1.8875832159447664e-16,
      "fixed_point_residual": 2.7755575615628914e-16,
      "inclusion_residual": 4.002966042486721e-16,
      "iteration": 80,
      "method": "douglas_rachford",
      "norm": 0.5830951894845302,
      "x1": 0.08461538461538454,
      "x2": -0.5769230769230771
    },
    {
      "error_to_reference": 1.8875832159447664e-16,
      "fixed_point_residual": 2.7755575615628914e-16,
      "inclusion_residual": 4.002966042486721e-16,
      "iteration": 120,
      "method": "douglas_rachford",
      "norm": 0.5830951894845302,
      "x1": 0.08461538461538454,
      "x2": -0.5769230769230771
    },
    {
      "error_to_reference": 1.8875832159447664e-16,
      "fixed_point_residual": 2.7755575615628914e-16,
      "inclusion_residual": 4.002966042486721e-16,
      "iteration": 200,
      "method": "douglas_rachford",
      "norm": 0.5830951894845302,
      "x1": 0.08461538461538454,
      "x2": -0.5769230769230771
    }
  ],
  "schema": "o015-original-02-monotone-splitting-lab-v1",
  "theory": {
    "beta": 0.3076923076923077,
    "diagnostic_step_outside_proved_interval": true,
    "forward_backward_upper_bound": 0.6153846153846154,
    "stable_step_inside_open_interval": true
  },
  "upstream_contact": false
}

Hasil CSV lengkap

method,iteration,x1,x2,norm,error_to_reference,fixed_point_residual,inclusion_residual
forward_backward_stable,0,2.5,-2.0,3.2015621187164243,2.8034319626541264,2.0215835377248204,5.05395884431205
forward_backward_stable,1,0.68,-2.88,2.959189078109069,2.378790901665414,1.5279057562559282,4.288426284780933
forward_backward_stable,2,-0.74,-2.316,2.4313485969724704,1.9246763564098446,1.2964710255150327,3.2411775637875815
forward_backward_stable,5,-0.0,0.0665920000000002,0.0665920000000002,0.6490542485346841,0.46803967472991015,1.4614116829312678
forward_backward_stable,10,0.0,-0.8034007756800001,0.8034007756800001,0.2417683009574272,0.14136031027200002,0.35340077568000017
forward_backward_stable,20,0.061875967999999976,-0.5770040216012856,0.5803122231695571,0.02273956068284884,0.016397730404707232,0.04099432601176812
forward_backward_stable,40,0.0854667270535843,-0.5769200464302164,0.5832163418546286,0.0008513478319503896,0.0006139156522705296,0.0015347891306762313
forward_backward_stable,80,0.08461657792794391,-0.5769230726752853,0.5830953584494807,1.1933201195565088e-06,8.605153759058425e-07,2.151288439710652e-06
forward_backward_stable,120,0.08461538628803106,-0.5769230769171229,0.5830951897213638,1.6726569660632432e-09,1.2061701768457911e-09,3.0154253724902848e-09
forward_backward_stable,200,0.08461538461538787,-0.576923076923077,0.5830951894845305,3.1780134079895106e-15,2.401779625492033e-15,5.821000005975887e-15
forward_backward_outside_range,0,2.5,-2.0,3.2015621187164243,2.8034319626541264,4.148062800874644,5.05395884431205
forward_backward_outside_range,1,-1.145,-3.98,4.141427893854968,3.6184093934298724,5.242403915428493,6.239141066685381
forward_backward_outside_range,2,-4.182499999999999,0.29274999999999995,4.192732857278173,4.354836962085509,6.7562350887092615,7.885150039195511
forward_backward_outside_range,5,0.18739346875000037,-10.561808,10.563470288735333,9.98541387533172,15.826250825263434,18.001460867119047
forward_backward_outside_range,10,-39.451837669007126,-14.822525965047928,42.14445125335256,42.02461566400635,67.8580890355725,75.88240964986971
forward_backward_outside_range,20,402.4422505581068,747.0885925288309,848.5877268267457,849.0555869955879,1377.5910545842958,1531.098125152578
forward_backward_outside_range,40,-301992.0606033278,200161.4563083331,362303.48226164863,362303.871523797,587837.1595466494,653152.8605182628
forward_backward_outside_range,80,47456243914.1256,-45957520179.19019,66062006837.9523,66062006837.49017,107185478855.24078,119094976506.31174
forward_backward_outside_range,120,-6973546010449878.0,9821819296157182.0,1.2045682971348158e+16,1.2045682971348158e+16,1.954409742053064e+16,2.17156638005896e+16
forward_backward_outside_range,200,-9.882929849502497e+25,3.8810350930568894e+26,4.004891561283648e+26,4.004891561283648e+26,6.49792884459655e+26,7.219920938440611e+26
douglas_rachford,0,2.325,-1.825,2.9557148035627523,2.564569989446424,2.9293818673911396,4.623344298232611
douglas_rachford,1,0.7103318722604886,-1.6975579211020664,1.8401832148580914,1.2834888300639757,1.271073151629751,2.3138423941404755
douglas_rachford,2,0.05632520117361578,-1.2186466954908017,1.21994766146663,0.6423468977949716,0.5672530458990993,1.1580073383174985
douglas_rachford,5,0.0,-0.6242923525599455,0.6242923525599455,0.09697222070248318,0.12237340991344488,0.17481915701920683
douglas_rachford,10,0.08675954580797979,-0.5735613436904881,0.5800860572060366,0.003987314578375228,0.005031763507307906,0.007188233581868407
douglas_rachford,20,0.08461467133432576,-0.5769192116113238,0.5830912615802498,3.930573090358453e-06,4.960158986575774e-06,7.085941409434631e-06
douglas_rachford,40,0.08461538461158907,-0.5769230769235045,0.5830951894844023,3.81962062324116e-12,4.820196128874869e-12,6.885867582289481e-12
douglas_rachford,80,0.08461538461538454,-0.5769230769230771,0.5830951894845302,1.8875832159447664e-16,2.7755575615628914e-16,4.002966042486721e-16
douglas_rachford,120,0.08461538461538454,-0.5769230769230771,0.5830951894845302,1.8875832159447664e-16,2.7755575615628914e-16,4.002966042486721e-16
douglas_rachford,200,0.08461538461538454,-0.5769230769230771,0.5830951894845302,1.8875832159447664e-16,2.7755575615628914e-16,4.002966042486721e-16