Lecture9-使用導(dǎo)數(shù)的最優(yōu)化方法分析課件

1、最優(yōu)化方法 Optimization第九章 使用導(dǎo)數(shù)的最優(yōu)化方法第1頁，共54頁。無約束優(yōu)化問題算法 最速下降法 牛頓法 共軛梯度法 擬牛頓法 信賴域法 最小二乘法第2頁，共54頁。最速下降法最速下降方向取搜索方向:第3頁，共54頁。步驟:帶精確線搜索的最速下降法第4頁，共54頁。例:第一次迭代解:第5頁，共54頁。第二次迭代最速下降法的收斂性第6頁，共54頁。二次函數(shù)情形第7頁，共54頁。最速下降法表示為第8頁，共54頁。Kantorovich不等式第9頁，共54頁。定理（最速下降法二次情形）第10頁，共54頁。第11頁，共54頁。第12頁，共54頁。定理：條件數(shù)非二次情形第13頁，共54頁

2、。結(jié)論：在相繼兩次迭代中,梯度方向互相正交.第14頁，共54頁。Ex 陳寶林書 P3281. 第15頁，共54頁?；舅枷胗靡粋€(gè)二次函數(shù)去近似目標(biāo)函數(shù)f(x),然后精確地求出這個(gè)二次函數(shù)的極小點(diǎn).牛頓法第16頁，共54頁。牛頓方向第17頁，共54頁。定理：第18頁，共54頁。第19頁，共54頁。牛頓法計(jì)算步驟:第20頁，共54頁。第21頁，共54頁。第22頁，共54頁。第23頁，共54頁。第24頁，共54頁。用Newton法求解無約束問題會出現(xiàn)以下情形：（1）收斂到極小點(diǎn)（2）收斂到鞍點(diǎn)（3）Hesse矩陣不可逆，無法迭代下去第25頁，共54頁。優(yōu)點(diǎn):（1）Newton法產(chǎn)生的點(diǎn)列x(k)若收

3、斂，則收斂速度快-具有至少二階收斂速率。(2) Newton法具有二次終止性第26頁，共54頁。缺點(diǎn):（1）可能會出現(xiàn)在某步迭代時(shí)，目標(biāo)函數(shù)值上升.（2）當(dāng)初始點(diǎn)遠(yuǎn)離極小點(diǎn)時(shí)，牛頓法產(chǎn)生的點(diǎn)列可能不收斂，或者收斂到鞍點(diǎn)，或者Hesse矩陣不可逆，無法計(jì)算.（3）需要計(jì)算Hesse矩陣，計(jì)算量大.第27頁，共54頁。步驟:阻尼牛頓法第28頁，共54頁。修正牛頓法第29頁，共54頁。Ex 陳寶林書 P328 2 并用牛頓法從給定點(diǎn)處出發(fā)求解極小點(diǎn)第30頁，共54頁。共軛方向法共軛方向定義：第31頁，共54頁。例：第32頁，共54頁。定理1證明：第33頁，共54頁。定理2：第34頁，共54頁。證明：

4、第35頁，共54頁。定理3：第36頁，共54頁。第37頁，共54頁。第38頁，共54頁。共軛梯度法(FR法)記號： 在共軛梯度法中，初始點(diǎn)處的搜索方向取為該點(diǎn)的負(fù)梯度方向，即取 而以下各共軛方向d(k)由第k次迭代點(diǎn)x(k)處的負(fù)梯度-gk與已經(jīng)得到的共軛向量d(k-1)的線性組合來確定。第39頁，共54頁。第40頁，共54頁。第41頁，共54頁。以此類推，得第42頁，共54頁。第43頁，共54頁。第44頁，共54頁。第45頁，共54頁。第46頁，共54頁。第47頁，共54頁。定理:第48頁，共54頁。FR共軛梯度法(二次凸函數(shù))第49頁，共54頁。例:第50頁，共54頁。一般函數(shù)的共軛梯度法第51頁，共54頁。迭代的延續(xù)方法：第52頁，共54頁。FR共軛梯度法（一般可微函數(shù)）第53頁，共54頁。Ex 陳寶林書 P 330 14 （1）Homework1.