機械優(yōu)化設計第二章(哈工大-孫靖民)

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

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

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

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

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

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

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

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

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

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

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

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

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

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