《優(yōu)化方法數(shù)學(xué)基礎(chǔ)》PPT課件.ppt

2 優(yōu)化方法數(shù)學(xué)基礎(chǔ),優(yōu)化設(shè)計(jì)極值 多變量、多約束非線性優(yōu)化,高等數(shù)學(xué)極值理論是求解基礎(chǔ)，但是不能直接求出最優(yōu)解。 對(duì)多變量約束優(yōu)化問題的求解方法所涉及的數(shù)學(xué)概念及有關(guān)理論進(jìn)行補(bǔ)充和擴(kuò)展。 介紹二次函數(shù)、多元函數(shù)的梯度、函數(shù)的近似表示以及極值條件和數(shù)值迭代解法等基本概念。,一、正定二次型,二次函數(shù),XTHX二次型，H二次型矩陣 正定和負(fù)定矩陣。對(duì)于所有非零向量 XTHX 0，矩陣正定 XTHX =0，矩陣半正定 XTHX 0，矩陣負(fù)定 XTHX =0，矩陣半負(fù)定 XTHX =0，矩陣不定,寫成向量形式,一、正定二次型,線性代數(shù)可知，矩陣H的正定性除用定義判斷外，還可以用矩陣的各階主子式進(jìn)行判別 主子式包含第一個(gè)元素在內(nèi)的左上角各階子矩陣所對(duì)應(yīng)的行列式。,一、正定二次型,二次型矩陣H正定正定二次函數(shù)。 正定二次函數(shù)性質(zhì)： 正定二次函數(shù)的等值線或等值面是一族同心橢圓(或同心橢球)。橢圓族或橢球族的中心是極小點(diǎn)。 函數(shù)橢圓族等值線與一組平行線切點(diǎn)的連線通過橢圓中心；反之，過橢圓中心的直線與各橢圓的交點(diǎn)所作橢圓的切線是一組平行線。,非正定二次函數(shù)在極小點(diǎn)附近的等值線或等值面近似于橢圓或橢球。 求極值時(shí)，近似按二次函數(shù)處理，即用二次函數(shù)的極小點(diǎn)近似函數(shù)的極小點(diǎn)，反復(fù)進(jìn)行，逐漸逼近函數(shù)的極小點(diǎn)。,一、正定二次型,二、方向?qū)?shù)和梯度,1方向?qū)?shù) 導(dǎo)數(shù)是描述函數(shù)變化率的數(shù)學(xué)量。 微分理論知，一元函數(shù)在點(diǎn)xk的一階導(dǎo)數(shù)表示函數(shù)在該點(diǎn)的變化率。,二元函數(shù)在某點(diǎn)沿坐標(biāo)方向xi的變化率用函數(shù)對(duì)該坐標(biāo)變量的一階偏導(dǎo)數(shù)表示。,二、方向?qū)?shù)和梯度,函數(shù)沿任一方向的變化率，用方向?qū)?shù)描述。 二元函數(shù)在X（k）處沿與坐標(biāo)軸夾角為i的 S方向的變化率，即方向?qū)?shù),二、方向?qū)?shù)和梯度,二、方向?qū)?shù)和梯度,多元函數(shù)在X（k）處方向?qū)?shù),梯度 ；方向S上的單位向量； S的方向角； S的方向余弦,2梯度,函數(shù)在點(diǎn)X（k）的梯度是由函數(shù)在該點(diǎn)的一階偏導(dǎo)數(shù)組成的向量 。,根據(jù)矢量代數(shù),2梯度,函數(shù)在某點(diǎn)沿方向S的方向?qū)?shù)等于 該點(diǎn)的梯度在方向S上的投影。,函數(shù)梯度性質(zhì),(1) 梯度方向是函數(shù)等值線(或等值面)的法線方向 當(dāng)S方向與該點(diǎn)的梯度相垂直時(shí)，函數(shù)在該點(diǎn)沿S的方向?qū)?shù)等于零。,說明方向位于該點(diǎn)等值線的切線上(或等值面的切平面內(nèi))函數(shù)在該點(diǎn)的梯度方向必定是該點(diǎn)等值線或等值面的法線方向。,函數(shù)梯度性質(zhì),(2) (負(fù))梯度方向是函數(shù)值(下降)增長最快的方向 當(dāng)S方向與梯度夾角為零時(shí)，方向?qū)?shù)達(dá)到最大值,函數(shù)在一點(diǎn)的梯度方向是該點(diǎn)方向?qū)?shù)最大的方向(函數(shù)值增長最快的方向)； 與梯度相反的方向稱為負(fù)梯度方向 。函數(shù)在一點(diǎn)的負(fù)梯度方向是該點(diǎn)函數(shù)值下降最快的方向。 與梯度成銳角的方向是函數(shù)值上升的方向，與梯度成鈍角的方向是函數(shù)值下降的方向。,函數(shù)梯度性質(zhì),(3) 各點(diǎn)函數(shù)梯度不同。 梯度大小就是梯度的模長。 (4) 梯度是函數(shù)在一點(diǎn)鄰域內(nèi)局部性態(tài)的描述。 (5) 極值點(diǎn)處梯度為零 梯度為零不一定是極值點(diǎn)。,函數(shù)梯度,例 求函數(shù)f(X)=(x1-2)2+(x2-1)2在點(diǎn)X(1)=3,2T和X(2)=2,2T處的梯度并作圖表示。,解 梯度,三、多元函數(shù)的近似表示,一元函數(shù)在點(diǎn)xk的鄰域內(nèi)n階可導(dǎo)，可在該點(diǎn)的鄰域內(nèi)泰勒展開,多元函數(shù)若在點(diǎn)X（k）作泰勒展開，展開式一般取三項(xiàng)，形式與一元函數(shù)展開式的前三項(xiàng)相似，即,三、多元函數(shù)的近似表示,二階導(dǎo)數(shù)矩陣海賽(Hessian)矩陣，n階對(duì)稱矩陣,取泰勒展開式的前兩項(xiàng)，得到泰勒線性近似式,例 用泰勒展開函數(shù)f(X)=x13-x23+3x12+3x22-9x1，在點(diǎn)X(1)=1,1T簡化成線性函數(shù)和二次函數(shù)。,三、多元函數(shù)的近似表示,解 函數(shù)在點(diǎn)X(1)的函數(shù)值、梯度和二階導(dǎo)數(shù)矩陣,三、多元函數(shù)的近似表示,簡化線性函數(shù),簡化二次函數(shù),將X(1)代入簡化所得的線性函數(shù)和二次函數(shù)中，其函數(shù)值等于-3，與原函數(shù)在點(diǎn)X(1)的值相等，說明簡化正確。,四、函數(shù)的極值,無約束優(yōu)化問題的極值只取決于目標(biāo)函數(shù)本身性態(tài)，約束優(yōu)化問題的極值不僅與目標(biāo)函數(shù)的性態(tài)有關(guān)，且與約束函數(shù)的構(gòu)成相關(guān)。,(一)無約束問題極值條件 高等數(shù)學(xué)知，一元函數(shù)在點(diǎn)xk 取得極值： 必要條件是函數(shù)在該點(diǎn)的一階導(dǎo)數(shù)等于零，充分條件是二階導(dǎo)數(shù)不等于零。,四、函數(shù)的極值,多元函數(shù)在點(diǎn)X(k)取得極值的必要條件： 函數(shù)在該點(diǎn)的所有方向?qū)?shù)等于零函數(shù)在該點(diǎn)的梯度等于零。,多元函數(shù)在點(diǎn)X(k)取得極小值條件： 函數(shù)在該點(diǎn)的梯度為零，二階導(dǎo)數(shù)矩陣為正定,展開成泰勒二次近似式,四、函數(shù)的極值,例 求函數(shù)f(X)=x12+x1x2+x22-6x1-3x2的極值。 解,(二)約束問題極值條件(后述),五、數(shù)值迭代算法,最優(yōu)化方法基本思想 消去法和爬山法 消去法處理單變量函數(shù)極值問題時(shí)有效 對(duì)于多維函數(shù)，消去的不是線段，而是平面(兩變量函數(shù))、立體(三變量函數(shù))或多維空間的一部分，使求解問題變得復(fù)雜 爬山法上山或下山 極大值上升算法；極小值下將算法 每前進(jìn)一步，函數(shù)值有所改善，同時(shí)為下一步移動(dòng)方向提供有用信息數(shù)值迭代算法基本思想。,五、數(shù)值迭代算法,按照某一迭代格式，從一個(gè)初始點(diǎn)X(0)出發(fā)逐步產(chǎn)生一個(gè)點(diǎn)列 X(0)， X(1)， X(k)， X(k+1)， 點(diǎn)列所對(duì)應(yīng)的目標(biāo)函數(shù)值呈下降趨勢(shì)，構(gòu)成此點(diǎn)列的方法就是下降迭代算法。,點(diǎn)列的極限就是目標(biāo)函數(shù)的極小點(diǎn),1下降迭代算法基本格式,迭代點(diǎn)列遞推方法,為使每一次迭代都能讓目標(biāo)函數(shù)獲得最大的下降量，新的迭代點(diǎn)X(k+1)通常取作方向S(k)上的一維極小點(diǎn)，對(duì)應(yīng)的步長記作k，稱最優(yōu)步長因子。,下降迭代算法基本格式： 給定初始點(diǎn)X(k)和收斂精度； 選取搜索方向S(k) ； 確定步長因子k ，得到迭代點(diǎn)X(k+1) ； 收斂判斷：若滿足收斂精度，以X(k+1)作為最優(yōu)點(diǎn)，終止計(jì)算；否則，以X(k+1)作為新起點(diǎn)，轉(zhuǎn)進(jìn)行下一輪迭代。,1下降迭代算法基本格式,下降迭代算法的構(gòu)成需要解決基本問題： 選擇搜索方向 不同的搜索方向，構(gòu)成不同的下降迭代算法； 確定步長因子 一般通過一維搜索法取得最優(yōu)步長因子； 給定收斂準(zhǔn)則 用以判斷迭代點(diǎn)是否能夠作為近似的最優(yōu)點(diǎn)。,2收斂準(zhǔn)則,判斷迭代點(diǎn)與精確解近似程度的方法收斂準(zhǔn)則。 (1) 點(diǎn)距準(zhǔn)則(坐標(biāo)準(zhǔn)則) 一般來說，迭代點(diǎn)向極小點(diǎn)的逼近速度是逐近變慢的，越接近極小點(diǎn)，相鄰迭代點(diǎn)間的距離越短。當(dāng)相鄰兩迭代點(diǎn)間的距離充分小，即有,(2)函數(shù)值準(zhǔn)則 迭代點(diǎn)接近極小點(diǎn)，迭代點(diǎn)距離接近，函數(shù)值也越接近。將相鄰的函數(shù)值之差作為判斷極小點(diǎn)的準(zhǔn)則函數(shù)值準(zhǔn)則。,2收斂準(zhǔn)則,(2)函數(shù)值準(zhǔn)則,2收斂準(zhǔn)則,(3)梯度準(zhǔn)則 梯度等于零的點(diǎn)是極小點(diǎn)，梯度近似于零的點(diǎn)則必定是近似極小點(diǎn)。當(dāng),準(zhǔn)則選用： 優(yōu)化方法、函數(shù)性態(tài)。,3算法的收斂性,點(diǎn)列向極小點(diǎn)逼近的速度算法的收斂速度 算法的收斂性和收斂速度定義,p點(diǎn)列 的收斂階，正實(shí)數(shù)；q 收斂比 對(duì)于與迭代次數(shù)k無關(guān)的常數(shù) q(0,1) ，如果存在一個(gè)大于零的數(shù)p使公式成立，則 p=1，線性收斂性(線性收斂速度)； p=2，二次收斂性； 1p 2，超