1、第六章 約束優(yōu)化方法4.1概述返回4.2隨機方向法4.3復(fù)合形法4.4可行方向法重點4.5懲罰函數(shù)法4.6增廣乘子法4.74.8廣義簡約梯度法4.9二次規(guī)劃法自學(xué) 不作要求7/17/20226.1 概述問題的提出機械優(yōu)化設(shè)計中的問題，大多數(shù)屬于約束優(yōu)化設(shè)計問題，其一般數(shù)學(xué)模型為： 求解上式的方法稱為約束優(yōu)化方法。7/17/2022直接解法和間接解法根據(jù)有約束優(yōu)化問題求解方式的不同，可分為直接解法，間接解法。直解解法通常適用于僅含不等式約束的問題，基本思路如右圖所示。直接解法的搜索路線7/17/2022即在 個不等式約束條件所確定的可行域內(nèi)，選擇一個初始點 ，然后決定可行搜索方向 ，且以適當(dāng)?shù)牟?/p>

2、長 ，沿方向進行搜索，得到一個使目標(biāo)函數(shù)值下降的可行的新點 ，即完成一次迭代。再以新點為起點，重復(fù)上述搜索過程，滿足收斂條件后，迭代終止。7/17/2022每次迭代計算均按以下基本迭代格式進行： 式中 步長； 可行搜索方向。可行搜索方向是指，當(dāng)設(shè)計點沿該方向作微量移動時，目標(biāo)函數(shù)值將下降，且不會越出可行域。產(chǎn)生可行搜索方向的方法將由直接解法中的各種算法決定。7/17/2022直接解法的原理簡單，方法實用。其特點是：由于整個求解過程在可行域內(nèi)進行，因此，迭代計算不論何時終止，都可以獲得一個比初始點好的設(shè)計點。若目標(biāo)函數(shù)為凸函數(shù)，可行域為凸集，則可保證獲得全域最優(yōu)解。否則，因存在多個局部最優(yōu)解，當(dāng)

3、選擇的初始點不相同時，可能搜索到不同的局部最優(yōu)解。因此，常在可行域內(nèi)選擇幾個差別較大的初始點分別進行計算，以便從求得的多個局部最優(yōu)解中選擇更好的最優(yōu)解。要求可行域為有界的非空集，即在有界可行域內(nèi)存在滿足全部約束條件的點，且目標(biāo)函數(shù)有定義。7/17/2022間接解法有不同的求解策略。其中一種方法的基本思路是將約束優(yōu)化問題中的約束函數(shù)進行特殊的加權(quán)處理，然后和目標(biāo)函數(shù)結(jié)合，構(gòu)成一個新的目標(biāo)函數(shù)，即將原約束優(yōu)化問題轉(zhuǎn)化成為一個或一系列的無約束優(yōu)化問虬再對新的目標(biāo)函數(shù)進行無約束優(yōu)化計算，從而間接地搜索到原約束問題的最優(yōu)解。7/17/2022因此間接解法的基本迭代過程是，首先將一般約束優(yōu)化問題轉(zhuǎn)化成新的

4、無約束目標(biāo)函數(shù) 式中 轉(zhuǎn)換后的新目標(biāo)函數(shù)； 分別為約束函數(shù) 和 經(jīng)過加權(quán)處理后構(gòu)成的某種形式的復(fù)合函數(shù)或泛函數(shù)； 加權(quán)因子。 然后對 進行無約束極小化計算。7/17/2022由于在新目標(biāo)函數(shù)中包含了各種約束條件，而且在求極值的過程中還將改變加權(quán)因子的大小。因此可以不斷地調(diào)整設(shè)計點，使其逐步逼近約束邊界。從而間接地求得原約束問題的最優(yōu)解。間接解法框圖7/17/2022間接解法例題求約束優(yōu)化問題 的最優(yōu)解。解: 易知該問題理論上的最優(yōu)解為：由該問題的幾何意義（右圖）可知，約束最優(yōu)點 為目標(biāo)函數(shù)等值線與等式約束函數(shù)（直線）的切點，7/17/2022用間接解法求解時，可取 ，轉(zhuǎn)換后的新目標(biāo)函數(shù)為從而可

