【文章內(nèi)容簡介】 檢查鮑威爾條件 于是可知 鮑威爾條件兩式均不成立。第二環(huán)取基本方向組和起始 點為 沿 e2方向作一維搜索得 以 為起點沿 S1方向一維搜索得 構成新生方向 沿 S2方向一維搜索得 檢查迭代終止條件 需再作第三環(huán)迭代計算。 根據(jù)具體情況來分析， S1， S2實際上為共軛方向，見下圖。 本題又是二次函數(shù)，有共軛方向的二次收斂性，上面結果就 是問題的最優(yōu)解?？梢灶A料，如果做第三環(huán)迭代，則一定各 一維搜索的步長為零，必有 故得最優(yōu)解 梯度法 優(yōu)化設計是追求目標函數(shù)值最小，因此，自然可以設想從某點出發(fā)，其搜索方向取該點的負梯度方向，使函數(shù)值在該點附近下降最快。這種方法也稱為最速下降法。 一、基本原理 梯度法的迭代公式為： x(k+1)=x(k)?(k)g(k) 其中 g(k)是函數(shù) F(x)在迭代點 x(k)處的梯度 ?f(x(k)) ， ?(k)一般采用一維搜索的最優(yōu)步長，即 f(x(k+1))=f(x(k)?(k)g(k))=min f(x(k)?(k)g(k))=min?(?) 據(jù)一元函數(shù)極值條件和多元復合函數(shù)求導公式，得 ?’ (?)= (? f(x(k)?(k)g(k)))T g(k) =0 即 (? f(x(k+1)))T g(k) =0 或 (g(k+1))Tg(k)=0 此式表明，相鄰的兩個迭代點的梯度是彼此正交的。也即在梯度的迭代過程中，相鄰的搜索方向相互垂直。梯度法向極小點的逼近路徑是鋸齒形路線，越接近極小點，鋸齒越細，前進速度越慢。 這是因為 梯度 是函數(shù)的局部性質(zhì)， 從局部上看，在該點 附近函數(shù)的下降最快， 但從總體上看則走了 許多彎路，因此函數(shù) 值的下降并不快。 二、迭代終止條件 采用梯度準則： || g(k) ||? ? 三、迭代步驟 （ 1）任選初始迭代點 x(0)，選收斂精度 ? 。 （ 2）確定 x(k)點的梯度（開始 k=0) （ 3）判斷是否滿足終止條件 || g(k) ||? ?？ 若滿足輸出最優(yōu)解，結束計算。否則轉下步。 （ 4）從 x(k)點出發(fā)，沿 g(k)方向作一維搜索求最優(yōu)步長 ?(k)。得下一迭代點 x(k+1)=x(k)?(k)g(k) ,令 k=k+1 返回步驟 (2)。 四、梯度法流程圖 入口 給定： x(0)， ? k=0 ||g(k)||? ? ？ x*=x(k) f*=f(x(k)) 出口 x(k)= x(0) 計算： g(k) k=k+1 沿 g(k)方向一維搜索， 求最優(yōu)步長 ?(k)。 x(k+1)= x(k) ?(k) g(k)/ ||g(k)|| N Y 例題 的最優(yōu)解。 已知初始點 迭代精度 ε= 解： 函數(shù)的梯度 第一次迭代： 以 為起點沿一 方向作一維搜索 得第一個迭代點 繼續(xù)第二 次迭代 到第五次迭代結束時，有 故迭代可終止，最優(yōu)解為 迭代數(shù)據(jù)表見課本表 共軛梯度法 共軛梯度法是共軛方向法的一種，因為該方法中每一個共軛向量都是依賴于迭代點處的負梯度而構造出來的，所以稱作共軛梯度法。 一、共軛梯度法的搜索方向 共軛梯度法的搜索方向采用梯度法基礎上的共軛方向，如圖所示，目標函數(shù) F(x)在迭代點 xk+1處的負梯度為 ? f(xk+1)，該方向與前 一搜索方向 Sk互為正交，在此 基礎上構造一種具有較高收斂 速度的算法，該算法的搜索方 向要滿足以下兩個條件： （ 1）以 xk+1點出發(fā)的搜索方 向 Sk+1是 ? f(xk+1)與 Sk的線性 組合。即 xk x* xk+1 ? f(xk+1) Sk+1 Sk Sk+1 = ? f(xk+1) + ?kSk （ 2）以與為基底的子空間中，矢量與相共軛，即滿足 [ Sk+1]T G Sk = 0 二、 ?k的確定 確定方法自學，不作要求。記住 三、 共軛梯度法的算法 （ 1）選初始點 x0和收斂精度 ?。 （ 2）令 k=0，計算 S0 = ? f(x0) 。 （ 3）沿 Sk方向進行一維搜索求 ?(k)，得 x(k+1)=x(k)+?(k)S(k) （ 4）計算 ? f(xk+1) ，若 ||? f(xk+1)||? ? ，則終止迭代，取x*=xk+1；否則進行下一步。 （ 5）檢查搜索次數(shù)，若 k=n，則令 x0=xk+1，轉（ 2），否則，進行下一步。 （ 6）構造新的共軛方向 Sk+1 = ? f(xk+1) + ?kSk 令 k=k+1，轉（ 3） 四、共軛梯度法流程圖 入口 k=0， 計算 ： ? f(x0) || ? f(xk+1) ||? ? ？ 出口 求 ?(k) ， x(k+1)= x(k) +?(k)S(k) 計算 ： ? f(xk+1) x*=xk+1 f(x*)=f(xk+1) Y N 給定： x(0)， ? k? n ？ x0=xk+1 N Y Sk+1 = ? f(xk+1) + ?kSk K=K+1 五、共軛梯度法的特點 共軛梯度法屬于解析法，其算法需求一階導數(shù)，所用公式及算法簡單，所需存儲量少。 該方法以正定二次函數(shù)的共軛方向理論為基礎，對二次型函數(shù)可以經(jīng)過有限步達到極小點，所以具有二次收斂性。但是對于非二次型函數(shù)，以及在實際計算中由于計算機舍入誤差的影響，雖然經(jīng)過 n次迭代，仍不能達到極小點，則通常以重置負梯度方向開始，搜索直至達到預定精度，其收斂速度也是較快的。 六、例題 牛頓法 牛頓法是求無約束最優(yōu)解的一種古典解析算法 。 牛頓法可以分為 原始牛頓法 和 阻尼牛頓法 兩種。