历史更新能交付哪一种误差证书 ​

一个算法保留历史以后，当前位置通常不再是全部状态。上一位移、旧残差、原子权重分别决定下一步；而函数值、点误差和可行性又需要不同证书。本终点要求读者逐项检查这些隐藏状态，并在模型发生结构变化时重新决定哪些保证仍成立。

沿历史更新与误差证书路线阅读PL条件理路Polyak–Łojasiewicz 条件Polyak–Łojasiewicz condition · Polyak-Lojasiewicz inequality · PL inequality · 梯度支配条件以梯度范数平方控制全局目标差，允许非凸和非唯一解，并给出确定性梯度下降的几何函数值证书。、重球法理路重球法Heavy-ball method · Polyak momentum · Polyak heavy-ball method在当前梯度步中保留上一位移，按二次模态审计稳定域、最优谱半径和瞬态，并给强凸非二次三周期边界。、Anderson加速理路Anderson 加速Anderson acceleration · Anderson mixing · 安德森加速用有限历史残差的仿射最小二乘产生候选，再在已知收缩模型上以真实残差保护和Picard回退保留可验证误差界。与远离步FW理路远离步 Frank–Wolfe 法Away-step Frank–Wolfe · Away-steps Frank-Wolfe · AFW · 远离步条件梯度法在有限凸包中维护原子权重，允许撤回不利原子的质量，并用权重上限、drop计数和可行gap分别认证更新与误差。。下载精确复算程序及结果记录。一般定理由正文证明；程序核验本页明示的有理更新、预算和拒绝条件。

任务一：目标差趋零，迭代点却能一直漂移 ​

令

$$f(s)=s^2+\frac{3}{2}{\sin }^{2}s,F(x,y)=f(x-y).$$

从$(x_0,y_0)=(1,0)$出发，取步长$1/10$。先使用真实梯度，再考虑每轮求值都加入同一个确定性偏差$e=(1/10,1/10)$。分别求有效光滑常数、PL常数、目标差预算与点的位置；判断136次更新后能认证什么。

答案：差值与平均值承担不同状态 ​

记$s=x-y$。由PL页的逐段证明，$f\ge s^2$、$|f^{\prime }|\ge |s|$、$f\le (5/2)s^2$，且$|f^{″}|\le 5$。现在

$$\mathrm{\nabla }F=(f^{\prime }(s),-f^{\prime }(s)),{\mathrm{\nabla }}^{2}F=f^{″}(s)\left(\begin{array}{cc}1& -1\\ -1& 1\end{array}\right).$$

后一个矩阵的特征值是0和2，因此$L=10$有效。另一方面，

$$\frac{1}{2}\Vert \mathrm{\nabla }F{\Vert }^2=|f^{\prime }(s){|}^2\ge \frac{2}{5}f(s),$$

故$\mu =2/5$有效。最小点是整条$x=y$，而非单个原点；$F$仍非凸，因为在$s=\pi /2$处存在负曲率方向。

真实梯度更新使

$$s_{k+1}=s_k-\frac{1}{5}{f}^{\prime }(s_k),\frac{x_{k+1}+y_{k+1}}{2}=\frac{x_k+y_k}{2}=\frac{1}{2}.$$

因此目标差满足$F(x_k,y_k)\le (5/2)(24/25{)}^k$，最终点趋于$(1/2,1/2)$。

加入共同偏差后，两坐标的误差在差值里抵消，$s_k$仍执行完全相同的递推；平均值却每轮减去$1/100$。精确地，

$$\begin{array}{}\text{(1)}& x_k=\frac{1}{2}-\frac{k}{100}+\frac{s_k}{2},y_k=\frac{1}{2}-\frac{k}{100}-\frac{s_k}{2}.\end{array}$$

目标差仍按同一上界趋零，而两个坐标都趋于负无穷。这不违反PL定理：误差沿整个目标都看不见的平坦方向积累，PL的直接证书是目标差。

136步时的三种答案 ​

Fraction比较给

$$\frac{5}{2}{\left(\frac{24}{25}\right)}^{135}>\frac{1}{100},\frac{5}{2}{\left(\frac{24}{25}\right)}^{136}\le \frac{1}{100}.$$

所以136是这份保守目标上界首次达标的预算。又因$F\ge s^2$，此时$|s_{136}|\le 1/10$，到对角解集的距离至多$1/(10\sqrt{2})$。

但是偏差版本的平均值为$-43/50$，到指定原点的距离至少为$43\sqrt{2}/50>1$。目标差小、靠近某个解、靠近指定的解是三个不同问题。