5、以用解析法求 的極小值，即令 得到方程組7/17/2022解此方程組，求得的無約束最優(yōu)解為：右圖表示出最優(yōu)點 為新目標(biāo)函數(shù)等值線族的中心。7/17/2022間接解法是目前在機械優(yōu)化設(shè)計中得到廣泛應(yīng)用的一種有效方法。其特點是：由于無約束優(yōu)化方法的研究日趨成熟，已經(jīng)研究出不少有效的無約束最優(yōu)化方法和程序，使得間接解法有了可靠的基礎(chǔ)。目前，這類算法的計算效率和數(shù)值計算的穩(wěn)定性也都有較大的提高。可以有效地處理具有等式約束的約束優(yōu)化問題。間接解法存在的主要問題是，選取加權(quán)因子較為困難。加權(quán)因子選取不當(dāng)，不但影響收斂速度和計算精度，甚至?xí)?dǎo)致計算失敗。7/17/2022求解約束優(yōu)化設(shè)計問題的方法：屬于直接

6、解法的隨機方向法、復(fù)合形法、可行方向法、廣義簡約梯度法；屬于間接解法的懲罰函數(shù)法，增廣乘子法；另一類解法線性逼近方法，二次規(guī)劃法。 返回7/17/20226.2 隨機方向法概述隨機方向法是一種原理簡單的直接解法。它的基本思路是在可行域內(nèi)選擇一個初始點，利用隨機數(shù)的概率特性，產(chǎn)生若干個隨機方向，并從中選擇一個能使目標(biāo)函數(shù)值下降最快的隨機方向作為可行搜索方向，記作 。從初始點 出發(fā)，沿 方向以一定的步長進行搜索，得到新點 ，新點 應(yīng)滿足約束條件： ， 且 。至此完成一次迭代。然后，將起始點移至 ，即令 。重復(fù)以上過程，經(jīng)過若干次迭代計算后，最終取得約束最優(yōu)解。7/17/2022隨機方向法的算法原理

7、7/17/2022隨機方向法的的特點：對目標(biāo)函數(shù)的性態(tài)無特殊要求，程序設(shè)計簡單，使用方便。由于可行搜索方向是從許多髓機方向中選擇的使目標(biāo)函數(shù)下降最快的方向，加之步長還可以靈活變動，所以此算法的收斂速度比較快。若能取得一個較好的初始點，迭代次數(shù)可以大大減少。是求解小型的機械優(yōu)化設(shè)計問題的一種十分有效的算法。7/17/2022隨機數(shù)的產(chǎn)生在隨機方向法中，為產(chǎn)生可行的初始點及隨機方向，需要用到大量的 和 區(qū)間內(nèi)均勻分布的隨機數(shù)。在計算機內(nèi)，隨機數(shù)通常是按一定的數(shù)學(xué)模型進行計算后得到的。這樣得到的隨機數(shù)稱偽隨機數(shù)，它的特點是產(chǎn)生速度快，計算機的內(nèi)存占用少，并且有較好的概率統(tǒng)計特性。7/17/2022產(chǎn)

8、生偽隨機數(shù)的方法很多，下面是一種常用的產(chǎn)生偽隨機數(shù)的數(shù)學(xué)模型。首先令 ，取 （ 為小于 的正奇數(shù)），然后按以下步驟計算令 若 ，則 ；若 ，則 ；若 ，則 ；則 即為 區(qū)間內(nèi)的偽隨機數(shù)。利用 ，容易求得任意區(qū)間 內(nèi)的偽隨機數(shù)，其計算公式為7/17/2022初始點的選擇隨機方向法的初始點 必須是一個可行點，即滿足全部不等式約束條件： 的點。當(dāng)約束條件較為復(fù)雜，用人工不易選擇可行初始點時，可用隨機選擇的方法來產(chǎn)生。其計算步驟如下：輸人設(shè)計變量的下限值和上限值，即7/17/2022在區(qū)間 內(nèi)產(chǎn)生 個偽隨機數(shù) 。計算隨機點x的各分量判別隨機點 是否可行，若隨機點 為可行點，則取初始點 ；若隨機點 為非

