第二章 優(yōu)化設(shè)計(jì)理論基礎(chǔ)

實(shí)用優(yōu)化技術(shù)任課教師：董明望第二章優(yōu)化設(shè)計(jì)理論基礎(chǔ)回顧優(yōu)化設(shè)計(jì)數(shù)學(xué)的理論基礎(chǔ)，使學(xué)習(xí)優(yōu)化技術(shù)變得相對(duì)容易，可以提高學(xué)習(xí)優(yōu)化技術(shù)的效率。本章節(jié)主要介紹的優(yōu)化設(shè)計(jì)的理論基礎(chǔ)有極值理論（分為有約束極值問題和無約束極值問題）、向量與矩陣、正定二次函數(shù)和泰勒函數(shù)。目錄第一節(jié)極值理論

第二節(jié)向量與矩陣第三節(jié)正定二次函數(shù)與泰勒函數(shù)第四節(jié)共軛方向法第五節(jié)拉格朗日乘子第一節(jié)極值理論由微分理論可知，一元函數(shù)

在點(diǎn)

取得極值的必要條件是函數(shù)在該點(diǎn)的一階導(dǎo)數(shù)等于零，充分條件是對(duì)應(yīng)的二階導(dǎo)數(shù)不等于零，即當(dāng)

時(shí)，函數(shù)

在點(diǎn)

取得極小值。當(dāng)

時(shí)，函數(shù)

在點(diǎn)

取得極大值。極值點(diǎn)和極值分別記作

和

。無約束問題的極值條件第一節(jié)極值理論與此相似，多元函數(shù)

在點(diǎn)

取得極值的必要條件是函數(shù)在該點(diǎn)的所有方向?qū)?shù)都等于零，也就是說函數(shù)在該點(diǎn)的梯度等于零，即：

把函數(shù)在點(diǎn)

展開成泰勒二次近似式，并將以上必要條件代人，整理后得：當(dāng)

為函數(shù)的極小點(diǎn)時(shí)，因?yàn)橛?/p>

，故必有無約束問題的極值條件第一節(jié)極值理論此式說明函數(shù)的二階導(dǎo)數(shù)矩陣必須是正定的，這就是多元函數(shù)取得極小值的充分條件。由此可知，多元函數(shù)在點(diǎn)

取得極小值的充要條件是：函數(shù)在該點(diǎn)的梯度為零，二階導(dǎo)數(shù)矩陣為正定，即：同理，多元函數(shù)在點(diǎn)

取得極大值的充要條件是：函數(shù)在該點(diǎn)的梯度等于零，二階導(dǎo)數(shù)矩陣為負(fù)定。若二階導(dǎo)數(shù)矩陣

不定，則

為非極值點(diǎn)。無約束問題的極值條件第一節(jié)極值理論例求函數(shù)

的極值。無約束問題的極值條件

解：由極值的必要條件解得以下4個(gè)駐點(diǎn)：第一節(jié)極值理論由極值的充分條件求函數(shù)的二階導(dǎo)數(shù)矩陣，并判斷其正定性得由此知

是函數(shù)的極小值點(diǎn)，

函數(shù)的極大值點(diǎn)，

和

均為非極值點(diǎn)。第一節(jié)極值理論約束問題的極值有多種狀態(tài)，如下圖所示。其中，(a)為目標(biāo)函數(shù)的極小點(diǎn)在約束可行域內(nèi)的情況，此時(shí)目標(biāo)函數(shù)的極小點(diǎn)也就是約束問題的極小點(diǎn)。(b)為目標(biāo)函數(shù)的極小點(diǎn)在可行域外的情況，此時(shí)約束問題的極小點(diǎn)是約束邊界上的一點(diǎn)，該點(diǎn)是約束邊界與目標(biāo)函數(shù)的一條等值線的切點(diǎn)。(c)中有兩個(gè)極值點(diǎn)，一個(gè)是目標(biāo)函數(shù)的等值線與約束邊界的切點(diǎn)，一個(gè)是兩條約束邊界線的交點(diǎn)。約束問題的極值條件第一節(jié)極值理論可見，約束問題的極值條件比無約束問題復(fù)雜得多。下面分別就等式約束和不等式約束兩種情況加以討論。1)等式約束問題的極值條件

