優(yōu)化設(shè)計第三次課課件

第六節(jié)約束優(yōu)化問題的極值條件

一、約束極值問題

約束優(yōu)化問題,即求一個設(shè)計點使目標(biāo)函數(shù)且滿足約束條件

這個滿足所有約束條件的最優(yōu)點稱為約束最優(yōu)點。

由于約束化問題的最優(yōu)解受到約束條件的限制，它不僅與目標(biāo)函數(shù)的性質(zhì)有關(guān)，而且與約束函數(shù)的性質(zhì)也有密切關(guān)系。所以，一般來說，目標(biāo)函數(shù)的無約束最優(yōu)解不一定是它的約束最優(yōu)解。這一點，可以從下圖所示的幾種情況來說明。圖中帶陰影線的曲線為約束曲線，無陰影線是目標(biāo)函數(shù)的等值線。

a)圖a)所示的目標(biāo)函數(shù)是凸函數(shù)，三個約束曲線圍成的可行域是一個凸集。從圖中看到，橢圓形等值線族的中點是目標(biāo)函數(shù)的極值點，即無約束最優(yōu)點。因為這個點落在可行域之內(nèi)，所以，它也是約束的最優(yōu)點。當(dāng)所有的約束條件對最優(yōu)點都不起作用時，這些約束條件存在或不存在，其最優(yōu)點都是點，因此，可以不考慮這些約束。

c)

圖c)所示，目標(biāo)函數(shù)等值線在約束邊界處呈波浪形彎曲，有三條不同的等值線與約束曲線分別相切于、、三點。比較這三點，可以確定目標(biāo)函數(shù)值最小的一點是最優(yōu)點。由此可知，利用等值線與約束曲線相切點來判斷是否為約束最優(yōu)點，只是一個必要條件，并不是充分條件,也就是說等值線與約束相切點不一定是最優(yōu)點。

d)

圖d)表示由于約束條件形狀的原因，使可行域為非凸集，因而產(chǎn)生了多個局部極值點，對于這種情況，通常也只有通過比較，從中挑選一個全局極值點。

經(jīng)過上面的分析，可以看到，由于目標(biāo)函數(shù)和約束函數(shù)的非凸性，使約束極值點的數(shù)目增多，從而也使優(yōu)化過程復(fù)雜化了。目前雖然已有一些實用的求解方法，但是尋求更完善有效的求

解方法，至今還是優(yōu)化技術(shù)中的一個研究課題。

二、等式約束優(yōu)化問題的極值條件

求解等式約束優(yōu)化問題,即求一個設(shè)計點使目標(biāo)函數(shù)且滿足約束條件

(1)消去法(降維法)先討論二元函數(shù)只有一個等式約束的簡單情況，即且滿足約束條件

求解這個問題可以應(yīng)用代數(shù)中的消元法，先把約束函數(shù)變成以某一變量表示另一變量的函數(shù)關(guān)系，例如，，

然后將這個函數(shù)關(guān)系代入目標(biāo)函數(shù)中，消去，變成一元函數(shù)。經(jīng)過這樣代換，把等式約束問題轉(zhuǎn)化為無約束問題，把目標(biāo)函數(shù)由二維降為一維。最后，將函數(shù)極小化求，再代入，求出，就可得到此優(yōu)化問題的最優(yōu)解。

對于維目標(biāo)函數(shù)帶有個等式約束的優(yōu)化問題，可以把上述方法加以推廣。若作為個方程的聯(lián)立方程組，把個變量中的個變量(例如，)，用其余個變量來表示，可由聯(lián)立方程組解出

拉格朗日乘子法是求解等式約束優(yōu)化問題的另一種經(jīng)典方法。它是通過增加變量將等式約束優(yōu)化問題變成無約束優(yōu)化問題，所以又稱作升維法。現(xiàn)在仍先研究二元函數(shù)只帶一個等式約束的簡單優(yōu)化問題。當(dāng)不考慮約束條件時，根據(jù)無約束極值的必要條件為即由全微分原理，有(A)(1)拉格朗日乘子法(升維法)

若把式（C）寫成，并令它等于一個非零的常數(shù)，則（C）可改寫成式中為待定常數(shù)，稱為拉格朗日乘子，解聯(lián)立方程組：

三個方程三個未知數(shù)，可解。求得極值點和值。上式的無約束極值必要條件為