9、可行點，則轉(zhuǎn)步驟2重新計算，直到產(chǎn)生的隨機點是可行點為止。7/17/2022可行搜索方向的產(chǎn)生在隨機方向法中，產(chǎn)生可行搜索方向的方法是從 個隨機方向中，選取一個較好的方向。其計算步驟為：在 區(qū)間內(nèi)產(chǎn)生偽隨機數(shù) 再按下式計算隨機單位向量7/17/2022取一試驗步長 ，按下式計算 個隨機點 顯然， 個隨機點分布在以初始點 為中心，以試驗步長 為半徑的超球面上。檢驗 個隨機點 是否為可行點，除去非可行點，計算余下的可行隨機點的目標(biāo)函數(shù)值，比較其大小，選出目標(biāo)函數(shù)值最小的點 。比較 和 兩點的目標(biāo)函數(shù)值，若 ，則取 和 的連線方向作為可行搜索方向；若 ，則將步長 縮小，轉(zhuǎn)步驟1重新計算，直至 為止。

10、如果 縮小到很小，仍然找不到一個 ，使 則說明 是一個局部極小點，此時可更換初始點，轉(zhuǎn)步驟1。7/17/2022綜上所述，產(chǎn)生可行搜索方向的條件可概括為，當(dāng) 點滿足 則可行搜索方向為7/17/2022搜索步長的確定可行搜索方向 確定后，初始點移至 點，即 ，從 點出發(fā)沿 方向進行搜索，所用的步長 一般按加速步長法來確定。加速步長法是指依次迭代的步長按一定的比例遞增的方法。各次迭代的步長按下式計算： 式中 步長加速系數(shù)，可取 ； 步長，初始步長取 。7/17/2022隨機方向法的計算步驟隨機方向法的計算步驟如下：選擇一個可行的初始點 ；產(chǎn)生 個 維隨機單位向量 ；取試驗步長 ，計算出 個隨機點

11、；在 個隨機點中，找出的隨機點 ，產(chǎn)生可行搜索方向 。從初始點 出發(fā)，沿可行搜索方向 以步長 進行迭代計算，直至搜索到一個滿足全部約束條件，且目標(biāo)函數(shù)值不再下降的新點 。7/17/2022若收斂條件 得到滿足，迭代終止。約束最優(yōu)解為 。否則，令 轉(zhuǎn)步驟2。7/17/2022隨機方向法的程序框圖（P126）返回7/17/20226.3 復(fù)合形法概述復(fù)合形法的基本思路：在可行域內(nèi)構(gòu)造一個具有是個頂點的初始復(fù)合形。對該復(fù)合形各頂點的目標(biāo)函數(shù)值進行比較，找到目標(biāo)函數(shù)值最大的頂點（稱最壞點），然后按一定的法則求出目標(biāo)函數(shù)值有所下降的可行的新點，并用此點代替最壞點，構(gòu)成新的復(fù)合形，復(fù)合形的形狀每改變一次，

12、就向最優(yōu)點移動一步，直至逼近最優(yōu)點。7/17/2022復(fù)合形法的特點由于復(fù)合形的形狀不必保持規(guī)則的圖形，對目標(biāo)函數(shù)及約束函數(shù)的性狀又無特殊要求，因此該法的適應(yīng)性較強，在機械優(yōu)化設(shè)計中得到廣泛應(yīng)用。初始復(fù)合形的形成初始復(fù)合形必須在可行域內(nèi)生成（復(fù)合形的k個頂點必須都是可行點）生成初始復(fù)合形的方法由設(shè)計者自行決定k個初始點，構(gòu)成初始復(fù)合形在設(shè)計變量較少、約束函數(shù)簡單情況下適用。7/17/2022由設(shè)計者選定一個可行點，其余的(k-1)個可行點用隨機法產(chǎn)生頂點坐標(biāo)的計算 式中 復(fù)合形中的第 j 個頂點； 設(shè)計變量的下限和上限； 在(0，1)區(qū)間內(nèi)的偽隨機數(shù)。上式計算得到的(k - 1)個隨機點不一定

