[所有分類]第五章 約束優化方法-全文預覽

　　

【正文】 子 r1(k) 和 r2(k)的值 ， 求得一序列的無約束最優解 ， 不斷地逼近原約束優化問題的最優解 。 55內懲罰函數法 將有約束的優化問題轉化為無約束優化問題來求解 。 ?0 x 1 x 2 x k d k x k+1 g 2 ( x )=0 g 1 ( x )=0 a* d k a M d k x ??圖 513容許的區間 收斂條件 2[ ( ) ]k T kfs e?e? ???????x2） 設計點 xk滿足庫恩 塔克條件 1[ ( ) ( ) 00 ( 1 , 2 , , )jkkjjjjfgjJ????? ? ? ???? ????xx 1） 設計點 xk及約束允差 滿足 ? 例 :已知約束優化問題 (課堂練習 ) 試從第 k次的迭代點 Xk=[1 2]T出發，沿由 (1,1)區間隨機數 ，完成一次迭代，獲取一個新的迭代點 Xk+1，并作圖畫出目標函數的等值線、可行域和本次迭代的搜索路線。 0x1x2xkskxk + 1g2( x ) = 0g1( x ) = 0a * sk圖 511迭代點為可行點 取到約束邊界的最大步長 從 xk點出發，沿 sk方向進行一維最優化搜索， 得到的新點 x為不可行點 。 若適時約束面是切面，每次搜索到約束面的交集時，移至另一個約束面，直至收斂到最優點。 0x1x2x0xkdkxk + 1g2( x ) =0g1( x ) =00()f?? x圖 59最優步長法 邊界反彈法 ： 第一次搜索為負梯度方向，終止于邊界。 圖 58 適用可行方向的幾何解釋 三 .可行方向法的搜索策略 第一步迭代都是從可行的初始點 出發 ， 沿點的負梯度 方向 ， 將初始點移動 到某一個約束面 （ 只有一個起作用的約束時 ） 上 , 或約束面的交集 （ 有幾個起作用的約束時 ） 上 。 圖 58（ a）是 J=1的情況，適用可行方向 必須在一個既與 又與 成銳角的扇形空間 x 內。實際上，可行點與非可行點的標志 是該點的約束函數值。 或簡記為 這說明，凡與目標函數負梯度矢量 成銳角的方向 都能滿足適用性要求（圖 56 ）。 由上述可行方向法的基本搜索過程可知，如何尋求 適用可行方向 和 適當的步長 ， 使迭代點逼近約束最優點，這是可行方向法要解決的兩個基本問題。一般地，對于不在約束邊界上的域內點 X(K)，下一次迭代總沿該點的負梯度方向進行一維搜索， a (K) 取為最優步長 a*，即 a (K) ? a*，其迭代式為 直至迭代點落在約束邊界上或越出某約束邊界為止 。沿 S(0)方向進行一維搜索，得最優步長為 a(0)，則第一個迭代點為 X(1) 所在的位置可能是下述三種情況之一 : ? ① 在可行域的內部； ? ② 在容許的約束邊界上； ? ③ 已越出可行域，即落入非可行域。 同時滿足以上兩個條件的方向，稱為 適用可行方向。 具體算法由兩部分組成： 1 確定一個適當的步長； 2 選擇 一 個可行方向。 54 可行方向法 從任一可行點 X (K) 出發，尋找一個恰當的方向 S(K) 和 一個合適的步長因子 a(K)，于是產生的新迭代點為 使其滿足 即在每次迭代中都保證搜索方向是在可行域內進行（ 稱為可行方向 ），并且目標函數值必須穩步地下降方向（ 稱為適用方向 ）。 （ 2）復合形法適用于僅含不等式約束的問題。對于本題， 不滿足迭代終止條件，需繼續迭代。 求 4個點的目標函數值： 知 . 計算除壞點外所有頂點的中心 XC： 經檢驗 XC在可行域內。 (課堂練習 ) 解： n=2,取復合形頂點數 k=2n=4。 2）映射點次于壞點 : F(X(R)) ＞ F(X(H)) 這種情況由于映射點過遠引起的，減半映射系數，若有F(X(R)) F(X(H))，這又轉化為第一種情況。 （ 3）計算壞點外的其余各頂點的中心點 X(s)。若新的 X(q+1)點仍為非可行點 ， 按上式再產生 X(q+1)， 使它更向 X(s)靠攏 ， 最終使其成為可行點 。 將非可行點調入可行域 用上述方法產生的 K個隨機點，并不一定都是可行的。這第一個點記作 X (1)。對于維數較低的優化問題，由于頂點數目較少，可試湊幾個可行點作為復合形的頂點。 計算各個頂點函數值 F(X(1))、 F(X(2))、 F(X(3))， 找出最大值 ， 記為壞點 X(H)。 一般情況下，映射點的函數值比壞點的函數值要小，即 F(X(R)) F(X(H))。 以新的復合形頂點 , 代替原復合形中的最壞點 ， 組 成新的復合形 ， 以不斷的迭代 ， 使新復合形逐漸逼近 最優點 。 在用于求解約束問題的復合形法中 ， 復合形各頂點的選擇和替換 ， 不僅要滿足目標函數值的下降 ， 還應當滿足所有的約束條件 。 （以下過程略） 目標函數值下降 隨機方向法 方法評價： 優點： 1 對目標函數無性態要求； 2 收斂快 （ 當 隨機方向限定數 m 足夠大時 ） ； 3不受維數影響 ， 維數愈高 ， 愈體現優點 。 生成兩個偽隨機數 由此得第一個隨機方向為： 2) 求第一個迭代點 第一個迭代點表達式為： 式中 a為步長 。 約束隨機方向法的搜索方向比較靈活 ， 當預定的隨機方向限定數 m足夠大時 ， 無 “ 病態 ”問題出現 ， 一般都能求出最優點 。 (2) 當在某個轉折點處沿 m個（預先限定的次數）隨機方向試探均失敗，如圖中點 X (2)，則說明以此點為中心， h0 為半徑的圓周上各點都不是適用、可行的。 若兩者均滿足， X作為新的起點， 繼續按上述迭代式在 S(1)方向上取得新點。 如圖 51所示的二維問題 。 隨機方向法 ， 是約束最優化問題的一種常用的 直接求解方法 。 間接法主要包括：內點罰函數法 、 外點罰函數法和混合罰函數法 、 擴展內懲罰函數法 。 其迭代過程中，每一次的新迭代點 X(K+1)都要經過可行性 和 適用性 條件的檢驗。 思路 :是在 m個不等式約束條件所確定的可行域內，選擇一個初始點，然后決定可行搜索方向 sk且以適當的步長 αk ，進行搜索，得到一個使目標函數值下降的可行的新點，即完成一次迭代。否則，將由于所選擇的初始點的不同，而探索到不同的局部最優解上。 58 擴展內懲罰函數法 167。 54 可行方向法 167。第五章 約束優化方法 167。 53 復合形法 167。 57 混合懲罰函數法 167。 只要由約束條件所決定的可行域是一個凸集，目標函數是凸函數，其約束最優解就是全域最優解。 ) （ 1）直接法 直接解法通常適用于 僅含不等式約束 的問題。 直接法主要包括：隨機方向法 、 復合形法和可行 方向法 。 通過不斷調整加權因子 ， 產生一系列 Φ函數的極小點序列 xk* (r1k,r2k) k= 0,1,2… ， 逐漸收斂到原目標函數的約束最優解 。 但要確保： ① 新迭代點在可行域中； ② 目標函數值的下降性 。 把隨機數 ， 轉化為另一區間 （ 1， 1） 之間的隨機數 然后由隨機數 yi構成以下隨機方向 由于隨機數 yi在區間（ 1， 1）內產生，所構成的隨機方向 矢量 S一定是在超球面空間里均勻分布且模等于 1的單位矢量。 如此循環 ， 點列 X (1)、 X (2)、 …… 必將逼近于約束最優點 X*。試探成功就前進，試探失敗再重新產生新的隨機方向。對于性態不好的目標函數或可行域有狹長彎道的問題， m應取較大的值，以提高解題的成功率。 第一次迭代 1) 產生兩個偽隨機數，求出第一個隨機方向。 相應的目標函數值為 : 第二次迭代 以 X1為初始點，繼續使用 e1方向直到不滿足可行性和適用性條件，再重新生成隨機搜索方向 e2。 不需計算目標函數的梯度 ， 而是 靠選取復合形的頂點井比較各頂點處目標函數值的大小 ，來尋找下一步的探索方向 的 。 一 、 復合形法基本思想 : 在 n 維空間中，由 n+1≤ k≤2n 個點組成的多（邊）面體稱為復合形。 取次好點和好點連線的中點為 X(S)。 在可行域內任選三個初始點 X(1)、 X(2)、 X(3)， 連接這三點形成一個三角形 ， 此三角形稱為初始復合形 。 二、初始復合形的構成 復合形的頂點 K≥n+1個。 復合形的產生可以： （ 1） 人工選擇初始復合形 （ 2） 隨機產生初始復合形 xi= ai +ξi (bi ai)