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

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

1）對初始搜索點無嚴格要求；

2）收斂速度不快；

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

4）收斂速度與目標函數值的性質有關，對等值線是同心圓的目標函數來說，經過一次迭代就可以達到極值點。4.2梯度法（最速下降法）第7頁，共42頁，2022年，5月20日，0點21分，星期五4.3牛頓型法，牛頓型法的基本思想：利用二次曲線來逐點近似原目標函數，以二次曲線的極小點來近似原目標函數的極小點并逐漸逼近該點。

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

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

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

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

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

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

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

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

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

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

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