最速下降算法、牛頓算法、BFGS擬牛頓算法、共軛梯度算法無約束極值問題

2021-02-13 數學與MATLAB之美

2）基於matlab語言的函數定義

function [x0,X,iter] = steepest_descent(f,x0,tol,maxiter)

df=sdf(f,x0);f_sym1='f(';df_sym='df(';

for k=1:length(x0)

    f_sym1=[f_sym1,'x1(',num2str(k),'),'];

    df_sym=[df_sym,'x0(',num2str(k),'),'];

end

f_sym1(end)=[];f_sym1=[f_sym1,')'];df_sym(end)=[];df_sym=[df_sym,')'];

f_td = eval(df_sym);d_k=-f_td/norm(f_td);iter=0;X=x0;nn=0;

while norm(f_td) > tol

    if iter > maxiter

        break

    end

    iter = iter+1;

    syms SL

    assume(SL>=0);x1=x0+SL*d_k;fx1=eval(f_sym1);d_x1=diff(fx1);

    d_SL=double(solve(d_x1));fx1=matlabFunction(fx1);

    ff=zeros([1 length(d_SL)]);

    for ii=1:length(d_SL)

        ff(ii)=fx1(d_SL(ii));

    end

    d_SL=d_SL(ff==min(ff));x0=x0+d_SL(1)*d_k;f_td=eval(df_sym);

    d_k=-f_td/norm(f_td);nn=nn+1;X(:,nn+1)=x0;

end

end

2）基於matlab語言的函數定義

function [x0,X,iter] = newton_min(f,x0,tol,maxiter)

df=sdf(f,x0);ddf=sddf(f,x0);

df_sym='df(';ddf_sym='ddf(';

for k=1:length(x0)

    df_sym=[df_sym,'x0(',num2str(k),'),'];

    ddf_sym=[ddf_sym,'x0(',num2str(k),'),'];

end

df_sym(end)=[];df_sym=[df_sym,')'];

ddf_sym(end)=[];ddf_sym=[ddf_sym,')'];

f_td = eval(df_sym);iter=-1;X=x0;nn=0;

while norm(f_td) > tol

    if iter > maxiter

        break

    end

    nn=nn+1;iter = iter+1;

    X(:,nn)=x0;f_td = eval(df_sym);

    f_hessian = eval(ddf_sym);

    x0 = x0 - f_hessian\f_td; 

end

end

2) 基於matlab語言的函數定義

function [x0,X,iter] = BFGS_Newton(f,x0,tol,maxiter)

df=sdf(f,x0);H0=eye(length(x0));f_sym1='f(';df_sym='df(';

for k=1:length(x0)

    f_sym1=[f_sym1,'x1(',num2str(k),'),'];

    df_sym=[df_sym,'x0(',num2str(k),'),'];

end

f_sym1(end)=[];f_sym1=[f_sym1,')'];df_sym(end)=[];

df_sym=[df_sym,')'];f_td = eval(df_sym);iter=0;X=x0;nn=0;

