直接搜索數(shù)值解法演示文稿

直接搜索數(shù)值解法演示文稿目前一頁\總數(shù)三十五頁\編于七點優(yōu)選直接搜索數(shù)值解法目前二頁\總數(shù)三十五頁\編于七點1緒論無約束最優(yōu)化問題的經(jīng)典解法中，都必須求其函數(shù)的導數(shù)。但是很多實際問題往往難以求出目標函數(shù)f(X)關于X的偏導數(shù)。這時就放棄求偏導的方法，而直接從分析目標函數(shù)f(X)的特征、信息出發(fā)，構造一種逐次使目標函數(shù)值下降（或上升）的搜索方法。目前三頁\總數(shù)三十五頁\編于七點1緒論

搜索方法是迭代算法中的一種。它由搜索方向S(k)和步長因子αk構成每一次迭代的修正量，為決定其算法的好壞的重要因素。各種算法的區(qū)別在于確定S(k)與αk的不同，尤其是搜索方向。目前四頁\總數(shù)三十五頁\編于七點1緒論搜索方法主要分成兩類：（1）直接搜索法——只需要進行函數(shù)值的計算與比較來確定最優(yōu)化的方向和步長。（2）間接搜索法——需要利用函數(shù)的一階、二階導數(shù)及偏導數(shù)矩陣來確定最優(yōu)方向和最優(yōu)步長。目前五頁\總數(shù)三十五頁\編于七點2進退法進退法的基本思想是，每次搜索都要改變搜索的步長。對于求極小值問題，如果在第K次迭代沿某方向搜索成功，則函數(shù)值一定下降，下一步仍可按該方向搜索，而且可大步向前搜索；如果在第K次迭代沿某方向搜索失敗，則函數(shù)值上升，應退回原地，下一步便按其相反方向，即向后退小步搜索。目前六頁\總數(shù)三十五頁\編于七點2進退法進退法可用來搜索最優(yōu)點和搜索最優(yōu)區(qū)間。搜索最優(yōu)點的具體過程：從某點x0出發(fā)，步長取為h,比較兩點函數(shù)值。（1）若f(x0)>f(x0+h)，則搜索成功；于是，下一步取步長為2h;若第k步的步長為nh,并搜索成功，那么，第K＋1步的步長就是2nh。（2）若f(x0)≤f(x0+h)，則搜索失??；于是，退回到x0之后，再后退并按(nh)/4或(nh)/3步長搜索，直到步長小于ε，停止搜索。目前七頁\總數(shù)三十五頁\編于七點2進退法進退法的程序框圖目前八頁\總數(shù)三十五頁\編于七點3黃金分割法3.1黃金分割法的特點和步驟黃金分割法的基本思路：通過不斷縮小單峰區(qū)間的長度來搜索目標函數(shù)的極小點，且是按可行域全長的黃金點——0.618選取兩個新點，更新區(qū)間，這種尋優(yōu)方法比任意取兩點的消去法效果更好，尋優(yōu)區(qū)間縮短的速度更快。目前九頁\總數(shù)三十五頁\編于七點3黃金分割法目前十頁\總數(shù)三十五頁\編于七點3黃金分割法黃金分割法有如下特點：（1）每次選取的λ1、λ2兩點為對稱點；（2）舍去兩端任一段后，保留下來的λ在新區(qū)間仍占有著相應的位置；（3）舍去兩端任一段，新區(qū)間的長度為原區(qū)間長度的0.618倍。（4）迭代n次以后，區(qū)間長度成為0.618nL.目前十一頁\總數(shù)三十五頁\編于七點3黃金分割法目前十二頁\總數(shù)三十五頁\編于七點4二次插值法目前十三頁\總數(shù)三十五頁\編于七點4二次插值法例：求f(x)=8x2-2x+7的極小點解：在尋優(yōu)區(qū)間[0,2]中間取點1，即取xa=0,xb=1,xc=2則有：f(xa)=7,f(xb)=13,f(xc)=35按極小點公式有：驗證：由df(x)/dx=0