13、都在可行域內(nèi)，因此需要將非可行點移到可行域內(nèi)。可以采用這樣的方法：首先求出已經(jīng)在可行域內(nèi)的L個頂點的中心 xc7/17/2022然后將非可行點向中心點移動若xL+1仍為不可行點，可以利用上式繼續(xù)向中心點移動。只要中心點可行， xL+1點一定可以移到可行域內(nèi)。 (k - 1)個點經(jīng)過這樣的處理后，全部成為可行點，并構(gòu)成初始復(fù)合形。7/17/2022只要可行域為凸集，其中心點必為可行點，用以上方法可以成功地在可行域內(nèi)構(gòu)成初始復(fù)合形。如果可行域為非凸集（如下圖所示），中心點不一定在可行域之內(nèi)。此時可以通過改變設(shè)計變量的下限和上限值，重新產(chǎn)生各頂點，并經(jīng)過多次試算，就有可能在可行域內(nèi)生成初始復(fù)合形。7

14、/17/2022由計算機自動生成初始復(fù)合形的全部頂點其方法是首先隨機產(chǎn)生一個可行點，然后按第二種方法產(chǎn)生其余的(k - 1)個可行點。這種方法對設(shè)計者來說最為簡單，但因初始復(fù)合形在可行域內(nèi)的位置不能控制，可能會給以后的計算帶來困難。復(fù)合形法的搜索方法在可行域內(nèi)生成初始復(fù)合形后，需要采用不同的搜索方法來改變其形狀，使復(fù)合形逐步向約束最優(yōu)點趨近。7/17/2022改變復(fù)合形形狀的搜索方法如下：反射反射是改變復(fù)合形形狀的一種主要策略，其計算步驟為：計算復(fù)合形各頂點的目標(biāo)函數(shù)值，并比較其大小，求出最好點xL、最壞點xH及次壞點xG7/17/2022計算除去最壞點xH外的(k - 1)個頂點的中心xc從

15、統(tǒng)計的觀點來看，一般情況下，最壞點xH和中心點xc的連線方向為目標(biāo)函數(shù)下降的方向。可以以xc點為中心，將最壞點xH按一定比例進行反射，有希望找到一個比最壞點xH的目標(biāo)函數(shù)值為小的新點xR（反射點）。 式中 反射系數(shù)，一般取 。7/17/2022判別反射點xR的位置：若xR為可行點，則比較xR和xH兩點的目標(biāo)函數(shù)值，如果 ，則用xR取代xH ，構(gòu)成新的復(fù)合形，完成一次迭代；如果 ，則將 縮小0.7倍，重新計算新的反射點，若仍不可行， 繼續(xù)縮小，直至 為止。若xR為非可行點，則將 縮小0.7倍，計算反射點xR ，直至可行為止。然后重復(fù)以上步驟，即判別 和 的大小，一旦 ，就用xR取代xH完成一次迭

16、代。7/17/2022綜上所述，反射成功的條件是：擴張當(dāng)求得的反射點xR為可行點，且目標(biāo)函數(shù)值下降較多，則沿反射方向繼續(xù)移動，即采用擴張的方法，可能找到更好的新點xE， xE稱為擴張點。其計算公式為 式中 擴張系數(shù)，一般取 。7/17/2022若擴張點xE為可行點，且 ，則稱擴張成功，用xE取代xR ，構(gòu)成新的復(fù)合形。否則稱擴張失敗，放棄擴張，仍用原反射點xR 取代xH ，構(gòu)成新的復(fù)合形。7/17/2022收縮若在中心點xc以外找不到好的反射點，可以在xc以內(nèi)，即采用收縮的方法尋找較好的新點xk， xk稱為收縮點。 其計算公式為 式中 收縮系數(shù)，一般取 。若 ，則收縮成功，用xk取代xH，構(gòu)成

