<acronym id="yw0ww"><small id="yw0ww"></small></acronym>
<acronym id="yw0ww"></acronym>
<acronym id="yw0ww"><center id="yw0ww"></center></acronym>

最優化理論與算法(第四章的).docx 13頁

  • 1
  • 0
  • 0
  • 約1.04萬字
  • 2020-12-12 發布
文檔工具:
    1. 1、本文檔共13頁,可閱讀全部內容。
    2. 2、本文檔內容版權歸屬內容提供方,所產生的收益全部歸內容提供方所有。如果您對本文有版權爭議,可選擇認領,認領后既往收益都歸您。
    3. 3、本文檔由用戶上傳,本站不保證質量和數量令人滿意,可能有諸多瑕疵,付費之前,請仔細先通過免費閱讀內容等途徑辨別內容交易風險。如存在嚴重掛羊頭賣狗肉之情形,可聯系本站下載客服投訴處理。
    4. 文檔侵權舉報電話:19940600175。
    實用標準文檔 第四章 共軛梯度法 4.1 共軛方向法 共軛方向法是無約束最優化問題的一類重要算法。它一方面克服了最速下降法中,迭代點列呈 鋸齒形前進,收斂慢的缺點,同時又不像牛頓法中計算牛頓方向耗費大量的工作量,尤其是共軛方向法具有所謂二次收斂性質,即當將其用于二次函數時,具有有限終止性質。 一、共軛方向 定義 4.1 設 G 是 n n 對稱正定矩陣, d1 , d2 是 n 維非零向量,若 d1T Gd2 0 (4.1 ) 則稱 d1 , d2 是 G -共軛的。類似地,設 d1 , , dm 是 Rn 中一組非零向量。若 diT Gd j 0 (i j ) ( 4.2 ) 則稱向量組 d , , d m 是 G -共軛的。 1 注: (1) 當 G I 時,共軛性就變為正交性,故共軛是正交概念的推廣。 (2) 若 d1 , , dm G -共軛,則它們必線性無關。 二、共軛方向法 共軛方向法就是按照一組彼此共軛方向依次搜索。 模式算法: 1)給出初始點 x0 ,計算 g0 g( x0 ) ,計算 d0 ,使 d0T g0 0 , k : 0 (初始共軛方向) ; 2)計算 k 和 xk 1,使得 f (xk k dk ) min f ( xk dk ) ,令 xk 1 xkkdk ; 0 3)計算 dk 1 ,使 d T Gd j 0 , j 0,1, , k ,令 k : k 1,轉 2)。 k 1 三、共軛方向法的基本定理 共軛方向法最重要的性質就是:當算法用于正定二次函數時,可以在有限多次迭代后終止,得 到最優解(當然要執行精確一維搜索) 。 精彩文案 實用標準文檔 定理 4.2 對于正定二次函數, 共軛方向法至多經過 n 步精確搜索終止; 且對每個 xi 1 ,都是 f (x) 在 x x x0 i j d j , 線性流形 j 中的極小點。 j 0 證明: 首先證明對所有的 i n 1,都有 gT d j 0 , j 0,1, , i (即每個迭代點處的梯度與以前的搜索方向均正交) i 1 事實上,由于目標函數是二次函數,因而有 gk 1 gk G xk 1 xk kGdk 1)當 j i 時, giT 1d j g Tj 1 d j i gk 1 T gk dj k j 1 gTj 1d j i k dkT Gdj 0 k j 1 2)當 j i 時,由精確搜索性質知: gT d 0 i 1 j 綜上所述,有 giT 1d j 0 ( j 0,1, , i ) 。 再證算法的有限終止結論。若有某個 gi 1 0 ( i n 1),則結論已知。若不然,那么由上面 已證則必有: gnT d j 0 ( j 0, , n 1) 。 而由于 d0 , , dn 1 是 Rn 的一組基,由此可得 gn 0 。故至多經過 n 次精確一維搜索即可獲得最優解。 下面證明定理的后半部分。由于 f (x) 1 xT Gx bT x c 2 是正定二次函數,那么可以證明 (t0 , ,ti ) f ( x0 i t j d j ) j 0 是線性流形上的凸函數。事實上, i (t0 , , ti ) f (x0 t j d j ) j 0 1 ( x i )T G( x i ) bT (x i t d j t d j 0 t j d j ) c 2 0 j 0 j j 0 j 0 j 0 精彩文案 實用標準文檔 1 i 2 T i T T 1 T T 2 j 0 t j ( d j Gd j ) j 0 [ x0 Gd j b d j ]t j ( 2 x0 Gx0 b x0 c) 由 d jTGd j 0 ( j 0, , i ) 知 (t0 , , ti ) 為 t0 , , ti 的凸函數。因而 min i 1 (t0 , , ti ) 0 ( j 0, , i) (t0 , ,ti ) R t j i f ( x0 t j d j )T d j 0 ( j 0, ,i) j 0 注意到:當 t j j , ( j 0, , i ) 時, i i x0 t j dj x0 j d j xi 1 。 j 0 j 0 而由定理前部分證明,在 xi 1 處有 f ( x i 1 )T d j gT d j 0 ( j 0, ,i) , i 1 故在 (t0 , ,ti ) ( 0 , , i ) 處, (t0 , ,ti ) 取得極小,即 i xi 1 x0 i d j j 0 是 f ( x) 在線性流形上的極小點。 4.2 共軛梯度法 上節一般地討論了共軛方向法,在那里n 個共軛方向是預先給定的,而如何

    文檔評論(0)

    • 內容提供方:153****3726
    • 審核時間:2020-12-12
    • 審核編號:6131050154003033

    相關文檔

    5分彩官网