本文目錄一覽：
無約束最優化(二) 共軛方向法與共軛梯度法
之前文章 最速下降法、Newton法、修正Newton法 介紹的最速下降法存在鋸齒現象，Newton法需要計算目標函數的二階導數。接下來介紹的 共軛方向法 是介於最速下降法和Newton法之間的一種方法，它克服了最速下降法的鋸齒現象，從而提高了收斂速度；它的迭代公式也比較簡單，不必計算目標函數的二階導數，與Newton法相比，減少了計算量和存儲量。它是比較實用而有效的最優化方法。
我們先將其在正定二次函數 上研究，然後再把算法用到更一般的目標函數上。首先考慮二維的情形。
任選初始點 ，沿它的某個下降方向，例如向量 的方向，作直線搜索，如上圖所示。由下面這個定理：
定理 ：設目標函數 具有一階連續偏導數，若 ,則 。
知 。如果按照最速下降法選擇的就是負梯度方向為搜索方向(也就是 方向)，那麼將要發生鋸齒現象。於是一個設想是，乾脆選擇下一個迭代的搜索方向 就從 直指極小點 ，也就是找到上圖所示的 方向。
因為 從 直指極小點 ,所以 可以表示為：
其中 是最優步長因子。顯然，當 時， 。到這裡，我們還有一個已知條件沒用，就是目標函數為二次正定，所以我們對目標函數求導，得到：
因為 是極小點，所以有:
將 帶入上述方程式，有：
上式兩邊同時左乘 ，並注意到 和 ，得到 。這就是為使 直指極小點 ， 所必須滿足的條件。並且我們將兩個向量 和 稱為 共軛向量 或稱 和 是 共軛方向 。
由上面共軛梯度法那張圖可以設：
上式兩邊同時左乘 ,得：
由此解出：
代回 得：
從而求到了 的方向。
歸納一下，對於正定二元二次函數，從任意初始點 出發，沿任意下降方向 做直線搜索得到 再從 出發，沿 的共軛方向 作直線搜索，所得到的 必是極小點 。到目前為止的共軛梯度法依舊是假設了目標函數是二次正定矩陣。
上面的結果可以推廣到 維空間中，即在 維空間中，可以找出 個互相共軛的方向，對於 元正定二次函數從任意初始點出發，順次沿着這 個共軛方向最多作 次直線搜索，就可以求到目標函數的極小點。
對於 元正定二次目標函數，如果從任意初始點出發經過 有限次迭代 就能夠求到極小點，那麼稱這種算法具有 二次終止性 。例如，Newton法對於二次函數只須經過一次迭代就可以求到極小點，因此是二次終止的；而最速下降法就不具有二次終止性。共軛方向法（如共軛梯度法、擬Newton法等）也是二次終止的。
一般說來，具有二次終止性的算法，在用於一般函數時，收斂速度是較快的。
定義：設 是 對稱正定矩陣。若 維向量空間中的非零向量 滿足 ， 則稱 是 共軛向量或稱向量 是 共軛的（簡稱共軛）。
當 (單位矩陣)時 變為 ， 。即向量 互相正交 。由此看到，「正交」是「共軛」的一種特殊情形，或說，「共軛」是「正交」的推廣。
下面介紹幾個定理：
定理 ：若非零向量 是 共軛的，則線性無關。
推論 ：在 維向量空間中， 非零的共軛向量的個數不超過 。
定義 設 是 中的線性無關向量， 。那麼形式為：
的向量構成的集合，記為 。稱為由點 和向量 所生成的 線性流形 。
共軛方向法的理論基礎是下面的定理。
定理 假設
(1) Q為 對稱正定矩陣;
(2) 非零向量 是 共軛向量;
(3) 對二次目標函數 順次進行 次直線搜索:
其中 是任意選定的初始點，則有：
i) ， ;
ii) 是二次函數 在線性流形 上的極小點。
這個定理看來較繁，但可借用直觀的幾何圖形來幫助理解。 ， 的情形為例，如圖示。
和 是Q共軛向量，張成了二維空間 ，這是過坐標原點的一個平面。 現在，過點 沿 方向作直線搜索得到 ，再過點 沿 方向作直線搜索得到 過點 由向量 和 張成的平面就是線性流形 。它是 的平行平面。
定理的論斷是，最後一個迭代點 處的梯度 必與 和 垂直。並且 是三元二次目標函數 在線性流形 (即過 由 和 張成的平面)上的極小點。
共軛方向法算法的大體流程 就是：選定初始點 和下降方向向量 ，做直線搜索 。提供的梯度方向 使得 ， 。提供共軛方向的方法有多種。不同的提供方法將對應不同的共軛方法。每種方法也因產生共軛方向的特點而得名。
那麼這裡做直線搜索 中的 是如何確定的呢？這裡我們先回顧一下在最速下降法中是如何計算這個 的。最速下降法：
依據定理 設目標函數 具有一階連續偏導數，若 ,則 。，我們可以得到 。由此有：
由此，可求解出 :
這裡還可以採用另外一種種方式計算 ，下面對另外一種方式進行公式推導：
由 ，用 左乘上式兩邊，然後再同時加上 ，利用 能夠得到：
左乘 有
由此解出：
在最速下降法中 ，在共軛方向法中 。
在共軛方向法中，如果初始共軛向量 恰好取為初始點 處的負梯度 ，而其餘共軛向量 由第 個迭代點 處的負梯度 與已經得到的共軛向量 的線性組合來確定，那麼這個共軛方向法就稱為 共軛梯度法 。
針對目標函數是正定二次函數來討論：
(1) 第一個迭代點的獲得 ：
選定初始點 ，設 (否則迭代終止)，因此 。取 ，（以下用 表示 ）從 出發沿 方向做直線搜索，得到第1個迭代點 ，其中 可由下式確定：
顯然
(2) 第二個迭代點的獲得 ：
設 ，因此 。由 知 與 線性無關。取 其中 是使 與 共軛的待定係數，令：
由此解出
並代回確定 ，並獲得第2個迭代點。
由公式 可以求得 ，帶入公式 可進一步優化得到：
(3) 第三個迭代點的獲得 ：
設 ，因此 。由 知 與 線性無關。取 其中 是使 與 共軛的待定係數，令：
由此解出
並代回確定 ，並獲得第3個迭代點。
其中
上述過程僅表明 與 ， 與 共軛，現在問， 與 也共軛嗎？
(4) 第 個迭代點的獲得 ：
由 知 與 線性無關。取 其中 是使 與 共軛的待定係數，令：
由此解出
並代回確定 ，並獲得第k+1個迭代點。
其中
以上就是共軛梯度法得核心內容。
為使共軛梯度算法也適用於非二次函數，需要消去算法中的 對於正定二次函數，有 代入到 中，得：
此式中已不再出現矩陣 ，將 兩端轉置運算，並同時右乘 得：
將共軛方向法中的定理帶入得到 ，由直線搜索的性質有 ，帶入上式有 。此外：
帶入 ，得到：
此式稱為Fletcher－Reeves公式(1964年)。
神經網絡中rprop是什麼算法
對於bp神經網絡來說沒有固定的標準可以得到最好的bp網絡，設計好後只能手動修改參數然後選擇最好的。下邊是個分類的例子
clc
clear
close all
%—————————————————
% 產生訓練樣本與測試樣本，每一列為一個樣本
P1 = [rand(3,5),rand(3,5)+1,rand(3,5)+2];
T1 = [repmat([1;0;0],1,5),repmat([0;1;0],1,5),repmat([0;0;1],1,5)];
P2 = [rand(3,5),rand(3,5)+1,rand(3,5)+2];
T2 = [repmat([1;0;0],1,5),repmat([0;1;0],1,5),repmat([0;0;1],1,5)];
%—————————————————
% 歸一化
[PN1,minp,maxp] = premnmx(P1);
PN2 = tramnmx(P2,minp,maxp);
%—————————————————
% 設置網絡參數
NodeNum = 10; % 隱層節點數
TypeNum = 3; % 輸出維數
TF1 = ‘tansig’;TF2 = ‘purelin’; % 判別函數(缺省值)
%TF1 = ‘tansig’;TF2 = ‘logsig’;
%TF1 = ‘logsig’;TF2 = ‘purelin’;
%TF1 = ‘tansig’;TF2 = ‘tansig’;
%TF1 = ‘logsig’;TF2 = ‘logsig’;
%TF1 = ‘purelin’;TF2 = ‘purelin’;
net = newff(minmax(PN1),[NodeNum TypeNum],{TF1 TF2});
%—————————————————
% 指定訓練參數
% net.trainFcn = ‘traingd’; % 梯度下降算法
% net.trainFcn = ‘traingdm’; % 動量梯度下降算法
%
% net.trainFcn = ‘traingda’; % 變學習率梯度下降算法
% net.trainFcn = ‘traingdx’; % 變學習率動量梯度下降算法
%
% (大型網絡的首選算法 – 模式識別)
% net.trainFcn = ‘trainrp’; % RPROP(彈性bp)算法,內存需求最小
%
% 共軛梯度算法
% net.trainFcn = ‘traincgf’; % Fletcher-Reeves修正算法
% net.trainFcn = ‘traincgp’; % Polak-Ribiere修正算法,內存需求比Fletcher-Reeves修正算法略大
% net.trainFcn = ‘traincgb’; % Powell-Beal複位算法,內存需求比Polak-Ribiere修正算法略大
% (大型網絡的首選算法 – 函數擬合,模式識別)
% net.trainFcn = ‘trainscg’; % Scaled Conjugate Gradient算法,內存需求與Fletcher-Reeves修正算法相同,計算量比上面三種算法都小很多
%
% net.trainFcn = ‘trainbfg’; % Quasi-Newton Algorithms – BFGS Algorithm,計算量和內存需求均比共軛梯度算法大,但收斂比較快
% net.trainFcn = ‘trainoss’; % One Step Secant Algorithm,計算量和內存需求均比BFGS算法小,比共軛梯度算法略大
%
% (中小型網絡的首選算法 – 函數擬合,模式識別)
net.trainFcn = ‘trainlm’; % Levenberg-Marquardt算法,內存需求最大,收斂速度最快
%
% net.trainFcn = ‘trainbr’; % 貝葉斯正則化算法
%
% 有代表性的五種算法為:’traingdx’,’trainrp’,’trainscg’,’trainoss’, ‘trainlm’
%———————%
net.trainParam.show = 1; % 訓練顯示間隔
net.trainParam.lr = 0.3; % 學習步長 – traingd,traingdm
net.trainParam.mc = 0.95; % 動量項係數 – traingdm,traingdx
net.trainParam.mem_reduc = 10; % 分塊計算Hessian矩陣(僅對Levenberg-Marquardt算法有效)
net.trainParam.epochs = 1000; % 最大訓練次數
net.trainParam.goal = 1e-8; % 最小均方誤差
net.trainParam.min_grad = 1e-20; % 最小梯度
net.trainParam.time = inf; % 最大訓練時間
%—————————————————
% 訓練與測試
net = train(net,PN1,T1); % 訓練
%—————————————————
% 測試
Y1 = sim(net,PN1); % 訓練樣本實際輸出
Y2 = sim(net,PN2); % 測試樣本實際輸出
Y1 = full(compet(Y1)); % 競爭輸出
Y2 = full(compet(Y2));
%—————————————————
% 結果統計
Result = ~sum(abs(T1-Y1)) % 正確分類顯示為1
Percent1 = sum(Result)/length(Result) % 訓練樣本正確分類率
Result = ~sum(abs(T2-Y2)) % 正確分類顯示為1
Percent2 = sum(Result)/length(Result) % 測試樣本正確分類率
Python怎麼做最優化
一、概觀scipy中的optimize子包中提供了常用的最優化算法函數實現。我們可以直接調用這些函數完成我們的優化問題。optimize中函數最典型的特點就是能夠從函數名稱上看出是使用了什麼算法。下面optimize包中函數的概覽：1.非線性最優化fmin — 簡單Nelder-Mead算法fmin_powell — 改進型Powell法fmin_bfgs — 擬Newton法fmin_cg — 非線性共軛梯度法fmin_ncg — 線性搜索Newton共軛梯度法leastsq — 最小二乘2.有約束的多元函數問題fmin_l_bfgs_b —使用L-BFGS-B算法fmin_tnc —梯度信息fmin_cobyla —線性逼近fmin_slsqp —序列最小二乘法nnls —解|| Ax – b ||_2 for x=03.全局優化anneal —模擬退火算法brute –強力法4.標量函數fminboundbrentgoldenbracket5.擬合curve_fit– 使用非線性最小二乘法擬合6.標量函數求根brentq —classic Brent (1973)brenth —A variation on the classic Brent（1980）ridder —Ridder是提出這個算法的人名bisect —二分法newton —牛頓法fixed_point7.多維函數求根fsolve —通用broyden1 —Broyden』s first Jacobian approximation.broyden2 —Broyden』s second Jacobian approximationnewton_krylov —Krylov approximation for inverse Jacobiananderson —extended Anderson mixingexcitingmixing —tuned diagonal Jacobian approximationlinearmixing —scalar Jacobian approximationdiagbroyden —diagonal Broyden Jacobian approximation8.實用函數line_search —找到滿足強Wolfe的alpha值check_grad —通過和前向有限差分逼近比較檢查梯度函數的正確性二、實戰非線性最優化fmin完整的調用形式是：fmin(func, x0, args=(), xtol=0.0001, ftol=0.0001, maxiter=None, maxfun=None, full_output=0, disp=1, retall=0, callback=None)不過我們最常使用的就是前兩個參數。一個描述優化問題的函數以及初值。後面的那些參數我們也很容易理解。如果您能用到，請自己研究。下面研究一個最簡單的問題，來感受這個函數的使用方法：f(x)=x**2-4*x+8，我們知道，這個函數的最小值是4，在x=2的時候取到。from scipy.optimize import fmin #引入優化包def myfunc(x):return x**2-4*x+8 #定義函數x0 = [1.3] #猜一個初值xopt = fmin(myfunc, x0) #求解print xopt #打印結果運行之後，給出的結果是：Optimization terminated successfully.Current function value: 4.000000Iterations: 16Function evaluations: 32[ 2.00001953]程序準確的計算得出了最小值，不過最小值點並不是嚴格的2，這應該是由二進制機器編碼誤差造成的。除了fmin_ncg必須提供梯度信息外，其他幾個函數的調用大同小異，完全類似。我們不妨做一個對比：from scipy.optimize import fmin,fmin_powell,fmin_bfgs,fmin_cgdef myfunc(x):return x**2-4*x+8×0 = [1.3]xopt1 = fmin(myfunc, x0)print xopt1printxopt2 = fmin_powell(myfunc, x0)print xopt2printxopt3 = fmin_bfgs(myfunc, x0)print xopt3printxopt4 = fmin_cg(myfunc,x0)print xopt4給出的結果是：Optimization terminated successfully.Current function value: 4.000000Iterations: 16Function evaluations: 32[ 2.00001953]Optimization terminated successfully.Current function value: 4.000000Iterations: 2Function evaluations: 531.99999999997Optimization terminated successfully.Current function value: 4.000000Iterations: 2Function evaluations: 12Gradient evaluations: 4[ 2.00000001]Optimization terminated successfully.Current function value: 4.000000Iterations: 2Function evaluations: 15Gradient evaluations: 5[ 2.]我們可以根據給出的消息直觀的判斷算法的執行情況。每一種算法數學上的問題，請自己看書學習。個人感覺，如果不是純研究數學的工作，沒必要搞清楚那些推導以及定理云云。不過，必須了解每一種算法的優劣以及能力所及。在使用的時候，不妨多種算法都使用一下，看看效果分別如何，同時，還可以互相印證算法失效的問題。在from scipy.optimize import fmin之後，就可以使用help(fmin)來查看fmin的幫助信息了。幫助信息中沒有例子，但是給出了每一個參數的含義說明，這是調用函數時候的最有價值參考。有源碼研究癖好的，或者當你需要改進這些已經實現的算法的時候，可能需要查看optimize中的每種算法的源代碼。在這裡：https:/ / github. com/scipy/scipy/blob/master/scipy/optimize/optimize.py聰明的你肯定發現了，順着這個鏈接往上一級、再往上一級，你會找到scipy的幾乎所有源碼！
共軛梯度法是什麼？
共軛梯度法（Conjugate Gradient）是介於最速下降法與牛頓法之間的一個方法，它僅需利用一階導數信息。
但克服了最速下降法收斂慢的缺點，又避免了牛頓法需要存儲和計算Hesse矩陣並求逆的缺點，共軛梯度法不僅是解決大型線性方程組最有用的方法之一，也是解大型非線性最優化最有效的算法之一。
在各種優化算法中：
共軛梯度法是非常重要的一種。其優點是所需存儲量小，具有步收斂性，穩定性高，而且不需要任何外來參數。
共軛梯度法是一個典型的共軛方向法，它的每一個搜索方向是互相共軛的，而這些搜索方向d僅僅是負梯度方向與上一次迭代的搜索方向的組合，因此，存儲量少，計算方便。
共軛梯度法的算法介紹
又稱共軛斜量法，是解線性代數方程組和非線性方程組的一種數值方法，例如對線性代數方程組 Ax=ƒ, (1)式中A為n階矩陣，x和ƒ為n維列向量,當A對稱正定時,可以證明求(1)的解X*和求二次泛函
的極小值問題是等價的。此處(x,у)表示向量x和у的內積。由此，給定了初始向量x（0），按某一方向去求(2)式取極小值的點x(1),就得到下一個迭代值x(2),再由x(2)出發，求x(3)等等，這樣來逼近x*。若取求極小值的方向為F在 x(k=1,2,…)處的負梯度方向就是所謂最速下降法，然而理論和實際計算表明這個方法的收斂速度較慢，共軛梯度法則是在 x(k-1)處的梯度方向r(k-1)和這一步的修正方向p(k-1)所構成的二維平面內，尋找使F減小最快的方向作為下一步的修正方向p(k),即求極小值的方向p（其第一步仍取負梯度方向）。計算公式為
再逐次計算(k=1,2,…)。可以證明當i≠j時，
從而平p(1),p(2)形成一共軛向量組;r(0),r(1),…形成一正交向量組。後者說明若沒有舍入誤差的話，至多 n次迭代就可得到(1)的精確解。然而在實際計算中,一般都有舍入誤差，所以r(0),r(1),…並不真正互相正交，而尣(0)尣(1),…等也只是逐步逼近(1)的真解,故一般將共軛梯度法作為迭代法來使用。
近來在解方程組(1)時,常將共軛梯度法同其他一些迭代法結合作用。特別是對病態方程組這種方法往往能收到比較顯著的效果。其方法是選取一對稱正定矩陣B並進行三角分解，得B=LLT。將方程組(1)化為 hу=b, (3)
此處y=lTx,b=l-1ƒ,h=l-1Al-T,而
再對(3)用共軛梯度法，計算公式為
k=0,1,2,…)適當選取B，當B很接近A時，h的條件數較之A大大減小,從而可使共軛梯度法的收斂速度大為加快，由一些迭代法的矩陣分裂A=M -N，可選取M 為這裡的B，例如對稱超鬆弛迭代(SSOR)，強隱式迭代(SIP)等,這類方法常稱為廣義共軛梯度法或預條件共軛梯度法，它也可用於解代數特徵值問題。
原創文章，作者：0PIB5，如若轉載，請註明出處：https://www.506064.com/zh-hk/n/128838.html
微信掃一掃 
支付寶掃一掃 