最優條件描述解;算法則需要找到解。線搜索法由 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,所以所有足夠小的正步長均滿足不等式。這是單次線搜索的局部論證;整個序列收斂仍需對方向、光滑性和目標函數作額外假設。下降測試本身並不是通用收斂定理。
例題:方向與曲率
取 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。