有16x-2=0,x*=0.125目前十四頁\總數(shù)三十五頁\編于七點4二次插值法目前十五頁\總數(shù)三十五頁\編于七點4二次插值法例：求minf(x)=ex-5x解：1)先按從求函數(shù)導數(shù)獲得極值的方法有：可得：λ*=0.6092)再按二次插值法求解取λa=0,λb=1,λc=2則有：f(0)=e-5=-2.282,f(1)=e2-10=-2.611,f(2)=5.086由此可計算出λ0=0.531而原函數(shù)的λ*=0.609，現(xiàn)用二次插值法一步迭代的結果為0.531，精度不高，還有11％的誤差，故還應繼續(xù)進行迭代目前十六頁\總數(shù)三十五頁\編于七點5有理插值法在某些情況下，當目標函數(shù)連續(xù)可導、存在極值點時，用0.618法迭代計算量大，而用二次、三次多項式去插值也不太合適，這時可采用有理插值法。所謂有理插值法，就是用一個有理函數(shù)（有限連分數(shù)形式）去擬和原目標函數(shù)，從而找出函數(shù)的駐點、導數(shù)的近似值的一種最優(yōu)化的計算方法。目前十七頁\總數(shù)三十五頁\編于七點5有理插值法有限連分數(shù)的基本概念：設a0為實數(shù)，a1,a2,…,an均為大于、等于1的實數(shù)，把分數(shù)：成為有限連分數(shù)。由于這種寫法很占篇幅，故常用符號：表示。目前十八頁\總數(shù)三十五頁\編于七點5有理插值法例如：目前十九頁\總數(shù)三十五頁\編于七點5有理插值法（1）計算有理插值函數(shù)的公式目前二十頁\總數(shù)三十五頁\編于七點5有理插值法則有：由這個迭代形式，要把xi與ai計算出來目前二十一頁\總數(shù)三十五頁\編于七點5有理插值法（2）計算駐點f’(x)=0的公式公式：目前二十二頁\總數(shù)三十五頁\編于七點5有理插值法（5）若目前二十三頁\總數(shù)三十五頁\編于七點6坐標輪換法坐標輪換法是一種最古老的多維搜索轉一維搜索的算法。它的迭代過程是沿不同的坐標方向輪流地進行搜索。設初始點為X0,先只改變一個變量，保持其它變量為常數(shù)，進行一維尋優(yōu)，得到第一個最優(yōu)點X1；再換一個變量，同樣進行一維搜索，得到第二個最優(yōu)點X2。如此繼續(xù)下去，逐步逼近。像“爬山”一樣，一步一步地爬上頂峰。目前二十四頁\總數(shù)三十五頁\編于七點6坐標輪換法迭代公式：Xk+α*S=Xk+1式中S——搜索方向的單位向量；

α——步長，是個標量一維問題的方法可以拓展到多維問題：多維問題的計算程序：（1）給出初始點及精度ε目前二十五頁\總數(shù)三十五頁\編于七點6坐標輪換法目前二十六頁\總數(shù)三十五頁\編于七點7步長加速法坐標輪換法尋優(yōu)時，當目標函數(shù)出現(xiàn)了“脊線”，本來沿脊線方向一步或較少步數(shù)可達最優(yōu)，但因坐標輪換法總是沿平行于坐標軸方向搜索，不能沿脊線前進方向搜索，所以會浪費很多時間。并且，若從X0前進一步，恰好搜索到脊線上的X點，便會無法繼續(xù)向前搜索，因而不能或很難找到最優(yōu)點。目前二十七頁\總數(shù)三十五頁\編于七點7步長加速法可是，脊線方向卻是到達最優(yōu)點的有利方向。因此，遵循脊線方向爬山的方法正是步長加速法的基本思想。下面以二維為例，具體介紹這一方法的計算過程。目前二十八頁\總數(shù)三十五頁\編于七點計算過程：7步長加速法目前二十九頁\總數(shù)三十五頁\編于七點7步長加速法目前三十頁\總數(shù)三十五頁\編于七點步長加速法編程容易、又可靠，但需要做大量的函數(shù)值的計算。主要缺點是：這種方法不能根據(jù)實際情況改變搜索方向，因而，收斂速度慢7步長加速法目前三十一頁\總數(shù)三十五頁\編于七點8單純形算法單純形算法作為直接搜索的數(shù)值解法之一，是利用單純形的頂點，計算其函數(shù)值，按一定的規(guī)則進行探測性搜索。通過對搜索區(qū)內(nèi)單純形頂點的函數(shù)值進行直接比較，可以判斷目標函數(shù)的變化趨勢，確定有利的搜索方向和步長。此方法的核心是在選擇新的較好的單純形頂點的過程中，包含有反射、擴展、壓縮三種類型的過程。目前三十二頁\總數(shù)三十五頁\編于七點單純形算法的基本過程：（1）構造單純形、計算函數(shù)值首先，以初始點X0為一點，沿某一方向按一定初始步長h取另外兩個點，構造一個三角形，即二維單純形HGL。然后，計算各頂點的函數(shù)值。8單純形算法目前三十三頁\總數(shù)三十五頁\編于七點（2）反射過程若函數(shù)值fH>fG>fL,說明最差點H的反對稱方向目標函數(shù)會有所改進，可作為下一步的搜索方向。于