Douglas–Rachford 分裂

固定点怎样恢复原问题解 ​

若 $z=Tz$，则两影子相同，记为 $p=q$。预解定义分别给

两项相加为零，所以 $p\in Z$。反过来，若 $p\in Z$，选 $a\in Ap$使 $-a\in Bp$，令 $z=p+\gamma a$，便有 $J_{\gamma A}z=p$及$J_{\gamma B}(2p-z)=p$。因此解存在恰好保证辅助不动点存在，但恢复公式必须保留。

为什么反射之后还要平均 ​

牢固非扩张性给任意输入 $z,w$的

这里为简洁省略共同的 $\gamma$。展开 $R_{A}z-R_{A}w=2(J_{A}z-J_{A}w)-(z-w)$，便得 $\Vert R_{A}z-R_{A}w\Vert \le \Vert z-w\Vert$。$R_B$也非扩张，故 $S=R_B{R}_A$非扩张。

取任意不动点 $z^{\ast }$，$S{z}^{\ast }=z^{\ast }$。平方中点恒等式给

使用非扩张性及 $Tz-z=(Sz-z)/2$，得到

平均不仅不放大距离，还用距离下降支付主点位移。仅知道未平均的 $S$非扩张，只能得到距离不增，不能排除周期。

两条直线上的四轮计算 ​

令 $A=N_U,B=N_V$，其中 $U=\{(t,0)\}$、$V=\{(t,t)\}$。法锥预解就是投影，所以

相应反射为 $R_U(a,b)=(a,-b)$、$R_V(a,b)=(b,a)$，故 $R_V{R}_U=J$为逆时针直角旋转。DR更新是

从 $z_0=(1,0)$开始，

状态每轮旋转 ${45}^{\circ }$，长度乘 $1/\sqrt{2}$，最终趋于两线交点零。第二轮影子恰好经过零，不代表以后每轮都停在零；状态仍未固定，下一影子可以离开这个偶然的交点。

若只迭代 $R_V{R}_U=J$，得到的是未平均的Peaceman–Rachford更新，非零初值永远四周期。这不是“计算精度不够”，而是迭代矩阵本身没有收缩。

状态极限可以在解集之外 ​

在实直线上取 $A=\partial f$、$f(x)=(x-2{)}^2/2$，$B=N_{\{0\}}$。唯一零点为 $p^{\ast }=0$，因为在那里 $A{p}^{\ast }=-2$可由法锥中的 $2$抵消。

取 $\gamma =1$，两个近端/预解理路近端算子Proximal operator · Proximity operator在降低凸函数值与保持靠近输入点之间取得精确平衡的单值算子。分别为 $J_{A}z=(z+2)/2$、$J_{B}w=0$。所以

从 $z_0=0$开始，状态依次为 $-1,-3/2,-7/4,-15/8$，趋向 $-2$；第一影子依次为 $p_0=1,p_1=1/2,p_2=1/4,\dots$，趋向正确解零。若直接把状态 $-2$交给原问题，它甚至违反 $x=0$的约束。

图中灰色辅助状态可以在原问题的不可行位置收敛，蓝色影子才是要交付的原变量。极限线分别标出两份对象，不能只看某条曲线已变平便报告答案。

子问题可解仍需零点存在 ​

极大单调性确保两次预解都可执行，不保证两部分能够平衡。例如 $A=0,B(x)=\{1\}$，有 $J_{A}z=z,J_{B}z=z-\gamma$，故 $z_{k+1}=z_k-\gamma$持续漂移。没有零点时，式(2)没有可用的不动点作比较。

非凸近端、随轮变化的步长或仅近似预解都超出当前精确固定参数证明。两条直线的几何速度来自显式矩阵，并非对所有极大单调算子都成立。

从平方可求和到整列收敛 ​

将式(2)求和，$z_k$有界，且 $\sum _k\Vert z_{k+1}-z_k{\Vert }^2<\mathrm{\infty }$。有限维聚点定理理路Bolzano–Weierstrass 定理Bolzano–Weierstrass theorem实数空间中的每个有界序列都存在收敛子列。给 $z_{k_j}\to \overline{z}$。两次预解连续，故 $T$连续；相邻位移趋零使 $T\overline{z}=\overline{z}$。到这个不动点的距离不增而有子列趋零，整个状态序列收敛。

由预解连续性，$p_k\to J_A\overline{z}$。又有 $q_k-p_k=z_{k+1}-z_k\to 0$，所以第二影子也有同一极限。固定点恢复证明已保证这个极限解决原包含关系。

停止时保留两份位置和两份算子值 ​

每轮可计算

且 $a_k+b_k=(p_k-q_k)/\gamma$。影子差同时衡量两位置是否一致与两算子值是否平衡；但当 $p_k\ne q_k$时，不能声称 $a_k+b_k\in (A+B)p_k$，因为 $b_k$是在 $q_k$处取得。

式(2)还给前 $N$轮中 $\underset{k}{min}\Vert p_k-q_k{\Vert }^2\le \Vert z_0-z^{\ast }{\Vert }^2/N$。如果初始到某不动点的距离没有可知上界，这不是可以凭空报出的数值精度；实际仍可报告两份残差和模型允许的更强证书。

每轮调用两次预解，另需 $O(d)$向量运算及存储。凸函数拆分时它们可由两个prox实现；ADMM理路交替方向乘子法（ADMM）Alternating direction method of multipliers · ADMM将凸目标拆成两个近端子问题，用乘子累积一致性误差，并以原始与对偶残差检查最优性的算法。与DR在适当对偶拆分下有联系，但变量变换、初始化和资格条件需要逐项给出，本页不把它们无条件标成同一迭代。