最速下降法課件

4.1非線性規(guī)劃數(shù)學(xué)模型4.2凸函數(shù)和凸規(guī)劃4.3一維搜索4.4無約束優(yōu)化問題的解法第四章無約束最優(yōu)化問題

4.1非線性規(guī)劃數(shù)學(xué)模型第四章無約束最優(yōu)化問題

第四節(jié)無約束優(yōu)化問題的解法最速下降法Newton法擬Newton法共軛梯度法

第四章無約束最優(yōu)化問題

第四節(jié)無約束優(yōu)化問題的解法最速下降法第四章無約束最優(yōu)化問一.最速下降法收斂性問題的基本概念最速下降法的迭代原理最速下降法的迭代步驟最速下降法的舉例最速下降法的收斂結(jié)論

無約束問題4-4一.最速下降法收斂性問題的基本概念無約束問題4-41.收斂性問題的基本概念定義4-9若序列，對于，存在正整數(shù)當(dāng)時，有，即則稱收斂于，記為無約束問題4-41.收斂性問題的基本概念定義4-9若序列，對于定義4-101.收斂性問題的基本概念若收斂于，且滿足則p稱為收斂于的階。當(dāng)p=1時，稱為一階收斂；當(dāng)p=2時，稱為二階收斂；當(dāng)時，稱為超線性收斂；無約束問題4-4定義4-101.收斂性問題的基本概念若收斂于當(dāng)時，當(dāng)p=2

時，同階無窮小若收斂于，且滿足則p稱為收斂于的階。1.收斂性問題的基本概念定義4-10無約束問題4-4當(dāng)時，當(dāng)p=2時，當(dāng)時，當(dāng)p=1

時，同階無窮小若收斂于，且滿足則p稱為收斂于的階。1.收斂性問題的基本概念定義4-10無約束問題4-4當(dāng)時，當(dāng)p=1時，定義4-101.收斂性問題的基本概念若收斂于，且滿足則p稱為收斂于的階。當(dāng)p=1時，稱為一階收斂；當(dāng)p=2時，稱為二階收斂；當(dāng)時，稱為超線性收斂；無約束問題4-4最速下降法Newton法擬Newton法定義4-101.收斂性問題的基本概念若收斂于定義4-12若某算法對于任意正定二次目標(biāo)函數(shù),從任意初始點出發(fā),都能經(jīng)過有限次迭代達(dá)到其極小點,則該算法稱為具有二次終止性的算法或二次收斂算法.1.收斂性問題的基本概念結(jié)論：當(dāng)Q為正定陣時，稱f(X)為正定二次函數(shù)。正定二次函數(shù)有唯一全局極小點：無約束問題4-4定義4-12若某算法對于任意正定二次目標(biāo)函數(shù),從任意初一.最速下降法收斂性問題的基本概念最速下降法的迭代原理最速下降法的迭代步驟最速下降法的舉例最速下降法的收斂結(jié)論

無約束問題4-4一.最速下降法收斂性問題的基本概念無約束問題4-4是X(k)處函數(shù)值下降最快的方向。當(dāng)時，p(k)是f(X)在X(k)處的下降方向。函數(shù)f(X)在X(k)處的負(fù)梯度方向梯度的性質(zhì)：2.迭代原理證明：結(jié)論：一元函數(shù)泰勒公式：無約束問題4-4是X(k)處函數(shù)值下降最快的方向。當(dāng)2.迭代原理最優(yōu)步長無約束問題4-42.迭代原理最優(yōu)步長無約束問題4-4最速下降法迭代原理：一維搜索找極小點：1)確定[0,1],精度0.12)用0.618法得到

