資源描述：
《最速下降法課件.ppt》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。
1、4.1非線性規(guī)劃數(shù)學(xué)模型4.2凸函數(shù)和凸規(guī)劃4.3一維搜索4.4無(wú)約束優(yōu)化問(wèn)題的解法第四章無(wú)約束最優(yōu)化問(wèn)題第四節(jié)無(wú)約束優(yōu)化問(wèn)題的解法最速下降法Newton法擬Newton法共軛梯度法第四章無(wú)約束最優(yōu)化問(wèn)題一.最速下降法收斂性問(wèn)題的基本概念最速下降法的迭代原理最速下降法的迭代步驟最速下降法的舉例最速下降法的收斂結(jié)論無(wú)約束問(wèn)題4-41.收斂性問(wèn)題的基本概念定義4-9若序列，對(duì)于，存在正整數(shù)當(dāng)時(shí)，有，即則稱收斂于，記為無(wú)約束問(wèn)題4-4定義4-101.收斂性問(wèn)題的基本概念若收斂于，且滿足則p稱為收斂于的階。當(dāng)p=1時(shí)，稱為一階收斂；當(dāng)p=2時(shí)，稱為二階收斂；當(dāng)時(shí)，稱為超線性收斂；無(wú)約束問(wèn)題
2、4-4當(dāng)時(shí)，當(dāng)p=2時(shí)，同階無(wú)窮小若收斂于，且滿足則p稱為收斂于的階。1.收斂性問(wèn)題的基本概念定義4-10無(wú)約束問(wèn)題4-4當(dāng)時(shí)，當(dāng)p=1時(shí)，同階無(wú)窮小若收斂于，且滿足則p稱為收斂于的階。1.收斂性問(wèn)題的基本概念定義4-10無(wú)約束問(wèn)題4-4定義4-101.收斂性問(wèn)題的基本概念若收斂于，且滿足則p稱為收斂于的階。當(dāng)p=1時(shí)，稱為一階收斂；當(dāng)p=2時(shí)，稱為二階收斂；當(dāng)時(shí)，稱為超線性收斂；無(wú)約束問(wèn)題4-4最速下降法Newton法擬Newton法定義4-12若某算法對(duì)于任意正定二次目標(biāo)函數(shù),從任意初始點(diǎn)出發(fā),都能經(jīng)過(guò)有限次迭代達(dá)到其極小點(diǎn),則該算法稱為具有二次終止性的算法或二次收斂算法.1.
3、收斂性問(wèn)題的基本概念結(jié)論：當(dāng)Q為正定陣時(shí)，稱f(X)為正定二次函數(shù)。正定二次函數(shù)有唯一全局極小點(diǎn)：無(wú)約束問(wèn)題4-4一.最速下降法收斂性問(wèn)題的基本概念最速下降法的迭代原理最速下降法的迭代步驟最速下降法的舉例最速下降法的收斂結(jié)論無(wú)約束問(wèn)題4-4是X(k)處函數(shù)值下降最快的方向。當(dāng)時(shí)，p(k)是f(X)在X(k)處的下降方向。函數(shù)f(X)在X(k)處的負(fù)梯度方向梯度的性質(zhì)：2.迭代原理證明：結(jié)論：一元函數(shù)泰勒公式：無(wú)約束問(wèn)題4-42.迭代原理最優(yōu)步長(zhǎng)無(wú)約束問(wèn)題4-4最速下降法迭代原理：一維搜索找極小點(diǎn)：1)確定[0,1],精度0.12)用0.618法得到040.53184無(wú)約束問(wèn)題4-4
4、最速下降法迭代原理：無(wú)約束問(wèn)題4-42.迭代原理最優(yōu)步長(zhǎng)最優(yōu)步長(zhǎng)無(wú)約束問(wèn)題4-4線性收斂2.迭代原理最優(yōu)步長(zhǎng)最優(yōu)步長(zhǎng)得到一個(gè)點(diǎn)列：可以證明：無(wú)約束問(wèn)題4-42.迭代原理證明：無(wú)約束問(wèn)題4-4一.最速下降法收斂性問(wèn)題的基本概念最速下降法的迭代原理最速下降法的迭代步驟最速下降法的舉例最速下降法的收斂結(jié)論無(wú)約束問(wèn)題4-4無(wú)約束問(wèn)題4-43.迭代步驟3.迭代步驟注釋：(一階必要條件)10停機(jī)準(zhǔn)則：設(shè)連續(xù)(即f(X)連續(xù)可微)無(wú)約束問(wèn)題4-4注釋：3.迭代步驟一維搜索最優(yōu)解的梯度與搜索方向正交20結(jié)論：證明：無(wú)約束問(wèn)題4-4注釋：最速下降法的任何兩個(gè)相鄰搜索方向正交(垂直)3.迭代步驟30結(jié)
5、論：無(wú)約束問(wèn)題4-4注釋：3.迭代步驟40將一維搜索用于正定二次函數(shù)：則可以得到的表達(dá)式：無(wú)約束問(wèn)題4-4證明：3.迭代步驟40將一維搜索用于正定二次函數(shù)：則可以得到的表達(dá)式：注釋：該公式具有普遍性無(wú)約束問(wèn)題4-4注釋：3.迭代步驟40將一維搜索用于正定二次函數(shù)：則可以得到的表達(dá)式：無(wú)約束問(wèn)題4-4注釋：3.迭代步驟50將最速下降法用于正定二次函數(shù)：則可以得到的表達(dá)式：無(wú)約束問(wèn)題4-4注釋：3.迭代步驟50最速下降法，Newton法，擬Newton法，共軛梯度法的區(qū)別就是搜索方向p(k)取得不同。無(wú)約束問(wèn)題4-4一.最速下降法收斂性問(wèn)題的基本概念最速下降法的迭代原理最速下降法的迭代
6、步驟最速下降法的舉例最速下降法的收斂結(jié)論無(wú)約束問(wèn)題4-44.舉例例4-10解：用最速下降法求的極小點(diǎn)，迭代兩次。無(wú)約束問(wèn)題4-44.舉例例4-10解：用最速下降法求的極小點(diǎn)，迭代兩次。無(wú)約束問(wèn)題4-4解：1無(wú)約束問(wèn)題4-4解：1無(wú)約束問(wèn)題4-4解：2無(wú)約束問(wèn)題4-4解：3（太大）繼續(xù)迭代。最速下降法收斂速度很慢。注釋：無(wú)約束問(wèn)題4-4例4-10注釋：本例的計(jì)算結(jié)果如圖4-14(P156).迭代點(diǎn)在向極小點(diǎn)靠近的過(guò)程中形成一條鋸齒折線,這種現(xiàn)象稱為鋸齒現(xiàn)象.這是由于最速下降法的任何兩個(gè)相鄰搜索方向正交.因此,從直觀上可以看到,在遠(yuǎn)離極小點(diǎn)的地方,每次迭代可使目標(biāo)函數(shù)值有較大的下降,但
7、越接近極小點(diǎn),由于鋸齒現(xiàn)象,函數(shù)值下降速度顯著變慢.優(yōu)點(diǎn)：計(jì)算簡(jiǎn)單,存儲(chǔ)量小.缺點(diǎn)：由于鋸齒現(xiàn)象,迭代后期收斂速度變慢.4.舉例用最速下降法求的極小點(diǎn)，迭代兩次。無(wú)約束問(wèn)題4-4一.最速下降法收斂性問(wèn)題的基本概念最速下降法的迭代原理最速下降法的迭代步驟最速下降法的舉例最速下降法的收斂結(jié)論無(wú)約束問(wèn)題4-45.最速下降法的收斂結(jié)論線性收斂最速下降法所產(chǎn)生的迭代點(diǎn)列是的局部最優(yōu)解無(wú)約束問(wèn)題4-4一.最速下降法收斂性問(wèn)題的基本概念最速下降法的迭代原理最速下降法的迭代步驟最速下
