最優(yōu)化問題數(shù)學基礎(chǔ)

關(guān)于最優(yōu)化問題數(shù)學基礎(chǔ)§1.1二次型與正定矩陣

一、二次型與實對稱矩陣二次型理論在最優(yōu)化設(shè)計中應(yīng)用十分廣泛．應(yīng)用矩陣的乘法運算，二次型與實對稱矩陣緊密地聯(lián)系在一起了，從而二次型的基本問題又可轉(zhuǎn)化成實對稱矩陣問題．二次型理論問題起源于化二次曲線和二次曲面的方程為標準形式的問題．推廣到n維空間中，二次超曲面的一般方程為第2頁,共67頁，2024年2月25日，星期天

第3頁,共67頁，2024年2月25日，星期天用矩陣表示為其中，矩陣A的元素正是二次型的項的系數(shù)的一半，是二次型的項的系數(shù)．因此，二次型和它的矩陣A是相互唯一決定的，且．第4頁,共67頁，2024年2月25日，星期天二、正定矩陣定義2.1如果二次型對于任何一組不全為零的數(shù)恒有則稱正定，且二次型矩陣A也稱為正定．簡言之，一個對稱矩陣A如果是正定的，則二次型對于所有非零向量X其值總為正．類似可以給出定義，若二次型則A為半正定矩陣；若，則A為半負定矩陣；若二次型既不是半正定又不是半負定，就稱矩陣A為不定的．第5頁,共67頁，2024年2月25日，星期天

矩陣A為正定的充要條件是它的行列式的順序主子式全部大于零，即由此可見，正定矩陣必然是非奇異的．例2.1判斷矩陣是否正定．解∵，∴A是正定的．第6頁,共67頁，2024年2月25日，星期天一、方向?qū)?shù)所謂方向?qū)?shù)的概念是作為偏導數(shù)的一個推廣而引入，它主要研究函數(shù)沿任一給定方向的變化率．定義2.2設(shè)在點處可微，P是固定不變的非零向量，是方向P上的單位向量，則稱極限

(2.1)為函數(shù)在點處沿P方向的方向?qū)?shù)，式中

是它的記號．§2.2方向?qū)?shù)與梯度第7頁,共67頁，2024年2月25日，星期天

定義2.3設(shè)是連續(xù)函數(shù)，，且，若存在，當時都有，則稱P為在點處的下降方向．若，則稱P為在點處的上升方向．由以上兩個定義可立刻得到如下的結(jié)論：若，則從出發(fā)在附近沿P方向是下降；若，則從出發(fā)在附近沿P方向是上升．第8頁,共67頁，2024年2月25日，星期天二、梯度定義2.4以的n個偏導數(shù)為分量的向量稱為在X處的梯度，記為． 梯度也可以稱為函數(shù)關(guān)于向量的一階導數(shù)．以下幾個特殊類型函數(shù)的梯度公式是常用的：（1）若（常數(shù)），則，即；（2） ．證設(shè)，則于是的第個分量是．所以（3）．（4）若Q是對稱矩陣，則第9頁,共67頁，2024年2月25日，星期天三、梯度與方向?qū)?shù)之間的關(guān)系定理2.1設(shè)在點處可微，則，其中是方向上的單位向量.由這個定理容易得到下列結(jié)論：(1)若，則P的方向是函數(shù)在點處的下降方向；(2)若，則的方向是函數(shù)在點處的上升方向．方向?qū)?shù)的正負決定了函數(shù)值的升降，而升降的快慢就由它的絕對值大小決定．絕對值越大，升降的速度就越快，即第10頁,共67頁，2024年2月25日，星期天=·1·

