1、,1,第二章 優(yōu)化設(shè)計(jì)的數(shù)學(xué)基礎(chǔ),2-1 多元函數(shù)的方向?qū)?shù)和梯度 2-2多元函數(shù)的泰勒展開 2-3無(wú)約束優(yōu)化問(wèn)題的極值條件 2-4凸集、凸函數(shù)與凸規(guī)劃 2-5等式約束優(yōu)化問(wèn)題的極值條件 2-6不等式約束優(yōu)化問(wèn)題的極值條件,2,1、方向?qū)?shù),二元函數(shù),在,點(diǎn)處的偏導(dǎo)數(shù)的定義是：,二元函數(shù),在,點(diǎn)處沿某一方向,的變化率，其定義為,方向?qū)?shù),2-1多元函數(shù)的方向?qū)?shù)和梯度,3,圖1 二維空間中的方向,偏導(dǎo)數(shù)與方向?qū)?shù)的關(guān)系,4,三元函數(shù) 在 點(diǎn)處沿s方向的方向?qū)?shù),依次類推，即可得到n元函數(shù)在點(diǎn)x0處沿s方向的方向?qū)?shù),5,2、二元函數(shù)的梯度,令,為函數(shù)F(x1，x2)在x0點(diǎn)處的梯度,6,當(dāng)梯度

2、方向和d方向重合時(shí)，方向?qū)?shù)值最大，即梯度方向是函數(shù)值變化最快方向，而梯度的模就是函數(shù)值變化率的最大值。,梯度的模：,7,多元函數(shù)的梯度,8,多元函數(shù)的梯度的模：,函數(shù)的梯度方向與函數(shù)的等值面相垂直，也就是和等值面上過(guò)x0的一切曲線相垂直。 由于梯度的模因點(diǎn)而異，即函數(shù)在不同點(diǎn)處的最大變化率是不同的。因此，梯度是函數(shù)的一種局部性質(zhì)。,9,解：,10,解：,則函數(shù)在 處的最速下降方向?yàn)?11,該方向上的單位向量為,新點(diǎn),該點(diǎn)函數(shù)值,12,常用梯度公式：,注意：梯度為向量,二次型,13,在 點(diǎn)處的泰勒展開為：,其中,1、一元函數(shù),2-2多元函數(shù)的泰勒展開,14,2、二元函數(shù),其中：,二元函數(shù) 在

3、點(diǎn)處的泰勒展開式為：,15,上式寫成矩陣形式：,16,令,上式可寫成,稱為函數(shù) 在 點(diǎn)處的 海賽（Hessian）矩陣,參見教材例題P30,17,海賽矩陣是由函數(shù) 在點(diǎn) 處的二階偏導(dǎo)數(shù)組成的方陣。由于函數(shù)的二次連續(xù)性，有：,所以 矩陣為對(duì)陣方陣。,18,海賽矩陣,3、多元函數(shù),其中：梯度,泰勒展開式,19,若將函數(shù)的泰勒展開式只取到線性項(xiàng)，即取,則 是過(guò)點(diǎn) 和函數(shù) 所代表的超曲面相切的切平面。,若將函數(shù)的泰勒展開式取到二次項(xiàng)時(shí)，則得到二次函數(shù)形式，在線性代數(shù)中將二次齊次函數(shù)稱為二次型。,矩陣形式,-對(duì)稱矩陣,20,當(dāng)對(duì)任何非零向量x使,則二次型函數(shù)正定，G為正定矩陣。,21,海賽矩陣的特征：是

4、實(shí)對(duì)稱矩陣。,4、海賽矩陣與正定,矩陣正定的充要條件：矩陣G的各階順序主子式為正，即,矩陣負(fù)定的充要條件：矩陣G的,奇數(shù)階主子式,主子式,偶數(shù)階主子式,海賽矩陣的正定性：,正定- 為全局極小值點(diǎn)的充分條件,負(fù)定- 為全局極大值點(diǎn)的充分條件,22,例3 判定矩陣 是否正定？,解：該對(duì)稱矩陣的三個(gè)主子式依次為：,故可知矩陣G是正定的。,23,定理：若二次函數(shù) 中Q正定，則它的等值面是同心橢球面族，且中心為,證明：作變換 ，代入二次函數(shù)式中：,結(jié)論：Q為正定矩陣的二次型 的等值面是以 的同心橢球面族。原二次函數(shù)就是以 為中心的同心橢球面族，橢圓中心為極小值點(diǎn)。,24,例4 把二次函數(shù) 化為矩陣向量形