17、新的復(fù)合形。7/17/2022壓縮若采用上述各種方法均無效，可以采取將復(fù)合形各頂點向最好點xL靠攏，采用壓縮的方法來改變復(fù)合形的形狀。壓縮后的各頂點的計算公式為然后，再對壓縮后的復(fù)合形采用反射、擴張或收縮等方法，繼續(xù)改變復(fù)合形的形狀。7/17/2022還何以采用旋轉(zhuǎn)等方法來改變復(fù)合形形狀。采用改變復(fù)合形形狀的方法越多，程序設(shè)計越復(fù)雜，可能降低計算效率及可靠性。在進行優(yōu)化方法的程序設(shè)計時，需要針對具體情況采用某些有效的方法。7/17/2022復(fù)合形法的計算步驟基本的復(fù)合形法（只含有“反射”）的計算步驟為：選擇復(fù)合形的頂點數(shù)k，一般取n+1k2n，在可行域內(nèi)構(gòu)成具有k個頂點的初始復(fù)合形。計算復(fù)合形

18、各頂點的目標(biāo)函數(shù)值，比較其大小，找出最好點xL、最壞點xH及次壞點xG。計算除去最壞點xH以外的(k1)個頂點的中心xc并判別是否可行，若xc為可行點，則轉(zhuǎn)步驟4；若xc為非可行點，則重新確定設(shè)計變量的下限和上限值，即令 然后轉(zhuǎn)步驟1，重新構(gòu)造初始復(fù)合形。7/17/2022計算反射點xR，必要時改變反射系數(shù) 的值，直至反射成功。然后以xR取代xH，構(gòu)成新的復(fù)合形。若收斂條件 得到滿足，計算終止。約束最優(yōu)解為： 否則，轉(zhuǎn)步驟2。7/17/2022復(fù)合形法的程序框圖（P131）返回7/17/20226.4 可行方向法概述約束優(yōu)化問題的直接解法中，可行方向法是最大的一類，它也是求解大型約束優(yōu)化問題的

19、主要方法之一。可行方向法的基本原理是在可行域內(nèi)選擇一個初始點 ，當(dāng)確定了一個可行方向d和適當(dāng)?shù)牟介L后，按下式 進行迭代計算。在不斷調(diào)整可行方向的過程中，使迭代點逐步逼近約束最優(yōu)點。7/17/2022可行方向法的搜索策略可行方向法的第一步迭代都是從可行的初始點 出發(fā)，沿 點的負梯度方向 將初始點移動到某一個約束面（只有一個起作用的約束時）上或約束面的交集（有幾個起作用的約束時）上。然后根據(jù)約束函數(shù)和目標(biāo)函數(shù)的不同性狀，分別采用以下幾種策略繼續(xù)搜索：7/17/20227/17/2022第二種情況如右圖，沿可行方向 作一維搜索，所得到的新點 在可行域外，則設(shè)法將 點移動到約束面上，即取 和約束面的交

20、點作為新的迭代點 。7/17/2022第三種情況是沿約束面搜索對于只具有線性約束條件的非線性規(guī)劃問題（如右圖所示），從 點出發(fā)，沿約束面移動，在有限的幾步內(nèi)即可搜索到約束最優(yōu)點；7/17/2022對于非線性約束函數(shù)（如右圖），沿約束面移動將會進入非可行域，因此需將進入非可行域的新點 設(shè)法調(diào)整到約束面上，然后才能進行下一次迭代。7/17/2022調(diào)整的方法是先規(guī)定約束面容差 ，建立新的約束邊界，然后將已離開約束面的 點，沿起作用約束函數(shù)的負梯度方向 返回到約束面上。其計算公式為 式中的 稱為調(diào)整步長，可用試探法決定，或用下式估算7/17/2022產(chǎn)生可行方向的條件可行方向是指沿該方向作微小移動后

21、，所得到的新點是可行點，且目標(biāo)函數(shù)值有所下降。因此，可行方向應(yīng)滿足可行和下降兩個條件。可行條件可行條件是指將某點沿可行方向作微小移動后，所得到的新點為可行點需滿足的條件。7/17/2022如右圖，若 點在一個約束面上，過 點作約束面 的切線 ，顯然滿足可行條件的方向 應(yīng)與起作用的約束函數(shù)在 點的梯度 的夾角大于或等于90。用向量關(guān)系式可表示為：7/17/2022若 點在 個約束面的交集上（如右圖所示），為保證方向 可行，要求 和 個約束函數(shù)在點的梯度 的夾角均大于等于90。則其向量關(guān)系可表示為7/17/2022下降條件可行方向的下降條件是指沿該方向作微小移動后，所得新點的目標(biāo)函數(shù)值是下降的。7