上式中的等號，當且僅當?shù)姆较蚺c的方向相同時才成立．由此可得如下重要結(jié)論(如圖2.1所示）：(1)梯度方向是函數(shù)值的最速上升方向；(2)函數(shù)在與其梯度正交的方向上變化率為零；(3)函數(shù)在與其梯度成銳角的方向上是上升的，而在與其梯度成鈍角的方向上是下降的；(4)梯度反方向是函數(shù)值最速下降方向．

·1·第11頁,共67頁，2024年2月25日，星期天對于一個最優(yōu)化問題，為了盡快得到最優(yōu)解，在每一步迭代過程中所選取的搜索方向總是希望它等于或者是靠近于目標函數(shù)的負梯度-----圖2.1的方向，這樣才能使函數(shù)值下降的最快．第12頁,共67頁，2024年2月25日，星期天例2.2試求目標函數(shù)在點處的最速下降方向，并求沿這個方向移動一個單位長后新點的目標函數(shù)值．解因為所以最速下降方向是－==．這個方向上的單位向量是故新點是對應(yīng)目標函數(shù)值為第13頁,共67頁，2024年2月25日，星期天§2.3海色矩陣及泰勒展式

一、海色（Hesse）矩陣前面說過，梯度是關(guān)于的一階導數(shù)，現(xiàn)在要問關(guān)于的二階導數(shù)是什么？定義2.5設(shè)：:，，如果在點處對于自變量的各分量的二階偏導數(shù)都存在，則稱函數(shù)在點處二階可導，并且稱矩陣第14頁,共67頁，2024年2月25日，星期天是在點處的Hesse矩陣．在數(shù)學分析中已經(jīng)知道，當在點處的所有二階偏導數(shù)為連續(xù)時有因此，在這種情況下Hesse矩陣是對稱的．第15頁,共67頁，2024年2月25日，星期天例2.3求目標函數(shù)的梯度和Hesse矩陣．解因為

所以第16頁,共67頁，2024年2月25日，星期天又因為所以第17頁,共67頁，2024年2月25日，星期天例2.4設(shè)，求線性函數(shù)在任意點X處的梯度和Hesse矩陣．解:設(shè),則

（2.2）

∴

由式（2.2）進而知∴（階零矩陣）．第18頁,共67頁，2024年2月25日，星期天

例2.5設(shè)是對稱矩陣，，求二次函數(shù)在任意點處的梯度和Hesse矩陣．解設(shè)則將它對各變量求偏導數(shù)，得∴

第19頁,共67頁，2024年2月25日，星期天在上式中顯然再對它們求偏導數(shù)得∴以上例子說明，元函數(shù)求導與一元函數(shù)的求導在形式上是一致的，即線性函數(shù)的一階導數(shù)為常向量，其二階導數(shù)為零矩陣；而二次函數(shù)的一階導數(shù)為線性向量函數(shù)，二階導數(shù)為常矩陣．最后介紹在今后的計算中要用到的向量函數(shù)的導數(shù)．第20頁,共67頁，2024年2月25日，星期天定義2.6設(shè)，記如果在點處于自變量的各分量的偏導數(shù)都存在，則稱向量函數(shù)在點處是一階可導的，并且稱矩陣第21頁,共67頁，2024年2月25日，星期天是在點處的一階導數(shù)或Jacobi矩陣，簡記為由于n元函數(shù)的梯度是向量函數(shù)所以的一階導數(shù)或Jacobi矩陣為第22頁,共67頁，2024年2月25日，星期天

得到第23頁,共67頁，2024年2月25日，星期天據(jù)此，從上式得知，函數(shù)梯度的Jacobi矩陣即為此函數(shù)的Hesse矩陣．下面給出今后要用到的幾個公式：（1），其中是分量全為常數(shù)的維向量，是階零矩陣．（2），其中是維向量，是階單位矩陣．（3），其中是階矩陣．（4）設(shè)，其中，則第24頁,共67頁，2024年2月25日，星期天二、泰勒展開式

多元函數(shù)的泰勒展開在最優(yōu)化方法中十分重要，許多方法及其收斂性的證明是從它出發(fā)，這里給出泰勒展開定理及其證明．

定理2.2設(shè)具有二階連續(xù)偏導數(shù)，則（2.3）其中，而．證設(shè)，于是．對按一元函數(shù)在點展開，得到其中．令，于是(2.4)第25頁,共67頁，2024年2月25日，星期天又因為代入式（2.4）中，所以

式（2.3）還可以寫成

第26頁,共67頁，2024年2月25日，星期天§2.4極小點的判定條件函數(shù)在局部極小點應(yīng)滿足什么條件？反之，滿足什么條件的是局部極小點？這是我們關(guān)心的基本問題．下面針對多元函數(shù)的情形給出各類極小點的定義．定義2.7

對于任意給定的實數(shù)，滿足不等式集合稱為點的鄰域，記為定義2.8

設(shè)，若存在點和數(shù)，都有，則稱為局部極小點（非嚴格）．第27頁,共67頁，2024年2月25日，星期天定義2.9

設(shè)，若存在點和數(shù)，但，都有，則稱為的嚴格局部極小點．定義2.10

設(shè)，若存在點和數(shù)，都有，則稱為在D上的全局極小點（非嚴格）．定義2.11

設(shè)，若存在點，但，都有，則稱為在D上的嚴格全局極小點．第28頁,共67頁，2024年2月25日，星期天由以上定義看到，是局部極小點，是指在以為中心的一個鄰域中在點處取得最小的值；而是全局極小點，是指在定義域D中在點處取得最小的值．全局極小點可能在某個局部極小點處取得，也可能在D的邊界上取得．實際問題通常是求全局極小點，但是直到目前為止，最優(yōu)化中絕大多數(shù)方法都是求局部極小點的，解決這一矛盾的一種方法是先求出所有的局部極小點，再求全局極小點．第29頁,共67頁，2024年2月25日，星期天定理2.3

設(shè)具有連續(xù)的一階偏導數(shù)．若是的局部極小點并且是D的內(nèi)點，則（2.5）證設(shè)是任意單位向量，因為是的局部極小點，所以存在，當或時總有． （2.6）引入輔助一元函數(shù)，此時，由式（2.6）得．又因第30頁,共67頁，2024年2月25日，星期天是D的內(nèi)點，所以與它對應(yīng)的是的局部極小點．又根據(jù)一元函數(shù)極小點的必要條件，得到，即再由單位向量的任意性得．這里條件（2.5）僅僅是必要的，而不是充分的．例如在點處的梯度是，但是雙曲面的鞍點，而不是極小點（如圖2.2所示）．第31頁,共67頁，2024年2月25日，星期天定義2.12

設(shè)是D的內(nèi)點．若，則稱為的駐點．定理2.4

設(shè)具有連續(xù)二階偏導數(shù)，是D的一個內(nèi)點．若，并且是正定的，則是的嚴格局部極小點．第32頁,共67頁，2024年2月25日，星期天證因為是正定矩陣，則必存在，使得對于所有的都有（參看高等代數(shù)二次型理論）．現(xiàn)在將在點處按泰勒公式展開，并注意到，于是可得第33頁,共67頁，2024年2月25日，星期天當充分接近（但）時，上式左端的符號取決于右端第一項，因此一般說來，這個定理僅具有理論意義．因為對于復雜的目標函數(shù)，Hesse矩陣不易求得，它的正定性就更難判定了．第34頁,共67頁，2024年2月25日，星期天定理2.5

若多元函數(shù)在其極小點處的Hesse矩陣是正定的，則它在這個極小點附近的等值面近似地呈現(xiàn)為同心橢球面族．證設(shè)是多元函數(shù)的極小點，并設(shè)是充分靠近極小點的一個等值面，即充分?。言邳c展成泰勒表達式，即右端第二項因是極小點有而消失．如果略去第4項,那么又因為，所以（2.7）按假設(shè)正定，由二次型理論知式（2.7）是以為中心的橢球面方程．第35頁,共67頁，2024年2月25日，星期天§2.5錐、凸集、凸錐

在本節(jié)中，給出維Euclid空間中的錐、凸集和凸錐的定義，以及與其相關(guān)的一些概念和性質(zhì)．一、定義與簡單性質(zhì)定義2.13

集合．若，及任意的數(shù)，均有，則稱C為錐．定義2.14

設(shè)是中的個已知點．若對于某點存在常數(shù)且使得，則稱是的凸組合．若且，則稱是的嚴格凸組合．第36頁,共67頁，2024年2月25日，星期天定義2.15

集合．若和，以及任-意的數(shù)，均有則稱C為凸集．定義2.16

設(shè)且，，則集合稱為中的半空間．特別地，規(guī)定：空集是凸集．容易驗證，空間、半空間、超平面、直線、點、球都是凸集．第37頁,共67頁，2024年2月25日，星期天定理2.6

任意一組凸集的交仍然是凸集．證設(shè)，其中I是的下標集，都是凸集．任取，則對于任意都是．任取且，因是凸集,有于是，即C是凸集．若集合C為錐，C又為凸集，則稱C為凸錐．若C為凸集，也為閉集，則稱C為閉凸集．若C為凸錐，也為閉集，則稱C為閉凸錐．第38頁,共67頁，2024年2月25日，星期天由數(shù)學歸納法不難證明如下的定理2.7和2.8．定理2.7

集合C為凸集的充分必要條件是，及任意數(shù)（），有定理2.8

集合C為凸錐的充分必要條件是，及任意數(shù),()，均有定義2.17

有限個半空間的交稱為多面集,其中為矩陣，為向量第39頁,共67頁，2024年2月25日，星期天例2.6

集合為多面集，其幾何表示如圖2.3畫斜線部分．圖2.3在多面集的表達式中，若，則多面集也是凸錐，稱為多面錐．在有關(guān)凸集的理論及應(yīng)用中，極點和極方向的概念有著重要作用．第40頁,共67頁，2024年2月25日，星期天定義2.18

設(shè)C為非空凸集，,若不能表示成C中兩個不同點的凸組合；換言之，若設(shè),必推得，則稱是凸集C的極點．按此定義，圖2.4(a)中多邊形的頂點，，，和是極點，而和不是極點．圖2.4(b)中圓周上的點均為極點．由圖2.4可以看出，在給定的兩個凸集中，任何一點都能表示成極點的凸組合．第41頁,共67頁，2024年2月25日，星期天

定義2.19

設(shè)C為中的閉凸集，P為非零向量，如果對C中的每一個，都有射線，則稱向量P為C的方向．又設(shè)和是的兩個方向，若對任何正數(shù)，有，則稱和是兩個不同的方向．若C的方向P不能表示成該集合的兩個不同方向的正的線性組合，則稱p為c的極方向．第42頁,共67頁，2024年2月25日，星期天概括起來，有下列定理：定理2.9

（RepresentationTheorem）設(shè)為非空多面集，則有（1）極點集非空，且存在有限個極點（2）極方向集合為空集的充要條件是C有界．若無界，則存在有限個極方向（3）的充要條件是其中第43頁,共67頁，2024年2月25日，星期天二、凸集分離定理凸集分離定理是凸分析中最重要的定理之一，它在最優(yōu)化理論和模型當中具有重要的應(yīng)用．所謂集合的分離是指對于兩個集合C1和C2存在一個超平面H，使得C1在H的一邊，而C2在H的另一邊．如果超平面方程為，那么對位于H某一邊的點必有，而對位于H另一邊的必有．定義2.20

設(shè)C1和C2是中的兩個非空集合，是超平面，若對于每一個都有，對于每一個都有（或情況恰好相反），則稱超平面H分離集合C1和C2．第44頁,共67頁，2024年2月25日，星期天定理2.10若C為閉凸集，，則存在以及數(shù)，對，有并且存在，使得．定理2.11設(shè)C為凸集，，則存在使得，有定理2.12設(shè)C為閉凸集，則C可表為所有包含C的半空間的交，即其中第45頁,共67頁，2024年2月25日，星期天§2.6凸函數(shù)

一、各類凸函數(shù)定義及性質(zhì)設(shè)函數(shù)定義在凸集R上，其中定義2.21若存在常數(shù)，使得以及，有則稱為一致凸函數(shù)；有則稱為嚴格凸函數(shù)；有則稱為凸函數(shù)．第46頁,共67頁，2024年2月25日，星期天定義2.22設(shè)為可微函數(shù)．若滿足都有則稱為偽凸函數(shù)．定義2.23對，且，以及，若則稱為嚴格擬凸函數(shù)；定義2.24對，以及，若則稱為擬凸函數(shù)；定義2.25對則稱為強擬凸函數(shù)．第47頁,共67頁，2024年2月25日，星期天定理2.13

若為一致凸函數(shù)，則為嚴格凸函數(shù)．證：設(shè)為一致凸函數(shù)，則，，，及，有即為嚴格凸函數(shù)．第48頁,共67頁，2024年2月25日，星期天定理2.14若為嚴格凸函數(shù)，則為凸函數(shù)．定理2.15設(shè)為可微函數(shù)．若為凸函數(shù)，則為偽凸函數(shù)．定理2.16設(shè)為偽凸函數(shù)，則為嚴格擬凸函數(shù)．定理2.17設(shè)為下半連續(xù)的嚴格擬凸函數(shù)，則為擬凸函數(shù)．定理2.18若為嚴格凸函數(shù)，則為強擬凸函數(shù)．定理2.19設(shè)為強擬凸函數(shù)，則為嚴格擬凸函數(shù)．第49頁,共67頁，2024年2月25日，星期天凸函數(shù)與凸集之間有如下關(guān)系：定理2.20

設(shè)，其中C為非空凸集．若f是凸函數(shù)，則對于任意實數(shù)，水平集是凸集．證若是空集，則是凸集．以下設(shè)非空，任取，則．設(shè)且，由f是凸函數(shù)知即，所以是凸集．判定一個函數(shù)是否為凸函數(shù)，一般說來是比較困難，但當函數(shù)可微時，有如下幾個定理可供使用．第50頁,共67頁，2024年2月25日，星期天定理2.21

設(shè)是可微函數(shù)，其中C為凸集．則（1）為凸函數(shù)的充要條件是，，都有 （2.11）（2）為嚴格凸函數(shù)的充要條件是，且都有證（1）必要性已知f是C上的凸函數(shù)，要證式（2.11）．由凸函數(shù)定義知，對滿足的任意數(shù)都有令，則．代入上式中，經(jīng)移項可得第51頁,共67頁，2024年2月25日，星期天

（2.12）令，由f的可微性，利用一階泰勒展式、方向?qū)?shù)定義及式（2.12），可得這就證明了式（2.11）．充分性任取一對數(shù)且考慮點，根據(jù)充分性假設(shè)，應(yīng)有第52頁,共67頁，2024年2月25日，星期天兩式分別乘以和后相加，得到由凸函數(shù)定義知,f是C上的凸函數(shù)．（2）充分性可依照（1）的充分性證得．必要性因為嚴格凸函數(shù)本身是凸函數(shù)，所以且,都有以下證明式中只能取“>”號．假設(shè)存在，且，使得 （2.12）第53頁,共67頁，2024年2月25日，星期天取，由的嚴格凸性，有 （2.13）把式（2.12）代入式（2.13）中，經(jīng)整理得根據(jù)本定理（1）部分結(jié)論得知，此式與是凸函數(shù)相矛盾．定理2.22

