更新 工程優(yōu)化方法及應(yīng)用 第二章(6學(xué)時(shí))

第二章基本概念和理論基礎(chǔ)本章主要內(nèi)容：§1代數(shù)基礎(chǔ)：范數(shù)、正定性§2多元函數(shù)分析基礎(chǔ)：Hesse矩陣、方向?qū)?shù)、中值公式§3多元函數(shù)的極值§4等高線§5凸分析基礎(chǔ)：凸集、凸函數(shù)、凸規(guī)劃§6

最優(yōu)化算法的結(jié)構(gòu)向量范數(shù)定義——橢球范數(shù)(A正定)

——l2范數(shù)——l1范數(shù)——lp范數(shù)——l∞范數(shù)§1代數(shù)基礎(chǔ)——列向量范數(shù)常見(jiàn)不等式l1-范數(shù)l2-范數(shù)l∞范數(shù)橢球范數(shù)相互等價(jià)——l2范數(shù)也稱(chēng)譜范數(shù)(ATA最大特征值開(kāi)平方)特別地，方陣有如下范數(shù)——l1范數(shù)(列和的最大者)——l∞范數(shù)(行和的最大者)矩陣范數(shù)定義：設(shè)Q為n×n

階對(duì)稱(chēng)矩陣,若

，均有，則稱(chēng)

Q正定。若

，均有

，則稱(chēng)Q半正定。若，均有，則稱(chēng)Q負(fù)定。若,均有，則稱(chēng)Q半負(fù)定。矩陣正定性正定判定定理矩陣

Q半正定

Q的所有特征根大于等于零;

Q的各階主子式都大于等于零；存在矩陣G，使得Q=GGT。矩陣

Q正定

Q的所有特征根大于零;

Q的各階順序主子式都大于零；Q的各階主子式都大于零；存在非奇異矩陣G，使得Q=GGT

負(fù)定判定定理矩陣

Q半負(fù)定

Q的所有特征根小于等于零;

Q的所有奇數(shù)階主子式都小于等于零，且偶數(shù)階主子式都大于等于零；存在矩陣G，使得-Q=GGT。矩陣

Q負(fù)定

Q的所有特征根小于零;

Q的所有奇數(shù)階順序主子式都小于零，且偶數(shù)階順序主子式都大于零；Q的所有奇數(shù)階主子式都小于零且偶數(shù)階主子式都大于零；存在非奇異矩陣G，使得-Q=GGT

解：對(duì)稱(chēng)矩陣Q的三個(gè)順序主子式依次為例1

判定矩陣是否正定:矩陣Q是正定的。第二章基本概念和理論基礎(chǔ)本章主要內(nèi)容：§1代數(shù)基礎(chǔ)：范數(shù)、正定性§2多元函數(shù)分析基礎(chǔ)：Hesse矩陣、方向?qū)?shù)、中值公式§3多元函數(shù)的極值§4等高線§5凸分析基礎(chǔ)：凸集、凸函數(shù)、凸規(guī)劃§6

最優(yōu)化算法的結(jié)構(gòu)§2

多元函數(shù)分析基礎(chǔ)n元函數(shù)：

n元線性函數(shù)：

n元二次函數(shù)：

n元向量值線性函數(shù)：多元函數(shù)序列收斂定義若滿(mǎn)足，則稱(chēng)為Cauchy序列。i.e.注：收斂是Cauchy序列.Cauchy序列的任一子列都收斂。定義

設(shè)為一向量序列，如果則稱(chēng)序列依范數(shù)收斂到,記為

給定區(qū)域D上的n

元實(shí)值函數(shù)梯度、Hesse

矩陣——列向量的梯度的梯度的Hesse

矩陣常用的梯度和Hesse陣公式：其中Q為實(shí)對(duì)稱(chēng)矩陣方向?qū)?shù)定義(方向?qū)?shù))設(shè)在點(diǎn)x

處可微,d為固定單位向量，則稱(chēng)f(x)

在x

處沿方向d

的方向?qū)?shù)為最速上升方向最速下降方向解：由于則函數(shù)在處的最速下降方向例1試求目標(biāo)函數(shù)在點(diǎn)處的最速下降方向，并求沿這個(gè)方向移動(dòng)一個(gè)單位長(zhǎng)度后新點(diǎn)的目標(biāo)函數(shù)值。此方向上的單位向量新點(diǎn)是中值公式設(shè)

