一維優(yōu)化方法

1、維優(yōu)化方法最優(yōu)化設(shè)計數(shù)學(xué)模型中的基本概念：1 、設(shè)計變量在機械設(shè)計中，區(qū)別不同的設(shè)計方案，通常是以一組取值不同的參數(shù)來表示。這些參 數(shù)可以是表示構(gòu)件形狀、大小、位置等的幾何量，也可以是表示構(gòu)件質(zhì)量、速度、加速度、 力、力矩等的物理量。在構(gòu)成一項設(shè)計方案的全部參數(shù)中，可能有一部分參數(shù)根據(jù)實際情 況預(yù)先確定了數(shù)值，它們在優(yōu)化設(shè)計過程中始終保持不變，這樣的參數(shù)稱為給定參數(shù)（或叫預(yù)定參數(shù)）或設(shè)計常數(shù)。另一部分參數(shù)則是需要優(yōu)選的參數(shù)，它們的數(shù)值在優(yōu)化設(shè)計過 程中則是需要優(yōu)選的參數(shù)，它們的數(shù)值在優(yōu)化計算過程中是變化的，這類參數(shù)稱為設(shè)計變 量，它相當(dāng)于數(shù)學(xué)上的獨立自變量。一個優(yōu)化問題如果有n個設(shè)計變量，而每

2、個設(shè)計變量用xi（i=1,2,n） 表示，則可以把n個設(shè)計變量按一定的次序排列起來組成一個列陣或行 陣的轉(zhuǎn)置，即寫成? x1?x= ?x?2 ?=x1,x2, ,xT? ?n?x?n ?我們把x定義為n維歐式空間的一個列向量，設(shè)計變量x1,x2, ,xn 為向量x的n個分量。以設(shè)計變量x1,x2, ,xn 為坐標(biāo)軸展成的空間稱為 n維歐式空間，用 Rn表示。該空 間包含了該項設(shè)計所有可能的設(shè)計方案，且每一個設(shè)計方案就對應(yīng)著設(shè)計空間上的一個設(shè) 計向量或者說一個設(shè)計點 x。2 、目標(biāo)函數(shù)優(yōu)化設(shè)計是在多種因素下欲尋求使設(shè)計者員滿意、且適宜的一組參數(shù)?！白顫M意”、 “最適宜”是針對某具體的設(shè)計問題，人

3、們所追求的某一特定目標(biāo)而言。在機械設(shè)計中， 人們總希望所設(shè)計的產(chǎn)品具有最好的使用性能、體積小、結(jié)構(gòu)緊湊、重量最輕和最少的制 造成本以及最多的經(jīng)濟效益，即有關(guān)性能指標(biāo)和經(jīng)濟指標(biāo)方面最好。在優(yōu)化設(shè)計中，一般將所追求的目標(biāo) （最優(yōu)指標(biāo)）用設(shè)計變量的函數(shù)形式表達，稱該函 數(shù)為優(yōu)化設(shè)計的目標(biāo)函數(shù)。目標(biāo)函數(shù)的值是評價設(shè)計方案優(yōu)劣程度的標(biāo)準(zhǔn)，也可稱為準(zhǔn)則 函數(shù)。建立這個函數(shù)的過程稱為建立目標(biāo)函數(shù)。一般的表達式為F(x)=F(x1,x2, ,xn)它代表著某項重要的特征，例如機器的某種性能、體積、質(zhì)量、成本、誤差、效率等目標(biāo)函數(shù)是設(shè)計變量的標(biāo)量函數(shù)。優(yōu)化設(shè)計的過程就是通過優(yōu)選設(shè)計變量使目標(biāo)函數(shù)達到最優(yōu)值，最優(yōu)

