最优条件描述解;算法则需要找到解。线搜索法由 xk 出发,选择方向 pk 和步长 αk>0,令 xk+1=xk+αkpk。方向应至少使目标值在起步时下降,但表现还取决于步长和函数的曲率。二次函数让这些区别可以用手算检验。
下降方向及步长
设 f 在 x 附近连续可微。若 ∇f(x)Tp<0,则称向量 p 为 f 在 x 处的下降方向。
由可微性,
f(x+αp)=f(x)+α∇f(x)Tp+o(α),
因此足够小的正 α 会降低函数值。梯度非零时,负梯度是下降方向,因为其内积为 −∥∇f(x)∥2。梯度为零则没有这个保证:x3 以零为驻点,但零不是局部极小点。沿下降方向走得太远也可能使函数值上升;f(x)=x2,x=1、p=−2、α=2 时,终点为 −3,函数值由 1 升至 9。
步长要多小,取决于梯度变化得多快。梯度的 Lipschitz 界把一阶展开变成对每个步长都成立的不等式。
若 ∇f 在 Rn 上以常数 L 满足 Lipschitz 条件,则对所有 x,s∈Rn,
f(x+s)≤f(x)+∇f(x)Ts+2L∥s∥2.
对 φ(t)=f(x+ts) 在 [0,1] 上用微积分基本定理,其导数为 ∇f(x+ts)Ts。减去线性项得
f(x+s)−f(x)−∇f(x)Ts=∫01[∇f(x+ts)−∇f(x)]Tsdt.由 Cauchy–Schwarz 不等式及 Lipschitz 界,被积函数不超过 ∥∇f(x+ts)−∇f(x)∥∥s∥≤Lt∥s∥2。因 ∫01Ltdt=L/2,所述不等式成立。
对固定梯度步 s=−α∇f(x),引理给出
f(x−α∇f(x))≤f(x)−α(1−2Lα)∥∇f(x)∥2,
所以当 0<α<2/L 且梯度非零时必严格下降。若 f 还有下界,沿固定步长梯度法把这些不等式相加,便得 k=0∑∞∥∇f(xk)∥2<∞,因此梯度趋于零。这个结论比迭代点收敛弱;对非凸目标而言,驻点也比最优点弱。分清这些结论可避免夸大下降计算的作用。
二次函数线搜索
设 f(x)=21xTAx−bTx,A 对称正定。唯一最小点满足 Ax=b;围绕 x∗=A−1b 配方得 f(x)−f(x∗)=21(x−x∗)TA(x−x∗)。沿非零方向 p,
f(x+αp)=f(x)+αgTp+21α2pTAp,g=Ax−b.
精确线搜索的最小步长为 α=−gTp/(pTAp),它恰在 p 是下降方向时为正。若 p=−g,则 α=(gTg)/(gTAg)。精确线搜索的最速下降法每次重新计算步长;对狭长的二次曲面,它可能曲折前进,因为欧氏梯度方向一般没有充分考虑不同方向的曲率。
相比之下,固定步长梯度法的误差满足 ek+1=(I−αA)ek。在 A 的标准正交特征向量基中,第 i 个分量乘以 1−αλi。所有分量严格收缩,当且仅当 0<α<2/λmax。这是固定步长法的结论,不是上面自适应精确线搜索的公式。
共轭方向
设 A 对称正定。若非零向量 p0,…,pn−1 对所有 i=j 满足 piTApj=0,则称它们为 A-共轭。
由正定性,它们线性无关:若 i∑cipi=0,左乘 pjTA 得 cjpjTApj=0,而 pjTApj>0 迫使 cj=0。因此 n 个这样的方向构成一组基。
概念视角几何
共轭就是能量内积下的正交
对对称正定的 A,⟨u,v⟩A=uTAv 是内积,而 A-共轭正是这个内积下的正交。等价地,把 A 分解为 A=RTR(R 可逆),并换元 z=Rx。目标差变成 21∥R(x−x∗)∥2,其等值集是球面;pi,pj 共轭当且仅当 Rpi 与 Rpj 欧氏正交。在这组坐标中,沿 Rpi 的精确搜索删去误差在该正交轴上的分量,其后沿其他正交轴的搜索不会使它重新出现。因此,在 A-内积下作 Gram–Schmidt 正交化,可把任何一组基化为共轭方向。
从任意点出发,依次沿每个方向精确最小化二次函数。下一定理记录这样做的结果,其证明不必换元,就把上述坐标图像说得精确。
设 f(x)=21xTAx−bTx,A∈Rn×n 对称正定,并设 p0,…,pn−1 为 A-共轭。由任意 x0 出发,以精确步长 αk=−gkTpk/(pkTApk)(其中 gk=Axk−b)作迭代 xk+1=xk+αkpk,则在精确运算下 xn=A−1b。
由 xk+1=xk+αkpk,梯度满足 gk+1=gk+αkApk。因 pkTApk>0,精确步长有定义,并给出
pkTgk+1=pkTgk+αkpkTApk=0.现固定 i,并设 j>i。由共轭性,piTgj+1=piTgj+αjpiTApj=piTgj。对 j 归纳,得对每个 k>i 都有 piTgk=0;特别地,对 i=0,…,n−1 均有 piTgn=0。这些方向构成一组基,故 gn=0,即 Axn=b。由配方式,xn 是唯一最小点。若较早的梯度已为零,之后每个精确步长都是零,所以至多 n 个非零步就到达最小点。
证明透视
精确性、共轭性与正定性分别在哪里用到
证明有两个独立的步骤。线搜索的精确性每步只用一次,用来建立正交关系 pkTgk+1=0。共轭性只用来说明其后的步骤不会破坏这些正交关系,因为沿 pj 的一步使 piTg 改变 αjpiTApj。正定性用了两次:它使每个精确步长有定义,又使 n 个方向构成一组基,论证正是靠这一点在 gn=0 处收尾。若去掉共轭性,第二步就明显失效。取 A=(2112)、b=0、x0=(1,1)T,先沿 e1 再沿 e2 精确搜索,得 x1=(−1/2,1)T、x2=(−1/2,1/4)T,而 g2=(−3/4,0)T=0。正交关系 e1Tg1=0 被第二步破坏,改变量恰为 α1e1TAe2=(−3/4)(1)。
例如 A=diag(1,2)、b=(1,2)T、x0=(0,0)T。坐标方向 p0=(1,0)T、p1=(0,1)T 是 A-共轭的。精确搜索得 x1=(1,0)T、x2=(1,1)T=A−1b。对非对角矩阵,欧氏正交未必等于共轭;相关内积是 uTAv,不是 uTv。
每步的目标下降量不必相同;如果当前梯度已与下一方向正交,该步可以为零。这个有限步结论假设精确运算、精确线搜索及完整的共轭方向组;舍入误差和不精确搜索会改变实际表现。预先构造所有方向可能代价很高;共轭梯度法利用对称二次结构,以短递推构造合适的方向。不能把这个有限步结论原封不动地用于非线性目标。
拟牛顿曲率更新
牛顿(Newton)法用 Hessian 变换梯度;拟牛顿法则从相邻的迭代点与梯度中累积曲率信息。令 sk=xk+1−xk、yk=∇f(xk+1)−∇f(xk),以 Hk 近似逆 Hessian。逆 BFGS 更新为
Hk+1=(I−ρskykT)Hk(I−ρykskT)+ρskskT,ρ=ykTsk1.
ykTsk=0 时公式没有定义。当曲率条件 ykTsk>0 成立时,更新保留线搜索法所需的两个性质。
命题 3.1.5
(BFGS 更新的割线方程与正定性)
若 Hk 对称正定且 ykTsk>0,则 Hk+1 对称正定,并满足割线方程 Hk+1yk=sk。
因 Hk 对称,(I−ρskykT)Hk(I−ρykskT) 的转置就是它本身,所以 Hk+1 对称。由 (I−ρykskT)yk=yk−ρyk(skTyk)=0 及 ρskskTyk=sk,割线方程成立。对任意 v,令 w=(I−ρykskT)v=v−ρ(skTv)yk,则
vTHk+1v=wTHkw+ρ(skTv)2≥0,因为 ρ>0。若和为零,两项都为零:skTv=0 给出 w=v,于是 vTHkv=0 迫使 v=0。
证明透视
曲率条件实际在哪里用到
对称性只用到 Hk 的对称性,割线方程只用到恒等式 (I−ρykskT)yk=0;除了使 ρ 有定义之外,两者都不需要 ykTsk>0。真正的关键是代换 w=(I−ρykskT)v,它把 vTHk+1v 拆成由 Hk 控制的部分与秩一项 ρ(skTv)2。曲率条件恰好在这里用上:它保证 ρ>0。正定性再通过分情形收尾:秩一项只在 skTv=0 时为零,而此时 w=v,于是由 Hk 的正定性接手。若 ρ<0,秩一项为负;本节后面的反例表明结论确实会失效。
所以在非驻点处 −Hk+1∇f 是下降方向。曲率条件不可缺少。正定近似及下降方向本身也不足以保证任意线搜索的全局收敛。
回溯与可计算的下降测试
下降方向保证足够小的步长可改善目标值,却没有直接指出步长。回溯法先取 αˉ>0,然后反复乘以固定因子 β∈(0,1),直至 Armijo 不等式成立:
f(x+αp)≤f(x)+cα∇f(x)Tp,0<c<1.
对下降方向,右边小于 f(x)。可微性保证这个搜索会终止:把一阶展开除以 α 并令 α↓0,极限斜率为 ∇f(x)Tp。因它为负,故严格小于 c∇f(x)Tp,所以所有足够小的正步长均满足不等式。这是单次线搜索的局部论证;整个序列收敛仍需对方向、光滑性和目标函数作额外假设。下降测试本身并不是通用的收敛定理。
例题:方向与曲率
例题 3.1.6
(非各向同性二次函数的精确最速下降)
取 f(x,y)=21(x2+4y2),起点 (1,1)。梯度 g=(1,4),负梯度方向为 (−1,−4)。精确步长为 α=(12+42)/(12+4⋅42)=17/65,新点为 (48/65,−3/65)。新梯度为 (48/65,−12/65),与旧梯度内积为零。一般情况下,这个正交性来自沿精确搜索线求导;但新梯度未必为零,也不表示已到达最小点。
令 f(x)=x2,由 x=1 沿 p=−2 出发,取 c=1/2、初始步长 1 和因子 β=1/2。当 α=1,左边 f(−1)=1,右边为 1+(1/2)(1)(−4)=−1,测试失败。当 α=1/2,左边 f(0)=0,右边 1−1=0,故接受此步。充分下降测试允许取等号。不同参数可接受不同步长,但下降方向的定义不变。
设 A=(2112)。标准基向量的欧氏内积为零,但 e1TAe2=1,所以并非 A-共轭。改取 p0=e1、p1=(−1/2,1)T,则 p0TAp1=2(−1/2)+1=0。两方向非零,由正定性构成一组基。不论线性项是什么,依次沿它们精确搜索,至多两步解出 Hessian 为 A 的二次问题。
割线方程与正定性
若 Hessian 在线段上连续,yk 等于沿该步的 Hessian 积分作用于 sk。因此它是沿线段平均得到的曲率观测,未必等于某个端点的 Hessian。逆割线方程 Hk+1yk=sk 要求更新后的逆近似重现这一个观测到的位移。一对向量不能决定整个矩阵,因此更新规则还需决定如何保留已有信息。
对任意对称正定 H,若 g=0,则 p=−Hg 满足 gTp=−gTHg<0。这说明保持正定性的重要性:下一方向在局部是下降方向。但 BFGS 的 sTy>0 条件必须由算法检查或保证。若目标函数的 Hessian 是固定的对称正定矩阵 A,则 y=As,非零步长有 sTy=sTAs>0。一般非凸函数的这个乘积却可以非正。
反例模式
没有曲率条件时套用 BFGS
断言:只要该步使 f 下降,正定 Hk 的逆 BFGS 更新就是正定的。取 f(x)=−x2、H0=1、x0=0、x1=1,于是 f 由 0 降至 −1。因 f′(x)=−2x,得 s=1、y=−2−0=−2,故 ρ=−1/2。一维时 1−ρsy=0,所以更新给出 H1=ρs2=−1/2,它确实满足 H1y=1=s。在 x1 处梯度为 −2,新方向 −H1g=−1 的斜率为 (−2)(−1)=2>0:它指向上坡。修正后的表述正是上面的命题,它假设 ykTsk>0;算法必须检查这个条件,条件不成立时跳过或修改更新。
解读数值结果
步长小可能源于线搜索或尺度选择不佳,未必代表接近解。对无约束问题,梯度小是有意义的一阶残差;但在约束边界上,最优点的梯度不一定为零,应使用合适的约束残差。即使是精确的驻点也可能是鞍点。解读输出时应记录目标、约束、停止准则,以及声称收敛所依据的假设,把计算结果联系回前面的最优性证书。
条件数与二次函数的启示
对对称正定二次函数,令 ek=xk−x∗,并以正交矩阵对角化 A=QΛQT。目标差为 21ekTAek,梯度则为 Aek。不同特征方向即使有相同的欧氏距离,也可能有不同的目标差。若 0<λmin≤λmax,则
2λmin∥ek∥2≤f(xk)−f(x∗)≤2λmax∥ek∥2.
比值 κ=λmax/λmin 称为谱条件数。比值大表示不同特征方向的曲率差别大。固定步长若小到足以控制最大特征值,最小特征值方向的分量可能衰减得很慢。精确线搜索虽调整步长,在狭长的等高线上仍可能交替转向。这只是几何解释,并非说条件数大的问题都需要相同的迭代次数。
若已知极端特征值,可选固定正步长使最坏的绝对收缩因子最小。令两端的大小相等,1−αλmin=−(1−αλmax),得 α=2/(λmin+λmax)。因 1−αλ 关于 λ 是仿射的,中间特征值的因子位于两端之间。最坏因子为 (κ−1)/(κ+1),小于一,但 κ 增大时趋近一。这是固定步长误差收缩的计算,并非取决于当前梯度的精确线搜索公式。
预条件化改变几何而不改变最优点。若 M 对称正定,则 g=0 时 p=−M−1g 是下降方向,因 gTp=−gTM−1g<0。若 M 近似 A,用 M 解线性方程组可减少有效曲率的差异,但必须计入求解成本。正定性对上述证明不可缺少;任意可逆矩阵未必产生下降方向。
例如 A=diag(1,4) 且 M=A,预条件方向是 −A−1g=−e,单位步长直接到达此二次问题的最小点。这个理想选择本身已需要用 A 解方程组,即原来的任务,所以它说明预条件化的目标,并非通用的廉价方法。拟牛顿法则从观测到的步长中获取相关曲率信息,仍须遵守上文的割线与正定性条件。
常见错误
初学这些方法时有三种错误经常出现;BFGS 的曲率条件已在上文讨论。
下降方向只保证足够小的正步长使目标下降。对 f(x)=x2,在 x=1 取 p=−2,步长 α=2 使 f 由 1 升至 9。精确搜索、小于 2/L 的固定步长或 Armijo 回溯等步长规则是方法的一部分,不是可有可无的补充。
精确线搜索与固定步长梯度法是不同算法。对 f(x,y)=21(x2+4y2),在 (1,1) 处精确步长是 17/65,并取决于当前梯度;而 0<α<1/2 是使每个误差分量收缩的固定步长范围。两个公式互不决定,其收敛结论也不可互换。同样,欧氏正交一般不等于 A-共轭,第三个例题已说明这一点。
梯度小只表示近似为驻点。函数 x3 在零处导数为零,但零不是局部极小点。需要凸性等额外结构,才能把驻点与最优联系起来。
总结
线搜索决定沿某方向前进多远;曲率影响这一选择对目标的作用。在精确运算下,共轭方向保留先前的二次函数最小化结果;BFGS 则由割线对累积局部曲率信息。实际结论都依赖所列的假设及停止准则。
练习
快速检查
(对 f(x)=x2,在 x=1 沿 p=−2 求精确步长。)
把 f 写成 21Ax2−bx,再用精确线搜索的最小步长公式。
解答 · 答案
此处 A=2、b=0、g=2。精确步长为 α=−gp/(pAp)=−(2)(−2)/(2⋅4)=1/2,新点为 1+21(−2)=0,即最小点。
快速检查
(若 A=diag(1,4),求两个误差分量都严格收缩的正固定步长范围。)
每个特征分量乘以 1−αλi。
解答
两个因子为 1−α 和 1−4α。条件 ∣1−α∣<1 即 0<α<2,而 ∣1−4α∣<1 即 0<α<1/2。两者同时成立当且仅当 0<α<1/2,即 0<α<2/λmax。
快速检查
(一维情形中,H0=1、s=2、y=4。用逆 BFGS 更新求 H1,并检查割线方程。)
解答 · 答案
ρ=1/(sy)=1/8,两个标量因子 1−ρsy 均为零,所以 H1=ρs2=4/8=1/2,且 H1y=2=s。一维时,不论 H0 是什么,更新总是给出 s/y。