優(yōu)化設(shè)計4課件

本章主要內(nèi)容優(yōu)化設(shè)計概述優(yōu)化問題的數(shù)學(xué)分析基礎(chǔ)一維探索優(yōu)化方法

無約束多維問題的優(yōu)化方法約束問題的優(yōu)化方法多目標(biāo)函數(shù)的優(yōu)化方法

LINGO在優(yōu)化設(shè)計中的應(yīng)用優(yōu)化問題一維優(yōu)化問題（1個設(shè)計變量）多維優(yōu)化問題（多個設(shè)計變量）無約束多維問題單目標(biāo)函數(shù)的優(yōu)化問題多目標(biāo)函數(shù)的優(yōu)化問題有約束多維問題3.4無約束多維問題的優(yōu)化方法無約束優(yōu)化方法的核心是確定探索方向（能使目標(biāo)函數(shù)值下降的方向），有了方向，沿這個方向應(yīng)該走多遠(yuǎn)（最優(yōu)探索步長），則可采用一維搜索方法解決。一、

坐標(biāo)輪換法（變量輪換法）基本原理：沿著多維優(yōu)化設(shè)計空間的每一個坐標(biāo)軸作一維探索，求得最小值。坐標(biāo)輪換法的基本原理(以二維問題為例)x1x2X*X(0,1)X(1)X(2)X(3)X(0)0x1(0)x1(1)x1(2)x1(3)x1*x2(0)x2(1)x2(2)x2(3)x2*初始點平行于x1軸理論極小值坐標(biāo)輪換法的迭代路線是呈鋸齒形前進(jìn)的迭代步驟：（1）第1次迭代時，先固定x2=x2(0)

變量值不動，由初始點X(0)沿x1軸向進(jìn)行一維探索，得到該軸方向上的最優(yōu)點X(0,1)=[x1(1),

x2(0)]；（2）固定x1=x1(1)

變量值不動，由初始點X(0,1)

沿x2軸向進(jìn)行一維探索，得到該軸方向上的最優(yōu)點X(1)=[x1(1),

x2(1)]（3）將X

(1)

作為第1次迭代的改進(jìn)點，之后，完全依照第1次的步驟進(jìn)行第2、3、…、k次的坐標(biāo)輪換迭代，直到滿足精度要求后停止迭代。不同性質(zhì)目標(biāo)函數(shù)坐標(biāo)輪換法的求優(yōu)效能x1x2X(1)X*X(0)0x1x2X*X(0)X(1)X(2)X(3)X(4)0X(0)0x1x2X*X(1)收斂速度很快收斂速度很慢求優(yōu)失效等值線為橢圓,長、短軸與x1,x2軸平行等值線為橢圓,長、短軸與x1,x2軸不平行二、梯度法1.基本思想梯度方向是函數(shù)值增加最快的方向，而負(fù)梯度方向是函數(shù)下降最快的方向，所以梯度法以負(fù)梯度方向為搜索方向，每次迭代都沿著負(fù)梯度方向進(jìn)行一維搜索，直到滿足精度要求為止。因此，梯度法又稱為最速下降法。設(shè)在某次迭代中已取得迭代點X(k)，從該點出發(fā)，取負(fù)梯度方向為搜索方向S(k)，即：其中：以單位負(fù)梯度方向為探索方向，第k+1次迭代計算所得的新點為：上式即為梯度法迭代公式。以負(fù)梯度方向為探索方向，第k+1次迭代計算所得的新點為：因為X(k)已知，故f(X(k))和不難求出，只要知道步長

后，就可以得到新點X(k+1)。由于每次迭代能保證f(X(k+1))<f(X(k))

(以負(fù)梯度方向為搜索方向)，如此反復(fù)計算，最后總能達(dá)到最優(yōu)點X*。為了使目標(biāo)函數(shù)值在搜索方向S(k)上獲得最多的下降，每次迭代都進(jìn)行一維搜索求最優(yōu)步長，即求

：步長因子；

(k)

：最優(yōu)步長因子2.迭代步驟1）任選初始點X(0)，計算精度ε，令k=0

；2）計算

f(X(k))和；3）收斂判斷，(梯度準(zhǔn)則)A.若，則X(k)為近似最優(yōu)點，停止迭代，輸出最優(yōu)解X*=X(k)

和f(X*)=f(X(k))；B.若，則轉(zhuǎn)下一步繼續(xù)迭代；4）令5）確定最優(yōu)步長因子(k)

，使6）計算

；7）令k=k+1，轉(zhuǎn)2）。Eg:用梯度法求函數(shù)f(X)=(x1-1)2+(x2-1)2

的極小值，初始點X(0)=(0,0)T

，計算精度=0.01

。解:1)2)3)令則負(fù)梯度方向4)5)令得即6)因此,最優(yōu)解為(1,1)x1x20判斷X(1)點是否為極小值點梯度準(zhǔn)則解:（1）

如果轉(zhuǎn)（2），否則轉(zhuǎn)（5）。Eg:用梯度法求目標(biāo)函數(shù)f(X)=x12+4x22

在初始點X(0)=[22]T，迭代精度=10-2

下的最優(yōu)解。單位負(fù)梯度方向（2）（3），并轉(zhuǎn)（1）。（4）第7次迭代后，成立，停止迭代。（5）取時，