二階可導(dǎo)，則在x*的鄰域內(nèi)有：一階Taylor展開(kāi)式二階Taylor展開(kāi)式第二章基本概念和理論基礎(chǔ)本章主要內(nèi)容：§1代數(shù)基礎(chǔ)：范數(shù)、正定性§2多元函數(shù)分析基礎(chǔ)：Hesse矩陣、方向?qū)?shù)、中值公式§3多元函數(shù)的極值§4等高線§5凸分析基礎(chǔ)：凸集、凸函數(shù)、凸規(guī)劃§6

最優(yōu)化算法的結(jié)構(gòu)§3

多元函數(shù)的極值

對(duì)于一個(gè)極小化問(wèn)題，我們的目的是求出全局極小點(diǎn)，而全局極小點(diǎn)不好求，因此我們一般的做法是先求出所有局部極小值點(diǎn)，再?gòu)闹姓页鋈謽O小點(diǎn)。為了求出函數(shù)的局部極小值點(diǎn)，我們需要考察函數(shù)f在局部極小點(diǎn)處滿(mǎn)足什么條件？反過(guò)來(lái)，滿(mǎn)足什么條件的點(diǎn)是局部極小點(diǎn)？首先回顧二元函數(shù)的極值條件（高等數(shù)學(xué)），然后推廣到多元函數(shù)。二元函數(shù)極值的判別條件定理(必要條件)

設(shè)(1)為D的一個(gè)內(nèi)點(diǎn);可微;(2)在處,

（駐點(diǎn)）則在的極值點(diǎn);(3)為且注：可微的極值點(diǎn)一定是駐點(diǎn)，反之不一定成立。例

在處梯度為，但只是雙曲拋物面的鞍點(diǎn)，而不是極小點(diǎn)。f

(2)當(dāng)時(shí)，不是的極值點(diǎn)，稱(chēng)為函數(shù)的鞍點(diǎn)；(3)當(dāng)時(shí)，不能確定，需另行討論。定理(充分條件)

設(shè)(1)為D的一個(gè)內(nèi)點(diǎn);二次連續(xù)可微;(2)在的駐點(diǎn)，即(3)為且令則(1)當(dāng)時(shí)，具有極值取嚴(yán)格極大值取嚴(yán)格極小值Hesse陣負(fù)定Hesse陣正定多元函數(shù)的極值判別條件定理(必要條件)

設(shè)(1)x*為D的一個(gè)內(nèi)點(diǎn);可微;(2)在則的極值點(diǎn);(3)為且證明:

借助一元函數(shù)極值的必要條件，見(jiàn)下頁(yè)。

設(shè)是的局部極小點(diǎn)，為任意單位向量。由定義知：當(dāng),即時(shí)，總有：令則而是D的內(nèi)點(diǎn)，從而與之對(duì)應(yīng)的t=0是的局部極小點(diǎn)。

由一元函數(shù)極小點(diǎn)必要性條件知,而由前述性質(zhì)知?jiǎng)t,由單位向量任意性，即知。證明:（若，取，則

矛盾。）定理(充分條件)

設(shè)(1)x*為D的一個(gè)內(nèi)點(diǎn);(2)二次連續(xù)可微;在(3)則的嚴(yán)格局部極小點(diǎn)（嚴(yán)格局部極大點(diǎn)）。為(4)正定（負(fù)定）；證明：借助多元函數(shù)的泰勒公式：（x充分接近時(shí)）。課后作業(yè)P382.12.32.9--2.14第二章基本概念和理論基礎(chǔ)本章主要內(nèi)容：§1代數(shù)基礎(chǔ)：范數(shù)、正定性§2多元函數(shù)分析基礎(chǔ)：Hesse矩陣、方向?qū)?shù)、中值公式§3多元函數(shù)的極值§4等高線§5凸分析基礎(chǔ)：凸集、凸函數(shù)、凸規(guī)劃§6

最優(yōu)化算法的結(jié)構(gòu)Z=f(x,y)

的圖形是一條曲面。f(x,y)=c

