資源描述：
《共軛方向法和共軛梯度法》由會員上傳分享，免費在線閱讀，更多相關內容在行業(yè)資料-天天文庫。
1、《最優(yōu)化理論與方法》邵建峰第三章無約束最優(yōu)化的梯度方法信息與計算科學系邵建峰邵建峰本章內容：?3.1無約束最優(yōu)化問題的最優(yōu)性條件?3.2最速下降法?3.3Newton法?3.4共軛方向法和共軛梯度法?3.5擬Newton法?3.6最小二乘問題邵建峰3.4共軛方向法和共軛梯度法信息與計算科學系邵建峰邵建峰本節(jié)內容：?一.共軛方向法?二．共軛梯度法一.共軛方向法(針對二次函數)1.最速下降法minf(x)(?f(x,x,?,x))12ns.t.x?D?Rn*?求使?f(x)?0的點x??f(x)kxk?1*·xxk最速下降法是：若已知目標函數f(x)的梯度g
2、(x)(??f(x))則選取初始搜索方向與每個當前點處的搜索方向為pk??gk一.共軛方向法(針對二次函數)2.牛頓法??f(x)?1kpk??Gx(k)gx()kTT?1gx()p???gx()Gx()gx()0·kkkkk*xx??xpx·k?1kkk在x點處，用二次函數來近似原函數f(x)，即kT1Tf(x)?Q(x)?f(xk)?g(xk)?(x?xk)?(x?xk)G(xk)?(x?xk)2尋找近似二次函數的“中心”點，即令0??Q(x)?g(x)?G(x)?(x?x)kkkx?x?G(x)?1g(x)?k?1kkk1、對n元二次函數1TTfx
3、()?xQxbxC??2n??Q是n階正定陣，*1?其中x,bR,cR,x??Qb.x?x?t?p1000p0p1*x0??f(x)1x1?ls(x0,p0)（ls—Linearsearch）即f(x)?f(x?t?p)?minf(x?t?p)100000t?0*現(xiàn)在令p10??xx,下面:對n元二次函數1TTfx()?xQxbxC??2研究方向p與p有什么關系?10x?x?t?p1000p0p1*x0??f(x)1因為*x?x1?t1?p1?argminf(x1?t?p1)(1)t?0又g(x)??f(x)?Qx?b***(2)g(x)??f(x)?Q
4、x?b?0*x?x1?t1?p1?argminf(x1?t?p1)(1)t?0***(2)g(x)??f(x)?Qx?b?0（1）式代入（2）式，得Q(x?t?p)?b?0111即?f(x)?tQp?0(3)111用p0與（3）式兩邊做內積，有TpQp?0(*)01我們稱滿足（*）式的方向p,p是Q共軛的。01‘共軛’是‘正交’概念的推廣。定義1(Q-共軛)設Q為n階正定矩陣，p1,p2,···,pk為n維非零向量組，如果piTQpj=0(i≠j)則稱向量組p1,p2,···,pk關于Q-共扼.在空間Rn上，重新定義內積與范數:T12//T12?xy,,
5、??QxQy
6、
7、x
8、
9、Q??xx,?Q?(xQx)實際上，在新的內積意義下，Q-共扼即為正交.性質1(線性無關）設Q是已知的n階正定矩陣，則Q共軛的向量組pp0,1,,pm?1必定是線性無關的.定義2(線性流型）設p1,p2,···,pm-1是m個線性無關的向量，xR?n.則稱集合0k??L???xx
10、,?x0????ipii?R??i?1是由點x和線性無關向量組p,p,···,p所產生的一個線性流型，012m-1m叫做流形的維數。顯然，在三維空間中，一維流形是直線，二維流形是平面，而三維流形是整個空間。性質2(共軛化)設Q是已知的n階正定矩陣，任何線性
11、無關的向量組pp0,1,,pm?1必定可以Q共軛化。即若令q?p00TqQp01q?p?q11T0qQq00TTqQpqQp0212q?p?q?q22T0T1qQqqQq0011……………TTTqQpqQpqQp0m?11m?11m?1q?p?q?q??qm?1m?1T0T1Tm?2qQqqQqqQq0011m?2m?2pp,,,p則向量組01m?1是Q共軛的。共扼方向法的思路：1TTminfx()()?xQxbxc??2n??Q是n階正定陣，*1?其中x,bR,cR,x??Qb.1TT則fx()?xQxbxc??21??11T1T?1?(x?QbQx)
12、(?Qb)?c?bQb221?121T?1?
13、
14、x?Qb
15、
16、?c?bQbQ22?12*2因此原問題等價于：min
17、
18、x?Qb
19、
20、Q??
21、
22、xx
23、
24、Q在Rn上，按照上面定義的內積給出一組Q-共扼的基底p1,p2,···,pn，則p1,p2,···,pn線性無關，且?pp,??0,(i?j)ijQ設問題的最優(yōu)解x*=-Q-1b在這組基底下的表示為x*=u1p1+u2p2+···+unpn并任取初始點x0=s1p1+s2p2+···+snpn.先在方向p1上進行一維搜索，即求解問題x*=up+up+···+up1122nn因為x0=sp+sp+···+sp11
25、22nnx=x0+a1p1a1∈R*2min
26、
27、
28、
29、xx?Q=(s1+a1)p1