f(X*)=2.596×10-6≈0初始點位置不同,目標(biāo)函數(shù)等值線形狀不同,搜索效率(算法收斂速度)不同。梯度法的特點：負(fù)梯度方向只是函數(shù)值在點X(k)的鄰域內(nèi)下降最快的方向，離開該鄰域以后函數(shù)值不一定下降最快。因此，采用負(fù)梯度方向，從局部看函數(shù)值下降快，從全局看卻要走很多彎路。因此，梯度法的收斂速度較慢。梯度法的迭代過程，每相鄰兩步的搜索方向是垂直的，也就是說梯度法的迭代路線是呈鋸齒形前進(jìn)的。（坐標(biāo)輪換法也是呈鋸齒形）梯度法迭代過程中，當(dāng)?shù)c離理論極小點較遠(yuǎn)時，一次迭代的函數(shù)值下降量比較大。迭代點離極小點越近，函數(shù)值下降的速度就越慢。因此，梯度法常與其它優(yōu)化方法結(jié)合使用。即第一步采用梯度法，后面采用其它的方法確定搜索方向。梯度法的收斂速度與目標(biāo)函數(shù)的性質(zhì)有關(guān)。如果目標(biāo)函數(shù)的等值線（面）為同心圓（球），則無論從哪里出發(fā)，只需要一次搜索就能達(dá)到極小點。

（沿著等直線半徑方向搜索即可）三、牛頓法1.基本牛頓法設(shè)目標(biāo)函數(shù)是連續(xù)二階可微的，將函數(shù)在X(k)點按泰勒級數(shù)展開后，得到二次項將上式去括號展開，得對X求導(dǎo)，設(shè)X(K+1)是極小點，并令一階導(dǎo)數(shù)為0，得

即上式即為基本牛頓法的迭代公式，其中S(k)稱為牛頓方向。則

令等式兩邊同時左乘[2f(X(k))]-1,解出X(k+1),得到牛頓法步長總為1Eg:用牛頓法求下列函數(shù)的極小值。解：(1)取初始點

(2)計算牛頓方向故(3)極小值(0)=1基本牛頓法的特點：對于二次函數(shù)而言，取到二次項的泰勒展開式就是目標(biāo)函數(shù)本身。如果二階導(dǎo)數(shù)矩陣(海色矩陣)正定，那么按基本牛頓法求出的X(1)就是目標(biāo)函數(shù)的精確極小點。因此，對正定二次函數(shù)而言，牛頓法只需一次迭代就可以達(dá)到精確極小點。基本牛頓法迭代時步長總是為1，對非二次函數(shù)、非正定函數(shù)而言，一次迭代并不能達(dá)到極小點，有時還可能失效（即總是不能收斂）。2.阻尼牛頓法基本牛頓法對非正定函數(shù)失效是因為沿牛頓方向搜索時，步長總是為1，這并不能保證找到的下一個迭代點是該方向上的極小點。為此，增加步長因子和一維搜索過程。此時的牛頓法稱為阻尼牛頓法。阻尼牛頓法比基本牛頓法多一個一維搜索過程阻尼牛頓法迭代步驟：1）選取初始點X(0)，計算精度ε，令k=0

；

4）一維搜索，求(k),使3）令

２)計算

５）按一維搜索結(jié)果，計算6）收斂判斷，A.若，則X(k+1)為近似最優(yōu)點，停止迭代，輸出最優(yōu)解X*=X(k+1)和f(X*)=f(X(k+1))；B.若，則令k=k+1，轉(zhuǎn)2）繼續(xù)迭代；數(shù)學(xué)分析表明，牛頓法具有很好的局部收斂性質(zhì)，對二次函數(shù)來說，僅一步就達(dá)到優(yōu)化點，但對一般函數(shù)來說，在一定條件下，當(dāng)初始點的選取充分接近目標(biāo)函數(shù)的極小點時，有很快的收斂速度，但若初始點選取離極小點比較遠(yuǎn)，就難保證收斂；另外，牛頓法必須求一階導(dǎo)數(shù)、二階導(dǎo)數(shù)矩陣及其逆陣，這對復(fù)雜的目標(biāo)函數(shù)來說，是比較困難的。四、變尺度法梯度法構(gòu)造簡單，只用到一階偏導(dǎo)數(shù)，計算量小，迭代初期收斂速度快，但當(dāng)?shù)c到最優(yōu)點附近時收斂速度極慢；變尺度法是在梯度法和牛頓法的基礎(chǔ)上發(fā)展起來的一種優(yōu)化方法。用得較多的是DFP（Davidon-Fletcher-Powell)變尺度法。1.基本思想牛頓法收斂很快，對二次函數(shù)只需迭代一次就能達(dá)到最優(yōu)點，對非二次函數(shù)也能較快達(dá)到最優(yōu)點，但牛頓法計算量和存儲量偏大。而且某些函數(shù)可能根本無法計算二階偏導(dǎo)數(shù)矩陣及其逆陣。為了綜合梯度法和牛頓法的優(yōu)點，揚(yáng)長避短，產(chǎn)生了變尺度法。變尺度法的搜索方向為變尺度法的基本迭代公式為式中，A(k)是一個需要構(gòu)造的n階方陣，稱為變尺度矩陣，它隨迭代點位置的變化而變化，形成一個矩陣序列。搜索方向S(k)=-A(k)f(X(k))稱為擬牛頓方向。2.變尺度矩陣的構(gòu)建變尺度矩陣A(k)的構(gòu)建是從A(0)=I開始，通過迭代公式

A(k+1)=A(k)

+E(k)得到的。E(k)稱為修正矩陣，通過它的一步步修正，使A(k)逐步逼近[2f(X(k))]-1

，即使變尺度法的迭代方向逐步逼近牛頓方向。修正矩陣取不同的形式，就形成了不同的變尺度法。DFP變尺度法修正矩陣E(k)的構(gòu)造公式為E(0)=?(k)=?3.變尺度法的迭代步驟解：(1)取初始點：Eg:用變尺度法求下列函數(shù)的極小值。一維搜索最優(yōu)步長因子的求解

（2）一維搜索（3）（4）求A(1)則有：