的圖形稱(chēng)為等高線或等值線。令c=c1,c2,…等一系列的值，得到一族等高線。從等高線族的圖形上大致可以看出函數(shù)值的變化情況。（利用二維觀察三維）§4

等高線二元函數(shù)的等值線性質(zhì)：極值點(diǎn)附近，二元函數(shù)的等高線近似于一族同心橢圓.理由:注：極值點(diǎn)附近，二次函數(shù)的等高線就是一族準(zhǔn)確的同心橢圓.極值點(diǎn)正好就是橢圓族的共同中心。因此，求二次函數(shù)的極值點(diǎn)問(wèn)題，從幾何上講，也就是求等值線族的共同中心。解：展開(kāi)例把二次函數(shù)

化為矩陣向量形式并檢驗(yàn)Q是否正定，如正定，試用公式

求這個(gè)函數(shù)的極小點(diǎn)。與題中函數(shù)比較各項(xiàng)系數(shù)為：由前例知正定,極小點(diǎn)為性質(zhì)：若函數(shù)在某點(diǎn)的梯度不為零，則該梯度必與過(guò)該點(diǎn)的等值線垂直.（梯度方向也稱(chēng)法向量）理由:注：梯度所指的方向總是等值線的法方向，并且在極大值點(diǎn)處梯度方向指向近似橢圓的中心，而在極小值點(diǎn)處梯度方向背離近似橢圓的中心。定義（等值面）在三維以上的空間中，使目標(biāo)函數(shù)z=f(x)取同一常數(shù)值的面{x|f(x)=r,r是常數(shù)}稱(chēng)為目標(biāo)函數(shù)z=f(x)的等值面。定理

若多元函數(shù)在其極小點(diǎn)處的

Hesse陣正定，則它在這個(gè)極小點(diǎn)附近的等值面近似地呈現(xiàn)為同心超橢球面族。多元函數(shù)的等值面等值面的性質(zhì)小結(jié)不同值的等值面之間不相交，因?yàn)槟繕?biāo)函數(shù)是單值函數(shù)；除了極值點(diǎn)所在的等值面外，不會(huì)在區(qū)域內(nèi)部中斷，因?yàn)槟繕?biāo)函數(shù)是連續(xù)的；一般地，在極值點(diǎn)附近，等值面（線）近似地呈現(xiàn)為同心橢球面族（橢圓族），因?yàn)樘├展?；二次函?shù)的等值面是同心橢球面族，極值點(diǎn)是這個(gè)橢圓球面的共同中心。

二元函數(shù)，梯度所指的方向總是等值線的法方向，并且在極大值點(diǎn)處梯度方向指向近似橢圓的中心，而在極小值點(diǎn)處梯度方向背離近似橢圓的中心。例

用圖解法求解解：先畫(huà)出目標(biāo)函數(shù)等值線，再畫(huà)出約束曲線。對(duì)應(yīng)的最優(yōu)值為由圖易見(jiàn)約束直線與等值線的切點(diǎn)是最優(yōu)點(diǎn)，利用解析幾何的方法得該切點(diǎn)為本處約束曲線是一條直線，這條直線就是可行域；而最優(yōu)點(diǎn)就是可行域上使等值線具有最小值的點(diǎn).第二章基本概念和理論基礎(chǔ)本章主要內(nèi)容：§1代數(shù)基礎(chǔ)：范數(shù)、正定性§2多元函數(shù)分析基礎(chǔ)：Hesse矩陣、方向?qū)?shù)、中值公式§3多元函數(shù)的極值§4等高線§5凸分析基礎(chǔ)：凸集、凸函數(shù)、凸規(guī)劃§6

最優(yōu)化算法概述一元函數(shù)有結(jié)論：若f(x)在區(qū)間[a,b]上是凸的，則x*是f(x)的極小值點(diǎn)等價(jià)于x*是f(x)的最小值。且由微分學(xué)知：若，則f(x)是凸的?！?凸分析基礎(chǔ)問(wèn)題（極小值點(diǎn)和最小值點(diǎn)之間的關(guān)系）：設(shè)f(x)定義在D內(nèi)，若x*為f(x)的最小值點(diǎn)，則x*為f(x)的極小值點(diǎn)。反過(guò)來(lái)不一定成立。為研究多元函數(shù)的極值與最值的關(guān)系，下面介紹多元函數(shù)凸性。規(guī)定：空集和單元素集是凸集。根據(jù)定義：三角形，矩形，圓，球，凸多邊形，第一象限，第一卦限等都是凸集。等價(jià)定義（凸集）：設(shè)§5.1凸集定義（凸集）：若集合中任意兩點(diǎn)的連線都屬于，則稱(chēng)為凸集。因?yàn)閮牲c(diǎn)