22、/17/2022如右圖所示，滿足下降條件的方向 應(yīng)和目標(biāo)函數(shù)在 點的梯度 的夾角大于90 。其向量關(guān)系可表示為7/17/2022滿足可行和下降條件（如右圖所示），它位于約束曲面在 點的切線和目標(biāo)函數(shù)等值線在 點的切線所圍成的扇形區(qū)內(nèi)，該扇形區(qū)稱為可行下降方向區(qū)。7/17/2022綜上所述，當(dāng) 點位于 個起作用的約束面上時，滿足 的方向 稱可行方向。7/17/2022可行方向的產(chǎn)生方法滿足可行、下降條件的方向位于可行下降扇形區(qū)內(nèi)，在扇形區(qū)內(nèi)尋找一個最有利的方向作為本次迭代的搜索方向，其方法主要有優(yōu)選方向法和梯度投影法兩種。優(yōu)選方向法要求在可行下降扇形區(qū)內(nèi)選擇一個能使目標(biāo)函數(shù)下降最快的方向作為迭代

23、的方向，這可以看作是一個以搜索方向 為設(shè)計變量的約束優(yōu)化問題。7/17/2022這個新的約束優(yōu)化問題的數(shù)學(xué)模型可寫成： 由于 和 為定值，上述各函數(shù)均為設(shè)計變量 的線性函數(shù)，采用線性規(guī)劃的方法求解后，求得的最優(yōu)解 即為本次迭代的可行方向，即 。7/17/2022梯度投影法當(dāng) 點目標(biāo)函數(shù)的負梯度方向 不滿足可行條件時，可將 方向投影到約束面（或約束面的交集）上，得到投影向量 （如下圖所示），該投影向量顯然滿足方向的可行和下降條件。7/17/2022梯度投影法就是取該方向作為本次迭代的可行方向。可行方向的計算公式為 式中 點的目標(biāo)函數(shù)梯度； 投影算子，為 階矩陣 式中 單位矩陣， 階矩陣； 起作用

24、約束函數(shù)的梯度矩陣， 階矩陣； 式中 起作用的約束函數(shù)個數(shù)。7/17/2022步長的確定可行方向 確定后，按下式計算新的迭代點 但是由于目標(biāo)函數(shù)及約束函數(shù)的性狀不同，步長 的確定方法也不同，不論是用何種方法，都應(yīng)使新的迭代點 為可行點，且目標(biāo)函數(shù)具有最大的下降量。7/17/2022確定步長 的常用方法有以下兩種：取最優(yōu)步長如右圖所示，從 點出發(fā)，沿 方向進行一維搜索，取得最優(yōu)步長 ，計算新點x的值若新點x為可行點，則本次迭代的步長取7/17/2022 取到約束邊界的最大步長如右圖所示，從 點沿 方向進行一維搜索，得到的新點 為不可行點，則應(yīng)改變步長，使新點 返回到約束面上來。使新點 恰好位于約

25、束面上的步長稱為最大步長，記作 。則本次迭代的步長取 7/17/2022由于實際上 的確定較為困難，可按以下步驟計算取一試驗步長 ，計算試驗點 。試驗步長的值不能太大，以免因一步走得太遠導(dǎo)致計算困難；也不能太小，使得計算效率太低。根據(jù)經(jīng)驗，試驗步長 的值能使試驗點 的目標(biāo)函數(shù)值下降510，即 將目標(biāo)函數(shù) 在 點展開成泰勒級數(shù)的線性式 則 7/17/2022由此可得試驗步長 計算公式因 為目標(biāo)函數(shù)的下降方向， ，所以試驗步長 恒為正值。試驗步長選定后，試驗點 按下式計算7/17/2022判別試驗點 的位置由試驗步長 確定的試驗點 可能在約束面上，也可能在可行域或非可行域。只要 不在約束面上，就要

