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

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

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

2）收斂速度不快；

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

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

基本牛頓法的迭代公式：第8頁(yè)，共42頁(yè)，2022年，5月20日，0點(diǎn)21分，星期五，基本牛頓法的迭代公式：4.3牛頓型法第9頁(yè)，共42頁(yè)，2022年，5月20日，0點(diǎn)21分，星期五，基本牛頓法的迭代公式：阻尼牛頓法的迭代公式：4.3牛頓型法第10頁(yè)，共42頁(yè)，2022年，5月20日，0點(diǎn)21分，星期五，阻尼牛頓法的迭代步驟：4.3牛頓型法第11頁(yè)，共42頁(yè)，2022年，5月20日，0點(diǎn)21分，星期五，阻尼牛頓法的迭代公式：4.3牛頓型法第12頁(yè)，共42頁(yè)，2022年，5月20日，0點(diǎn)21分，星期五

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

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

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

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

4.5共軛方向及共軛方向法第24頁(yè)，共42頁(yè)，2022年，5月20日，0點(diǎn)21分，星期五，4.5共軛方向及共軛方向法第25頁(yè)，共42頁(yè)，2022年，5月20日，0點(diǎn)21分，星期五，共軛梯度法：先沿最速下降方向(負(fù)梯度方向)探索第一步，然后沿與該負(fù)梯度方向相共軛的方向進(jìn)行探索。4.5共軛梯度法第26頁(yè)，共42頁(yè)，2022年，5月20日，0點(diǎn)21分，星期五，共軛方向與梯度之間的關(guān)系：

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

直接利用迭代點(diǎn)的目標(biāo)函數(shù)值來(lái)構(gòu)造共軛方向，然后再?gòu)娜我怀跏键c(diǎn)出發(fā)，逐次的共軛方向作一維搜索求極值點(diǎn)。第32頁(yè)，共42頁(yè)，2022年，5月20日，0點(diǎn)21分，星期五，共軛方向的生成：結(jié)論：從不同的兩點(diǎn)出發(fā)，沿同一方向進(jìn)行兩次一維搜索，所得兩個(gè)極小點(diǎn)的連線方向便是原方向共軛的另一方向。第八節(jié)鮑威爾法第33頁(yè)，共42頁(yè)，2022年，5月20日，0點(diǎn)21分，星期五，共軛方向的生成：二維情況：任意點(diǎn)出發(fā)沿著x1軸方向和AB方向搜索，即可得到極小點(diǎn)。第八節(jié)鮑威爾法第34頁(yè)，共42頁(yè)，2022年，5月20日，0點(diǎn)21分，星期五，基本POWELL法（二維）：第八節(jié)鮑威爾法第35頁(yè)，共42頁(yè)，2022年，5月20日，0點(diǎn)21分，星期五基本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)過(guò)n輪后就可以找到極小點(diǎn)。第八節(jié)鮑威爾法第36頁(yè)，共42頁(yè)，2022年，5月20日，0點(diǎn)21分，星期五改進(jìn)POWELL法：

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

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

不滿足判別條件，下輪迭代仍用原方向組，并以中