漆黑的冷空中有你,
惺忪的眼睛中有你,
心底的记忆中有你,
你留在我的脑海中,
一直这么挥之不去。
无论哪时哪刻,
心中都想着你的笑,
想着你到我侧相拥,
I can dream about you.
——畅宝宝的傻逼哥哥
在早期的最优化中,对于两变量函数来说,用最速下降法得出的解轨迹表征出zig-zag模式。对于某些性质较好的函数,相邻的解差不多组成两条线,他们在最小值的邻域内相交,如图1所示,因此比较明显的策略是连接初始点与第二个解,沿着这个方向执行最速下降法。对于凸二次函数,在
n次迭代内就能收敛,这个方法也被称为parallel tangent法或着partan法,这是因为在二次函数的情况下,所得轮廓的正切属性。
图1
Partan算法如图2所示,假设初始点为
x0,并利用两次最速下降法得到点
x1,y1,然后沿着
y1−x1方向进行线搜索得到点
x2,这就完成了第一次迭代。对于第二次迭代,对点
x2执行最速下降得到点
y2,沿着
y2−x1方向得到点
x3,一直重复此过程。从效果上看,图2中的点
y1,y2,…是通过最速下降法得到的而
x2,x3,…是沿着方向
y2−x1,y3−x2,…方向用线搜索得到的。
图2
对于凸二次问题,连接
x1,x2,…,xk的线组成一个共轭梯度方向集,可以通过以下方法来证明:先假设
d0,d1,…,dk−1是共轭梯度方向集,然后说明
dk是
d0,d1,…,dk−1的共轭梯度方向。
考虑图3所示的步骤,注意到
gTkdi=0for 0≤i<k(1)
根据之前共轭梯度的结论可知点xk−1处的梯度可以写成
gk−1=∑i=0k−1aidi
其中ai,i=0,1,…,k−1为常数,所以
gTkgk−1=gTk(b+Hxk−1)=∑i=0k−1aigTkdi=0(2)
或者
gTkb=−gTkHxk−1(3)
因为yk是点xk用最速下降法得到的,所以我们有
yk−xk=−gk
另外
−g(yk)Tgk=gTk(b+Hyk)=0
或者
gTkb=−gTkHyk(4)
因此,根据等式3与4可得
gTkH(yk−xk−1)=0(5)
图3
因为
yk−xk−1=β(xk−1−xk−1)
其中β是常数,等式5可以写成
gTkH(xk+1−xk−1)=0
或者
gTkHxk+1=gTkHxk−1(6)
接下来我们能够写成
gTkHxk+1=gTkHxk−1(7)
那么根据
gTkgk+1=gTk(b+Hxk+1)(8)
以及等式2,等式6与等式9可得
gTkgk+1=gTk(b+Hxk−1)=gTkgk−1=0(9)
点xk+1是在xk+1−yk方向上使用线搜索得到的,因此
gTk+1(xk+1−yk)=0(10)
从图3可以看出
xk+1=xk+dk(11)
且
yk=xk−αgk(12)
其中α是最小化f(xk−αgk)的α值,因此等式9,10与11得到
gTk+1(dk+αkgk)=0
或者
gTk+1dk+αkgTkgk+1=0(13)
接下来根据等式8与12可得
gTk+1dk=0
再结合等式1与13可得
gTk+1di=0for 0≤i<k+1