《優(yōu)化方法數(shù)學基礎》PPT課件.pptVIP

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