求解上面的聯(lián)立方程組，由個方程解出和共個變量。要判斷是否極值點，通常還需要利用極值的充分條件。因為原等式約束問題是維的，而方程組增加到維。所以，拉格朗日乘子法又稱升維法。利用梯度和矩陣形式，可把方程組簡潔的寫成

式中，,

是向量的梯度矩陣，其矩陣表示為拉格朗日乘子法的幾何意義說明如下：

1.在維設(shè)計空間中，各等式約束面和目標(biāo)函數(shù)的等值面都可以想象成超曲面，而梯度和則分別為這些超曲面上的法線。

2.滿足所有等式約束條件的幾何含義是最優(yōu)點一定要符合這些約束曲面的交面(或交線、交點)之上。

3.極值必要條件表示目標(biāo)函數(shù)的負(fù)梯度(即等值面的法線)與所有約束函數(shù)的(即約束曲面的法線)為線性相關(guān)。其幾何意義就是目標(biāo)函數(shù)的負(fù)梯度應(yīng)落在所有約束曲面的法線所張成的空間中。拉格朗日乘子法幾何意義

如右圖所示三維空間中有兩個等式約束曲面、，最優(yōu)點應(yīng)落在這兩個約束面的交線上。另一方面，與、線性相關(guān)表示為這三個向量必須是共面。因為，這里在三維空間中只有兩個約束曲面的梯度、，這兩個向量張成一個平面。因此，向量就落在此平面上。

例：求、，使目標(biāo)函數(shù)極小，且滿足約束條件(1)一個起作用約束情況式中，——約束函數(shù)在點的梯度。(2)二個起作用約束情況

a)不是約束最優(yōu)點b)是約束最優(yōu)點式中，。

在實際求解過程中，事先并不知道最優(yōu)點位于哪一個或那幾個約束的交匯處。為此，可把個約束條件全部考慮進(jìn)去，并取不起作用的約束條件的乘子為零。在這種情況，一個局部最優(yōu)點的必要條件為上式就是著名的庫恩-塔克（Kuhn-Tucker）條件，又稱K-T條件。(##)庫恩-塔克（Kuhn-Tucker）條件的幾何意義K-T條件的幾何意義

a)不是約束最優(yōu)點b)是約束最優(yōu)點

最后，把前面的等式約束極值必要條件式與這里的不等式約束極值必要條件式合并起來，可得到即有等式約束，又有不等式約束優(yōu)化問題的K-T條件，即

其中與等式約束相關(guān)的乘子可正可負(fù)，但不能為零。四、庫恩-塔克條件應(yīng)用舉例

若給定優(yōu)化問題的數(shù)學(xué)模型為利用K-T條件確定極值點它的K-T條件可表示為因為待求，所以現(xiàn)在還無法知道哪些約束是起作用的，哪些約束是不起作用的，只能先根據(jù)各種可能情況進(jìn)行試驗。下面按照八種情況分析如下：

2）若、兩個約束在處起作用，則根據(jù)K-T條件有下式成立從約束方程中解得，相當(dāng)于圖中的A點。將得到的解代回K-T方程得到

由于K-T條件要求，所以A點不是極值點。

3）若、兩個約束在處起作用，則根據(jù)K-T條件有下式成立從約束方程中解得，相當(dāng)于圖中的B點。將得到的解代回K-T方程得到

由于K-T條件要求，所以B點不是極值點。

4）若、兩個約束在處起作用，則根據(jù)K-T條件有下式成立滿足K-T條件要求，所以C點是極值點。從約束方程中解得，但不滿足第三個不等式約束條件所以取相當(dāng)于圖中的C點。將得到的解代回K-T方程得到

5）若只有一個約束在處起作用，則根據(jù)K-T條件有下式成立從前兩方程組中解得因為假定只有一個約束在處起作用，那么第二個約束在處不起作用，有

即根據(jù)可推出由于K-T條件要求，所以此點不是極值點。

6）若只有一個約束在處起作用，則根據(jù)K-T條件有下式成立解上面方程組解得此解不滿足的要求，故次點不是極值點

7）若只有一個約束在處起作用，則根據(jù)K-T條件有下式成立解上面方程組，解得，此解不滿足的非負(fù)要求，故次點不是極值點

8）若、、三個約束都在處都不起作用，則根據(jù)K-T條件有下式成立解上面方程組，解得，此解不滿足的要求，故次點不是極值點

從上述八種情況的分析可以看出，利用K-T條件求極值點（解析法）往往是很繁瑣的，需要確定哪些約束在極值點出起作用。因此實際應(yīng)用中，很少利用K-T條件求極值點，而是主要用他來判斷所要求點是否只極值點，以及檢驗一種搜索方法是否合理。例：已知二維約束問題