26、設(shè)法將其調(diào)整到約束面上來。要想使 到達約束面 是很困難的。為此，先確定一個約束允差 。當(dāng)試驗點xt滿足若試驗點 位于非可行域，則轉(zhuǎn)步驟3。若試驗點 位于可行域內(nèi)，則應(yīng)沿 方向以步長 繼續(xù)向前搜索，直至新的試驗點 到達約束面或越出可行域，再轉(zhuǎn)步驟3。7/17/2022將位于非可行域的試驗點 調(diào)整到約束面上。若試驗點 位于右圖所示的位置，在 點處： 顯然應(yīng)將 點調(diào)整到 的約束面上，因為對于 點來說， 的約束違反量比 大。若設(shè) 為約束違反量最大的約束條件，則應(yīng)滿足約束違反量最大的約束條件7/17/2022將試驗點 調(diào)整到 的約束面上的方法有試探法和插值法兩種。試探法的基本內(nèi)容是當(dāng)試驗點位于非可行域時

27、，將試驗步長 縮短；當(dāng)試驗點位于可行域時，將試驗步長 增加，即不斷變化 的大小，直至滿足允差條件時，即認為試驗點 已被調(diào)整到約束面上了。7/17/2022插值法是利用線性插值將位于非可行域的試驗點 調(diào)整到約束面上。設(shè)試驗步長為 時，求得可行試驗點當(dāng)試驗步長為 時，求得非可行試驗點并設(shè)試驗點 和 的約束函數(shù)分別為7/17/2022它們之間的位置關(guān)系如右圖所示。若考慮約束允差 ，并按允差中心 作線性內(nèi)插，可以得到將 點調(diào)整到約束面上的步長 。其計算公式為：本次迭代的步長取為7/17/2022收斂條件 按可行方向法的原理，將設(shè)計點調(diào)整到約束面上后，需要判斷迭代是否收斂，即判斷該迭代點是否為約束最優(yōu)點

28、。常用的收斂條件有以下兩種：設(shè)計點 及約束允差滿足 條件時，迭代收斂。7/17/2022設(shè)計點 滿足庫恩塔克條件 時，迭代收斂。可行方向法的計算步驟在可行域內(nèi)選擇一個初始點 ，給出約束允差 及收斂精度值 。令迭代次數(shù) ，第一次迭代的搜索方向取 。估算試驗步長 ，計算試驗點 。7/17/2022若試驗點 滿足 ， 點必位于第 個約束面上，則轉(zhuǎn)步驟6；若試驗點 位于可行域內(nèi)，則加大試驗步長 ，重新計算新的試驗點，直至 越出可出域，再轉(zhuǎn)步驟5；若試驗點位于非可行域，則直接轉(zhuǎn)步驟5。確定約束違反量最大的約束函數(shù) 。用插值法計算調(diào)整步長 ，使試驗點 返回到約束面上，則完成一次迭代。再令 ， ，轉(zhuǎn)下步。在

29、新的設(shè)計點 處產(chǎn)生新的可行方向 。7/17/2022若 點滿足收斂條件，則計算終止。約束最優(yōu)解為 否則，改變允差 的值，即令 再轉(zhuǎn)步驟2。7/17/2022可行方向法的程序框圖返回7/17/20226.5 懲罰函數(shù)法概述懲罰函數(shù)法（SUMT）是一種間接解法。約束非線性規(guī)劃問題把約束引入原函數(shù)無約束極值子問題無約束優(yōu)化方法約束極值點“懲罰”：給予無約束極值求解過程中企圖違反約束的那些迭代點以很大的函數(shù)值，而子問題的目的是極小化目標(biāo)函數(shù)，這樣迫使無約束優(yōu)化子問題的極小點趨于滿足約束條件。重復(fù)地產(chǎn)生和求解一系列這樣的子問題，它們的解在極限情況下趨向于原約束優(yōu)化問題的約束極小值。7/17/2022基本