設(shè)是二次可微函數(shù)，C為非空開凸集，則f為c上凸函數(shù)的充要條件是，Hesse矩陣在C上到處半正定．證明略．第54頁,共67頁，2024年2月25日，星期天定理2.23

設(shè)是二次可微函數(shù)，C為非空凸集．若Hesse矩陣在C上到處正定，則f在C上為嚴格凸函數(shù)．證明略，需要注意，該定理的逆命題不真．例如為嚴格凸函數(shù)，但是它的Hesse矩陣在點x=0處是半正定的．二、凸規(guī)劃定義2.26

設(shè)，其中C是非空凸集，f是凸函數(shù)，則形式為的問題稱為凸規(guī)劃問題．第55頁,共67頁，2024年2月25日，星期天更進一步，設(shè)若都是上的凸函數(shù)，都是上的線性函數(shù)，則容易驗證C是凸集．事實上，因為都是凸函數(shù)，根據(jù)定理2.20集合也都是凸集．此外，超平面，也都是凸集．顯然，C是的交集，根據(jù)定理2.6，C是凸集．于是，在這種情況下凸規(guī)劃問題又可表示成如下形式：第56頁,共67頁，2024年2月25日，星期天定理2.24設(shè)是凸規(guī)劃問題的局部極小點，（1）若f是凸函數(shù)，則是凸規(guī)劃問題全局極小點；（2）若f是嚴格凸函數(shù)，則是凸規(guī)劃問題的唯一全局極小點．證（1）使用反證法．假設(shè)不是全局極小點，則必存在使得．對于Z與的任意凸組合，其中且，根據(jù)的凸性，有由此看到，當充分小時，充分接近,注意到此時也有,而這與是局部極小點相矛盾．因此必是全局極小點．第57頁,共67頁，2024年2月25日，星期天（2）假設(shè)不是唯一全局極小點．必存在但使得考慮中點．由f的嚴格凸性，有．此式與為全局極小點相矛盾．這就證明了唯一性．定義2.27形式為（2.14）的函數(shù)稱為n元二次函數(shù)，其中第58頁,共67頁，2024年2月25日，星期天這里的Q是對稱矩陣，即．若Q為正定，則稱（2.14）為正定二次函數(shù)．注意到，由定理2.23知，正定二次函數(shù)是嚴格凸函數(shù)，在最優(yōu)化算法構(gòu)造中它起著特殊的作用．定義2.28形式為 （2.15）的問題稱