第二章基本概念和理論基礎本章主要內容：§1代數基礎：范數、正定性§2多元函數分析基礎：Hesse矩陣、方向導數、中值公式§3多元函數的極值§4等高線§5凸分析基礎：凸集、凸函數、凸規劃§6

最優化算法的結構向量范數定義——橢球范數(A正定)

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

階對稱矩陣,若

，均有，則稱

Q正定。若

，均有

，則稱Q半正定。若，均有，則稱Q負定。若,均有，則稱Q半負定。矩陣正定性正定判定定理矩陣

Q半正定

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

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

Q正定

Q的所有特征根大于零;

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

負定判定定理矩陣

Q半負定

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

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

Q負定

Q的所有特征根小于零;

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

解：對稱矩陣Q的三個順序主子式依次為例1

判定矩陣是否正定:矩陣Q是正定的。第二章基本概念和理論基礎本章主要內容：§1代數基礎：范數、正定性§2多元函數分析基礎：Hesse矩陣、方向導數、中值公式§3多元函數的極值§4等高線§5凸分析基礎：凸集、凸函數、凸規劃§6

最優化算法的結構§2

多元函數分析基礎n元函數：

n元線性函數：

n元二次函數：

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

設為一向量序列，如果則稱序列依范數收斂到,記為

給定區域D上的n

元實值函數梯度、Hesse

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

矩陣常用的梯度和Hesse陣公式：其中Q為實對稱矩陣方向導數定義(方向導數)設在點x

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

在x

處沿方向d

的方向導數為最速上升方向最速下降方向解：由于則函數在處的最速下降方向例1試求目標函數在點處的最速下降方向，并求沿這個方向移動一個單位長度后新點的目標函數值。此方向上的單位向量新點是中值公式設

二階可導，則在x*的鄰域內有：一階Taylor展開式二階Taylor展開式第二章基本概念和理論基礎本章主要內容：§1代數基礎：范數、正定性§2多元函數分析基礎：Hesse矩陣、方向導數、中值公式§3多元函數的極值§4等高線§5凸分析基礎：凸集、凸函數、凸規劃§6

最優化算法的結構§3

多元函數的極值

對于一個極小化問題，我們的目的是求出全局極小點，而全局極小點不好求，因此我們一般的做法是先求出所有局部極小值點，再從中找出全局極小點。為了求出函數的局部極小值點，我們需要考察函數f在局部極小點處滿足什么條件？反過來，滿足什么條件的點是局部極小點？首先回顧二元函數的極值條件（高等數學），然后推廣到多元函數。二元函數極值的判別條件定理(必要條件)

設(1)為D的一個內點;可微;(2)在處,

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

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

(2)當時，不是的極值點，稱為函數的鞍點；(3)當時，不能確定，需另行討論。定理(充分條件)

設(1)為D的一個內點;二次連續可微;(2)在的駐點，即(3)為且令則(1)當時，具有極值取嚴格極大值取嚴格極小值Hesse陣負定Hesse陣正定多元函數的極值判別條件定理(必要條件)

設(1)x*為D的一個內點;可微;(2)在則的極值點;(3)為且證明:

借助一元函數極值的必要條件，見下頁。

設是的局部極小點，為任意單位向量。由定義知：當,即時，總有：令則而是D的內點，從而與之對應的t=0是的局部極小點。

由一元函數極小點必要性條件知,而由前述性質知則,由單位向量任意性，即知。證明:（若，取，則

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

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

最優化算法的結構Z=f(x,y)

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

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

等高線二元函數的等值線性質：極值點附近，二元函數的等高線近似于一族同心橢圓.理由:注：極值點附近，二次函數的等高線就是一族準確的同心橢圓.極值點正好就是橢圓族的共同中心。因此，求二次函數的極值點問題，從幾何上講，也就是求等值線族的共同中心。解：展開例把二次函數

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

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

若多元函數在其極小點處的

Hesse陣正定，則它在這個極小點附近的等值面近似地呈現為同心超橢球面族。多元函數的等值面等值面的性質小結不同值的等值面之間不相交，因為目標函數是單值函數；除了極值點所在的等值面外，不會在區域內部中斷，因為目標函數是連續的；一般地，在極值點附近，等值面（線）近似地呈現為同心橢球面族（橢圓族），因為泰勒公式；二次函數的等值面是同心橢球面族，極值點是這個橢圓球面的共同中心。

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

用圖解法求解解：先畫出目標函數等值線，再畫出約束曲線。對應的最優值為由圖易見約束直線與等值線的切點是最優點，利用解析幾何的方法得該切點為本處約束曲線是一條直線，這條直線就是可行域；而最優點就是可行域上使等值線具有最小值的點.第二章基本概念和理論基礎本章主要內容：§1代數基礎：范數、正定性§2多元函數分析基礎：Hesse矩陣、方向導數、中值公式§3多元函數的極值§4等高線§5凸分析基礎：凸集、凸函數、凸規劃§6