30、原理：將約束優(yōu)化問題 中的不等式和等式約束函數(shù)經(jīng)過加權(quán)轉(zhuǎn)化后，和原目標(biāo)函數(shù)結(jié)合成新的目標(biāo)函數(shù)懲罰函數(shù)。 求解該新目標(biāo)函數(shù)的無約束極小值，以期得到原問題的約束最優(yōu)解。7/17/2022這種方法按一定的法則改變加權(quán)因子 和 的值，構(gòu)成一系列的無約束優(yōu)化問題，求得一系列的無約束最優(yōu)解，并不斷地逼近原約束優(yōu)化問題的最優(yōu)解。懲罰函數(shù)中 和 稱為加權(quán)轉(zhuǎn)化項。根據(jù)它們在懲罰函數(shù)中的作用，又分別稱為障礙項和懲罰項。障礙項的作用是當(dāng)?shù)c在可行域內(nèi)時，在迭代過程中將阻止迭代點越出可行域。懲罰項的作用是當(dāng)?shù)c在非可行域或不滿足等式約夷條件時，在迭代過程中將迫使迭代點逼近約束邊界或等式約束曲面。7/17/2022

31、根據(jù)迭代過程是否在可行域內(nèi)進行，懲罰函數(shù)法又可分為內(nèi)點懲罰函數(shù)法，外點懲罰函數(shù)法和混合懲罰函數(shù)法三種。7/17/2022內(nèi)點懲罰函數(shù)法（內(nèi)點法）特點：將新目標(biāo)函數(shù)定義于可行域內(nèi)，序列迭代點在可行域內(nèi)逐步逼近約束邊界上的最優(yōu)點。內(nèi)點法只能用來求解具有不等式約束的優(yōu)化問題。對于只具有不等式約束的優(yōu)化問題轉(zhuǎn)化后的懲罰函數(shù)形式為 或7/17/2022式中 懲罰因子，它是由大到小且趨近于0的數(shù)列，即 。 或 障礙項。由于內(nèi)點法的迭代過程在可行域內(nèi)進行，障礙項的作用是阻止迭代點越出可行域。由障礙項的函數(shù)形式可知，當(dāng)?shù)c靠近某一約束邊界時，其值趨近于0，而障礙項的值陡然增加，并趨近于無窮大，好象在可行域的

32、邊界上筑起了一道“圍墻”，使迭代點始終不能越出可行域。顯然，只有當(dāng)懲罰因子 時，才能求得在約束邊界上的最優(yōu)解。7/17/2022內(nèi)點法中初始點 懲罰因子的初值 及其縮減系數(shù)c等重要參數(shù)的選取和收斂條件的確定初始點 的選取使用內(nèi)點法時，初始點 應(yīng)選擇一個離約束邊界較遠的可行點。若 太靠近某一約束邊界，構(gòu)造的懲罰函數(shù)可能由于障礙項的值很大而變得畸形，使求解無約束優(yōu)化問題發(fā)生困難。懲罰因子初值 的選取懲罰因子的初值 應(yīng)適當(dāng)，否則會影響迭代計算的正常進行。太大，將增加迭代次數(shù)； 太小，會使懲罰函數(shù)的性態(tài)變壞，甚至難以收斂到極值點。對于不同的問題，都要經(jīng)過試算取 ，根據(jù)試算的結(jié)果，決定增加或減小 的值。7/17/2022按經(jīng)驗公式 計算 值。懲罰因子的縮減系數(shù)c的選取在構(gòu)造序列懲罰函數(shù)時，懲罰因子 是一個逐次遞減到0的數(shù)列，相鄰兩次迭代的懲罰因子的關(guān)系為式中的c稱為懲罰因子的縮減系數(shù)，c為小于1的正數(shù)。通常的取值范圍在0.10.7之間。7/17/2022收斂條件內(nèi)點法的收斂條件為前式說明相鄰兩次迭代的懲罰函數(shù)的值相對變化量充分小，后式說明相鄰兩次迭代的無約束極小點已充分接近。滿足收斂條件的無約束極小點 已逼近原問題的約束最優(yōu)點，迭代終