5、式并檢驗(yàn)Q是否正定，如正定，試用公式 求這個(gè)函數(shù)的極小點(diǎn)。,解：,與題中函數(shù)比較各系數(shù)得：,由計(jì)算知Q正定，極小點(diǎn),25,的梯度和Hesse矩陣。,解：因?yàn)?則,又因?yàn)椋?故Hesse陣為：,例5：求目標(biāo)函數(shù),26,1、一元函數(shù),對(duì)于可微的一元函數(shù) 判斷在 處是否取得極值的過(guò)程：,則 為極小點(diǎn)。,逐次檢驗(yàn)其更高階導(dǎo)數(shù)的符號(hào)，開始不為零的導(dǎo)數(shù)階數(shù)若為偶次，則為極值點(diǎn)，若為奇次，則為拐點(diǎn)。,則 為極大點(diǎn)。,2-3無(wú)約束優(yōu)化問(wèn)題的極值條件,27,2、二元函數(shù),定理1：若二元可微函數(shù) 在 處取得極值的必要條件是：,即,凡滿足上式的點(diǎn)稱為函數(shù)的駐點(diǎn),（零向量）,28,如下圖所示的二元函數(shù)，在M0點(diǎn)雖有

6、和 是個(gè)駐點(diǎn)，但它不是極值點(diǎn)。,29,定理2：若二元可微函數(shù) 在 的某個(gè)鄰域取得極小值的充分條件是要求在該點(diǎn)附近的一切點(diǎn)均滿足：,若函數(shù)存在連續(xù)的一階及二階偏導(dǎo)數(shù)，當(dāng)滿足,則泰勒展開式的函數(shù)增量近似式（略三階以上高階微量）為：,30,令,則,可見，函數(shù)增量的性態(tài)與A,B,C的值有關(guān)?？梢宰C明，當(dāng)滿足以下條件時(shí)， 為極小值（證明略）。,此條件反映了函數(shù)在該點(diǎn)的海賽矩陣的各階主子式均大于零（即正定）。,31,結(jié)論：,二元函數(shù)在某點(diǎn)取得極小值的充分條件是要求該點(diǎn)處的海賽矩陣為正定。,且,對(duì)于二元函數(shù) 在 處取得極值的充分必要條件是：,參見教材例題P32,32,3、多元函數(shù),對(duì)于多元函數(shù) 若在 處取得

7、極值，則,必要條件：,充分條件：,正定 或負(fù)定,33,當(dāng)極值點(diǎn)x*能使f(x*)在整個(gè)可行域中為最小值時(shí)，即在整個(gè)可行域中對(duì)任一x都有f(x)=f(x*),則x*為全域最優(yōu)點(diǎn)（全域極小點(diǎn)）。若f(x*)為局部可行域中的極小值而非整個(gè)可行域的最小值時(shí)，則稱x*為局部最優(yōu)點(diǎn)或相對(duì)最優(yōu)點(diǎn)。優(yōu)化的目標(biāo)是全域最優(yōu)點(diǎn)。為了判斷某個(gè)極值點(diǎn)是否為全域最優(yōu)點(diǎn)，研究函數(shù)的凸性是必要的。,2-4凸集、凸函數(shù)與凸規(guī)劃,34,函數(shù)的凸性表現(xiàn)為單峰性。對(duì)于具有凸性特點(diǎn)的函數(shù)來(lái)說(shuō)，其極值點(diǎn)只有一個(gè)，因而該點(diǎn)既是局部最優(yōu)亦是全域最優(yōu)點(diǎn)。,為了研究函數(shù)的凸性，下面引入凸集的概念：,35,1、凸集,如果對(duì)一切 及一切滿足,的實(shí)數(shù)