連線上任一點(diǎn)可以表示為

凸集的幾何特征凸集的代數(shù)特征稱(chēng)集合為凸集。恒有凸集：在點(diǎn)集中任取兩點(diǎn)，則其連線仍在其中。即沒(méi)有凹入的部分；沒(méi)有空洞。⑴⑵⑶⑷⑸⑹ABCD證明:即所以即H是凸集。

例2:

集合是凸集,稱(chēng)為超平面，c為n維向量。

例3：鄰域是凸集。

例1:

集合是凸集.定義：設(shè)那么稱(chēng)是

的凸組合。

性質(zhì)2：S是凸集

S中任意有限個(gè)點(diǎn)的凸組合屬于S。證明：見(jiàn)書(shū)中定理2.9(P23)。充分性顯然。必要性：歸納法。性質(zhì)1：設(shè)是凸集，則也是凸集。注：不一定是凸集。性質(zhì)1：設(shè)是凸集，則也是凸集。定義（凸包）：包含集合D的所有凸集的交集,稱(chēng)為D的凸包.記作Co(D)或者H(D).注：由性質(zhì)1可知，Co(D)是包含D的最小凸集。0定義（凸錐）：設(shè)，如果對(duì)任意的及所有的，都有，則稱(chēng)是一個(gè)錐。一個(gè)同時(shí)是凸集的錐，稱(chēng)為凸錐。定義（多胞形）：有限個(gè)點(diǎn)的凸包凸集分離定理HS2S1定義（集合分離）：設(shè)是非空集合，如果存在向量及，使得則稱(chēng)超平面分離和。定理（投影定理）：設(shè)是非空凸集，，則（1）存在唯一的使得它與y

的距離最小，即（2）是點(diǎn)y

到S的距離最小的充要條件為證明：參考袁亞湘P39。令根據(jù)下確界的定義，存在序列使得。下面證它是柯西列即可。ySx定理（點(diǎn)與凸集的分離定理）：設(shè)是非空凸集，，則如果存在唯一的及，使得即存在超平面分離y

和S。ylS證明：參考袁亞湘P41定理（Farkas

）設(shè)

則下列關(guān)系式有且僅有一組有解：證明：參考袁亞湘P42幾何解釋:(1)有解，(2)無(wú)解a2a1amca1a2amc(1)無(wú)解，(2)有解(1)式有解當(dāng)且僅當(dāng)凸錐{x|Ax≤0}與半空間{x|cTx>0}的交非空.(2)式有解當(dāng)且僅當(dāng)c在由A的行向量a1,a2,…,am所生成的凸錐內(nèi).定義（凸函數(shù)）:

設(shè)集合D

Rn

為凸集，函數(shù)f:D

R,若x,y

D,

(0,1)，均有

f(

x+(1-

)y

)≤f(x)+(1-

)f(y)

，則稱(chēng)f(x)為凸集D上的凸函數(shù)。凸函數(shù)：任意兩個(gè)點(diǎn)的凸組合的函數(shù)值小于等于這兩個(gè)點(diǎn)的函數(shù)值的凸組合。嚴(yán)格凸函數(shù)：進(jìn)一步，若有上面不等式以嚴(yán)格不等式成立，則稱(chēng)f(x)為凸集上的嚴(yán)格凸函數(shù)。凹函數(shù)：當(dāng)-f(x)為凸函數(shù)(嚴(yán)格凸)時(shí)，則稱(chēng)f(x)為凹函數(shù)(嚴(yán)格凹)。§5.2凸函數(shù)f(X)Xf(X1)f(X2)

X1X2凸函數(shù)幾何意義：任意兩點(diǎn)的函數(shù)值的連線上的點(diǎn)都在曲線的上方，即弦位于曲線的上方．αx1+(1-α)x2f(αx1+(1-α)x2)αf(x1)

+(1-α)f(x2)性質(zhì)2：設(shè)f1,f2

