每个算法交出什么，怎样验证它 ​

一个可执行的迭代式还不是完整解法。需要先说明模型有哪些结构、一步允许调用什么运算，再确定输出是预测点平均、可行近端点、分裂影子，还是原对偶变量。本终点用几份小模型把这些区别变成能逐项核算的交付。

单调变分不等式理路单调变分不等式Monotone variational inequality · Stampacchia variational inequality · Minty variational inequality用一般单调场与可行方向的内积刻画平衡，证明两种量词形式和投影固定点的关系，并以可计算间隙区分解、存在性与误差尺度。给出平衡与间隙；外梯度理路外梯度法Extragradient method · Korpelevich method在同一原锚点上先预测再校正，用两次场求值和投影处理单调旋转，证明有限维点收敛及平均预测点的有界域间隙率。和Mirror–Prox理路Mirror-Prox 方法Mirror-Prox method · Mirror extragradient在同一镜像锚点上执行预测与校正，以Bregman三点恒等式证明单调Lipschitz问题的平均间隙率，并完整计算负熵矩阵博弈的双步更新。控制预测点的平均间隙。前向–后向理路前向—后向算子分裂Forward-backward splitting · Forward backward operator splitting把极大单调包含拆成一次便宜的显式余单调步和一次预解步，以直接Fejér不等式证明收敛，并用非梯度旋转和步长端点说明边界。利用余强单调性，前向–后向–前向理路Tseng 前向—后向—前向分裂Forward-backward-forward splitting · Tseng splitting · Modified forward-backward splitting以一次预解和两次单调Lipschitz场求值修正前后分裂，证明Fejér下降与残差平方率，并说明校正点可能离开约束而预测点仍可行。为一般 Lipschitz 单调场增加一次修正。Douglas–Rachford理路Douglas–Rachford 分裂Douglas–Rachford splitting · Douglas Rachford method · DR splitting分别计算两个极大单调算子的预解，通过反射平均恢复和算子的零点，证明状态与影子点的收敛，并用周期反例说明平均的作用。返回近端影子，PDHG理路原始—对偶混合梯度Primal-dual hybrid gradient · PDHG · Chambolle–Pock algorithm以两次分离近端和线性算子乘法求复合凸鞍点，将外推更新写成正定块度量下的隐式步，证明点收敛与平均受限间隙并计算完整融合例。将线性耦合拆为两次矩阵乘法与两次近端调用。

任务一：反馈变强后，平均间隙预算怎样改变 ​

盒上的旋转 ​

给定 $C=[-1,1{]}^2$、$F(x)=2Jx$，其中 $J(x_1,x_2)=(-x_2,x_1)$，初始点 $x_0=(1/2,0)$。目标是交出 Minty 间隙不超过 $1/50$ 的候选。

场的 Lipschitz 常数为 $L=2$。取外梯度步长 $\gamma =1/4$，计算

$$w_k=P_C(x_k-\gamma F(x_k)),x_{k+1}=P_C(x_k-\gamma F(w_k)).$$

于是 $\gamma L=1/2<1$。第一步为

$$w_0=(1/2,-1/4),x_1=(3/8,-1/4).$$

这些点与未缩放旋转、步长 $1/2$ 的点相同，因为两者的 $\gamma F$ 相同；但本问题的间隙为 $G_M(x)=2(|x_1|+|x_2|)$，数值是原来的两倍。不能只见迭代轨道没变，就照抄旧误差数值。

从初始点到盒中最远点的距离平方为

$$R^2=(3/2{)}^2+1^2=13/4.$$

输出 ${\overline{w}}_N=N^{-1}\sum _{k=0}^{N-1}{w}_k$，理论证书为

$$G_M({\overline{w}}_N)\le \frac{R^2}{2\gamma N}=\frac{13}{2N}.$$

取 $N=325$ 即达目标，需要650次场调用及650次盒投影；二维盒投影逐坐标截断。这个 N 是无需观察轨道的充分预算，实际间隙可能提前达标。若计算实际平均间隙，须平均预测点，而不是未经证明就改平均更新点。

若直接保留旧步长 $\gamma =1/2$，则 $\gamma L=1$。在此轨道上更新化为 $x_{k+1}=-J{x}_k$，出现四周期，点本身不收敛。这个边界例检出了遗漏缩放的风险。

单纯形上的同类缩放 ​

将两人零和博弈的支付矩阵改为

$$2M,M=\left(\begin{array}{cc}1& -1\\ -1& 1\end{array}\right).$$

仍取初始概率 $p_0=(3/4,1/4),q_0=(1/2,1/2)$，使用两块负熵与正文的块范数。此时 $L=2$，选择 $\gamma =(\log 2)/2$。指数更新中的 $\gamma F$ 不变，第一预测点仍是 $w_p=p_0,w_q=(2/3,1/3)$；校正锚点的首坐标为

