第六章約束優(yōu)化方法課件

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

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

3、選擇的初始點(diǎn)不相同時(shí)，可能搜索到不同的局部最優(yōu)解。因此，常在可行域內(nèi)選擇幾個(gè)差別較大的初始點(diǎn)分別進(jìn)行計(jì)算，以便從求得的多個(gè)局部最優(yōu)解中選擇更好的最優(yōu)解。要求可行域?yàn)橛薪绲姆强占?，即在有界可行域?nèi)存在滿足全部約束條件的點(diǎn)，且目標(biāo)函數(shù)有定義。7/17/2022間接解法有不同的求解策略。其中一種方法的基本思路是將約束優(yōu)化問題中的約束函數(shù)進(jìn)行特殊的加權(quán)處理，然后和目標(biāo)函數(shù)結(jié)合，構(gòu)成一個(gè)新的目標(biāo)函數(shù)，即將原約束優(yōu)化問題轉(zhuǎn)化成為一個(gè)或一系列的無約束優(yōu)化問虬再對新的目標(biāo)函數(shù)進(jìn)行無約束優(yōu)化計(jì)算，從而間接地搜索到原約束問題的最優(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)因子。 然后對 進(jìn)行無約束極小化計(jì)算。7/17/2022由于在新目標(biāo)函數(shù)中包含了各種約束條件，而且在求極值的過程中還將改變加權(quán)因子的大小。因此可以不斷地調(diào)整設(shè)計(jì)點(diǎn)，使其逐步逼近約束邊界。從而間接地求得原約束問題的最優(yōu)解。間接解法框圖7/17/2022間接解法例題求約束優(yōu)化問題 的最優(yōu)解。解: 易知該問題理論上的最優(yōu)解為：由該問題的幾何意義（右圖）可知，約束最優(yōu)點(diǎn) 為目標(biāo)函數(shù)等值線與等式約束函數(shù)（直線）的切點(diǎn)，7/17/2022用間接解法求解時(shí)，可取 ，轉(zhuǎn)換后的新目標(biāo)函數(shù)為從而可

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

29、新的設(shè)計(jì)點(diǎn) 處產(chǎn)生新的可行方向 。7/17/2022若 點(diǎn)滿足收斂條件，則計(jì)算終止。約束最優(yōu)解為 否則，改變允差 的值，即令 再轉(zhuǎn)步驟2。7/17/2022可行方向法的程序框圖返回7/17/20226.5 懲罰函數(shù)法概述懲罰函數(shù)法（SUMT）是一種間接解法。約束非線性規(guī)劃問題把約束引入原函數(shù)無約束極值子問題無約束優(yōu)化方法約束極值點(diǎn)“懲罰”：給予無約束極值求解過程中企圖違反約束的那些迭代點(diǎn)以很大的函數(shù)值，而子問題的目的是極小化目標(biāo)函數(shù)，這樣迫使無約束優(yōu)化子問題的極小點(diǎn)趨于滿足約束條件。重復(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)化項(xiàng)。根據(jù)它們在懲罰函數(shù)中的作用，又分別稱為障礙項(xiàng)和懲罰項(xiàng)。障礙項(xiàng)的作用是當(dāng)?shù)c(diǎn)在可行域內(nèi)時(shí)，在迭代過程中將阻止迭代點(diǎn)越出可行域。懲罰項(xiàng)的作用是當(dāng)?shù)c(diǎn)在非可行域或不滿足等式約夷條件時(shí)，在迭代過程中將迫使迭代點(diǎn)逼近約束邊界或等式約束曲面。7/17/2022

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

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