040.53184無約束問題4-4最速下降法迭代原理：一維搜索找極小點：1)確定[0最速下降法迭代原理：

無約束問題4-4最速下降法迭代原理：無約束問題4-42.迭代原理最優(yōu)步長最優(yōu)步長無約束問題4-42.迭代原理最優(yōu)步長最優(yōu)步長無約束問題4-4線性收斂2.迭代原理最優(yōu)步長最優(yōu)步長得到一個點列：可以證明：無約束問題4-4線性收斂2.迭代原理最優(yōu)步長最優(yōu)步長得到一個點列：可以證明：2.迭代原理證明：無約束問題4-42.迭代原理證明：無約束問題4-4一.最速下降法收斂性問題的基本概念最速下降法的迭代原理最速下降法的迭代步驟最速下降法的舉例最速下降法的收斂結(jié)論

無約束問題4-4一.最速下降法收斂性問題的基本概念無約束問題4-4無約束問題4-43.迭代步驟無約束問題4-43.迭代步驟3.迭代步驟注釋：(一階必要條件)10停機(jī)準(zhǔn)則：設(shè)連續(xù)(即f(X)連續(xù)可微)無約束問題4-43.迭代步驟注釋：(一階必要條件)10停機(jī)準(zhǔn)則：設(shè)注釋：3.迭代步驟一維搜索最優(yōu)解的梯度與搜索方向正交20結(jié)論：證明：無約束問題4-4注釋：3.迭代步驟一維搜索最優(yōu)解的梯度注釋：最速下降法的任何兩個相鄰搜索方向正交(垂直)3.迭代步驟30結(jié)論：無約束問題4-4注釋：最速下降法的任何兩個相鄰搜索方向正交(垂直)3.迭代步注釋：3.迭代步驟40將一維搜索用于正定二次函數(shù)：則可以得到的表達(dá)式：無約束問題4-4注釋：3.迭代步驟40將一維搜索用于正定二次函數(shù)：則可以得證明：3.迭代步驟40將一維搜索用于正定二次函數(shù)：則可以得到的表達(dá)式：注釋：該公式具有普遍性無約束問題4-4證明：3.迭代步驟40將一維搜索用于正定二次函數(shù)：則可以得注釋：3.迭代步驟40將一維搜索用于正定二次函數(shù)：則可以得到的表達(dá)式：無約束問題4-4注釋：3.迭代步驟40將一維搜索用于正定二次函數(shù)：則可以得注釋：3.迭代步驟50將最速下降法用于正定二次函數(shù)：則可以得到的表達(dá)式：無約束問題4-4注釋：3.迭代步驟50將最速下降法用于正定二次函數(shù)：則可以注釋：3.迭代步驟50最速下降法，Newton法，擬Newton法，共軛梯度法的區(qū)別就是搜索方向p(k)取得不同。無約束問題4-4注釋：3.迭代步驟50最速下降法，Newton法，擬New一.最速下降法收斂性問題的基本概念最速下降法的迭代原理最速下降法的迭代步驟最速下降法的舉例最速下降法的收斂結(jié)論

無約束問題4-4一.最速下降法收斂性問題的基本概念無約束問題4-44.舉例例4-10解：用最速下降法求的極小點，迭代兩次。無約束問題4-44.舉例例4-10解：用最速下降法求4.舉例例4-10解：用最速下降法求的極小點，迭代兩次。無約束問題4-44.舉例例4-10解：用最速下降法求解：1無約束問題4-4解：1無約束問題4-4解：1無約束問題4-4解：1無約束問題4-4解：2無約束問題4-4解：2無約束問題4-4解：3（太大）繼續(xù)迭代。最速下降法收斂速度很慢。注釋：無約束問題4-4解：3（太大）繼續(xù)迭代。最速下降法收斂速度很慢。注釋：無約束例4-10注釋：本例的計算結(jié)果如圖4-14(P156).迭代點在向極小點靠近的過程中形成一條鋸齒折線,這種現(xiàn)象稱為鋸齒現(xiàn)象.這是由于最速下降法的任何兩個相鄰搜索方向正交.因此,從直觀上可以看到,在遠(yuǎn)離極小點的地方,每次迭代可使目標(biāo)函數(shù)值有較大的下降,但越接近極小點,由于鋸齒現(xiàn)象,函數(shù)值下降速度顯著變慢.優(yōu)點：計算簡單,存儲量小.缺點：由于鋸齒現(xiàn)象,迭代后期收斂速度變慢.4.舉例用最速下降法求的極小點，迭代兩次。無約束問題4-4例4-10注釋：本例的計算結(jié)果如圖4-14(P156一.最速下降法收斂性問題的基本概念最速下降法的迭代原理最速下降法的迭代步驟最速下降法的舉例最速下降法的收斂結(jié)論

無約束問題4-4一.最速下降法收斂性問題的基本概念無約束問題4-45.最速下降法的收斂結(jié)論線性收斂最速下降法