受約束于

用K-T條件判斷是否為極小點。一維搜索方法第一節(jié)一維搜索概述

求一元函數(shù)的極值問題是一維優(yōu)化問題，利用直接法求一元函數(shù)極值點的過程叫一維搜索。一維搜索更重要的作用在于它是求解多元函數(shù)優(yōu)化問題的基礎(chǔ)。因為求解多元函數(shù)優(yōu)化問題的過程，通常可歸結(jié)為反復(fù)求解一維優(yōu)化問題。因此，它是優(yōu)化方法中最基本的方法。一維搜索的方法有：分?jǐn)?shù)法，0.618法（黃金分割法），二次插值法，三次插值法，切線法，割線法等，本章主要介紹0.618法、二次插值和切線法等常用的幾種一維搜索法。

現(xiàn)在的問題是，在初始點和搜索方向已確定的情況下，步長應(yīng)走多大，也就是說步長因子應(yīng)取多大，才能使得到的新點的函數(shù)值最小。

換句話說，要求得一個值，使函數(shù)值達(dá)到最小，這樣，問題就轉(zhuǎn)化為求參數(shù)的一元函數(shù)的極值問題，即

用數(shù)學(xué)歸納法求多元函數(shù)最優(yōu)解的過程為：選擇初始點，由這點出發(fā)，沿著給定的方向走一個步，到達(dá)一個新點，而且該點的函數(shù)值有所下降。如果要使這一步取得最好的效果，則希望所得到點是方向上函數(shù)值最小的一個點。然后，又以為新的初始點，沿著給定的方向走一個步長，到達(dá)點，同樣，該點是方向函數(shù)值最小的點，如此繼續(xù)，直到滿足給定的計算精度為止。其具體的迭代過程可以用下式來表示=顯然，上式就是一維優(yōu)化問題，式中的稱為最優(yōu)步長因子。上述概念可以用圖形來形象地表示。一維搜索的幾何表示設(shè)在第步迭代中，從初始點出發(fā)，沿著給定的方向走了一個步長，到達(dá)新點從圖上可以看出這個點是在方向上函數(shù)值最小的一個點，如果步長走小一些,得到點，或步長走大一些，得到點，這兩點都不是方向

上函數(shù)值最小點，因為、兩點處的等值線的函數(shù)值比點處的等值線的函數(shù)值要大。在一維搜索中，由于目標(biāo)函數(shù)可以看做步長因子的一元函數(shù)，根據(jù)一元函數(shù)極值的必要條件，則可以采用解析法求解的極小點。為了直接利用的函數(shù)式求解最佳步長因子，可把簡寫成的形式進(jìn)行泰勒展開，取到二次項，即令

得到由上面的推導(dǎo)可知，采用解析法求解一維搜索問題需要求解目標(biāo)函數(shù)在點處的梯度和海色矩陣，這對函數(shù)關(guān)系復(fù)雜、求導(dǎo)困難或無法求導(dǎo)的函數(shù)，采用解析法將是非常困難的，所以在優(yōu)化設(shè)計中，求解最佳步長因子主要采用數(shù)值解法，即利用計算機(jī)通過迭代計算求得最佳步長因子的近似解。采用數(shù)值解法求解一維優(yōu)化問題即一維搜索的基本步驟是：（1）先確定所在的搜索區(qū)間。（2）根據(jù)區(qū)間消去法的基本原理不斷縮小此區(qū)間，從而獲得的數(shù)值近似解。第二節(jié)搜索區(qū)間的確定與區(qū)間消去法原理

為了求得多元函數(shù)的最優(yōu)解，需要進(jìn)行多次迭代。而每次迭代都要求解一維優(yōu)化問題。所以，多元函數(shù)優(yōu)化問題的求解過程就歸結(jié)為反復(fù)求解一維優(yōu)化過程，即反復(fù)進(jìn)行一維搜索。

區(qū)間的單峰性