4、值的數(shù)學(xué)表征為最小值minF(x)或最大值 maxF(x)。按一般的規(guī)范做法,把優(yōu)化問題歸結(jié)為求目標(biāo)函數(shù)值的最小值居多。在求解過程中，目標(biāo)函數(shù)值越小，設(shè)計方 案越優(yōu)。對于某些追求目標(biāo)函數(shù)最大值的問題，例如前述求月生產(chǎn)利潤最大的問題或謀求設(shè)計的效率最高、壽命最長等等，可轉(zhuǎn)化 (8-1) (8-2)為求目標(biāo)函數(shù)負值的最小值問題，即maxF(x) ? min-F(x) (8-3) 因此，本章在后面的敘述中，一律把優(yōu)化問題規(guī)范為求 目標(biāo)函數(shù)的最小值，表達式見式 (8-2)。在優(yōu)化設(shè)計中，僅根據(jù)一項準(zhǔn)則建立的一個目標(biāo) 函數(shù)，稱為單目標(biāo)函數(shù)。如前面舉例中的生產(chǎn)調(diào)度問題中，為了實現(xiàn)單月生產(chǎn)利潤最大化 而建立

5、的目標(biāo)函數(shù)即屬于單目標(biāo)優(yōu)化設(shè)計問題。若在設(shè)計中需要同時兼顧多個設(shè)計準(zhǔn)則， 則需要建立多個目標(biāo)函數(shù)，這種問題即為多目標(biāo)優(yōu)化問題。在解決優(yōu)化設(shè)計問題時，正確選擇目標(biāo)函數(shù)是非常重要的，它不僅直接影響優(yōu)化設(shè)計 的結(jié)果，而且對整個優(yōu)化計算的繁簡難易也會有一定的影響。3 、約束條件與可行域優(yōu)化設(shè)計不僅要使所選擇方案的設(shè)計指標(biāo)達到最佳值，同時還必須滿足一些附加的設(shè) 計條件，這些附加的設(shè)計條件都是對設(shè)計變量取值的限制，在優(yōu)化設(shè)計中叫做設(shè)計約束或 約束條件。它的表現(xiàn)形式有兩種，一種是不等式約束，即另一種是等式約束，即gu(x) < 0 或 gu(x) >0hv(x)=0u=1,2, ,m v=1,2

6、, ,p式中g(shù)u(x)和hv(x)分別為設(shè)計變量的函數(shù)；m和p分別表示不等式約束和等式約束的個數(shù)，而且等式約束的個數(shù)p必須小于設(shè)計變量的個數(shù) n0因為從理論上講，存在一個等式約束就得以用它消去一個設(shè)計變量，這樣便可降低優(yōu)化設(shè)計問題的維數(shù)。所以，當(dāng) p=n 時，即可由p個方程組中解得唯一的一組 x1,x2, ,xn 值。這樣，方案的選擇就成為唯一 的或確定的了。在解決工程問題時，約束條件是優(yōu)化設(shè)計獲得工程可接受設(shè)計方案的重要條件。不等 式約束及其有關(guān)概念，在優(yōu)化設(shè)計中是相當(dāng)重要的。每一個不等式約束(如g(x)&0)都把設(shè)計空間劃分成兩部分，一部分是滿足該不等式約束條件的，即 g(x)&g

7、t;0 。兩部分的分界面叫做約束面，即由g(x)=0的點集構(gòu)成。在二維設(shè)計空間中約束面是一條曲線或直線，在三維以上的 設(shè)計空間中則是一個曲面或超曲面。一個優(yōu)化設(shè)計問題的所有不等式約束的邊界將組成一 個復(fù)合約束邊界，如圖 8-3表示了一個二維問題的情況。其約束邊界所包圍的區(qū)域(圖中陰影線內(nèi))是設(shè)計空間中滿足所有不等式約束條件的部分，在這個區(qū)域中所選擇的設(shè)計變 量是允許采用的，我們稱這個區(qū)域為設(shè)計可行域或簡稱為可行域，記作 D=xgu(x) < 0u=1,2, ,m若某項設(shè)計中除了具有 m個不等式約束條件外，還應(yīng)滿足 p個等式約束條件時，即對 設(shè)計變量的選擇又增加了限制。如圖 8-3所示，當(dāng)

8、有一個等式約束條件 h(x1,x2)=0時， 其可行設(shè)計方案只允許在 D域內(nèi)的等式函數(shù)曲線的 AB段上選擇。因此，在一般的情形下， 優(yōu)化問題的設(shè)計可行域可表示為?g(x) & 0 u=1,2, ,m ?D=?u? ?hv(x)=0 v=1,2, ,p與此相反，除去可行域以外的設(shè)計空間稱為非可行域。據(jù)此，在可行域內(nèi)的任一設(shè)計 點都代表了一個可接受的設(shè)計方案，這樣的點叫可行設(shè)計點或內(nèi)點，如圖所示的x(1)點;在約束邊界上的點叫極限設(shè)計點或邊界點，如點 x(3),此時這個邊界所代表的約束叫作起 作用約束。x(2)點則稱為外點，即非可行點，該點為不可接受的設(shè)計方案，因為該點違反 了約束條件2,

