【文章內容簡介】 21coscos??? 函數(shù)的梯度 ????????? x XFx XFS XF 2211c os)(c os)()( ?? 函數(shù) F(X)在某點 X 方向導數(shù)表明函數(shù)沿某一方向S的變化率。一般說來，函數(shù)在某一確定點沿不同方向的變化率是不同的。 為求得函數(shù)在某點 X 方向導數(shù)為最大的方向，引入 梯度 的概念。 以二元函數(shù)為例 ?????? ??????21)()()(xXFxXFXF函數(shù) F(X)在點 X處的梯度 ▽ F(X), 可記作 grad F(X) 方向 S的單位向量 ? ?T21 c o sc o s ???S 1?S )(,)(,)()(21??????????????nxXFxXFxXFXF ?n元函數(shù) ),(21 nxxxF ?的梯度 : 說明： 梯度▽ F(X) 是一個向量，梯度方向是函數(shù)具有最大變化率的方向（方向導數(shù)最大的方向），即： ?梯度▽ F(X)方向是函數(shù) F(X) 的最速上升方向； ?負梯度 ▽ F(X)方向是函數(shù) F(X) 的最速下降方向。 ? ? )),(c os ()()( )( T SXFSXFSXFS XF ??????????)( XF?分析 : 函數(shù) F(X)沿 S方向的方向導數(shù)等于向量▽ F(X)在 S方向上的投影。 當 cos（ ▽ F(X) ， S ）＝ 1時，即 S 與 ▽ F(X)方向相同時，向量▽ F(X) 在 S 方向上的投影最大，其值為 ? 凸集 ? 凸函數(shù) 為凹函數(shù)。若式中不等號反向，則上的凸函數(shù)；為則恒有和內任意兩點和實數(shù)一個函數(shù)，若對于任何上的為定義在中一凸集，為　設)()()()1()())1((,)10()(212121XFDXFXFXFXXFXXDDXFEDn?????????????1X 2X*Xa b X)(XFABK39。K凸函數(shù)的幾何意義? 凸規(guī)劃 則稱此問題為凸規(guī)劃。均為凸函數(shù)，、式中，若　　　　　　　對于約束優(yōu)化問題muXgXFmuXgtsRXXFuun,2,1)()(,2,1,0)(..),(m i n??????? ?? ? 0)()(,)()3)2,2,1,0)()1***???????XXXFDXXXFmuXgXDuＴ　　　都滿足于　充分必要條件是：對優(yōu)解的為上述凸規(guī)劃問題的最可微，則若優(yōu)解。局部最優(yōu)解都是全局最上述凸規(guī)劃問題的任何為凸集?？尚杏蛲挂?guī)劃的性質：? 最優(yōu)點性質 ? 局部及全局最優(yōu)點概念 最優(yōu)設計點可分為：局部最優(yōu)點、全局最優(yōu)點。 ? 目標函數(shù) Y=G(X)， ? 設計變量 X, ? 取值區(qū)間 [a， b]即 優(yōu)化問題的 可行區(qū)域D={X∣ a≤X≤b} 。 ★ 1 ● 2 ★ 3 ● 1 ● 3 ★ 2 Y=G(X) a b X ★ 3和● 3分別為閉區(qū)間上設計端點； ★ 2為開區(qū)間內極大點（或稱 局部極值點或局部最優(yōu)點 ） 。 ★ 1為可行區(qū)域 D內 全局最大點（全局最優(yōu)點） 。 ● 1為開區(qū)間內 極小點 。 ● 2為可行區(qū)域 D內 全局最小點 。 ? 局部及全局最優(yōu)點性質討論 ?全局最優(yōu)點一定也是局部最優(yōu)點，而局部最優(yōu)點不一定是全局最優(yōu)點。 判斷是否全局、局部最優(yōu)點的依據和最實用方法是高等數(shù)學中的極值原理（開區(qū)間上講極值，閉區(qū)間上講最值）。 ?全局最優(yōu)求解方法 最優(yōu)化問題常要求求解全局最優(yōu)點，然而由于優(yōu)化算法本身結構、優(yōu)化問題本身的復雜性等原因，傳統(tǒng)優(yōu)化算法（如黃金分割法或 ，單純形法、復合形法、最小二乘法等）以及新發(fā)展的模糊優(yōu)化法、神經網絡優(yōu)化法都很難直接求出全局最優(yōu)點。 目前，求解全局最優(yōu)點的有效方法主要有： 遺傳優(yōu)化法、多個局部最優(yōu)點比較綜合法 。 ?遺傳優(yōu)化法 GA （ geic algorithm) GA總能解決傳統(tǒng)優(yōu)化法難以解決的問題。 ?當優(yōu)化問題存在若干個 “ 山峰或極值點 ” （即 多極值問題 ）時，傳統(tǒng)優(yōu)化法很容易陷入或收斂于局部最優(yōu)點，而 GA則不然。 ?GA最擅長于求解 大型且復雜 的優(yōu)化問題，求解簡單優(yōu)化問題反而效率不高（此時還不如選用傳統(tǒng)優(yōu)化法）。 ?GA法不存在如何選擇搜索 初始點問題 ，總能搜索到全局最優(yōu)點附近。 ? 多個局部最優(yōu)點比較綜合法 先 取若干個相距較遠的初始點 ，再從各個初始點出發(fā)用選擇的優(yōu)化算法來求出最優(yōu)點。 全局最優(yōu)點的判斷： 在上述基礎上，觀察求解結果是否趨向同一點？ ? 若從不同初始點出發(fā)搜索的結果是 同一個最優(yōu)點 ，則認為所得點是 全局最優(yōu)點 ； ? 若從不同初始點出發(fā)搜索的結果 不是同一個點 ，則需要進一步比較這些結果值，從中找出 目標函數(shù)值最小或最大的 那個作為 全局最優(yōu)點 。 最優(yōu)化算法的類型 * 優(yōu)化算 法名稱 優(yōu)化算法細分類 說 明 解析法 無約束時 僅用于目標、約束函數(shù)均是設計變量的顯函數(shù)情況。采用求導數(shù)法或變分法求出泛函或目標最優(yōu)的必要條件得到一組方程或不等式組，再求解方程組或不等式組，得到最優(yōu)解。 古典微分法 古典變分法 有約束時 極大值原理 庫恩 圖克定理 數(shù)值計算 迭代法 一維搜索問題 廣泛用于目標或泛函復雜或無法改寫成設計變量的顯函數(shù)形式情況。選用直接搜索法經過若干次迭代計算而得到最優(yōu)點。一般，一維搜索問題（即單個設計變量的極值問題）可用區(qū)間消元法、多項式插值法；多維搜索問題（即多個設計變量的極值問題）可用爬山法。 區(qū)間消元法（如 法）；多項式插值法 多維搜索問題 爬山法 ：坐標輪換法、步長加速法、方向加速法、單純形法、隨機搜索法 優(yōu)化算 法名稱 優(yōu)化算法細分類 說 明 網絡優(yōu)化法 數(shù)學模型為網絡圖形，采用圖論法求解。 基于梯度的數(shù)值計算法 無約束梯度法 包括：最速下降法、擬牛頓法、共軛梯度法、變尺度法等 有約束梯度法 可行方向法、梯度投影法 有約束變成無約束問題法 SUMT法、 SWIFT法、復合形法 模糊優(yōu)化法 如基于最小二乘原理的模糊（ fuzzy）線性回歸等 神經網絡優(yōu)化 如 BP神經網絡優(yōu)化法、徑向基網絡優(yōu)化法等。 遺傳優(yōu)化法 GA法總能解決普通優(yōu)化法難以解決的問題。當優(yōu)化問題存在若干個“ 山峰或極值點 ” 時，普通優(yōu)化法很容易陷入或收斂于局部最優(yōu)點，而 GA則不然。 GA最擅長于求解大型且復雜的優(yōu)化問題，求解簡單優(yōu)化問題反而效率不高（此時還不如選用普通優(yōu)化法）。 GA法不存在如何選擇搜索初始點問題，總能搜索到全局最優(yōu)點附近。 167。 最速下降法 (梯度法） 第三節(jié) 基于導數(shù)的最優(yōu)化方法 問題提出 問題： 在點 kx處， 沿什么方向 ,kd ? ?xf下降最快 ? 分析 ： ? ? ? ? ? ? ? ?0????? ???? kkTkkkk dodgxfdxf考查 ： ?c o skkkTk dgdg ?顯然當 1c o s ??? 時， kTk dg取極小值． 因此： kk gd ??結論： 負梯度方向使 ? ?xf下降最快， 亦即最速 下降方向． 教： 最速下降法算法 Step1: 給出 0:,10,0 ????? kRx n ?Step2: 計算 ? ?,kxf?如果 ? ? ,???kxf停． Step3: 計算下降方向 .kk gd ??Step4: 計算步長因子 .k?Step5: 令 ,1 kkkk dxx ???? 轉步２ . ? function [x,minf] = minFD(f,x0,var,eps) ? format long。 ? if nargin == 3 ? eps = 。 ? end ? syms l。 ? tol = 1。 ? gradf = jacobian(f,var)。 ? ? while toleps ? v = Funval(gradf,var,x0)。 ? tol = norm(v)。 ? y = x0 + l*v。 ? yf = Funval(f,var,y)。 ? [a,b] = minJT(yf,0,)。 ? xm = minHJ(yf,a,b)。 ? x1 = x0 + xm*v。 ? x0 = x1。 ? end ? ? x = x1。 ? minf = Funval(f,var,x)。 ? format short。 學： 算法的 MATLAB實現(xiàn) 做： 算法舉例 ? 最速下降法求解無約束多維極值問題實例。用最速下降法求函數(shù) ? 解：在 MATLAB命令窗口中輸入： ? syms t s。 ? f=(t4)^2+(s+2)^2+1 ? [x,mf]=minFD(f,[1 3],[t s]) ? 所得結果為： ? X= ? Mf=1 ).3,1(1)2()4(),( 022 ??????? xststf 的極小值，初始點取最速下降法優(yōu)點 (1) 程序設計簡單，計算量小，存儲量小， 對初始點沒有特別要求． (2) 有著很好的整體收斂性，即使對一般的 目標函數(shù)，它也整體收斂． 最速下降法缺點 (1) 最速下降法是線性收斂的，并且有時是 很慢的線性收斂． 原因： ① kk gd ??僅反映 ? ?xf 在 kx處 的局部性質． ② ,01 ?? kTk dg相繼兩次迭代中搜索 方向是正交的． 小結 (1) 最速下降法是基本算法之一，而非有效 的實用算法． 最速下降法的本質是用線性函數(shù)來近似 目標函數(shù)， 要想得到快速算法，需要考 慮對目標函數(shù)的高階逼近． 167。 牛頓法 牛頓迭代法也稱為牛頓 拉夫森 (NewtonRaphson)迭代法，它是數(shù)值分析中最重要的方法之一，它不僅適用于方程或方程組的求解，還常用于微分方程和積分方程求解。 基本思想 利用目標函數(shù) ? ?xf在點 kx處的二階 Taylor 展開式去近似目標函數(shù)， 用二次函數(shù)的極小點 去逼近目標函數(shù)的極小點． 教： Newton迭代法的基本思想 ? 設 是 f(x)=0的一個近似根，把 f(x)在 處作泰勒展開 ? 若取前兩項來近似代替 f(x)(稱為 f(x)的線性化 )，則得近似的線性方程 ? 設 ,令其解為 ,得 ? (1) ? 這稱為 f(x)=0的牛頓迭代格式。 KXKX?????????? 2)(!2 )())(()()( kkkkk xxxfxxxfxfxf0))(()()( ????? kkk xxxfxfxf0)( ?? kxf 1?kx)()(1kkkk xfxfxx????它對應的迭代方程為 顯然是 f(x)=0的同解方程， 故其迭代函數(shù)為 在 f(x)=0的根 的某個鄰域 內 , 在 的鄰域 R 內，對任意初值 ， 應用 由公式（ 1） 來解方程的方法就稱為 牛頓迭代法 。它是解代數(shù)方程和超越方程的有效方法之一 . )( ????xR 0)( ?xf?0x)()()(xfxfxx?????? ? 1)()()()(2 ???????? ? Lxfxfxfx)()(xfxfxx???)0)(( ?? xf牛頓法的幾何意義 ? 由（ 1）式知 是點 處 的切線 與 X軸的交點的橫坐標（如圖）。也就是說，新的近似值 是用代替曲線 y=f(x)的切線與 x 軸相交得到的。繼續(xù)取點 ,再做切線與 x軸相交，又可得 。由圖可見，只要初值取的充分