最優(yōu)化：下降算法與線性搜索課件

最優(yōu)化主講：劉陶文課件制作：劉陶文唯楚有材於斯為盛學(xué)好最優(yōu)化，走遍天下都不怕最優(yōu)化主講：劉陶文課件制作：劉陶文唯楚有材1第二章無約束問題的下降算法與線性搜索第一節(jié)無約束問題的最優(yōu)性條件第二節(jié)下降算法的一般步驟第三節(jié)線性搜索第二章無約束問題的下降算法第一節(jié)無約束問題的最優(yōu)性條件2第一節(jié)無約束問題的最優(yōu)性條件第一節(jié)無約束問題的最優(yōu)性條件3最優(yōu)化：下降算法與線性搜索ppt課件4最優(yōu)化：下降算法與線性搜索ppt課件5注意這個條件不是充分的?！褡⒁膺@個條件不是充分的?！?最優(yōu)化：下降算法與線性搜索ppt課件7最優(yōu)化：下降算法與線性搜索ppt課件8最優(yōu)化：下降算法與線性搜索ppt課件9第二節(jié)下降算法的一般步驟第二節(jié)下降算法的一般步驟10最優(yōu)化：下降算法與線性搜索ppt課件11最優(yōu)化：下降算法與線性搜索ppt課件12第三節(jié)線性搜索第三節(jié)線性搜索13一、精確線性搜索

一、精確線性搜索14最優(yōu)化：下降算法與線性搜索ppt課件15最優(yōu)化：下降算法與線性搜索ppt課件161.單峰函數(shù)一、精確線性搜索——黃金分割法(0.618法)

定義：設(shè)是區(qū)間上的一元函數(shù)，是在上的極小點，且對任意的有（a）當(dāng)時，（b）當(dāng)則稱是單峰函數(shù)。.......1.單峰函數(shù)一、精確線性搜索——黃金分割法(0.61817性質(zhì)：通過計算區(qū)間內(nèi)兩個不同點的函數(shù)值，就可以確定一個包含極小點的子區(qū)間。定理設(shè)是區(qū)間上的單峰函數(shù)，是在上的極小點。任取點則有（1）如果，則（2）如果則.....性質(zhì)：通過計算區(qū)間內(nèi)兩個不同點的函數(shù)值，就可以確定一個包含極182.黃金分割法思想：通過選取試探點使包含極小點的區(qū)間按相同比例不斷縮短，直到區(qū)間長度小到一定程度，此時區(qū)間上各點的函數(shù)值均接近極小值。下面推導(dǎo)黃金分割法的計算公式2.黃金分割法思想：通過選取試探點使包含極小點的區(qū)間按相同19最優(yōu)化：下降算法與線性搜索ppt課件20通過確定的取值，使上一次迭代剩余的迭代點恰與下一次迭代的一個迭代點重合，從而減少算法的計算量。同理可得通過確定的取值，使上一次迭代剩余的迭代點恰與下同理可得21算法步驟：算法步驟：22黃金分割法的迭代效果：第k次后迭代后所得區(qū)間長度為初始區(qū)間長度的其它的試探點算法：Fibonacci算法(分?jǐn)?shù)法)。Fibonacci算法計算試探點的公式為：黃金分割法的迭代效果：第k次后迭代后所得區(qū)間長度為初始區(qū)間長23Fibonacci法為一維極小化最優(yōu)策略，而黃金分割法為近似最優(yōu),但后者簡單，因而較常用Fibonacci法為一維極小化最優(yōu)策略，而黃金分割法為近似24Fibonacci法是黃金分割法的推廣，黃金分割法是Fibonacci法的極限Fibonacci法是黃金分割法的推廣，黃金分割法25最優(yōu)化：下降算法與線性搜索ppt課件26二、非精確線性搜索—Armijo型線性搜索和Wolfe-Powell型線性搜索二、非精確線性搜索—Armijo型線性搜索27Oa可接受區(qū)間用進退法實現(xiàn)Armijo搜索：逐漸變小以滿足Armijo搜索條件Oa可接受區(qū)間用進退法實現(xiàn)Armijo搜索：逐漸變小以滿足28最優(yōu)化：下降算法與線性搜索ppt課件29最優(yōu)化：下降算法與線性搜索ppt課件30O可接受區(qū)間cO可接受區(qū)間c31為什么？為什么？32O可接受區(qū)間cO可接受區(qū)間c33最優(yōu)化：下降算法與線性搜索ppt課件34用進退法實現(xiàn)Wolfe-Powell搜索：逐漸增大以滿足搜索條件的第二個條件O可接受區(qū)間c逐漸變小以滿足搜索條件的第一個條件用進退法實現(xiàn)Wolfe-Powell搜索：逐漸增大以滿足搜索35最優(yōu)化：下降算法與線性搜索ppt課件36具體實現(xiàn)如下：滿足第一個條件不滿足第一個條件具體實現(xiàn)如下：滿足第一個條件不滿足第一個條件37作業(yè)題：用兩點插值法實現(xiàn)Wolfe-Powell搜索作業(yè)題：用兩點插值法實現(xiàn)Wolfe-Powell搜索38第三種重要的線性搜索：Goldstein搜索Oab第三種重要的線性搜索：Goldstein搜索Oab39最優(yōu)化：下降算法與線性搜索ppt課件40四、下降算法的全局收斂性和超線性收斂性四、下降算法的全局收斂性和超線性收斂性41如果(2.14)成立，我們認(rèn)為算法是全局收斂的.該定理表明:算法的收斂性與夾角有關(guān)如果(2.14)成立，我們認(rèn)為算法是全局收斂的.42最優(yōu)化：下降算法與線性搜索