一般近似梯度公式只用$\Vert e{\Vert }^2=1/50$，会给误差底$\Vert e{\Vert }^2/(2\mu )=1/40$；本例进一步利用偏差方向，证明目标差实际上仍趋零。通用上界保守，不影响式(1)揭示的点漂移。

任务二从固定正定二次模型的稳定结论出发。正定矩阵与Loewner序说明曲率上下界的含义；读清这一固定模型条件后，再检查交替调用是否仍是同一份模型。

任务二：每个冻结模型稳定，交替调用后是否仍稳定 ​

一维重球参数固定为$\alpha =1/9,\beta =4/9$，从$x_{-1}=x_0=1$启动。但梯度接口交替返回${\lambda }_k{x}_k$，偶数轮${\lambda }_k=1$、奇数轮${\lambda }_k=25$。两种二次目标都以0为唯一最小点。判断这条执行是否收敛，并与步长$1/25$的普通GD比较。

答案：需要检查两步状态乘积 ​

冻结任何一个曲率，重球特征根都是重根$2/3$或$-2/3$。交替执行却不是固定目标上的同一个二次递推。记状态为$(x_k,x_{k-1}{)}^{\mathsf{T}}$，两种矩阵为

$$P_{+}=\left(\begin{array}{cc}4/3& -4/9\\ 1& 0\end{array}\right),P_{-}=\left(\begin{array}{cc}-4/3& -4/9\\ 1& 0\end{array}\right).$$

两次更新先$P_{+}$、后$P_{-}$，所以实际乘积是

$$\begin{array}{}\text{(2)}& P=P_{-}{P}_{+}=\left(\begin{array}{cc}-20/9& 16/27\\ 4/3& -4/9\end{array}\right).\end{array}$$

它的迹为$-8/3$、行列式为$16/81$，特征多项式

$$p(\zeta )={\zeta }^2+\frac{8}{3}\zeta +\frac{16}{81}$$

在$-1$处为$-119/81<0$，在0处为正，远负端为正。因此有一个实根小于$-1$，另一个在$(-1,0)$；显式值为$-4/3\pm 8\sqrt{2}/9$。

初始状态$(1,1)$不是稳定特征线上的向量，因为$P(1,1)=(-44/27,8/9)$不与$(1,1)$成比例。两个根不同，特征分解中不稳定分量非零，故状态不收敛且无界。前四个点已可精确回放：

$$x_1=\frac{8}{9},x_2=-\frac{44}{27},x_3=-\frac{208}{81},x_4=\frac{112}{27}.$$

若改用GD，两个乘子分别是$24/25$与0，所以两次更新后到达零，之后保持零。这里比较的是题面这一个交替接口，并未证明GD总比重球快。

这份障碍属于切换模型：不能因为两种目标各自满足相同的强凸/光滑范围，就把固定Hessian的谱证明应用到它们交替产生的乘积。重球页另有同一个非二次固定目标的三周期反例；两种失败机制应分别记录。

任务三：残差保护还需要一次可行域检查 ​

给定盒域

$$D=[0,16]\times [0,4]\times [0,1],w=(16,4,1{)}^{\mathsf{T}},$$

以及只承诺在$D$内接收输入的接口

$$g(x)=Ax+b,A=\left(\begin{array}{ccc}1/4& 1& 0\\ 0& 1/4& 1\\ 0& 0& 1/4\end{array}\right),b=(8,2,3/4{)}^{\mathsf{T}}.$$

从0做一次Picard，再执行两历史Anderson。LS使用二范数，保护采用$\eta =3/5$及合适的加权无穷范数。交付候选、接受或拒绝的原因、真实执行的新点与点误差证书。

答案：先建立正确的范数合同 ​

$A$条目非负，$b=(I-A)w\ge 0$，所以$0\le x\le w$蕴含$0\le g(x)\le w$。映射保持$D$，固定点为$w$。

普通无穷范数给$\Vert A{\Vert }_{\mathrm{\infty }}=5/4$，不足以认证收缩。定义

$$\Vert x{\Vert }_w=max\{|x_1|/16,|x_2|/4,|x_3|\}.$$

在缩放坐标中，$\mathrm{diag}(w{)}^{-1}A\mathrm{diag}(w)$的三行绝对值和为$1/2,1/2,1/4$，所以$q=1/2$有效。不能只看到三个特征值都是$1/4$就把未说明范数的残差除以$1-1/4$。

两历史候选越过了盒的三个上界 ​

