第四章一維搜索法

1、第四章一維搜索法由第一章關(guān)于求解最優(yōu)化問題概述中我們知道，從已知迭代點nkRX?出發(fā)按照基本迭代公式kkkkPtXX???1來求解最優(yōu)化問題，其關(guān)鍵在于如何構(gòu)造一個搜索方向nkRP?和確定一個步長1Rtk?，使下一迭代點1?kX處的目標(biāo)函數(shù)值下降，即)()(1kkXfXf??現(xiàn)在我們來討論，當(dāng)搜索方向kP已經(jīng)確定的情況下，如何來確定步長kt？步長因子的選取有多種方法，如取步長為常數(shù)，但這樣選取的步長并不最好，如何選取最好步長呢？實際計算

2、通常采用一維搜索來確定最優(yōu)步長對無約束最優(yōu)化問題)(minXfnRX?，當(dāng)已知迭代點kX和下降方向kP時，要確定適當(dāng)?shù)牟介Lkt使??)(1kXf)(kkkPtXf?比)(kXf有所下降，即相當(dāng)于對于參變量t的函數(shù))()(kktPXft???要在區(qū)間]0[??上選取ktt?使)()(1kkXfXf??，即)0()()()(??????kkkkkXfPtXft由于這種從已知點kX出發(fā)，沿某一下降的探索方向kP來確定步長kt的問題，實質(zhì)上是單

3、變量函數(shù)()t?關(guān)于變量t的一維搜索選取問題，故通常叫做一維搜索按這種方法確定的步長kt又稱為最優(yōu)步長，這種方法的優(yōu)點是，它使目標(biāo)函數(shù)值在搜索方向上下降得最多今后為了簡便起見，我們用記號)(1kkkPXlsX，??（4.1）表示從點kX出發(fā)沿kP方向?qū)δ繕?biāo)函數(shù))(Xf作直線搜索所得到的極小點是1?kX其中l(wèi)和s分別是Linearsearch（直線搜索）兩詞的詞首在目標(biāo)函數(shù))(Xf已確定的條件下（4.1）等價于如下兩式：?????????

4、???kkkktkktkkkPtXXttPXfPtXf1)(min)(min)(，?下面進一步解釋迭代點kkkkPtXX???1的空間位置容易證明，若從kX出發(fā)，沿kP方向進行一維搜索得極小點kkkkPtXX???1，則該點1??kXX處的梯度方向)(1??kXf與搜索方向kP之間應(yīng)滿足0)(1???kTkPXf(4.2)事實上，設(shè))()(kktPXft???，對t求導(dǎo)有11minmaxkkattbtt????，，，輸出][ba，加步探

5、索法算法的流程圖如圖4.2所示。在加步探索法中，一般建議2??若能估計問題（4.3）的最優(yōu)解的大體位置的話，初始點0t要盡量取接近于問題（4.3）的最優(yōu)解在具體運用上述加步探索法時，有時還要考慮一些細(xì)節(jié)問題例如，當(dāng)探索得到新點處的目標(biāo)函數(shù)值和出發(fā)點處相同時，以及初始步長應(yīng)如何選取等，都需作適當(dāng)處理三、單谷區(qū)間與單谷函數(shù)由于以后要介紹的一些維搜索方法，主要適用于問題（4.3）在搜索區(qū)間中只有唯一的最優(yōu)解的情況，為此，我們再給出下面單谷區(qū)間

6、與單谷函數(shù)概念定義4.2設(shè)11RR?：?，閉區(qū)間1][Rba?，若存在點][bat，?，使得)(t?在][ta，上嚴(yán)格遞減，()t?在][bt，上嚴(yán)格遞增，則稱][ba，是函數(shù))(t?的單谷區(qū)間，)(t?是][ba，上單谷函數(shù)開始選取初始點t0，初始步長h00，加步系數(shù)α1，令k=0φ0=φ(t0)，比較目標(biāo)函數(shù)值tk1=tkhkφk1=φ(tk1)a=mint，tk1b=maxt，tk1結(jié)束NYNYφk1φkhk1=hkt=tktk=