是凸集D上的凸函數(shù)，設(shè)a,b>0,

則af1+bf2

是凸函數(shù)；

f(x)=max{f1(x),f2(x)}

是凸函數(shù)。思考：

af1-bf2

是否是凸函數(shù)？

g(x)=min{f1(x),f2(x)}是否是凸函數(shù)？凸函數(shù)的性質(zhì)性質(zhì)1：f(x)

為凸集S上的凸函數(shù)

S上任意有限點(diǎn)的凸組合的函數(shù)值小于等于各點(diǎn)函數(shù)值的凸組合。

證明參見(jiàn)文中P26定理2.10的證明。充分性顯然，必要性用數(shù)學(xué)歸納法。定理(一階條件):

設(shè)D

Rn

為非空凸集，函數(shù)f:D

R

在D上可微，則

(1)f在D上為凸函數(shù)任意x，y

D，恒有

f(y)

≥f(x)+

fT(x)(y-x)

(1)(2)f在D上為嚴(yán)格凸函數(shù)任意x≠y

D，恒有

f(y)>f(x)+

fT(x)(y-x).(2)

證明:

見(jiàn)書(shū)中定理2.11(P27)，見(jiàn)下一頁(yè)。凸函數(shù)的一階判定定理嚴(yán)格凸函數(shù)凸函數(shù)證明：（必要性）設(shè)f(x)

為凸函數(shù)，根據(jù)定義所以?xún)蛇吶O限得即若f(x)嚴(yán)格凸函數(shù)，則有故有證明：（充分性）設(shè)令由假設(shè)得一式乘以a，二式乘以1-a，相加得若f(x)嚴(yán)格凸函數(shù)，上述大于等于號(hào)均變成大于號(hào)，即成立。幾何解釋一個(gè)可微函數(shù)是凸函數(shù)當(dāng)且僅當(dāng)曲線位于切線的上方凸函數(shù)

f(y)

≥f(x)+

fT(x)(y-x)定理5（二階條件）:

設(shè)D

Rn

為含內(nèi)點(diǎn)的非空凸集，函數(shù)f:D

R在D上二次可微，則

a)f在D上為凸函數(shù)

x

D，2f(x)

半正定；

b)

x

D，2f(x)

正定

f在D上為嚴(yán)格凸函數(shù)（特別注意逆命題不成立）。凸函數(shù)的二階判定定理證明：（充分性)（必要性）令得，

2f(x)

半正定。例：設(shè)二次函數(shù)，根據(jù)二階條件得

(1)若為半正定矩陣，在中為凸函數(shù)；(2)若為正定矩陣，在中為嚴(yán)格凸函數(shù)。例：判斷f(x)=5x12-6x1x2+5x22在凸集D上是否是凸函數(shù)？的順序主子式都是正的，所以正定，因此f(x)在凸集D上是嚴(yán)格凸函數(shù)。由于故證明為凸函數(shù)。也是凸函數(shù)。根據(jù)性質(zhì)2，為凸函數(shù)?？聪率龈魇绞欠癯闪ⅲ鹤C明：用定義證明是凸函數(shù)，即對(duì)任意和例:

試證明為凹函數(shù)?；蚣达@然，不管和

取什么值，總有為凹函數(shù)。因此從而用同樣的方法可以證明用一階條件證明只需證任意選取兩點(diǎn)或或或不管y1、y2、x1、x2取什么值，上式均成立，從而得證。是凹函數(shù)，要證例:

試證明為凹函數(shù)。-f(x)的海賽矩陣處處正定，故為(嚴(yán)格)凹函數(shù)。

下面用二階條件證明:由于例:

試證明為凹函數(shù)。5.3凸規(guī)劃例（凸規(guī)劃）:

考慮如下非線性規(guī)劃當(dāng)都是凸函數(shù)時(shí)，則規(guī)劃(1)為凸規(guī)劃。定義（凸規(guī)劃）:設(shè)為凸集，為上的凸函數(shù)，則稱(chēng)規(guī)劃問(wèn)題為凸規(guī)劃問(wèn)題．證明:即證明為凸集，因?yàn)?gi

為凸函數(shù)，所以-gi(

x+(1-

)y)≤-gi(x)-(1-

)gi(y)進(jìn)而