最優化算法概述一元函數有結論：若f(x)在區間[a,b]上是凸的，則x*是f(x)的極小值點等價于x*是f(x)的最小值。且由微分學知：若，則f(x)是凸的?！?凸分析基礎問題（極小值點和最小值點之間的關系）：設f(x)定義在D內，若x*為f(x)的最小值點，則x*為f(x)的極小值點。反過來不一定成立。為研究多元函數的極值與最值的關系，下面介紹多元函數凸性。規定：空集和單元素集是凸集。根據定義：三角形，矩形，圓，球，凸多邊形，第一象限，第一卦限等都是凸集。等價定義（凸集）：設§5.1凸集定義（凸集）：若集合中任意兩點的連線都屬于，則稱為凸集。因為兩點

連線上任一點可以表示為

凸集的幾何特征凸集的代數特征稱集合為凸集。恒有凸集：在點集中任取兩點，則其連線仍在其中。即沒有凹入的部分；沒有空洞。⑴⑵⑶⑷⑸⑹ABCD證明:即所以即H是凸集。

例2:

集合是凸集,稱為超平面，c為n維向量。

例3：鄰域是凸集。

例1:

集合是凸集.定義：設那么稱是

的凸組合。

性質2：S是凸集

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

的距離最小，即（2）是點y

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

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

）設

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

設集合D

Rn

為凸集，函數f:D

R,若x,y

D,

(0,1)，均有

f(

x+(1-

)y

)≤f(x)+(1-

)f(y)

，則稱f(x)為凸集D上的凸函數。凸函數：任意兩個點的凸組合的函數值小于等于這兩個點的函數值的凸組合。嚴格凸函數：進一步，若有上面不等式以嚴格不等式成立，則稱f(x)為凸集上的嚴格凸函數。凹函數：當-f(x)為凸函數(嚴格凸)時，則稱f(x)為凹函數(嚴格凹)?！?.2凸函數f(X)Xf(X1)f(X2)

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

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

是凸集D上的凸函數，設a,b>0,

則af1+bf2

是凸函數；

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

是凸函數。思考：

af1-bf2

是否是凸函數？

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

為凸集S上的凸函數

S上任意有限點的凸組合的函數值小于等于各點函數值的凸組合。

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

設D

Rn

為非空凸集，函數f:D

R

在D上可微，則

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

D，恒有

f(y)

≥f(x)+

fT(x)(y-x)

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

D，恒有

f(y)>f(x)+

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

證明:

見書中定理2.11(P27)，見下一頁。凸函數的一階判定定理嚴格凸函數凸函數證明：（必要性）設f(x)

為凸函數，根據定義所以兩邊取極限得即若f(x)嚴格凸函數，則有故有證明：（充分性）設令由假設得一式乘以a，二式乘以1-a，相加得若f(x)嚴格凸函數，上述大于等于號均變成大于號，即成立。幾何解釋一個可微函數是凸函數當且僅當曲線位于切線的上方凸函數

f(y)

≥f(x)+

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

設D

Rn

為含內點的非空凸集，函數f:D

R在D上二次可微，則

a)f在D上為凸函數

x

D，2f(x)

半正定；

b)

x

D，2f(x)

正定

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

2f(x)

半正定。例：設二次函數，根據二階條件得

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

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

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

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

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

試證明為凹函數。5.3凸規劃例（凸規劃）:

考慮如下非線性規劃當都是凸函數時，則規劃(1)為凸規劃。定義（凸規劃）:設為凸集，為上的凸函數，則稱規劃問題為凸規劃問題．證明:即證明為凸集，因為-gi

為凸函數，所以-gi(

x+(1-

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

)gi(y)進而

gi(

x+(1-

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

)gi(y)≥0性質1:

設(1)為凸規劃，則

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

B.規劃(1)的最優解集是凸集；

C.規劃(1)的任何局部極小點都是全局極小點。

證明：見書中P30定理2.13.性質2:

設(1)為凸規劃，若f(x)在非空可行集R上是嚴格凸函

數，則(1)的全局極小點是唯一的。

證明：見書中P31定理2.14.注:

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

凸規劃的任一局部最優解都是它的整體最優解。證明：設x*是凸規劃的一個局部最優解，則存在δ>0,使如果x*不是整體最優解，則又因為f是凸函數，所以取α>0充分?。豪缦路蔷€性規劃是否為凸規劃：正定，凸函數所以，該問題為凸規劃。半正定，凸函數半正定，凸函數

如圖所示，該問題最優解（最小點）在x*點取得。練習驗證下列（MP）是凸規劃課后作業

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

最優化算法的結構n元函數求解無約束優化問題§6最優化算法的結構定理(必要條件)

設

(1)為D的一個內點;(2)

在可微;(3)為

的極值點;

則。定理(充分條件)

設

(1)為D的一個內點;(2)

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

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

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

，若存在實數，使得，則稱d

為f(x)在點的可行方向。xkxk+1dkak注：根據泰勒公式即當時，總存在使得當時，恒有