$x_0=0,x_1=b$，残差为$r_0=b,r_1=Ab=(4,5/4,3/16)$。令$d=r_0-r_1=(4,3/4,9/16)$。标量LS求导给

$$a_0=-\frac{⟨r_1,d⟩}{\Vert d{\Vert }^2}=-\frac{4363}{4321},a_1=\frac{8684}{4321}.$$

候选为

$$y=a_{0}g(x_0)+a_{1}g(x_1)=\frac{1}{4321}(69304,19497,4869).$$

它超过盒上界的量分别为$(168,2213,548)/4321$，全都为正。因此应在再次调用接口前拒绝。

这一步不能由残差检查代替。只为分析这个漏检风险，将仿射公式代数延拓到全空间，会得到

$$r(y)=(\frac{2087}{4321},-\frac{4447}{17284},-\frac{411}{4321}),\frac{\Vert r(y){\Vert }_w}{\Vert r(x_1){\Vert }_w}=\frac{6576}{21605}<\frac{3}{5}.$$

也就是说，仅检查残差会误放行一个越域状态。实际题目要求保持盒可行性，不能悄悄把接口定义域换成全空间。

回退仍有完整误差界 ​

真正接受的是Picard回退

$$x_2=g(x_1)=(12,13/4,15/16),r(x_2)=A^{2}b=(9/4,1/2,3/64).$$

加权残差为$9/64$，故

$$\Vert x_2-w{\Vert }_w\le \frac{9/64}{1-1/2}=\frac{9}{32}.$$

直接比较三个加权坐标，真实误差为$1/4$，确在上界内。此次拒绝在求值前发生，不支付越域候选的映射调用；回退新点的残差仍需一次合法求值。执行记录应保留“越域拒绝”，不能写成“LS失败”或“已经收敛”。

任务四：同一点与同一目标，两份表示会怎样改变更新 ​

原子依次为$(0,0),(1,0),(1,1),(0,1)$。在其正方形凸包上最小化

$$f(x)=\frac{1}{2}\Vert x-(1,1){\Vert }^2.$$

初始点固定为$(7/10,7/10)$，但分别保存两份权重

$$w^A=(1/10,1/5,1/2,1/5),w^B=(1/5,1/10,3/5,1/10).$$

使用$L=1$的短步长AFW，计算两种状态的第一步及gap，并判断能否把两份状态视为同一个算法输入。

答案：位置相同，允许撤回的质量不同 ​

两份权重都非负、和为一，并生成相同$x_0$。所以目标值$9/100$、梯度$(-3/10,-3/10)$、FW原子$(1,1)$、away原子$(0,0)$也相同。由式(1)型gap计算，

$$G_0=\frac{9}{50},A_0=\frac{21}{50}.$$

应选away，方向为$d=(7/10,7/10)$。未截短步长为$(21/50)/(49/50)=3/7$。但两种权重只分别允许

$${\gamma }_A=\frac{1/10}{9/10}=\frac{1}{9},{\gamma }_B=\frac{1/5}{4/5}=\frac{1}{4}.$$

因此都是drop，却产生不同点和支持权重：

$$\begin{array}{rlrl}{x}_A^{+}& =(7/9,7/9),& w_A^{+}& =(0,2/9,5/9,2/9),\\ x_B^{+}& =(7/8,7/8),& w_B^{+}& =(0,1/8,3/4,1/8).\end{array}$$

最小点$(1,1)$可行、最优值为零。重新算全域FW gap，得到

$$\begin{array}{ccc}& \text{状态A的一步}& \text{状态B的一步}\\ f& 4/81& 1/64\\ G& 8/81& 1/32\end{array}$$

两份后验证书都有效，这次B的值更低；这不构成任意目标上选择第二种表示更优的定理。改变表示还可能需要额外计算，不能把它当成免费步骤。

第一步的计数均为$N_1=0,D_1=1,s_0=4$，符合$D_1\le N_1+s_0-1$。若误用“good至少占一半”，会在这里立刻得到错误结论。存储一个$x$丢掉了away所需的权重状态；两种输入虽然位置相同，不能据此认为执行应相同。

交付检查 ​

四任务分别输出目标差与解集距离、两步状态乘积、域内真实残差、原子权重和全域gap。公共程序用有理算术回放矩阵、LS系数、步长上限与预算比较；它不把有限网格当成全局PL或稳定性证明。

报告实际查询与求解成本，保留失败原因，并标明使用的是固定目标、切换接口或带确定性误差的梯度。误差证书成立的对象与更新保存的状态一旦改变，就从对应定义重新检查。