【文章內(nèi)容簡介】 必要條件,等式兩邊同乘 得,是對G的共軛方向。,三、共軛方向法,選定初始點 ，下降方向 和收斂精度ε，k=0。,沿 方向進行一維搜索，得,判斷 是否滿足，若滿足則打印,否則轉(zhuǎn)4。,提供新的共軛方向 ，使,置 ，轉(zhuǎn)2。,第五節(jié) 共軛梯度法,共軛梯度法是共軛方向法的一種，共軛向量有迭代點 的負梯度構(gòu)造出來，所以稱共軛梯度法。,從點 出發(fā)，沿G某一共軛方向 作一維搜索,到達,而在點 、 處的梯度分別為：,圖49 共軛梯度法的幾何說明,第六節(jié)變尺度法,變尺度法的基本思想：,前面討論的梯度法和牛頓法，它們的迭代公式可以看作下列 公式的特例。,變尺度法是對牛頓法的修正，它不是計算二階導數(shù)的矩陣和 它的逆矩陣，而是設法構(gòu)造一個對稱正定矩陣H來代替Hesse 矩陣的逆矩陣。并在迭代過程中，使其逐漸逼近H1 。,由于對稱矩陣H在迭代過程中是不斷修正改變的，它對于一 般尺度的梯度起到改變尺度的作用，因此H又稱變尺度矩陣。,一、尺度矩陣的概念,變量的尺度變換是放大或縮小各個坐標。,通過尺度變換可以把函數(shù)的偏心程度降低到最低限度。,對于一般二次函數(shù),如果進行尺度變換,則在新的坐標系中，函數(shù)的二次項變?yōu)?選擇這樣變換的目的：降低二次項的偏心程度。,若矩陣G是正定的，則總存在矩陣Q使,使得函數(shù)偏心度變?yōu)榱恪?用Q1 右乘等式兩邊，得,再用Q左乘等式兩邊，得,所以,說明二次函數(shù)矩陣G的逆矩陣，可以通過尺度變換矩陣Q 求得。,這樣，牛頓法迭代過程中的牛頓方向可寫成：,三、變尺度法的一般步驟,第七節(jié) 坐標輪換法,坐標輪換法是每次搜索只允許一個變量變化，其余變量保持 不變，即沿坐標方向輪流進行搜索的尋優(yōu)方法。,它把多變量的優(yōu)化問題輪流地轉(zhuǎn)化成單變量的優(yōu)化問題。,因此又稱變量輪換法。,其基本原理是將一個多維的無約束最優(yōu)化問題轉(zhuǎn)化為一系列較低維的最優(yōu)化問題來求解，簡單地說，就是先將(n1)個變量固定不動，只對第一個變量進行一維搜索得到最優(yōu)點x1（1）。然后，又保持(n1)個變量不變，再對第二個變量進行一維搜索到x2（1）等等。,圖4－12 坐標輪換法原理圖（動畫演示）,2. 搜索方向與步長的確定,（1）搜索方向的確定,對于第k輪第i次的計算,第k輪第I次的迭代方向，它輪流取n維坐標的單位向量。,3.搜索步長的確定,關于 值通常有以下幾種取法 （1）加速步長法 （2）最優(yōu)步長法 最優(yōu)步長法就是利用一維最優(yōu)搜索方法來完成每一次迭代，即 此時可以采用0.618方法或二次插值方法來計算 的值。,圖4－13 加速步長法的搜索路線,圖4－14 最優(yōu)步長法的搜索路線,4 . 坐標輪換法存在的問題,圖4－15 坐標輪換法在各種不同情況下的效能 （a）搜索有效；（b）搜索低效；（c）搜索無效,第八節(jié) Powell法（方向加速法）,Powell法是利用共軛方向可以加速收斂的性質(zhì)所形成的一種搜索算法。,一、共軛方向的生成,二、基本算法,三、改進的算法,在鮑維爾基本算法中，每一輪迭代都用連結(jié)始點和終點 所產(chǎn)生出的搜索方向去替換原來向量組中的第一個向量， 而不管它的“好壞”。,改進的算法是：首先判斷原向量組是否需要替換。如需要 替換，在產(chǎn)生新的向量。,第六章 約束優(yōu)化方法,根據(jù)求解方式的不同，可分為直接解法和間接解法兩類。,機械優(yōu)化設計的問題，大多屬于約束優(yōu)化設計問題，其數(shù)學模型為：,直接解法是在滿足不等式約束的可行設計區(qū)域內(nèi)直接求 出問題的約束最優(yōu)解。,屬于這類方法的有：隨機實驗法、隨機方向搜索法、 復合形法、可行方向法等。,間接解法是將約束優(yōu)化問題轉(zhuǎn)化為一系列無約束優(yōu)化問題來 解的一種方法。,由于間接解法可以選用已研究比較成熟的無約束優(yōu)化方法， 并且容易處理同時具有不等式約束和等式約束的問題。因而在機械優(yōu)化設計得到廣泛的應用。,間接解法中具有代表性的是懲罰函數(shù)法。,直接解法的基本思想：,在由m個不等式約束條件gu(x)≤0所確定的可行域φ內(nèi)，選擇一個初始點x(0)，然后確定一個可行搜索方向S，且以適當?shù)牟介L沿S方向進行搜索，取得一個目標函數(shù)有所改善的可行的新點x(1)，即完成了一次迭代。以新點為起始點重復上述搜索過程，每次均按如下的基本迭代格式進行計算：,x(k+1)＝ x(k)+α(k) S(k) (k=0,1,2,…) 逐步趨向最優(yōu)解，直到滿足終止準則才停止迭代。,直接解法的原理簡單，方法實用，其特點是：,1）由于整個過程在可行域內(nèi)進行，因此，迭代計算不論 何時終止，都可以獲得比初始點好的設計點。,2）若目標函數(shù)為凸函數(shù)，可行域為凸集，則可獲得全域 最優(yōu)解，否則，可能存在多個局部最優(yōu)解，當選擇的初始 點不同，而搜索到不同的局部最優(yōu)解。,3）要求可行域有界的非空集。,a) 可行域是凸集；b)可行域是非凸集,間接解法的求解思路：,將約束函數(shù)進行特殊的加權(quán)處理后，和目標函數(shù)結(jié)合起來， 構(gòu)成一個新的目標函數(shù)，即將原約束優(yōu)化問題轉(zhuǎn)化為一個 或一系列的無約束優(yōu)化問題。,新目標函數(shù),加權(quán)因子,然后對新目標函數(shù)進行無約束極小化計算。,第二節(jié)隨機方向法,隨機方向法的基本思路：,在可行域內(nèi)選擇一個初始點，利用隨機數(shù)的概率特性，產(chǎn) 生若干個隨機方向，并從中選擇一個能使目標函數(shù)值下降 最快的隨機方向作為搜索方向d。,從初始點x0出發(fā)，沿d 方向以一定步長進行搜索，得到新點 X，新點x應滿足約束條件且f(x)f(x0)，至此完成一次迭代。,基本思路如圖所示。,隨機方向法程序設計簡單，搜索速度快，是解決小型機械優(yōu) 化問題的十分有效的算法。,一、隨機數(shù)的產(chǎn)生,下面介紹一種常用的產(chǎn)生隨機數(shù)的數(shù)學模型,驟計算：,令,在任意(a,b)區(qū)間內(nèi)的隨機數(shù),二、初始點的選擇,隨機方向法的初始點x0必須是一個可行點，既滿足全部不等式約束條件。,初始點可以通過隨機選擇的方法產(chǎn)生。,1）輸入設計變量的下限值和上限值，即,2）在區(qū)間（0，1）內(nèi)產(chǎn)生n個偽隨機數(shù),3）計算隨機點x的各分量,4）判別隨機點x是否可行，若隨機點可行，用x代替x0為 初始點；若非可行點，轉(zhuǎn)到步驟2）重新產(chǎn)生隨機點，只 到可行為止。,三、可行搜索方向的產(chǎn)生,產(chǎn)生可行隨機方向的方法：從k個隨機方向中， 選取一個 較好的方向。其計算步驟為：,2)取一試驗步長a0，按下式計算k個隨機點,3）檢驗k個隨機點是否為可行點，除去非可行點，計算余下 的可行點的目標函數(shù)值，比較其大小，選出目標函數(shù)最小的點 XL 。,4)比較XL 和X0兩點的目標函數(shù)值，若f(XL) f(X0)，則步長α0 縮小，專步驟1）重新計算，直至f(XL) f(X0)為止。如果α0 縮小到很小，仍然找不到一個XL，使f(XL) f(X0)則說明X0是一個局部極小點，此時可更換初始點，轉(zhuǎn)步驟1）。,產(chǎn)生可行搜索方向的條件為：,則可行搜索方向為：,四、搜索步長的確定,步長由加速步長法確定。,五、隨機方向法的計算步驟,第三節(jié)復合形法,復合形法是求解約束優(yōu)化問題的一種重要的直接解法。,它的基本思路是在可行域內(nèi)構(gòu)造一個具有k個頂點的初始復合形。對該復合形各頂點的目標函數(shù)值進行比較，找到目標函數(shù)最大的頂點（最壞點），然后按一定的法則求出目標函數(shù)值有所下降的可行的新點，并用此點代替最壞點，構(gòu)成新的復