8、 ，點(diǎn) 則稱集合,為凸集，否則稱為非凸集。,若y是x1和x2連線上的點(diǎn)，則有,整理后即得,圖2-8 二維空間的凸集與非凸集,36,圖2-9凸集的性質(zhì),37,2、凸函數(shù),具有凸性（表現(xiàn)為單峰性）或只有唯一的局部最優(yōu)值亦即全域最優(yōu)值的函數(shù)，稱為凸函數(shù)或單峰函數(shù)。其數(shù)學(xué)定義是：,設(shè)f(x)為定義在n維歐式空間中的一個(gè)凸集D上的函數(shù)，如果對(duì)于任何實(shí)數(shù) 以及對(duì)D中任意兩點(diǎn)x1，x2恒有：,則 為D上的凸函數(shù)，若不滿足上式，則為凹函數(shù)。如式中的等號(hào)去掉，則稱其為嚴(yán)格凸函數(shù)。,38,凸函數(shù)的幾何意義：在函數(shù)曲線上取任意兩點(diǎn)連成一直線段，則該線段上任一點(diǎn)的縱坐標(biāo)值必大于或等于該點(diǎn)處的原函數(shù)值。,39,凸函數(shù)的

9、性質(zhì),1）若f(x)為定義在凸集D上的一個(gè)凸函數(shù)，對(duì)于任意實(shí)數(shù)a0，則af(x)也是凸集D上的凸函數(shù)； 2）定義在凸集D上的兩個(gè)凸函數(shù)f1(x),f2(x)，其和f1(x)+f2(x)亦為該凸集上的一個(gè)凸函數(shù)； 3）若f1(x),f2(x)為定義在凸集D上的兩個(gè)凸函數(shù)， 為兩個(gè)任意正數(shù)，則 仍為D上的凸函數(shù)。,40,3、凸性條件,（1）根據(jù)一階導(dǎo)數(shù)（函數(shù)的梯度）來(lái)判斷函數(shù)的凸性,設(shè)f(x)為定義在凸集R上，且具有連續(xù)的一階導(dǎo)數(shù) 的函數(shù)，則f(x)在R上為凸函數(shù)的充要條件是對(duì)凸 集R內(nèi)任意不同兩點(diǎn) 、 ，下面不等式恒成立。,41,（2）根據(jù)二階導(dǎo)數(shù)（海賽矩陣)來(lái)判斷函數(shù)的凸性,設(shè)f(x)為定義在

10、凸集R上且具有連續(xù)二階導(dǎo)數(shù)的函數(shù)，則f(x)在R上為凸函數(shù)的充要條件為：,海賽矩陣在R上處處半正定。對(duì)于嚴(yán)格的凸函數(shù)，其充要條件為海賽矩陣為正定。,當(dāng)海賽矩陣G的主子式: det(G)0時(shí)，矩陣正定 det(G)0 時(shí)，矩陣半正定 det(G)0時(shí)，矩陣負(fù)定 det(G)0時(shí)，矩陣半負(fù)定,G(x*)正定， 是 x* 為全局極小值點(diǎn)的充分條件； G(x*)半正定, 是 x* 為局部極小值點(diǎn)的充分條件； G(x*)負(fù)定， 是 x* 為全局極大值點(diǎn)的充分條件； G(x*)半負(fù)定, 是 x* 為局部極大值點(diǎn)的充分條件。,說(shuō)明：,42,4、凸規(guī)劃,對(duì)于約束優(yōu)化問(wèn)題,若,、,都為凸函數(shù)，則稱此問(wèn)題為凸規(guī)劃