由高等數(shù)學(xué)可知，對(duì)于等式約束最優(yōu)化問題約束問題的極值條件可以建立如下拉格朗日函數(shù)式中，稱為拉格朗日乘子向量。第一節(jié)極值理論

令得：約束問題的極值條件

不全為零這就是等式約束問題在點(diǎn)X取得極值的必要條件。此式可概括為：在等式約束的極值點(diǎn)上，目標(biāo)函數(shù)的負(fù)梯度等于諸約束函數(shù)梯度的非零線性組合。第一節(jié)極值理論

2)不等式約束問題的極值條件 對(duì)于不等式約束問題：約束問題的極值條件引

入個(gè)松弛變量

，可將上面的不等式約束問題變成等式約束問題：第一節(jié)極值理論

建立這一問題的拉格朗日函數(shù)

約束問題的極值條件式中，

為松弛變量組成的向量。

令該拉格朗日函數(shù)的梯度等于零，即則有：第一節(jié)極值理論

根據(jù)分析，不等式約束問題的極小點(diǎn)取值條件可概括為：約束問題的極值條件式中，

為點(diǎn)的起作用約束。

上式不等式約束問題的極值條件，其意義可概括為：在不等式約束問題的極小點(diǎn)上，目標(biāo)函數(shù)的負(fù)梯度等于起作用約束梯度的非負(fù)線性組合。其幾何意義如上圖，即在不等式約束問題的極小點(diǎn)上，目標(biāo)函數(shù)的負(fù)梯度位于起作用約束梯度所成的夾角或錐體之內(nèi)。在非極小點(diǎn)上，目標(biāo)函數(shù)的負(fù)梯度位于起作用約束梯度所成的夾角或錐體之外。第一節(jié)極值理論約束問題的極值條件

上面兩個(gè)式子也稱Kuhn-Tucker條件，簡(jiǎn)稱k-t條件。k-t條件是約束問題極值的必要條件。滿足k-t條件的點(diǎn)稱為k-t點(diǎn)，在一般情況下k-t點(diǎn)就是約束問題的最優(yōu)點(diǎn)。因此k-t條件既可以用作約束問題的終止條件，也可以用來直接求解簡(jiǎn)單的約束最優(yōu)化問題。第一節(jié)極值理論約束問題的極值條件例

用k-t條件判斷點(diǎn)

是否為以下問題的最優(yōu)點(diǎn)：解：因得知，點(diǎn)的起作用約束是和。第一節(jié)極值理論約束問題的極值條件在點(diǎn)

有將以上各梯度值代人k-t條件式有：解得，均大于零，滿足k-t條件，說明就是所給約束最優(yōu)化問題的最優(yōu)點(diǎn)。第二節(jié)向量與矩陣

由線性代數(shù)知，

個(gè)有序的數(shù)

所組成的數(shù)組稱為

維向量。

維向量寫成一列時(shí)稱為列向量，記作

；寫成一行時(shí)稱為行向量，記作

。如:

個(gè)有序的數(shù)

排成的

行

列的數(shù)表稱為

行

列矩陣，可表示為:第二節(jié)向量與矩陣

向量和向量、矩陣和矩陣之間可以進(jìn)行各種運(yùn)算，除簡(jiǎn)單的加減法和數(shù)乘運(yùn)算外，還可進(jìn)行一般的乘法運(yùn)算。設(shè)

則有:第二節(jié)向量與矩陣第三節(jié)正定二次函數(shù)和泰勒函數(shù)

二次函數(shù)是最簡(jiǎn)單的非線性函數(shù)，在最優(yōu)化理論中具有重要的意義。根據(jù)函數(shù)的泰勒二次展開式，可以把一般的二次函數(shù)寫成以下向量形式：正定二次函數(shù)

式中，

為常數(shù)向量，相當(dāng)于函數(shù)的梯度；

為

階常數(shù)矩陣，相當(dāng)于函數(shù)的二階導(dǎo)數(shù)矩陣。

稱二次型，

