外梯度法

两条最近点不等式怎样支付场的变化 ​

一轮中简记 $x=x_k,y=y_k,p=x_{k+1}$。第二次投影给任意 $u\in C$ 的

第一次投影则给 $\gamma ⟨F(x),y-p⟩\le ⟨x-y,y-p⟩$。把目标内积拆成 $⟨F(y),y-u⟩$，相加并展开平方，得到

Lipschitz条件和 $2ab\le a^2+b^2$ 将最后一项控制为 $\gamma L(\Vert x-y{\Vert }^2+\Vert y-p{\Vert }^2)$。因此关键估计是

两个短位移支付两处反馈差。若第二步改从 $y$ 出发，上面第一行不再使用同一个平方距离中心，不能原样沿用式(3)。

为什么得到整列收敛 ​

取任一解 $u=x^{\ast }$。单调性与VI条件给 $⟨F(y),y-x^{\ast }⟩\ge 0$。由于 $1-\gamma L>0$，式(3)表明到每个解的距离不增，且 $\sum _k\Vert x_k-y_k{\Vert }^2<\mathrm{\infty }$。于是主点有界，预测位移趋于零。

由有限维Bolzano–Weierstrass定理理路Bolzano–Weierstrass 定理Bolzano–Weierstrass theorem实数空间中的每个有界序列都存在收敛子列。取 $x_{k_j}\to \hat{x}$。投影和 $F$ 连续，$y_{k_j}-x_{k_j}\to 0$，故 $\hat{x}=P_C(\hat{x}-\gamma F(\hat{x}))$，它是VI解。再把距离不增结论中的解选成 $\hat{x}$：这份距离沿子列趋零，因此整列也趋零。预测点与主点相差趋零，亦有同一极限。

旋转场的全部线性轨道 ​

先取 $C={\mathbb{R}}^2$、$F=J$，其中 $J(x_1,x_2)=(-x_2,x_1)$，$L=1$。投影是恒等映射，式(1)化成

因为 $J^{\mathsf{T}}=-J$、$J^{\mathsf{T}}J=I$，有

当 $0<\gamma <1$ 时系数小于一，故收敛到唯一零点。取 $\gamma =1/2,x_0=(1,0)$，前两轮为

主点平方长度每轮乘 $13/16$；只有一次前向更新时则每轮乘 $5/4$。算法多出的查询不是更精细地沿旧方向走，而是修正方向本身。

图中三条轨道使用同一初值和步长。右图比较主更新轮数，不表示两次场求值与一次完整预解的运算成本相同；这里的隐式轨道沿用单调算子页的精确矩阵。

有界盒中的平均输出证书 ​

改取 $C=[-1,1{]}^2$、$x_0=(1/2,0)$，步长仍为 $1/2$。主点长度不断缩小，预测点长度至多为 $\sqrt{5/4}/2<1$，所以两类点都在盒内，投影不改变上面的线性公式。

此时 $R^2=(3/2{)}^2+1=13/4$，而盒旋转的 $G_M(x)=|x_1|+|x_2|$。因而任何 $N\ge 1$ 都能同时报告实际平均间隙和保守上界 $13/(4N)$。例如要按这个上界保证间隙不超过 $0.01$，取 $N\ge 325$ 即可；需要650次场求值和650次投影调用，盒投影在本例虽不改变值，验证其不活跃仍是模型分析的一部分。

步长端点、解存在与误差来源 ​

旋转例中若 $\gamma =1$，主点更新为 $-Jx$，非零初值形成四周期；若 $\gamma >1$，平方放大系数大于一。这给出不能把严格步长条件任意放宽的具体反例，但没有说所有问题在端点都失败。

若没有解，距离证明没有可比较的目标。例如全空间常值场 $F(x)=1$ 是单调且满足任意正Lipschitz上界，却无零点，迭代持续平移。非单调场、带偏查询或近似投影也需要新的分析；名称相同不能保留当前常数。

平均间隙的望远镜证明 ​

对固定 $u\in C$，单调性给 $⟨F(u),y_k-u⟩\le ⟨F(y_k),y_k-u⟩$。式(3)求和、舍去非正项，有

除以 $2\gamma N$，再对 $u$取上确界，便得式(2)。不能把平均 ${\overline{y}}_N$ 换成 ${\overline{x}}_N$ 或最后一点而仍称使用同一证明；求和里的实际评估点是 $y_k$。

每轮有两次 $F$ 与两次投影，另需 $O(d)$ 向量运算和 $O(d)$ 工作存储；运行平均无需保存全部历史。若 $F(x)=Mx+b$，稠密矩阵每次求值为 $O(d^2)$，稀疏存储 $s$ 个条目时为 $O(s+d)$；投影本身的子问题成本另计。

在Mirror-Prox理路Mirror-Prox 方法Mirror-Prox method · Mirror extragradient在同一镜像锚点上执行预测与校正，以Bregman三点恒等式证明单调Lipschitz问题的平均间隙率，并完整计算负熵矩阵博弈的双步更新。中选平方欧氏生成函数，两次Bregman子问题就严格化为式(1)，故本法是其欧氏特例。一般范数可以改善有界域常数，但要重新计算强凸系数与对偶Lipschitz界，不能只替换图中的距离名称。

Tseng的前向–后向–前向分裂理路Tseng 前向—后向—前向分裂Forward-backward-forward splitting · Tseng splitting · Modified forward-backward splitting以一次预解和两次单调Lipschitz场求值修正前后分裂，证明Fejér下降与残差平方率，并说明校正点可能离开约束而预测点仍可行。在法锥情形只做一次投影，再加显式场差校正；校正状态可能离开可行集。本页的两次投影始终保持可行，因此只要求场在 $C$上有定义。两种更新在无约束零算子情形重合，一般约束下并不相同。