1、會計學1約束約束(yush)優(yōu)化方法課件優(yōu)化方法課件第一頁，共24頁。第1頁/共24頁第二頁，共24頁。npjxhmixgtsRDxminf(x)jin, 2, 10)(, 2, 10)(. .第2頁/共24頁第三頁，共24頁。（1). 直接(zhji)法 直接法是在滿足約束條件的可行域內(nèi)直接求出問題的約束最優(yōu)解，整個求解(qi ji)過程在可行域內(nèi)進行，因而所得的任一方案都是可行的。原理比較簡單，方法比較適用。 包括：網(wǎng)格法、分層降維枚舉法、復合形法、隨機試驗法、隨機方向法、可變?nèi)莶罘ê涂尚蟹较蚍?。?頁/共24頁第四頁，共24頁。 間接法是將約束(yush)優(yōu)化問題先轉(zhuǎn)變成一系列無約束(y

2、ush)優(yōu)化問題，用無約束(yush)優(yōu)化方法來求解?？梢?，無約束(yush)優(yōu)化方法是約束(yush)優(yōu)化方法的基礎(chǔ)。 間接(jin ji)法包括：罰函數(shù)法、內(nèi)點罰函數(shù)法、外點罰函數(shù)法、混合罰函數(shù)法、精確罰函數(shù)法、廣義乘子法、廣義簡約梯度法和約束變尺度法。 第4頁/共24頁第五頁，共24頁。3.2.2 約束(yush)隨機方向法 基本原理基本原理對于(duy)求解 nRxminf(x)m,1,2,u0(x)gs.t.u的約束非線性規(guī)劃(guhu)問題， 第5頁/共24頁第六頁，共24頁。采用約束隨機方向搜索法的迭代(di di)格式為 1,2,ksxx(k)(k)1)(k式中 (k)s第k次

3、迭代(di di)的隨機搜索方向;所用(su yn)的步長因子。 第6頁/共24頁第七頁，共24頁。 在約束可行域內(nèi)選取一個初始點x(0)。為了確定本次迭代(di di)的搜索方向，以若干個不同方向的向量x進行試驗性的探索，若f(x(0)+ x)f(x(0)，則以x為搜索方向，取適當步長因子，在不破壞約束條件的情況下，前進一步，取得新點x，若f(x)f(x(0)，則將起始點移至x點，重復前面的過程。否則需將步長因子縮短，直至取得一個好的可行點。如此周而復始，直至迭代(di di)步長已經(jīng)很小時(即相鄰二次迭代(di di)點已相距很近)，就結(jié)束計算過程，取得約束最優(yōu)解。 第7頁/共24頁第八頁

4、，共24頁。第8頁/共24頁第九頁，共24頁。 顯然，約束隨機方向(fngxing)搜索法的關(guān)鍵是如何確定初始(ch sh)點、搜索(su su)方向和搜索步長，而這些都需要涉及隨機數(shù)問題。 一、隨機數(shù)的產(chǎn)生一、隨機數(shù)的產(chǎn)生 在一般計算機上都備有過程或子程序，調(diào)用它即可得0，1區(qū)間內(nèi)均勻分布的偽隨機數(shù)列。若已產(chǎn)生了0，1區(qū)間上的偽隨機數(shù)r，則通過變換可以求得任意區(qū)間a，b內(nèi)的偽隨機數(shù)R R=a+r(b-a) 第9頁/共24頁第十頁，共24頁。二、初始二、初始(ch sh)點的選擇點的選擇 通常(tngchng)可以有兩種確定方法： (1)決定性的方法(fngf) 即在可行域內(nèi)人為地確定一個可行

5、的初始點。當約束條件比較簡單時，這種方法是可用的。但當約束條件比較復雜時，人為選擇一個可行點就比較困難，建議用下面的隨機選擇方法。 (2)隨機選擇方法 即利用計算機產(chǎn)生的偽隨機數(shù)來選擇一個可行的初始點x(0)。 第10頁/共24頁第十一頁，共24頁。需要輸入對設計(shj)變量估計的上限值和下限值，即 aixibi i=1,2,n這樣，所產(chǎn)生(chnshng)的隨機點的各分量為 xi(0) = ai+ri(bi - ai ) i=1,2,n式中 ri0，1區(qū)間(q jin)內(nèi)服從均勻分布的偽隨機數(shù)。 第11頁/共24頁第十二頁，共24頁。這樣(zhyng)產(chǎn)生的隨機點不一定滿足所有的約束條件。

6、因此還必須經(jīng)過可行性條件的檢驗。若是可行點，即可作為初始點x(0)。若為非可行點，則另取偽隨機數(shù)再產(chǎn)生一個隨機點。直到產(chǎn)生一個可行的隨機點為止。采用這種方法來產(chǎn)生可行的初始點，對于中等規(guī)模的優(yōu)化設計問題都比較適用。第12頁/共24頁第十三頁，共24頁。三、隨機搜索方向三、隨機搜索方向(fngxing)的產(chǎn)生的產(chǎn)生 利用(lyng)偽隨機數(shù)可以用不同的方法產(chǎn)生隨機搜索方向s。以二維問題(wnt)為例， 若r1(j) 、r2(j)為一1，1區(qū)間內(nèi)均勻分布的偽隨機數(shù)，則可用下式產(chǎn)生N個隨機單位向量 N1,2,jrr)(r)(r1ejj1/22(j)22(j)1(j)(2)(1第13頁/共24頁第十四

7、頁，共24頁。取得N個隨機(su j)單位向量后，可按下式產(chǎn)生N個隨機(su j)試驗點x(j) =x(0) +H0 e(j) j=1,2,N式中H0 試驗步長因子，一般可取為0.1或0.01， 或者(huzh)更小一點。 然后檢查試驗點是否為可行點，計算可行試驗點的目標函數(shù)值，比較它們的大小(dxio)，選出其中目標函數(shù)值最小的點x(L)，即 f(x(L)=min f(x(j), j=1,2,N；非可行點除外若f(x(L)f(x(0)，則取x(0) 和x(L)的連線方向作為按索方向，即 s= x(L) - x(0) 第14頁/共24頁第十五頁，共24頁。對于2維問題，其單位向量e(j) 的端

8、點分布于單位圓的圓周上。為了盡可能獲得較優(yōu)的搜索方向，應選取適當?shù)牟介L因子H0。將單位圓縮小或放大，使試驗點落在以H0 e(j)為半徑的圓周上。H0太小，搜索方向的選擇將受目標函數(shù)局部性質(zhì)的影響，若H0太大，同樣數(shù)量的試驗點分布在很大圓周上，降低了密度，取得較優(yōu)的搜索方向的機會也就減少(jinsho)了，影響了收斂速度。 第15頁/共24頁第十六頁，共24頁。 對于三維問題，其隨機單位向量 e(j) 的端點位于以單位長為半徑(bnjng)的球面上。對于n維問題，則位于超球面上。在這種情況下，其單位隨機向量 e(j) 的分量 ei(j) 按下式計算： N1,2,jnir)(r)(rre1/2jn

9、2(j)22(j)1(j)i(j)i, 2 , 1)(2)(式中 r1(j) 、r2(j)、rn(j)1，1區(qū)間(q jin)內(nèi)的n個偽隨機數(shù)。 第16頁/共24頁第十七頁，共24頁。綜上所述，在約束隨機(su j)方向搜索法中，產(chǎn)生隨機(su j)搜索方向s時應滿足的條件是N,1,2,j)minf()f(j)(L)xxm,1,2,u0)(g(L)uxf(x(L)f(x(0)第17頁/共24頁第十八頁，共24頁。 四、搜索(su su)步長的確定 沿已確定的搜索(su su)方向s進行搜索(su su)，從而取得一個目標函數(shù)值有所下降且滿足約束條件的新的迭代點。其計算公式為0,1,2,ksxx

10、(k)(k)1)(k式中 x(k) 已確定(qudng)的第k一1次迭代點；(k)s 第k次迭代的隨機搜索方向;所用的步長因子。 第18頁/共24頁第十九頁，共24頁。步長因子步長因子(ynz)的確定有兩種方法：的確定有兩種方法：（1）定步長法， 即步長按規(guī)定長度等差遞增，只要所得新點的目標函數(shù)值是下降的且滿足約束條件，就在原基礎(chǔ)上增加一個規(guī)定的步長向前移動，直至違背了約束條件或目標函數(shù)的下降性條件時為止(wizh)，于是迭代點由起始點移到新點。 （2）變步長法， 即步長按一定的倍增系數(shù)等比遞增或遞減。例如以1. 3倍遞增，那么(n me)每次向前的移動步長為前一次的13倍。這樣做可以減少計算

11、工作量，提高計算效率。 第19頁/共24頁第二十頁，共24頁。第20頁/共24頁第二十一頁，共24頁。522算法算法(sun f)的步驟的步驟 s1 選擇初始點 x(0)，檢驗(jinyn)其是否滿足可行性條件。若滿足則進行下一步；否則重新選擇初始點。 s2 產(chǎn)生N個隨機(su j)單位向量 e(j) (j1，2，N)，然后在設計空間中以 x(0) 為中心，H0為半徑的超球面上產(chǎn)生N個隨機(su j)試驗點 x(j)，即x(j) =x(0) +H0 e(j) j=1,2,N 檢查試驗點的可行性、計算可行試驗點的目標函數(shù)值并選出其中最小值點 x(L)。若滿足 f(x(L)f(x(0) 條件，則確

12、定可行搜索方向 s= x(L) - x(0)，否則重復上述過程，重新產(chǎn)生N個隨機試驗點，或者將試驗步長縮小到0.7 H0，再確定可行搜索方向s。 第21頁/共24頁第二十二頁，共24頁。s3 從初始點x(0)出發(fā)(chf)，沿可行搜索方向s先以13 H0的步長移動若新點是可行點，且目標函數(shù)值下降，則繼續(xù)以13加大步長前進。否則以07的步長移動。直到目標函數(shù)值不再下降同時又不違背約束條件時為止，即完成了一次迭代，將搜索終點x，作為下次搜索的初始點x(0)。s4 當一次迭代的初始(ch sh)點與終點的函數(shù)值達到1(0)(0)f()f()f(xxx和其步長達到(d do)2(0) xx時，即結(jié)束搜索過程。其最優(yōu)解為： x*= x， f(x* ) f(x )。否則轉(zhuǎn)向第2步。第22頁/共24頁第二十三頁，共24頁。隨機方向搜索隨機方向搜索(su su)法的特點法的特點（1）隨