稱二次型矩陣。矩陣有正定、負(fù)定和不定之分。對(duì)于任意非零向量

：

(1)若有

，則稱矩陣

是正定矩陣。(2)若有

，則稱矩陣

是負(fù)定矩陣。(3)若有時(shí)

，有時(shí)

，則稱矩陣

是不定矩陣。第三節(jié)正定二次函數(shù)和泰勒函數(shù)

由線性代數(shù)可知，矩陣的正定性除了可以用上面的定義判斷外，還可以用矩陣的各階主子式進(jìn)行判別。所謂矩陣的主子式，就是包含第一個(gè)元素在內(nèi)的左上角各階子矩陣所對(duì)應(yīng)的行列式。如果矩陣的各階主子式的值均大于零，即正定二次函數(shù)一階主子式二階主子式三階主子式.................則矩陣

是正定的。第三節(jié)正定二次函數(shù)和泰勒函數(shù)

如果矩陣

的各階主子式的值負(fù)正相間，即正定二次函數(shù)..............即奇數(shù)階主子式小于零，偶數(shù)階主子式大于零時(shí)，矩陣負(fù)定，否則不定。第三節(jié)正定二次函數(shù)和泰勒函數(shù)

正定二次函數(shù)具有以下性質(zhì)：(1)正定二次函數(shù)的等值線(面)是一族同心橢圓(球)。橢圓(球)族的中心就是該二次函數(shù)的極小點(diǎn)，如圖1所示。(2)非正定二次函數(shù)在極小點(diǎn)附近的等值線(面)近似于橢圓(球)，如圖2所示。正定二次函數(shù)圖1正定二元二次函數(shù)的等值線

圖2非正定二元二次函數(shù)的等值線第三節(jié)正定二次函數(shù)和泰勒函數(shù)

為了便于數(shù)學(xué)問題的分析和求解，往往需要將一個(gè)復(fù)雜的非線性函數(shù)簡(jiǎn)化成線性函數(shù)或二次函數(shù)，簡(jiǎn)化的方法一般采用泰勒展開。

由高等數(shù)學(xué)可知，一元函數(shù)

若在點(diǎn)

的鄰域內(nèi)

階可導(dǎo)，則函數(shù)可在該點(diǎn)的鄰域內(nèi)作如下泰勒展開：函數(shù)的泰勒展開式中，

為余項(xiàng)。多元函數(shù)

在點(diǎn)

處也可以作泰勒展開，展開式一般取三項(xiàng)，其形式與一元函數(shù)展開式的前三項(xiàng)相似，即：第三節(jié)正定二次函數(shù)和泰勒函數(shù)

上式稱為函數(shù)

的泰勒二次近似式。其中，

是由函數(shù)在點(diǎn)

的所有二階偏導(dǎo)數(shù)組成的矩陣，稱為函數(shù)

在點(diǎn)

的二階導(dǎo)數(shù)矩陣或黑塞(Hessian)矩陣，有時(shí)也記作

，即：函數(shù)的泰勒展開二階導(dǎo)數(shù)矩陣

也可看作對(duì)梯度

的每一個(gè)元素分別再求一次梯度，橫排而成的矩陣。由于n元函數(shù)的二階偏導(dǎo)數(shù)有

個(gè)，而且二階偏導(dǎo)數(shù)的值與求導(dǎo)次序無關(guān)，所以二階導(dǎo)數(shù)矩陣是

階對(duì)稱矩陣。第三節(jié)正定二次函數(shù)和泰勒函數(shù)

例

用泰勒展開的方法將函數(shù)

在點(diǎn)

簡(jiǎn)化成線性函數(shù)和二次函數(shù)。函數(shù)的泰勒展開

解：分別求函數(shù)在點(diǎn)

的函數(shù)值、梯度和二階導(dǎo)數(shù)矩陣

第三節(jié)正定二次函數(shù)和泰勒函數(shù)

代人式得：函數(shù)的泰勒展開和展開式的二次項(xiàng)：

第三節(jié)正定二次函數(shù)和泰勒函數(shù)

將上面的結(jié)果相加得簡(jiǎn)化后的二次函數(shù)函數(shù)的泰勒展開將