11、。,43,凸規(guī)劃的性質(zhì)：,2）可行域 為凸集。,3）凸規(guī)劃的任何局部最優(yōu)解就是全局最優(yōu)解。,1）若給定一點(diǎn) ，則集合 為凸集。,44,不論是無(wú)約束或有約束的優(yōu)化問(wèn)題，在實(shí)際應(yīng)用中，要證明一個(gè)優(yōu)化問(wèn)題是否為凸規(guī)劃，一般比較困難，有時(shí)甚至比求解優(yōu)化問(wèn)題本身還要麻煩。尤其對(duì)一些工程問(wèn)題，由于其數(shù)學(xué)模型的性態(tài)都比較復(fù)雜，更難實(shí)現(xiàn)。因此，在優(yōu)化設(shè)計(jì)的求解中，就不必花精力進(jìn)行求證，而通常是從幾個(gè)初始點(diǎn)出發(fā)，找出幾個(gè)局部最優(yōu)解，從中選擇目標(biāo)函數(shù)值最好的解。,注意：,45,等式約束優(yōu)化問(wèn)題：,求解等式約束化問(wèn)題的理論基礎(chǔ)是導(dǎo)出極值存在的條件。,2-5等式約束優(yōu)化問(wèn)題的極值條件,46,1、消元法（降維法）,47

12、,48,2、拉格朗日乘子法（升維法）,思想: 通過(guò)增加變量將等式約束化問(wèn)題變成無(wú)約束化問(wèn)題。所以又稱作升維法。,引入拉格朗日乘子,，并構(gòu)成一個(gè),新的目標(biāo)函數(shù),拉格朗日函數(shù),拉格朗日乘子,新目標(biāo)函數(shù)的極值的必要條件：,49,50,庫(kù)恩塔克條件（K-T條件）,不等式約束的多元函數(shù)極值的必要條件是著名的庫(kù)恩塔克（Kuhn-Tucker）條件,它是非線性優(yōu)化問(wèn)題的重要理論。,為了便于理解庫(kù)恩塔克條件，首先分析一元函數(shù)在給定區(qū)間的極值條件。,2-6不等式約束優(yōu)化問(wèn)題的極值條件,51,1、一元函數(shù)在給定區(qū)間上的極值條件,一元函數(shù)f(x)在區(qū)間a,b的極值問(wèn)題，可表示為：,求解思想:引入松弛變量使不等式約束

13、變成等式約束，再利用拉格朗日乘子法求解等式約束的極值問(wèn)題。,52,這樣可以轉(zhuǎn)化為拉格朗日函數(shù)：,是對(duì)應(yīng)于不等式約束的拉格朗日乘子，,其值均為非負(fù)的。,設(shè) 為松弛變量，則上兩個(gè)不等式可寫為如下兩個(gè)等式：,53,結(jié)論：,54,從以上分析可以看出，對(duì)應(yīng)于不起作用的約束的拉格朗日乘子取零值，因此可以引入起作用約束的下標(biāo)集合。,一元函數(shù)在給定區(qū)間的極值條件，可以改寫為：,極值條件中只考慮起作用的約束和相應(yīng)的乘子。,55,2、庫(kù)恩塔克條件,庫(kù)恩塔克條件（K-T條件）可表述為：,對(duì)于多元函數(shù)不等式的約束優(yōu)化問(wèn)題：,56,庫(kù)恩塔克條件表明：,如點(diǎn) 是函數(shù) 的極值點(diǎn)，要么 （此時(shí) ）或者目標(biāo)函數(shù)的負(fù)梯度等于起作

14、用約束梯度的非負(fù)線性組合 （此時(shí) ）。,57,庫(kù)恩塔克條件的幾何意義：在約束極小值點(diǎn) 處，函數(shù) 的負(fù)梯度一定能表示成起作用約束在該點(diǎn)梯度（法向量）的非負(fù)線性組合。,58,59,起作用約束：,60,從圖中可以看出，,處在,和,即線性組合的系數(shù)為正，是在,取得極值的必要條件。,角錐之內(nèi)，,61,同時(shí)具有等式和不等式約束的優(yōu)化問(wèn)題：,庫(kù)恩塔克條件（K-T條件）：,62,庫(kù)恩塔克條件是多元函數(shù)取得約束極值的必要條件，可用來(lái)作為約束極值的判斷條件，又可以來(lái)直接求解較簡(jiǎn)單的約束優(yōu)化問(wèn)題。,對(duì)于目標(biāo)函數(shù)和約束函數(shù)都是凸函數(shù)的情況，符合K-T條件的點(diǎn)一定是全局最優(yōu)點(diǎn)。 這種情況K-T條件即為多元函數(shù)取得約束極值的充分必要條件。,63,例