無約束優(yōu)化方法

關(guān)于無約束優(yōu)化方法4.1概述，數(shù)值解法：是利用已有的信息，通過計(jì)算點(diǎn)一步一步地直接移動(dòng)，逐步逼近最后達(dá)到最優(yōu)點(diǎn)。1）選擇迭代方向即探索方向；2）在確定的方向上選擇適當(dāng)步長(zhǎng)邁步進(jìn)行探索第2頁,共42頁，2024年2月25日，星期天，無約束優(yōu)化方法可以分成兩類：一類是利用目標(biāo)函數(shù)的一階或二階導(dǎo)數(shù)的無約束優(yōu)化方法（如最速下降法、共軛梯度法、牛頓法及變尺度法）；另一類只利用目標(biāo)函數(shù)的無約束優(yōu)化方法（如坐標(biāo)輪換法、單形替換法及鮑威爾法等）。4.1概述第3頁,共42頁，2024年2月25日，星期天，定義：最速下降法就是采用使目標(biāo)函數(shù)值下降得最快的負(fù)梯度方向作為探索方向，來求目標(biāo)函數(shù)的極小值的方法，又稱為梯度法。最速下降法的迭代公式4.2梯度法（最速下降法）第4頁,共42頁，2024年2月25日，星期天，最速下降法的迭代步驟：4.2梯度法（最速下降法）第5頁,共42頁，2024年2月25日，星期天，4.2梯度法（最速下降法）第6頁,共42頁，2024年2月25日，星期天，梯度法的特點(diǎn)：

1）對(duì)初始搜索點(diǎn)無嚴(yán)格要求；

2）收斂速度不快；

3）相鄰兩次迭代搜索方向互相垂直，在遠(yuǎn)離極值點(diǎn)處收斂快，在靠近極值點(diǎn)處收斂慢；

4）收斂速度與目標(biāo)函數(shù)值的性質(zhì)有關(guān)，對(duì)等值線是同心圓的目標(biāo)函數(shù)來說，經(jīng)過一次迭代就可以達(dá)到極值點(diǎn)。4.2梯度法（最速下降法）第7頁,共42頁，2024年2月25日，星期天4.3牛頓型法，牛頓型法的基本思想：利用二次曲線來逐點(diǎn)近似原目標(biāo)函數(shù)，以二次曲線的極小點(diǎn)來近似原目標(biāo)函數(shù)的極小點(diǎn)并逐漸逼近該點(diǎn)。

基本牛頓法的迭代公式：第8頁,共42頁，2024年2月25日，星期天，基本牛頓法的迭代公式：4.3牛頓型法第9頁,共42頁，2024年2月25日，星期天，基本牛頓法的迭代公式：阻尼牛頓法的迭代公式：4.3牛頓型法第10頁,共42頁，2024年2月25日，星期天，阻尼牛頓法的迭代步驟：4.3牛頓型法第11頁,共42頁，2024年2月25日，星期天，阻尼牛頓法的迭代公式：4.3牛頓型法第12頁,共42頁，2024年2月25日，星期天

設(shè)法構(gòu)造出一個(gè)對(duì)稱正定矩陣來代替，并在迭代過程中使逐漸逼近

,那么就簡(jiǎn)化了牛頓法的計(jì)算，并且保持了牛頓法收斂快的優(yōu)點(diǎn)。4.4變尺度法（擬牛頓法），變尺度法的基本思想：牛頓方向：變尺度法的迭代公式：尺度矩陣第13頁,共42頁，2024年2月25日，星期天，尺度矩陣G正定牛頓迭代公式：目的：目標(biāo)函數(shù)的偏心率減小到零。4.4變尺度法（擬牛頓法）第14頁,共42頁，2024年2月25日，星期天，變尺度矩陣的建立：變尺度法的迭代公式：搜索方向：尺度矩陣應(yīng)具備的條件：1）為正定對(duì)稱矩陣；2）具有簡(jiǎn)單的迭代形式:3）滿足擬牛頓條件：令則4.4變尺度法（擬牛頓法）第15頁,共42頁，2024年2月25日，星期天，變尺度法的一般步驟：4.4變尺度法（擬牛頓法）第16頁,共42頁，2024年2月25日，星期天，變尺度法的流程圖：4.4變尺度法第17頁,共42頁，2024年2月25日，星期天，DFP算法：DFP算法的校正公式4.4變尺度法（擬牛頓法）第18頁,共42頁，2024年2月25日，星期天，DFP算法：4.4變尺度法（擬牛頓法）第19頁,共42頁，2024年2月25日，星期天4.5共軛方向及共軛方向法，