代人簡(jiǎn)化所得的線性函數(shù)和二次函數(shù)，其函數(shù)值都等于-3，與原函數(shù)在點(diǎn)

的值是相等的。說明在給定的展開點(diǎn)上，泰勒展開式與原函數(shù)的值完全相等，離開展開點(diǎn)以后，兩者之間出現(xiàn)誤差，而且離展開點(diǎn)越遠(yuǎn)誤差越大。第四節(jié)共軛方法如果有兩個(gè)向量

，

，滿足以下關(guān)系：共軛方向

式中

為一個(gè)

階對(duì)稱正定矩陳，則稱

和

是關(guān)于

共軛的。

及

兩個(gè)方向即稱為共軛方向。實(shí)際上，共軛方向的概念是正交性(即當(dāng)

為

階單位矩陣)的一個(gè)推廣，也可以說正交是共軛的一個(gè)特殊情況。第四節(jié)共軛方法例：有兩個(gè)二維向量共軛方向若取則可滿足而

是單位矩陣，所以

和

又是正交的。第四節(jié)共軛方法如果有n個(gè)n維向量S1，S2，S3，…，Sn，滿足以下條件：共軛方向

則我們稱這

個(gè)向量是

共扼向量，它們的方向稱共軛方向。同樣地，如果

為單位矩陣，且滿足以上條件，則這

個(gè)向量正交，這是共軛的特殊情況。

關(guān)于共軛方向的幾何概念可用下圖所示二維問題的幾何圖形來說明。設(shè)從某初始點(diǎn)

出發(fā)，沿

方向進(jìn)行搜索得目標(biāo)函數(shù)

的小點(diǎn)

，則

必為該處等高線的切點(diǎn)。第四節(jié)共軛方法共軛方向設(shè)目標(biāo)函數(shù)為：

為

階對(duì)稱正定矩陣。

的梯度可寫為：因

處的梯度方向與該點(diǎn)處目標(biāo)函數(shù)等高線的切線方向正交，故有：若從另點(diǎn)

出發(fā)，仍以

方向進(jìn)行搜索，又得一極小點(diǎn)

，同理有：上面兩式之差：第四節(jié)共軛方法共軛方向令

，故有：

說明

和

是A共扼的，

、

為共軛方向。

是

與

兩切點(diǎn)連線方向，可以證明

的極小點(diǎn)必在此連線上。所以此方向上的極小點(diǎn)即是

的極小點(diǎn)。由此可見，對(duì)于一個(gè)二元二次函數(shù)，只需沿

，

共軛方向搜索二次即可達(dá)到極小點(diǎn)。第四節(jié)共軛方法共軛方向法原理

我們先來討論一下共軛向量的性質(zhì)。設(shè)有一組

個(gè)

維向且彼此為A共軛，即滿足：

則這m個(gè)向量一定是線性無關(guān)的。我們給出以下簡(jiǎn)單證明：

假設(shè)有一組數(shù)，能滿足下列式于：一定有：即線性相關(guān)，則一定有：即：

但已知是關(guān)于A共軛的，所以有：第四節(jié)共軛方法共軛方向法原理

由此我們可得出以下結(jié)論：

這就證明了一定是線性無關(guān)的。由于n維向量組最大的線性無關(guān)向量個(gè)數(shù)為n，所以n維向量空間最多可以找出n個(gè)彼此A共軛的向量，而其他任一方向均可由這n個(gè)向量的線性組合表示出來。

現(xiàn)在設(shè)有—個(gè)n維二次函數(shù)(對(duì)于非二次函數(shù)，可以理解為進(jìn)行泰勒展開后取其前三項(xiàng))：

它的極小點(diǎn)為

。若X0為任意給定的初始點(diǎn)，為關(guān)于A共扼的n個(gè)共扼方向，則有：

式中

為一組常數(shù)。移項(xiàng)后得：第四節(jié)共軛方法共軛方向法原理

此式意味著如果已知初始點(diǎn)X0，并能構(gòu)造一組n個(gè)共軛方向：經(jīng)過n次一維搜索，分別求得

，就一定可求出

。這就是