9、即g2(x(2)>0。二、優(yōu)化計算的數(shù)值解法及收斂條件最優(yōu)化技術(shù)總體包含兩個方面，首先是根據(jù)實際的生產(chǎn)或科技問題構(gòu)造出優(yōu)化的數(shù)學(xué) 模型，再采取恰當(dāng)?shù)膬?yōu)化方法對數(shù)學(xué)模型進行求解。無論是無約束優(yōu)化問題還是約束優(yōu)化 問題，其本質(zhì)上都是求極值的數(shù)學(xué)問題。從理論上，其求解可用解析法，即微積分學(xué)和變 分法中的極值理論，但由于實際中的優(yōu)化數(shù)學(xué)模型多種多樣，往往目標(biāo)函數(shù)及約束函數(shù)都 是非線性的，采用解析法求解變得非常復(fù)雜和困難，甚至在有些時候無法求解數(shù)學(xué)模型。 因此，隨著優(yōu)化技術(shù)和電子計算機技術(shù)的不斷發(fā)展，逐漸產(chǎn)生了以計算機程序計算為主的 一種更為實用的求優(yōu)方法一數(shù)值計算法，通常也稱為求解非線性規(guī)劃的最

10、優(yōu)化方法。1 、數(shù)值計算法的迭代過程最優(yōu)化方法是與電子計算機及計算技術(shù)的發(fā)展緊密相聯(lián)系的，數(shù)值計算法的迭代過程 也是依賴于計算機的運算特點而形成的。所以，計算過程完全有別于解析法的求解過程。 優(yōu)化方法的迭代特點是：按照某種人為規(guī)定的邏輯結(jié)構(gòu)，以一定的格式反復(fù)的數(shù)值計算， 尋求函數(shù)值逐次下降的設(shè)計點，直到滿足規(guī)定的精度時才終止迭代計算，最后的設(shè)計點即 為欲求的最優(yōu)點，所得到的解是滿足規(guī)定精度的近似解。圖8-9二維優(yōu)化問題的迭代過程總體做法如圖8-9所示，由選定的初始點 x(0)出發(fā)，沿著某種優(yōu)化方法所規(guī)定的搜尋 方向s(0),以一定的步長a (0),按迭代格式產(chǎn)生第一個新的設(shè)計點x(1),x(1

11、)=x(0)+ a (0)s(0),且同時滿足 F(x(1)x(k+1)=x(k)+ a (k)s(k)式(8-4)稱為優(yōu)化計算的基本迭代公式。其中的第 k次搜尋方向s(k)及步長a (k)是 根據(jù)x(k)點目標(biāo)函數(shù)值和約束函數(shù)值等信息依據(jù)某種算法而確定的，其最終目的是使 F(x(k)F(x(1)>F(x(2)>(x(3)> >F(x(k)>很顯然，迭代點必將不斷向理論最優(yōu)點逼近，最后必將達到滿足預(yù)定精度要求的近似最優(yōu)點，記作x*。由迭代算法的基本迭代公式可見，優(yōu)化方法的主要問題乃是解決迭代方向s(k)(k=1,2,)和迭代步長a(k)(k=1,2,)的問題，由于

12、s(k)與a (k)的確定方法及特性的不同而構(gòu)成了不同的優(yōu)化方法，即最優(yōu)化方法。已有的各種優(yōu)化方法盡管在選取方向和 步長的原則上各有不同，但有一點是共同的，就是各種方法都是以保證目標(biāo)函數(shù)值穩(wěn)定的 下降為前提，按照基本迭代公式通過計算機進行迭代計算并最終獲得理論最優(yōu)點的近似解。(8-4)2 、迭代計算的終止準(zhǔn)則數(shù)值計算采用迭代法產(chǎn)生設(shè)計點的點列x(1),x(2),x(3), ,x(k),x(k+1),是無窮的，但在解決實際問題的時候必須在適當(dāng)?shù)臅r候結(jié)束這種迭代計算，這就是迭代終止準(zhǔn)則問題。優(yōu)化設(shè)計是要求出設(shè)計問題的最優(yōu)解，從理論上，人們當(dāng)然希望最終迭代點到達理論 的極小點，或者使最終迭代點與理論

13、極小點之間的距離足夠小時即可終止迭代。但這在實 際計算中是辦不到的，因為對于一個待求的優(yōu)化問題，其理論極小點在哪里是未知的。因 此，只能通過迭代計算獲得的點列所提供的各種信息來判斷是否應(yīng)該結(jié)束迭代計算，不同 的判斷依據(jù)就構(gòu)成了不同的終止準(zhǔn)則。由于實際問題具有多樣性，且迭代過程與目標(biāo)函數(shù)的性質(zhì)密切相關(guān)，所以很難建立一 個統(tǒng)一的迭代終止準(zhǔn)則，往往還需要根據(jù)實際計算的具體情況進行判斷和選擇。經(jīng)常被采 用的終止準(zhǔn)則如下：3 、點距準(zhǔn)則若相鄰的兩個迭代點x(k)、x(k-1)之間的距離已達到充分小，即滿足 x(k)-x(k- 1)< £ 1式中e (k)1 是給定的收斂精度，取 x為最優(yōu)

14、點，即x(k)=x*。4 、函數(shù)下降量準(zhǔn)則由于最優(yōu)點的很小鄰域里函數(shù)值的變化很小，所以當(dāng)相鄰兩次迭代點的函數(shù)值下下降 量已達到充分小時，預(yù)示著已很接近最優(yōu)點了當(dāng)F(x(k)當(dāng)F(x(k) ni時，采用函數(shù)相對下降量準(zhǔn)則F(x(k)-F(x(k-1)F(x(k) & & 2其中£ k)1,£ 2為收斂精度，取x(k)為最優(yōu)點，即x(=x*。5 、梯度準(zhǔn)則按函數(shù)極值理論，在極值點處函數(shù)的梯度為零。當(dāng)目標(biāo)函數(shù)在 x(k)點處的梯度的模已 達到充分小時，即 ? F(x(k) & £ 1可以認為x*x(k) , £ 1是收斂精度。這一準(zhǔn)則對

15、凸集凸函數(shù)是完全正確的，若為非 凸函數(shù)，有可能會誤把鞍點當(dāng)作最優(yōu)點。上述準(zhǔn)則是無約束優(yōu)化問題迭代收斂準(zhǔn)則。由于約束優(yōu)化問題與無約束優(yōu)化(8-5)(8-6) (8-7) (8-8)問題的最優(yōu)解的條件不同，所以迭代終止準(zhǔn)則也不一樣，但以上各終止準(zhǔn)則對約束優(yōu) 化問題的求解仍然有著重要的意義。一維優(yōu)化方法求解以為目標(biāo)函數(shù)f (x)最優(yōu)解的過程，稱為一維優(yōu)化，所使用的方法稱為一維優(yōu)化 方法。一維優(yōu)化方法是優(yōu)化方法中最簡單、最基本的優(yōu)化方法。他不僅用來解決一維目標(biāo) 函數(shù)的求最優(yōu)問題，而且常用于多維優(yōu)化問題在既定方向上尋求最優(yōu)步長的一維搜索。對于任一次迭代計算，總是希望從已知的點x(k)出發(fā)，沿給定的方向s

16、(k)搜索該方向上到目標(biāo)函數(shù)值最小的點x(k+1),即求步長因子 a (k)的最優(yōu)值，使f(x(k+1)=minf(x(k)+ a (k)s(k) a這種在確定的搜索方向s(k)上求步長因子a(k)的最優(yōu)取值使得目標(biāo)函數(shù)在該方向上 達到極小值的過程稱為一維搜索優(yōu)化計算方法或稱為單變量優(yōu)化計算方法。一維搜索最優(yōu)化方法一般需要分兩步進行：第一步是在s(k)方向上確定使得目標(biāo)函數(shù)值取得最小值的步長因子a (k)所在的區(qū)間；第二步是求出該區(qū)間內(nèi)的最優(yōu)步長因子a(k)。1 、搜索區(qū)間的確定所謂搜索區(qū)間就是沿給定的搜索方向s(k)上找出一個單峰區(qū)間a 1, a 2,即在該區(qū)間內(nèi)目標(biāo)函數(shù)值的變化只有一個峰值

17、，如圖8-10所示。單峰區(qū)間對于簡單的優(yōu)化問題，一般其搜索區(qū)間可以根據(jù)實際情況給定。但對于多維優(yōu)化問題 每次一維搜索之前都人為的給定搜索區(qū)間是不現(xiàn)實的，因此必須建立一定的方法，使計算 機在優(yōu)化的過程中自動地確定搜索區(qū)間。搜索區(qū)間的確定主要有進退法與外推法，本節(jié)介紹確定搜索區(qū)間的進退法。為了使該算法的敘述更加簡潔明了，這里直接以一維函數(shù)為例。設(shè)函數(shù)為y=f(x),給定初始點x1,選定恰當(dāng)?shù)牟介L為 h0,求其最小點x*。進退法確定搜索區(qū)間用進退法對搜索區(qū)間確定主要分為三步：1 、試探搜索由于最小點X*的位置是未知的，所以首先要試探最小點x*位于初始點x1的左方還是右方，然后再確定包含 x*在內(nèi)的搜

18、索區(qū)間a,b。x2=x1+h0 ,由初始點x1沿Ox軸正向到x2點，分別計算兩點的函數(shù)值y1=f(x1),y2=f(x2) 并 比較y1和y2值的大小，可分為兩種情況，如圖所示：(1)若 y2(2)若y2>y1,則極小點必在x1點左方，應(yīng)反向，即作后退搜索，以圖 8-11中虛線所示。2 、前進搜索由探索后的x2點，沿Ox正向繼續(xù)前進搜索，見圖。令 h=2h0,取得前進方向的第三個點x3=x2+h,對應(yīng)的函數(shù)值y3=f(x3)，比較后兩個點的函數(shù)值，有如下兩種情況：(1)若 y2y2曲線呈高一低一高的形態(tài)，如圖中虛線II所示。此時函數(shù)f(x)在x1,x3區(qū)間內(nèi)必有極小點，于是令a=x1,

19、b=x3從而構(gòu)成了搜索區(qū)間a,b。(2)若y2>y3,如圖中實線I所示，則應(yīng)該繼續(xù)向前搜索，令x1=x2,y1=y2,x2=x3,y2=y3,再將步長倍增，即 h=2h,構(gòu)成新點并計算其函數(shù)值x3=x2+h,y3=x3 。比較y2和y3的值，若有 y2>y3則轉(zhuǎn)(2),直到出現(xiàn) y2y3 成立,轉(zhuǎn)(1),確定搜索區(qū)間、后退搜索此時，需沿Ox負方向搜索，因此令 h0=-h0,并將x1和x2點的位置調(diào)換，即令x3=x1,y3=y1x1=x2,y1=y2x2=x3,y2=y3進行這樣的處理以后，后面的步驟和前進搜索的處理完全相同，只是最后確定搜索區(qū) 間時，令a=x3,b=x1。圖所示為進

20、退法確定搜索區(qū)間的程序流程圖。進退法確定搜索區(qū)間流程圖在確定了搜索區(qū)間a,b以后，一維優(yōu)化的任務(wù)就在于采用某種方法將此區(qū)間逐步縮 小，使其達到包含極小點 x*在內(nèi)的很小的鄰域，這個鄰域的大小由設(shè)計者根據(jù)實際問題而 定，一般規(guī)定為一個足夠小的正數(shù)稱£為收斂精度或迭代精度。主要有格點法與黃金分割法2 、格點法格點法是一種思路極為簡單白一維求優(yōu)法，設(shè)函數(shù) f(x)的初始搜索區(qū)間a , b,在 此區(qū)間內(nèi)取n個內(nèi)等分點x 1 , x 2 x n ,并計算函數(shù)值y 1 , y 2y n ,并比較取出最小y m=min (y i) , i=1 , 2 - n,并取 x m左右兩相鄰點 xm-1 , xm+1為新區(qū)間。 判