在下一次迭代時(shí)，選擇搜索方d1指向極小點(diǎn)x*，共軛方向以二元函數(shù)為例：我們?nèi)我膺x擇一個(gè)初始點(diǎn)x0點(diǎn)，沿著某個(gè)下降方向d0作一維搜索第20頁,共42頁，2024年2月25日，星期天，共軛方向正交4.5共軛方向及共軛方向法第21頁,共42頁，2024年2月25日，星期天，共軛方向的性質(zhì)4.5共軛方向及共軛方向法第22頁,共42頁，2024年2月25日，星期天，共軛方向法的步驟4.5共軛方向及共軛方向法第23頁,共42頁，2024年2月25日，星期天，共軛方向的形成格拉姆-斯密特向量系共軛化的方法

n個(gè)線性無關(guān)的向量系vi（i=0,1，…，n-1）一組獨(dú)立向量dr（r=0,1，…，n-1）

4.5共軛方向及共軛方向法第24頁,共42頁，2024年2月25日，星期天，4.5共軛方向及共軛方向法第25頁,共42頁，2024年2月25日，星期天，共軛梯度法：先沿最速下降方向(負(fù)梯度方向)探索第一步，然后沿與該負(fù)梯度方向相共軛的方向進(jìn)行探索。4.5共軛梯度法第26頁,共42頁，2024年2月25日，星期天，共軛方向與梯度之間的關(guān)系：

它表示沿著方向dk做一維搜索，它的終點(diǎn)xk+1與始點(diǎn)xk的梯度之差與dk的共軛方向dj正交。4.5共軛梯度法第27頁,共42頁，2024年2月25日，星期天，共軛梯度法遞推公式：4.5共軛梯度法第28頁,共42頁，2024年2月25日，星期天，共軛梯度法步驟：4.5共軛梯度法第29頁,共42頁，2024年2月25日，星期天，共軛梯度法步驟：4.5共軛梯度法第30頁,共42頁，2024年2月25日，星期天，共軛梯度法4.5共軛梯度法第31頁,共42頁，2024年2月25日，星期天4.6鮑威爾法，鮑威爾法的基本思想：

直接利用迭代點(diǎn)的目標(biāo)函數(shù)值來構(gòu)造共軛方向，然后再?gòu)娜我怀跏键c(diǎn)出發(fā)，逐次的共軛方向作一維搜索求極值點(diǎn)。第32頁,共42頁，2024年2月25日，星期天，共軛方向的生成：結(jié)論：從不同的兩點(diǎn)出發(fā)，沿同一方向進(jìn)行兩次一維搜索，所得兩個(gè)極小點(diǎn)的連線方向便是原方向共軛的另一方向。第八節(jié)鮑威爾法第33頁,共42頁，2024年2月25日，星期天，共軛方向的生成：二維情況：任意點(diǎn)出發(fā)沿著x1軸方向和AB方向搜索，即可得到極小點(diǎn)。第八節(jié)鮑威爾法第34頁,共42頁，2024年2月25日，星期天，基本POWELL法（二維）：第八節(jié)鮑威爾法第35頁,共42頁，2024年2月25日，星期天基本POWELL法（n維）：1）從初始點(diǎn)出發(fā)，首先沿著n個(gè)坐標(biāo)軸方向進(jìn)行一維搜索，得到一個(gè)終點(diǎn)；2）由初始點(diǎn)和終點(diǎn)連線形成一個(gè)新方向，該方向排在原方向組的最后，去掉原方向組的的第一個(gè)方向，形成新的方向組；3）從上一輪的搜索終點(diǎn)出發(fā)沿新的搜索方向作一維搜索而得到的極小點(diǎn)，作為下一輪迭代的始點(diǎn)。4）從新的始點(diǎn)出發(fā)，沿著新的方向組做一維搜索。如此反復(fù)進(jìn)行n輪搜索后，可找到n個(gè)共軛方向，若目標(biāo)函數(shù)是正定二次型函數(shù)，則經(jīng)過n輪后就可以找到極小點(diǎn)。第八節(jié)鮑威爾法第36頁,共42頁，2024年2月25日，星期天改進(jìn)POWELL法：

獲得新方向構(gòu)成新方向組時(shí),不是輪換地去掉原來的方向,而是經(jīng)判別后,在n+1個(gè)方向中留下最接近共軛的n個(gè)方向。第八節(jié)鮑威爾法第37頁,共42頁，2024年2月25日，星期天1）給定初始點(diǎn)，選取初始方向組，它由n個(gè)線性無關(guān)的向量組成置k=02）從出發(fā)順次沿作一維搜索得接著以為起點(diǎn)，沿方向移動(dòng)一個(gè)距離得到并分別求出

改進(jìn)POWELL算法的步驟:一輪迭代的始點(diǎn)一輪迭代的終點(diǎn)一輪迭代的反射點(diǎn)第38頁,共42頁，2024年2月25日，星期天同時(shí)計(jì)算各中間點(diǎn)函數(shù)值計(jì)算n個(gè)函數(shù)值之差并找出其中最大的一個(gè)（3）根據(jù)是否滿足判別條件來確定是否對(duì)原方向組進(jìn)行替換。因此有第39頁,共42頁，2024年2月25日，星期天，

不滿足判別條件，下輪迭代仍用原方向組，并以中函數(shù)值小者作為