while norm(f_td) > tol

    if iter > maxiter

        break

    end

    iter = iter+1;

    syms SL

    assume(SL>=0);p0=-H0*f_td;x1=x0+SL*p0;fx1=eval(f_sym1); d_x1=diff(fx1); d_SL=double(solve(d_x1));

    fx1=matlabFunction(fx1);ff=zeros([1 length(d_SL)]);

    for ii=1:length(d_SL)

        ff(ii)=fx1(d_SL(ii));

    end

    d_SL=d_SL(ff==min(ff)); x0=x0+d_SL*p0; f_td2=eval(df_sym);dgk=f_td2-f_td;f_td=f_td2;dxk=d_SL*p0;

    H0=H0+(dxk*dxk')/(dxk'*dgk)*(1+dgk'*H0*dgk/(dxk'*dgk))-(dxk*dgk'*H0+H0*dgk*dxk')/(dxk'*dgk);

    nn=nn+1;X(:,nn+1)=x0;

end

end

2）基於matlab語言的函數定義

function [x0,X,iter] = conj_grad(f,x0,tol,maxiter)

df=sdf(f,x0);f_sym1='f(';df_sym='df(';

for k=1:length(x0)

    f_sym1=[f_sym1,'x1(',num2str(k),'),'];

    df_sym=[df_sym,'x0(',num2str(k),'),'];

end

f_sym1(end)=[];f_sym1=[f_sym1,')'];

df_sym(end)=[];df_sym=[df_sym,')'];

f_td = eval(df_sym);p0=-f_td;iter=0;X=x0;nn=0;

while norm(f_td) > tol

    if iter > maxiter

        break

    end

    iter = iter+1;

    syms SL

    assume(SL>=0);x1=x0(:)+SL*p0;fx1=eval(f_sym1);

    d_x1=diff(fx1);d_SL=double(solve(d_x1));

    fx1=matlabFunction(fx1);ff=zeros([1 length(d_SL)]);

    for ii=1:length(d_SL)

        ff(ii)=fx1(d_SL(ii));

    end

    d_SL=d_SL(ff==min(ff));x0=x0(:)+d_SL*p0;

    f_td2=eval(df_sym);p0=-f_td2+p0*(f_td2'*(f_td2-f_td))/(norm(f_td)^2);

    f_td=f_td2;d_k=-f_td/norm(f_td);nn=nn+1;X(:,nn+1)=x0;

end

end

代碼部分由王曉東同學提供

相關焦點

  • 計算機視覺:從入門到精通,極限剖析圖像識別學習算法
    本次課程將圍繞著計算機視覺中最常見的RCNN圖像識別算法進行極限剖析，從數學理論， 模型框架到實踐實操，讓你在短時間內從理論到實踐，掌握深度學習的基本知識和學習方法。· 目的：掌握神經網絡的基本原理，知其然亦知其所以然（從數學實踐到代碼的熟練和精通）; · 手段：科學的方法。
  • 想一個月搞定面試算法?來《九章算法班》!第一節免費試聽!
    想接受系統的面試算法培訓的同學，或想換工作的但是算法比較薄弱的工程師。0算法基礎即可參與學習。主講令狐衝老師，曾就職於超過2家矽谷頂尖IT企業,  北美和國內頂尖IT企業offer數10+，面試人數超過200人。課程大綱由易到難。只要你會任何一門計算機語言即可參加。尤其適合算法基礎相對薄弱的 or 轉專業的 or 想跳槽卻太久沒刷題的同學。分九個章節，系統的講授面試中涉及的算法知識。
  • 經典算法題:猜數(360軟體測試工程師筆試題)
    備註：1、不定期將從留言區選出認真答題的1名朋友，贈與書籍《算法詳解（卷1）》一本（兌獎方法跟獲獎者私下溝通）請留言，說出你的解題思路。不定期整理相關的問題答案分享。算法能力的考察，向來是頂級科研機構和IT公司面試時最具備區分度的成分，算法功夫紮實，提升面試效率。這種想法其實也不無道理，從小接受系統化訓練，參加過信息學競賽或ACM，肯定會對算法問題反應更快一些。可是這樣的人畢竟是極少數，而且即使是他們，也無一不是長期大量地訓練才會不斷進步。這至少說明，算法並非天外之學，而是一種能夠通過訓練掌握的技能。
  • 貪心算法:加油站
    可以看一下公眾號左下角的「算法匯總」，「算法匯總」已經把題目順序編排好了，文章順序即刷題順序，這是全網最詳細的刷題順序了，方便錄友們從頭打卡學習，「算法匯總」會持續更新！❞134.class Solution {public:    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {        int curSum = 0;        int min = INT_MAX; // 從起點出發，油箱裡的油量最小值
  • 益智遊戲剋星:BFS暴力搜索算法
    但是我們今天不來研究讓人頭禿的技巧，這些益智遊戲通通可以用暴力搜索算法解決，所以今天我們就學以致用，用 BFS 算法框架來秒殺這些遊戲。一、題目解析LeetCode 第 773 題就是滑動拼圖問題，題目的意思如下：給你一個 2x3 的滑動拼圖，用一個 2x3 的數組board表示。
  • 知其所以然之永不遺忘的算法
    我們當然希望自己掌握一個算法後，就永遠不會忘記，最好還能舉一反三，利用算法中的思想去解決新的問題。然而，現實與美好的願景往往是背道而馳，不要說舉一反三，我們甚至經常忘記那些算法本身。背算法與設計算法為什麼會這樣？
  • 一文讀懂哈希和一致性哈希算法
    "主要特點：•不可逆 從哈希值不能推導出原始數據, 所以Hash算法廣泛應用在現代密碼體系中•無碰撞 不同的信息進行哈希後得到的值應該是不同的, 但是從理論上來說, 哈希算法其實是有可能發生碰撞的, 輸入的信息是無窮的, 而輸出的哈希值長度是固定的, 所以是有限的。
  • 小視科技:狗臉識別算法,讓你告別狗盲症!
    其將極大解決「讓狗成為你的狗」以及「如何證明這是你的狗」的問題。當前，隨著狗的數量越來越多，管理問題逐漸顯現。如犬類傷人事件、走失事件等頻頻發生，犬類的管理已經迫在眉睫。眾所周知，養寵物需要為寵物建立檔案，而目前晶片植入是國內主要給寵物建檔的方式，該類方式可能存在：晶片植入難度大、寵物體驗不佳亦或是安全性不足等問題。因此狗臉識別技術，無疑將為犬類管理帶來一次革新。
  • Facebook 新算法:惡語也分三六九等
    但在整改前，公司的算法和制度並沒有對不同群體加以區分，系統無法判斷哪些群體易受仇恨言論的攻擊，哪些群體不屬於長期邊緣化人群。像「白人愚蠢」這樣的評論甚至會與反猶太主義和種族歧視並為一談。 多年來，民權倡導者一直在抨擊Facebook大量清除黑人用戶帖子的現象，這種情況在黑人描述歧視經歷時猶為明顯，此次算法修改也是對這一批評的回應。
  • 十二地支講解:天幹地支最正確的算法
    那麼問題來了，天幹地支的真確算法是什麼樣的呢？　　本期的十二地支為你講解：天幹地支最正確的算法。　　天幹地支計算方法　　一、年幹支計算公元後年份的口訣是：　　「公元年數先減三，除10餘數是天幹，基數改用12除，餘數便是地支年」。
  • 圖靈獎得主發推道歉:因去賽馬克算法被指歧視黑人
    前不久美國杜克大學的科研人員宣布了一種新的AI去馬賽克算法PULSE，跟傳統的超解析度算法不同，它不是填補像素，而是先生成高清大圖
  • 知識拓展:recommendation algorithm(推薦算法)讓你不知不覺深陷APP
    *吉米·威爾士維基百科現由非營利組織維基媒體基金會負責營運，是全球網絡上最大且最受大眾歡迎的參考工具書，名列全球十大最受歡迎的網站。目前，維基百科各個版本的條目之和已經超過5300萬條，支持各種語言，其中中文維基百科有超過113萬個條目。
  • 財務管理:成本計算--加權平均算法
    移動加權平均算法大多數的ERP使用的是加權平均算法，現在我們來舉個例子解釋一下加權平均算法步驟1：入庫2支鉛筆，每支
  • 網易遊戲面試題:如何設計一個公平的洗牌算法
    ）。我記得在面試網易遊戲的時候，面試官當時是這樣問我的：「給你一副撲克牌，你能設計一個公平的洗牌算法嗎？」。後來我復盤時發現，原來這就是著名的 Knuth 算法，不過我當時純屬瞎貓碰上死耗子，命好！細想一下，面試官問的是設計一個公平的洗牌算法？這裡的公平究竟是什麼意思呢？
  • 澳洲航司通過算法看人給價!你被套路了嗎?
    首先，當你上網看價格時，你用的設備型號，瀏覽器都會被航空公司記錄，它會通過算法給你形成一個個人檔案，判斷你的價格接受度，從而決定對你顯示的價格。也就是說，如果網站一不小心發現你是個富婆，那給你的價格就要比尋常人的高！
  • 新算法:換算成人類的年齡,你家汪是幾歲?
    新算法：換算成人類的年齡，你家汪是幾歲？綜合大量的數據，總結出，狗狗的壽命一般在12—15歲之間，而現有記錄中記載的最長壽狗狗活到了34歲！狗狗在一歲左右進入成年期，2-5歲是狗狗的壯年期，6歲以後，狗狗開始出現衰老現象，在10歲左右，它們的生殖能力就將停止。一般來說，串串狗比純種狗長壽，小型狗比大型狗長壽，公狗比母狗長壽，室內飼養的狗比室外飼養的狗長壽。
  • 圖解算法:摘取位運算的王冠「八皇后問題」!
    掌握這個很重要，有啥用呢，比如我要統計 1 的位數有幾個，只要寫個如下循環即可，不斷地將 x 最右邊的 1 置為 0，最後當值為 0 時統計就結束了。接下來我們看看位運算在算法題中的應用。4、 利用位運算來解八皇后問題接下來我們來看看終級 Boss 題，如何用位運算來解八皇后問題，解題中運用到了非常多的位運算技巧，相信你學完會收穫不少。
  • 柳葉刀子刊:我國學者開發檢測口腔癌深度算法,通過手機APP檢測,準確率98%
    該研究開發了一種基於臨床視覺特徵自動檢測口腔癌的深度學習算法，為口腔癌的篩查和早期診斷提供了一種非侵入式、快捷易用且成本低廉的輔助檢查工具。這項成果能從普通的臨床口腔照片中快速檢測出口腔癌的病灶區域，具有較高的準確性和靈敏度。
  • 海岸線提取:日本政府舉辦的CV算法大賽
    8月份，日本經濟產業省在日本算法競賽網站Signate舉辦了一個海岸線提取的比賽：https://signate.jp/competitions/284目前已有600多支團隊參賽，如果有感興趣的朋友現在還可以參加。比賽任務：千言萬語不如一張圖：
  • 【思源論壇】第95期:優秀學術人物洪永勝作學術報告: 分數階微分算法在土壤光譜領域中的應用
    12月29日晚19：00第95期思源論壇在資環院220學術報告廳如期開展，2017級土地資源管理專業博士生洪永勝同學向我們展示了分數階微分算法在土壤光譜領域中的應用。報告分為四個部分，第一部分介紹了分數階微分的研究背景；第二部分介紹了分數階微分（FOD）的方法原理；第三部分介紹了兩個研究案例，最後一部分為結論和討論。