$$p_1^{(1)}=\frac{3}{3+2^{2/3}},q_1^{(1)}=\frac{2}{3}.$$

初始 Bregman 半径仍为 $\mathrm{\Theta }=\log 8$，故平均预测策略的鞍点间隙不超过 $6/N$。要求间隙至多 $1/100$，取 $N=600$ 足够。改变支付尺度没有改变可行策略，却同时改变安全步长与证书数值；若初始概率含零，熵更新会锁死该坐标，不能继续使用覆盖整个单纯形的有限半径。

任务二：同一阻尼旋转，为什么有两种合法分裂 ​

设 $A=0$，$B(x)=3x+4Jx$，在整个 ${\mathbb{R}}^2$ 上寻找零点。其唯一零点为0，且对任意差向量 h，

$$⟨Bh,h⟩=3\Vert h{\Vert }^2,\Vert Bh{\Vert }^2=25\Vert h{\Vert }^2.$$

因此可取余强单调常数 $\beta =3/25$，而 Lipschitz 常数为5。前向–后向只需一次 B 调用，因为 $J_{\gamma A}=I$，更新为

$$x_{k+1}=((1-3\gamma )I-4\gamma J)x_k.$$

取 $\gamma =1/5<2\beta =6/25$，有

$$\Vert x_{k+1}{\Vert }^2=\frac{4}{5}\Vert x_k{\Vert }^2.$$

从 $x_0=(1,0)$ 得 $x_1=(2/5,-4/5)$。若误取 $\gamma =1/4$，平方范数因子变成 $17/16$，非零点发散。检查的是余强单调预算，并非只找一个看起来小的步长。

只使用单调与 Lipschitz 条件时，也可选 FBF 的 $\gamma =1/10<1/L$。预测点为 $p=x-\gamma Bx$，更新为 $x^{+}=p+\gamma (Bx-Bp)$。对于当前线性场，

$$x^{+}=(\frac{63}{100}I-\frac{4}{25}J)x,\Vert x^{+}{\Vert }^2=\frac{169}{400}\Vert x{\Vert }^2.$$

每轮多调用一次 B。这个具体例里平方范数收缩更快，但不能据此宣布 FBF 对所有模型都更快：每轮成本、参数限制与目标精度都要计入。

进一步把 A 改为约束集的法锥时，FBF 的预测点在约束内，校正状态却未必可行。需要可行候选就报告近端预测点及其包含残差；不得把“状态能继续迭代”和“当前状态满足约束”当成同一件事。

接口核验：分裂状态的极限，怎样变成原问题的解 ​

令

$$A(x)=x-4,B=N_{\{1\}},\gamma =2.$$

原包含关系只有 $x=1$ 可行，且在该点 $A(1)=-3$、$B(1)=\mathbb{R}$，所以 x=1 确为解。两个预解算子为

$$J_{2A}(z)=\frac{z+8}{3},J_{2B}(v)=1.$$

Douglas–Rachford 从 $z_0=0$ 开始，依次算 $p_k=J_{2A}{z}_k$、$q_k=J_{2B}(2p_k-z_k)$、$z_{k+1}=z_k+q_k-p_k$。因此

$$z_{k+1}=\frac{2z_k-5}{3},z_k=-5+5(2/3{)}^k,p_k=1+\frac{5}{3}(2/3{)}^k.$$

前三个新状态为 $-5/3,-25/9,-95/27$。状态趋于 -5，而原解影子趋于1；第二个影子 $q_k$ 恰好每步等于1。知道这一特例的可行点只有一个，已可直接认证 q 是解，但一般分裂问题没有这种捷径。

若以第一影子输出，位置误差就是 $|p_k-1|=(5/3)(2/3{)}^k$。分裂差 $q_k-p_k$ 同时趋零。不过有限 k 时所计算的算子值分别位于 $A(p_k)$ 与 $B(q_k)$；将它们的和未经说明写成 $(A+B)(p_k)$ 的成员，会把两个不同位置合并错。

输出时应逐项检查：返回哪个变量、它是否原可行，以及有限步的算子值究竟位于哪个位置。

任务三选择PDHG步长时，要先量清矩阵对向量的最大放大。诱导矩阵范数说明这里的二范数为何由最大奇异值决定；计算出范数上界以后，再检查两个步长的联合预算。

任务三：三点信号中的融合段和活动边 ​

给定观测信号 $b=(0,0,3)$，希望去除小幅相邻差异，同时保留最后一处较大跳变。求解

$$\underset{x\in {\mathbb{R}}^3}{min}P(x):=\frac{1}{2}\Vert x-b{\Vert }^2+|x_2-x_1|+|x_3-x_2|.$$

定义域包含三个信号值、两条相邻边，对偶变量为二维。令

$$K=\left(\begin{array}{ccc}-1& 1& 0\\ 0& -1& 1\end{array}\right),K^{\mathsf{T}}y=(-y_1,y_1-y_2,y_2).$$

