单调变分不等式

每一项条件在等价证明中做什么 ​

从(S)到(M)，单调性给

反向取任意 $v\in C$，令 $u_t=x^{\ast }+t(v-x^{\ast })$，$0<t\le 1$。凸性保证 $u_t\in C$。将它代入(M)，除以 $t$，再由连续性令 $t\downarrow 0$，得到 $⟨F(x^{\ast }),v-x^{\ast }⟩\ge 0$。所以单调性负责第一方向，沿可行线段的连续性负责第二方向。

投影把平衡写成一个可执行等式 ​

记 $P_C$ 为非空闭凸集的最近点投影理路Hilbert 空间投影定理Hilbert projection theorem · Projection theoremHilbert 空间中每个闭线性子空间都给出唯一的正交分解与最近点投影。。最近点 $p=P_C(a)$ 的平方距离最优性给

这一式也充分：展开 $\Vert a-u{\Vert }^2$ 后，交叉项非负，得到 $\Vert a-u{\Vert }^2\ge \Vert a-p{\Vert }^2$。令 $a=x-\gamma F(x)$，任意 $\gamma >0$，便得

因此可以计算自然残差 $R_{\gamma }(x)=\Vert x-P_C(x-\gamma F(x))\Vert /\gamma$。它为零能认证解；一个小但非零的值究竟对应多小的位置误差，仍取决于额外条件。

旋转盒：没有凸势，也有明确间隙 ​

取 $C=[-1,1{]}^2$，$F(x_1,x_2)=(-x_2,x_1)=Jx$。对差向量 $h$ 有 $⟨Jh,h⟩=0$，所以场单调；矩阵 $J$ 不对称，不能是二次凸函数的梯度，事实上也不是任何全域凸函数的次梯度场，单调算子页已给闭合三角形的反证。

对任意 $x\in C$，利用 $⟨Jx,x⟩=0$ 及 $J^{\mathsf{T}}=-J$，可算出

例如在 $x=(1/2,1/4)$，$F(x)=(-1/4,1/2)$。原始间隙在 $u=(1,-1)$ 达到 $3/4$；Minty间隙也为 $3/4$。零间隙只在原点出现，故该问题的解唯一。这里恰好能把间隙化为坐标范数，是这个场与盒几何共同造成的，不是一般等式。

连续性与单调性分别不能偷换 ​

令 $C=[-1,1]$，$F(u)=-1$ 当 $u\le 0$，$F(u)=1$ 当 $u>0$。这个函数单调但在零处不连续。$x=0$ 满足(M)，因为 $F(u)u\ge 0$；但 $F(0)=-1$，取 $u=1$ 即违反(S)。因此 $G_M(0)=0$ 而 $G_S(0)=1$，且整个问题没有(S)解。把零处输出补成区间 $[-1,1]$ 会得到另一份集合值模型，不能不声明就换掉原函数。

若改为连续但反单调的 $F(u)=-u$，原点满足(S)，却有 $G_M(0)=\underset{u\in [-1,1]}{max}{u}^2=1$。两种例子分别定位了等价证明的两项假设。

小残差没有无条件的位置解释 ​

取 $F(u)=\epsilon u$、$C=[-1,1]$，$0<\epsilon <1$。解为零，但候选 $x=1$ 的距离始终为一。对 $\gamma =1$，$R_1(1)=\epsilon$，而 $G_M(1)=\epsilon /4$、$G_S(1)=2\epsilon$，都随 $\epsilon \downarrow 0$ 变小。反馈的尺度变平时，同一个误差数字不能保持统一的位置含义。

无界域也会改变间隙。例如 $C={\mathbb{R}}^2,F=J$，对非零 $x$ 的线性上确界 $G_M(x)$ 为无穷大；算法仍可收敛到零，但不能套用有限盒的间隙常数。

存在性和定位算法是两件事 ​

若再假设 $C$ 紧，映射 $x\mapsto P_C(x-\gamma F(x))$ 连续地把 $C$ 送回自身。Brouwer 不动点定理理路Brouwer 不动点定理Brouwer fixed-point theorem闭球到自身的任意连续映射都有不动点。给出固定点，于是(S)有解。连续性及紧凸域足以完成这项存在性证明，单调性不是此证明必需的条件。

这个证明没有说反复执行该映射会收敛。旋转场在全空间上的直接前向步 $x^{+}=(I-\gamma J)x$ 满足 $\Vert x^{+}{\Vert }^2=(1+{\gamma }^2)\Vert x{\Vert }^2$，任意正步长都使非零轨道扩大。外梯度法理路外梯度法Extragradient method · Korpelevich method在同一原锚点上先预测再校正，用两次场求值和投影处理单调旋转，证明有限维点收敛及平均预测点的有界域间隙率。多查询一次预测位置的场，Mirror-Prox理路Mirror-Prox 方法Mirror-Prox method · Mirror extragradient在同一镜像锚点上执行预测与校正，以Bregman三点恒等式证明单调Lipschitz问题的平均间隙率，并完整计算负熵矩阵博弈的双步更新。再改变这两步的几何，以明确的能量估计解决这一算法缺口。

给出间隙数字还须说明它怎样算得。$G_S$只需一次 $F(x)$ 和对 $C$ 的线性最小化；$G_M$通常另含对比较点 $u$ 的全局优化，并不因写成sup就自动便宜。本页的盒旋转例两种计算都是 $O(d)$；一般模型应单列算子求值、投影或间隙子问题的成本。