gi(

x+(1-

)y)≥gi(x)+(1-

)gi(y)≥0性質(zhì)1:

設(shè)(1)為凸規(guī)劃，則

A.規(guī)劃(1)的可行集R是凸集；

B.規(guī)劃(1)的最優(yōu)解集是凸集；

C.規(guī)劃(1)的任何局部極小點(diǎn)都是全局極小點(diǎn)。

證明：見(jiàn)書(shū)中P30定理2.13.性質(zhì)2:

設(shè)(1)為凸規(guī)劃，若f(x)在非空可行集R上是嚴(yán)格凸函

數(shù)，則(1)的全局極小點(diǎn)是唯一的。

證明：見(jiàn)書(shū)中P31定理2.14.注:

非線性規(guī)劃的局部最優(yōu)解不一定是整體最優(yōu)解,其可行解和最優(yōu)解集也不一定是凸集,甚至不是連通集.如果是凸規(guī)劃,就有很多好的性質(zhì)。凸規(guī)劃的性質(zhì)定理

凸規(guī)劃的任一局部最優(yōu)解都是它的整體最優(yōu)解。證明：設(shè)x*是凸規(guī)劃的一個(gè)局部最優(yōu)解，則存在δ>0,使如果x*不是整體最優(yōu)解，則又因?yàn)閒是凸函數(shù)，所以取α>0充分?。豪缦路蔷€性規(guī)劃是否為凸規(guī)劃：正定，凸函數(shù)所以，該問(wèn)題為凸規(guī)劃。半正定，凸函數(shù)半正定，凸函數(shù)

如圖所示，該問(wèn)題最優(yōu)解（最小點(diǎn)）在x*點(diǎn)取得。練習(xí)驗(yàn)證下列（MP）是凸規(guī)劃課后作業(yè)

P382.192.20(1,3)2.282.29第二章基本概念和理論基礎(chǔ)本章主要內(nèi)容：§1代數(shù)基礎(chǔ)：范數(shù)、正定性、序列收斂§2多元函數(shù)分析基礎(chǔ)：Hesse矩陣、方向?qū)?shù)、中值公式§3多元函數(shù)的極值§4等高線§5凸分析基礎(chǔ)：凸集、凸函數(shù)、凸規(guī)劃§6

最優(yōu)化算法的結(jié)構(gòu)n元函數(shù)求解無(wú)約束優(yōu)化問(wèn)題§6最優(yōu)化算法的結(jié)構(gòu)定理(必要條件)

設(shè)

(1)為D的一個(gè)內(nèi)點(diǎn);(2)

在可微;(3)為

的極值點(diǎn);

則。定理(充分條件)

設(shè)

(1)為D的一個(gè)內(nèi)點(diǎn);(2)

在二次連續(xù)可微;(3);(4)正定;則為的嚴(yán)格局部極小點(diǎn)。對(duì)一般n元函數(shù)，由條件

得到一非線性方程組，解它相當(dāng)困難。對(duì)于不可微函數(shù)，當(dāng)然談不上使用這樣的方法。迭代算法根據(jù)一階必要條件，令函數(shù)梯度等于零，求得駐點(diǎn)；然后用充分條件進(jìn)行判別，求出所要的最優(yōu)解。大致想法：為了求函數(shù)f(x)

的最優(yōu)解，首先給定一個(gè)初始估計(jì)然后按某種規(guī)則(即算法)找出比更好的解再按此種規(guī)則找出比更好的解如此即可得到一個(gè)解的序列若這個(gè)解序列收斂于該問(wèn)題的最優(yōu)解x*，則算法有效。無(wú)約束優(yōu)化問(wèn)題(P1)——約束優(yōu)化問(wèn)題問(wèn)題(P2)——迭代法的基本思想步長(zhǎng)因子搜索方向：可行方向、下降方向迭代法的基本思想：希望找到迭代序列{xk}，其迭代格式為定義：（可行方向）設(shè)D為可行域，在點(diǎn)處，對(duì)于非零向量d

，若存在實(shí)數(shù)，使得，則稱(chēng)d

為f(x)在點(diǎn)的可行方向。xkxk+1dkak注：根據(jù)泰勒公式即當(dāng)時(shí)，總存在使得當(dāng)時(shí)，恒有