取 $f(x)=\Vert x-b{\Vert }^2/2$、$g(v)=\Vert v{\Vert }_1$。对偶可行域为盒 $[-1,1{]}^2$，各坐标分别控制一条边。$K{K}^{\mathsf{T}}=\left(\begin{array}{cc}2& -1\\ -1& 2\end{array}\right)$ 的两个特征值为1和3，故 $\Vert K{\Vert }_2^2=3$。取 $\tau =\sigma =1/2$，步长乘积为 $3/4<1$。

先给一份完整最优证书 ​

候选为

$$x^{\ast }=(1/2,1/2,2),y^{\ast }=(1/2,1).$$

先检验站立条件：$K^{\mathsf{T}}{y}^{\ast }=(-1/2,-1/2,1)$，因此

$$x^{\ast }-b+K^{\mathsf{T}}{y}^{\ast }=0.$$

再检验边上的次梯度：$K{x}^{\ast }=(0,3/2)$。第一条边融合，允许 $y_1^{\ast }\in [-1,1]$；当前值 $1/2$ 严格在盒内。第二条边是正跳变，必须 $y_2^{\ast }=1$，恰在盒边界。这两条边承担不同角色，不能只检查一个对偶向量的长度。

$f^{\ast }(u)=⟨b,u⟩+\Vert u{\Vert }^2/2$，所以可行 y 的完整对偶值为

$$D(y)=⟨b,K^{\mathsf{T}}y⟩-\frac{1}{2}\Vert K^{\mathsf{T}}y{\Vert }^2=3y_2-\frac{1}{2}(y_1^2+(y_1-y_2{)}^2+y_2^2).$$

代入得 $P(x^{\ast })=3/4+3/2=9/4$、$D(y^{\ast })=9/4$。零 gap 认证最优；平方损失的1-强凸性还给原最优点唯一。

有一个值得核查的错误候选：$y=(1,1)$ 虽对偶可行，由站立式恢复 $x=b-K^{\mathsf{T}}y=(1,0,2)$，第一条差分却为 -1，要求的次梯度应是 -1 而不是 +1。因此“对偶在盒内，并且站立方程成立”仍少了边上的相容性。它的 $P=4,D=2$，非零 gap 正好揭示缺失条件。

从零点执行原变量先更新的 PDHG ​

两个 prox 都显式：

$$x^{+}=\frac{2x-K^{\mathsf{T}}y+b}{3},y^{+}={\mathrm{clip}}_{[-1,1{]}^2}(y+\frac{1}{2}K(2x^{+}-x)).$$

从 $x_0=(0,0,0),y_0=(0,0)$ 开始，得到

$$x_1=(0,0,1),y_1=(0,1),P(x_1)=3,D(y_1)=2,P(x_1)-D(y_1)=1.$$

第一条边暂时也融合，但还没有全体最优性条件；状态不是最终解。第二轮为

$$x_2=(0,1/3,4/3),y_2=(1/3,1),P(x_2)=25/9,D(y_2)=20/9,\mathrm{gap}=5/9.$$

这轮第一条边又不相等，说明有限次算法的融合图样不能只看一次相邻值相同就永久固定。当前保证来自真实 P-D，而不是推测将来的活动集。

对任意原候选 x 与盒内 y，有

$$0\le P(x)-P(x^{\ast })\le P(x)-D(y).$$

由于原目标1-强凸，还可进一步给 $\Vert x-x^{\ast }\Vert \le \sqrt{2(P(x)-D(y))}$。这里能把 gap 转成距离，是因为明确用了曲率；一般 VI 的小间隙不自动给同样的位置误差。

迁移到较长信号时保留什么 ​

将 K 换成长度 n 路径的相邻差分，两个 prox 的形式仍成立，但 x 有 n 个坐标、y 有 n-1 个盒约束。每次 K 和 K转置乘法都可沿边表用线性工作量完成。要复用收敛定理，需重新给出该矩阵的有效范数上界及步长预算；要声明某段已融合，需检验各条边的次梯度与站立残差。不同边的盒内点、盒边界点，以及零差分之间的对应，正是从两点模型迁移到一段信号新增的结构。

交付与复算 ​

• 标准库复算脚本
• 确定性结果

运行 python foundations-operator-splitting-check.py --output result.json。有理旋转、投影、平方预算、分裂状态与融合目标使用 Fraction；负熵指数迭代用70位 Decimal，单独列出容差。精确恒等式与高精度交叉核验分开记录，后者不是机器有向舍入区间。

最终报告应包含模型及定义域、结构常数、合法步长、每轮调用成本、实际返回的对象、认证量及其范围。上述任务分别检查尺度与间隙、阻尼结构以及多边融合证书；额外的一维核验只帮助辨认内部状态和原解接口。每一次模型迁移都应能追到具体的结构条件与可行性检查。