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

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

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

2）收斂速度不快；

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

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

基本牛頓法的迭代公式：第8頁，課件共42頁，創(chuàng)作于2023年2月，基本牛頓法的迭代公式：4.3牛頓型法第9頁，課件共42頁，創(chuàng)作于2023年2月，基本牛頓法的迭代公式：阻尼牛頓法的迭代公式：4.3牛頓型法第10頁，課件共42頁，創(chuàng)作于2023年2月，阻尼牛頓法的迭代步驟：4.3牛頓型法第11頁，課件共42頁，創(chuàng)作于2023年2月，阻尼牛頓法的迭代公式：4.3牛頓型法第12頁，課件共42頁，創(chuàng)作于2023年2月

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

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

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

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

4.5共軛方向及共軛方向法第24頁，課件共42頁，創(chuàng)作于2023年2月，4.5共軛方向及共軛方向法第25頁，課件共42頁，創(chuàng)作于2023年2月，共軛梯度法：先沿最速下降方向(負(fù)梯度方向)探索第一步，然后沿與該負(fù)梯度方向相共軛的方向進(jìn)行探索。4.5共軛梯度法第26頁，課件共42頁，創(chuàng)作于2023年2月，共軛方向與梯度之間的關(guān)系：

它表示沿著方向dk做一維搜索，它的終點xk+1與始點xk的梯度之差與dk的共軛方向dj正交。4.5共軛梯度法第27頁，課件共42頁，創(chuàng)作于2023年2月，共軛梯度法遞推公式：4.5共軛梯度法第28頁，課件共42頁，創(chuàng)作于2023年2月，共軛梯度法步驟：4.5共軛梯度法第29頁，課件共42頁，創(chuàng)作于2023年2月，共軛梯度法步驟：4.5共軛梯度法第30頁，課件共42頁，創(chuàng)作于2023年2月，共軛梯度法4.5共軛梯度法第31頁，課件共42頁，創(chuàng)作于2023年2月4.6鮑威爾法，鮑威爾法的基本思想：

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

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

改進(jìn)POWELL算法的步驟:一輪迭代的始點一輪迭代的終點一輪迭代的反射點第38頁，課件共42頁，創(chuàng)作于2023年2月同時計算各中間點函數(shù)值計算n個函數(shù)值之差并找出其中最大的一個（3）根據(jù)是否滿足判別條件來確定是否對原方向組進(jìn)行替換。因此有第39頁，課件共42頁，創(chuàng)作于2023年2月，

不滿足判別條件，下輪迭代仍用原