進(jìn)行一維搜索時，首先要考慮在給定的方向上應(yīng)確定一個搜索區(qū)間，而且在這個區(qū)間內(nèi)部，函數(shù)具有單峰性（即函數(shù)在該區(qū)間有唯一的極小點），這種區(qū)間稱為單峰區(qū)間。如圖所示，區(qū)間內(nèi)函數(shù)只有一個峰值，即有唯一的極小點，這就是單峰區(qū)間。而區(qū)間內(nèi)函數(shù)有兩個極小點和一個極大點，即有三個峰值，顯然，這個區(qū)間就不是單峰區(qū)間。單峰區(qū)間是函數(shù)在該區(qū)間內(nèi)只有一個峰值，其函數(shù)按“大－?。蟆被颉案?低-高”規(guī)律變化的區(qū)間。在確定了搜索區(qū)間為單峰區(qū)間之后，就可在該區(qū)間作一維搜索，求得極小點。對于多峰函數(shù)，只要適當(dāng)劃分區(qū)間，也可以使該函數(shù)在每一個子區(qū)間上都是單峰的。為了確定極小點。所在的單谷區(qū)間應(yīng)使函數(shù)在區(qū)間里形成“高—低一高”趨勢。對于性態(tài)比較明顯的單變量函數(shù)，單峰區(qū)間可以根據(jù)實際情況人為地選定；但對于性態(tài)復(fù)雜的單變量函數(shù)，一般需要利用數(shù)值計算的方法來確定單蜂區(qū)間。外推法(也稱進(jìn)退法)就是確定單峰區(qū)間的一種數(shù)值計算方法。一、確定搜索區(qū)間的外推法（進(jìn)退法）采用外推法確定搜索區(qū)間的基本思想是：按照一定規(guī)律給出一些試算點，依次比較各試算點的函數(shù)值大小，直到滿足單峰區(qū)間的條件，即函數(shù)值呈現(xiàn)“大-小-大”變化形式，則為所確定的搜索區(qū)間。外推法的具體實現(xiàn)過程為，從開始，以初始步長向前試探。如果函數(shù)值上升，則步長變號，即改變試探方向；如果函數(shù)值下降，則維持原來的試探方向，并將步長加倍(),區(qū)間的始點、中間點依次沿試探方向移動一步。此過程一直進(jìn)行到函數(shù)值再次上升時為止，即可找到搜索區(qū)間的終點，形成函數(shù)值的“高-低-高”趨勢。下圖表示沿的正向試探。每走一步都將區(qū)間的始點、中間點沿試探方向移動一步（進(jìn)行換名）。經(jīng)過三步最后確定搜索區(qū)間，并且得到區(qū)間始點、中間點和終點，及所對應(yīng)的函數(shù)值。下圖中，如果開始的試探方向為函數(shù)值上升方向，即開始沿著的正向試探，但由于函數(shù)值上升而改變了試探方向，最后得到始點、中間點和終點，及它們所對應(yīng)的函數(shù)值，從而形成單谷區(qū)間為一維搜索區(qū)間。外推法的程序框圖例：試用外推法確定函數(shù)的初始一維搜索區(qū)間，設(shè)初始點，初始步長。解：根據(jù)給定的初始點和初始步長，直接按照上面外推法的程序框圖進(jìn)行求解。

(1)取，因為，則

(2)因為，所以向前試探，此時

(3)因為，所以繼續(xù)向前試探，此時再將步長增加兩倍，即，于是

(4)比較和，可知，所以搜索結(jié)束，已尋得初始搜索區(qū)間，所以繼續(xù)向前試探，此時此時相鄰3點的函數(shù)值分別是4,0,16，確實形成了“高-低-高”的一維搜索區(qū)間。

二、區(qū)間消去法原理

當(dāng)含有極值點的單谷搜索區(qū)間確定之后，應(yīng)逐步縮短搜索區(qū)間，從而找到極小點的數(shù)值近似解。這里采用區(qū)間消去法來實現(xiàn)搜索區(qū)間的逐步縮短。首先，在搜索區(qū)間內(nèi)任取兩點且，并計算函數(shù)值，比較函數(shù)值的大小將有下列3種情況。

(1)。由于函數(shù)為單谷，所以極小點不可能在區(qū)間內(nèi)，而應(yīng)在區(qū)間內(nèi)，這時可以去掉區(qū)間，把區(qū)間縮小為，如下圖(a)所示。

(2)。由于函數(shù)為單谷，所以極小點不可能在區(qū)間內(nèi)，而應(yīng)在區(qū)間內(nèi)，這時可以去掉區(qū)間，把區(qū)間縮小為，如下圖(b)所示。

(3)。這時極小點只能在區(qū)間內(nèi)，可以去掉區(qū)間或者，甚至將兩段同時去掉，只保留區(qū)間，，如下圖(c)所示。根據(jù)上述分析，在區(qū)間內(nèi)插入兩個點，并通過比較其函數(shù)值大小，就可以把搜索區(qū)間縮短成、