1、第四章 一維搜索方法,4.1 引言,求一元函數(shù),求解一維優(yōu)化問題的方法稱為一維優(yōu)化方法。,的極小點和極小值問題就是一維,最優(yōu)化問題。,1、一維優(yōu)化方法的迭代過程,優(yōu)化方法所確定的搜索方向,步長因子,目標函數(shù)值下降,當方向 給定，求最佳步長 就是求一元函數(shù) :,的極值問題，這一過程被稱為一維搜索.,2、一維優(yōu)化方法的分類：,一類是直接法：按某種規(guī)律取若干點計算其函數(shù)值， 然后通過函數(shù)值的直接比較來最后確定最優(yōu)解。,菲波那契法（Fibonaui法）、黃金分割法等。,一類是間接法：要利用函數(shù)的導數(shù)，故稱解析法，,牛頓法和二次插值法。,（1）確定初始搜索區(qū)間,函數(shù)極小點在內的單峰區(qū)間；,內尋求極小點。

2、,一維優(yōu)化一般分為兩大步驟：,該區(qū)間應包括一維,（2）在單峰區(qū)間,1、單峰(谷）區(qū)間 若在某區(qū)間內函數(shù)有唯一的極小點，這個搜索區(qū)間就是單峰區(qū)間。,4.2 確定初始區(qū)間的進退法,一、一維搜索的基本思想,圖形特點： “高低高”,單峰區(qū)間中一定能求得一個極小點,函數(shù)值的特點： “大小大”,二、確定初始單峰區(qū)間的進退法,基本思想： 按照一定的規(guī)則試算若干個點，比較其函數(shù)值的大小，直至找到函數(shù)值按“高-低-高”變化的單峰區(qū)間。,c:如y1y2，極小點在a1和a1h之間。,b:若y1y2, 向左后退；h=-h，取a3=a1-h,并計算 y3=f(a1-h),若y3y1,則a,b=a1-h,a1+h， 否則

3、繼續(xù)加倍步長后退；,步驟：,（1）選定初始點a, 初始步長h，a2=a1+h,計算 y1f(a1),y2f(a2)。,（2）比較y1和y2。 a:如y1y2,向右前進,加大步長h2h, a3=a2+2h,計 算y3f(a3)，若y2y3,則區(qū)間a,b=a1,a1+3h 否則，步長再加倍繼續(xù)。,進退法程序框圖,(1)取,因,則,；,解：,(2)因為,故作前進計算，,(3)因為,再繼續(xù)作前進運算，此時：,初始搜索區(qū)間,三點的函數(shù)值分別是4，0，16,（4）,f1f（a1）， f2f（b1）,4.3 一維搜索的區(qū)間消去方法_求最優(yōu)值,基本思想,搜索區(qū)間確定之后，采用區(qū)間消去法逐步縮短搜索區(qū)間，從而找

4、到極小點的數(shù)值近似解。 假定在搜索區(qū)間a,b內，任取兩點a1,b1;,綜合為兩種情況： 若 則取 為縮短后的搜索區(qū)間。 若 則取 為縮短后的搜索區(qū)間。,f1f（a1）， f2f（b1） (1)如f1f2, 則縮小的新區(qū)間為a1,b; (3)如f1=f2, 則縮小的新區(qū)間為a1,b1,黃金分割法適用于a,b區(qū)間上的任何單峰函數(shù)求極小值問題。對函數(shù)除要求“單谷”外不作其他要求，甚至可以不連續(xù)。因此，這種方法的適用面相當廣。,1、基本思想 黃金分割法是通過不斷縮短單峰區(qū)間的長度來搜索極小點的一種有效方法。,確定取舍區(qū)間,2、適用條件,在搜索區(qū)間,中取兩點,然后比較,兩點的函數(shù),有三種情況：,根據(jù)函數(shù)

5、的單峰性，極值點必在,極值點必在,極值點則在,值,(1) 如,(2)如,(3)如,區(qū)間,區(qū)間,貼圖。,3、迭代公式及迭代過程,(3)比較,(4)當逐漸縮短的新區(qū)間小于預先給定的精度,即,時，終止迭代，于是所求最優(yōu)點,；否則轉第(3)步繼續(xù)迭代。,黃金分割法程序框圖,例：試用黃金分割法求解優(yōu)化問題：,允許誤差,解：(1)依題意單峰區(qū)間,為,，,；,(2)取內分點并計算其函數(shù)值,(3) 比較函數(shù)值的大小.因為,故知新區(qū)間為,(4) 判斷是否滿足精度要求,區(qū)間縮短8次后，,求得的近似最優(yōu)解為：,作業(yè)：用黃金分割法求函數(shù)f(x)=3x3-4x+2的極小點，給定 x0=0, h=1, =0.2。,答案:

6、極小點與極小值：,x*=0.5(0.584+0.764)=0.674 f(x*)=0.222,例2：股票價格中的黃金點與實例,預測股價上升能力與可能反轉之價位時：,可用前段下跌行情之最低點值乘以0.191、0.382、 0.618、0.809、1；,超過一倍漲幅時，其反壓點為：1.191、0.382、 0.618、0.809、1；,當預測下跌反壓點時可乘以0.809、0.618、0.382、0.191；,例：當下跌行情結束前，某股的最低價位為10元， 那么，股價反轉上升時，可預測出不同反彈價位：,例：當上升行情結束前，某股的最高價位為30元， 那么，股價反轉下跌時，可預測出不同下跌反壓點：,4

7、.5 一維搜索的解析法,一、牛頓法,1、基本思想,牛頓法在一維探索中的應用，是用切線代替弧線逐漸逼近函數(shù)根值的方法。,當目標函數(shù)f(x) 有一階連續(xù)導數(shù)且 二階導數(shù)大于零時， 在曲線y=f (x)上作 一系列切線，使之 與x軸的交點x(0)， x(1) ，x(2)， x(3). 逐漸趨近于 y=f (x)=0的根x*。,的切線，切線方程為：,2、迭代公式,推廣到第k步迭代可得到牛頓法的迭代公式：,設f(x)連續(xù)、可微，則在點x0附近用一個二次函數(shù)(x)來逼近函數(shù)f(x) ，即：,用二次函數(shù)的(x)極小點x1作為f(x)極小點的一個近似點。根據(jù)極值必要條件:,牛頓迭代公式也可以用泰勒（Taylo

8、r)展開得到：,即,依次繼續(xù)下去，可得牛頓迭代公式：,3、牛頓法的迭代過程：,2、若用數(shù)值微分計算函數(shù)的二階導數(shù)，其舍入誤差將 嚴重影響牛頓法的收斂速度， f(x)的值越小，這 個問題就越嚴重。,牛頓法的優(yōu)點：收斂速度快。,牛頓法的缺點：,1、計算函數(shù)的一階和二階導數(shù)，增加了每次迭代的 工作量。,3、要求初始點選的比較好（離極小點不太遠），否 則有可能使極小化序列發(fā)散或收斂到非極小點。,解：,給定初始點：,控制誤差：,二、拋物線法（二次插值法）,1、基本思想: 是利用目標函數(shù)在若干點的信息，構成一個與目標函數(shù)值相近似的低次插值多項式p(x)，然后用多項式p(x)的最優(yōu)解作為函數(shù)的近似最優(yōu)解(即

9、p(x*p)=0的根)作為目標函數(shù)f(x)的近似極值點。,2、公式推導,在極小點附近，用二次三項式,如何計算函數(shù),令,以xm作為f(x)的極小點的估計值。,3、迭代過程：, 確定初始搜索區(qū)間，定出初始插值結點；, 終止判斷：,，則,為所求的極小點；如果,為所求的極小點；,b: 當,時，,則需比較,和,的大小，以便在,四點中丟掉,充分利用函數(shù)值的信息；,二次插值法的優(yōu)點：,收斂快；調用函數(shù)次數(shù)少,例：用二次插值法求函數(shù)f(x)=3x3-4x+2的極小點，給定 x0=0, =0.2。初始區(qū)間a,b=0,2,解 ： 1）取中間點x2=1。,2）用二次插值法逼近極小點，相鄰三點的函數(shù)值: x1=0,

10、x2=1, x3=2; f1=2, f2=1, f3=18. 代入公式：,xp*0.555, fp=0.292,由于fp0.2, 應繼續(xù)迭代。,在新區(qū)間，相鄰三點的函數(shù)值: x1=0, x2=0.555, x3=1; f1=2, f2=0.292, f3=1。 x*p0.607, fp=0.243,由于fpx2, 新區(qū)間a,b=x2,b=0.555,1 |x2-x*p|=|0.555-0.607|=0.0520.2, 迭代終止。,x*p0.607, f*=0.243,例：用二次插值法求 的極值點。初始搜索區(qū)間 ， 。,解：取x2點為區(qū)間x1,x3的中點,計算x1,x2,x33點處的函數(shù)值f1=19，f2=-96.9375，