無(wú)約束最優(yōu)化問(wèn)題的擬牛頓法畢業(yè)論文

1、題 目：無(wú)約束最優(yōu)化問(wèn)題的擬牛頓法畢業(yè)論文誠(chéng)信聲明本人聲明：1、本人所呈交的畢業(yè)設(shè)計(jì)（論文）是在老師指導(dǎo)下進(jìn)行的 研究工作及取得的研究成果；2、 據(jù)查證，除了文中特別加以標(biāo)注和致謝的地方外，畢業(yè) 設(shè)計(jì)（論文）中不包含其他人已經(jīng)公開(kāi)發(fā)表過(guò)的研究成果，也不包含為獲得其他教育機(jī)構(gòu)的學(xué)位而使用過(guò)的材料；矚慫潤(rùn)厲釤瘞睞櫪廡賴(lài)。3、我承諾，本人提交的畢業(yè)設(shè)計(jì)（論文）中的所有內(nèi)容均 真實(shí)、可信。作者簽名:日期：年 月曰或全部?jī)?nèi)容殘騖樓靜錈瀨濟(jì)溆塹籟。畢業(yè)設(shè)計(jì)（論文）原創(chuàng)性聲明和使用授權(quán)說(shuō)明原創(chuàng)性聲明本人鄭重承諾：所呈交的畢業(yè)設(shè)計(jì)（論文），是我個(gè)人在指導(dǎo)教 師的指導(dǎo)下進(jìn)行的研究工作及取得的成果。 盡我所知，除

2、文中特別加 以標(biāo)注和致謝的地方外，不包含其他人或組織已經(jīng)發(fā)表或公布過(guò)的研 究成果，也不包含我為獲得及其它教育機(jī)構(gòu)的學(xué)位或?qū)W歷而使用過(guò)的材料。對(duì)本研究提供過(guò)幫助和做出過(guò)貢獻(xiàn)的個(gè)人或集體，均已在文中作了明確的說(shuō)明并表示了謝意。聞創(chuàng)溝燴鐺險(xiǎn)愛(ài)氌譴凈。作者簽名：日期：指導(dǎo)教師簽名：日期：使用授權(quán)說(shuō)明本人完全了解大學(xué)關(guān)于收集、保存、使用畢業(yè)設(shè)計(jì)（論文）的規(guī)定，即：按照學(xué)校要求提交畢業(yè)設(shè)計(jì)（論文）的印刷本和電 子版本；學(xué)校有權(quán)保存畢業(yè)設(shè)計(jì)（論文）的印刷本和電子版，并提供 目錄檢索與閱覽服務(wù)；學(xué)?？梢圆捎糜坝?、縮印、數(shù)字化或其它復(fù)制 手段保存論文；在不以贏利為目的前提下，學(xué)?？梢怨颊撐牡牟糠肿髡吆灻?日

3、 期：學(xué)位論文原創(chuàng)性聲明本人鄭重聲明：所呈交的論文是本人在導(dǎo)師的指導(dǎo)下獨(dú)立進(jìn)行研究所取得的研究成果。除了文中特別加以標(biāo)注引用的內(nèi)容外， 本論文 不包含任何其他個(gè)人或集體已經(jīng)發(fā)表或撰寫(xiě)的成果作品。 對(duì)本文的研 究做出重要貢獻(xiàn)的個(gè)人和集體，均已在文中以明確方式標(biāo)明。本人完 全意識(shí)到本聲明的法律后果由本人承擔(dān)。 釅錒極額閉鎮(zhèn)檜豬訣錐。作者簽名：日期：年月日學(xué)位論文版權(quán)使用授權(quán)書(shū)本學(xué)位論文作者完全了解學(xué)校有關(guān)保留、使用學(xué)位論文的規(guī)定， 同意學(xué)校保留并向國(guó)家有關(guān)部門(mén)或機(jī)構(gòu)送交論文的復(fù)印件和電子版， 允許論文被查閱和借閱。本人授權(quán)大學(xué)可以將本學(xué)位論文的全部或部分內(nèi)容編入有關(guān)數(shù)據(jù)庫(kù)進(jìn)行檢索，可以采用影印、縮

4、印或掃描等復(fù)制手段保存和匯編本學(xué)位論文。彈貿(mào)攝爾霽斃攬磚鹵廡。涉密論文按學(xué)校規(guī)定處理。作者簽名：日期： 年 月 日導(dǎo)師簽名:日期： 年 月指導(dǎo)教師評(píng)閱書(shū)指導(dǎo)教師評(píng)價(jià)：一、撰寫(xiě)（設(shè)計(jì)）過(guò)程1、學(xué)生在論文（設(shè)計(jì)）過(guò)程中的治學(xué)態(tài)度、工作精神優(yōu) 良 中 及格 不及格2、學(xué)生掌握專(zhuān)業(yè)知識(shí)、技能的扎實(shí)程度優(yōu)良中及格不及格3、學(xué)生綜合運(yùn)用所學(xué)知識(shí)和專(zhuān)業(yè)技能分析和解決問(wèn)題的能力優(yōu)良中及格不及格4、研究方法的科學(xué)性；技術(shù)線路的可行性；設(shè)計(jì)方案的合理性 優(yōu) 良 中 及格 不及格5、完成畢業(yè)論文（設(shè)計(jì)）期間的出勤情況優(yōu)良中及格不及格二、論文（設(shè)計(jì)）質(zhì)量1、論文（設(shè)計(jì)）的整體結(jié)構(gòu)是否符合撰寫(xiě)規(guī)范？?jī)?yōu)良中及格不及格2、

5、是否完成指定的論文（設(shè)計(jì)）任務(wù)（包括裝訂及附件）？?jī)?yōu)良中及格不及格三、論文（設(shè)計(jì)）水平1、論文（設(shè)計(jì)）的理論意義或?qū)鉀Q實(shí)際問(wèn)題的指導(dǎo)意義優(yōu)良中及格不及格2、論文的觀念是否有新意？設(shè)計(jì)是否有創(chuàng)意？?jī)?yōu)良中及格不及格3、論文（設(shè)計(jì)說(shuō)明書(shū)）所體現(xiàn)的整體水平優(yōu) 良 中 及格 不及格建議成績(jī)：優(yōu) 良 中 及格 不及格（在所選等級(jí)前的內(nèi)畫(huà)“ V”）指導(dǎo)教師：（簽名）單位：（蓋章）評(píng)閱教師評(píng)閱書(shū)評(píng)閱教師評(píng)價(jià)：一、論文（設(shè)計(jì)）質(zhì)量1、論文（設(shè)計(jì)）的整體結(jié)構(gòu)是否符合撰寫(xiě)規(guī)范？?jī)?yōu)良中及格不及格2、是否完成指定的論文（設(shè)計(jì)）任務(wù)（包括裝訂及附件）？?jī)?yōu)良中及格不及格二、論文（設(shè)計(jì)）水平1、論文（設(shè)計(jì)）的理論意義或?qū)?/p>

6、決實(shí)際問(wèn)題的指導(dǎo)意義 優(yōu) 良 中 及格 不及格2、論文的觀念是否有新意？設(shè)計(jì)是否有創(chuàng)意？?jī)?yōu)良中及格不及格3、論文（設(shè)計(jì)說(shuō)明書(shū)）所體現(xiàn)的整體水平優(yōu)良中及格不及格建議成績(jī)：優(yōu) 良 中 及格 不及格（在所選等級(jí)前的內(nèi)畫(huà)“ V”）評(píng)閱教師：（簽名）單位：（蓋章）年 月 日教研室（或答辯小組）及教學(xué)系意見(jiàn)教研室（或答辯小組）評(píng)價(jià)：一、答辯過(guò)程1、畢業(yè)論文（設(shè)計(jì)）的基本要點(diǎn)和見(jiàn)解的敘述情況優(yōu) 良 中 及格 不及格2、對(duì)答辯問(wèn)題的反應(yīng)、理解、表達(dá)情況優(yōu)良中及格不及格3、學(xué)生答辯過(guò)程中的精神狀態(tài)優(yōu)良中及格不及格二、論文（設(shè)計(jì)）質(zhì)量1、論文（設(shè)計(jì)）的整體結(jié)構(gòu)是否符合撰寫(xiě)規(guī)范？?jī)?yōu)良中及格不及格2、是否完成指定的論

7、文（設(shè)計(jì)）任務(wù)（包括裝訂及附件）？?jī)?yōu)良中及格不及格三、論文（設(shè)計(jì)）水平1、論文（設(shè)計(jì)）的理論意義或?qū)鉀Q實(shí)際問(wèn)題的指導(dǎo)意義優(yōu) 良 中 及格 不及格2、論文的觀念是否有新意？設(shè)計(jì)是否有創(chuàng)意？?jī)?yōu)良中及格不及格3、論文（設(shè)計(jì)說(shuō)明書(shū)）所體現(xiàn)的整體水平優(yōu)良中及格不及格不及格（簽名）日評(píng)定成績(jī)：優(yōu) 良 中 及格（在所選等級(jí)前的內(nèi)畫(huà)“ V"）教研室主任（或答辯小組組長(zhǎng)）：年 月教學(xué)系意見(jiàn):（簽名）系主任:畢業(yè)設(shè)計(jì)（論文）任務(wù)書(shū)題目 無(wú)約束優(yōu)化問(wèn)題的擬牛頓法姓名 XX 院（系） xx 專(zhuān)業(yè)信息與計(jì)算科學(xué) 班級(jí) xx 學(xué)號(hào) XX指導(dǎo)老師 xx 職稱(chēng)教研室主任 xx一、基本任務(wù)及要求：1.基本任務(wù):在牛

8、頓法基礎(chǔ)上提出擬牛頓法，設(shè)計(jì)擬牛頓法的算法，了解擬牛頓法的優(yōu)點(diǎn)及用途。在一定的條件下證明該算法的合理性并對(duì)其收斂性進(jìn)行分析。討論算法的收斂速度，通過(guò)數(shù)值試驗(yàn)對(duì)算法的有效性進(jìn)行驗(yàn)證。謀蕎摶篋飆鐸懟類(lèi)蔣薔。2 基本要求：對(duì)擬牛頓法給岀合理的算法；利用理論知識(shí)對(duì)算法合理性進(jìn)行證明對(duì)其收斂性以及收斂速度進(jìn)行分析證明。寫(xiě)出畢業(yè)設(shè)計(jì)說(shuō)明書(shū)， 完成全部研究工作和畢業(yè)論文。廈礴懇蹣駢時(shí)盡繼價(jià)騷。.、進(jìn)度安排及完成時(shí)間：第一階段（第1 4周）：進(jìn)行調(diào)研，查閱相關(guān)資料，撰寫(xiě)開(kāi)題報(bào)告，并于第4周星期五交開(kāi)題報(bào)告；第二階段（第5- 12周）：在指導(dǎo)教師的指導(dǎo)下，對(duì)課題進(jìn)行研究，按預(yù)定要求獲得畢業(yè)論文開(kāi)題報(bào)告中的預(yù)期結(jié)

9、果（即進(jìn)行算法設(shè)計(jì)，研究算法的合理性，實(shí)現(xiàn)算法等工作），并撰寫(xiě)畢業(yè)論文，第 12周五之前交初稿；第三階段（第13 - 14周）：指導(dǎo)教師對(duì)畢業(yè)論文進(jìn)行批閱，提出修改意見(jiàn)并指導(dǎo)學(xué)生進(jìn)行畢業(yè)論文的修改，并檢查算法的實(shí)現(xiàn)情況（如程序的可行性和通用性等）第四階段（第15周）：指導(dǎo)教師指導(dǎo)學(xué)生將畢業(yè)論文定稿，并準(zhǔn)備畢業(yè)論文答辯；第五階段（第16周）：進(jìn)行畢業(yè)論文答辯。摘 要煢楨廣鰳鯡選塊網(wǎng)羈淚。前 言鵝婭盡損鶴慘歷蘢鴛賴(lài)。第1章最優(yōu)化基礎(chǔ)籟叢媽羥為贍債蟶練淨(jìng)。1.1無(wú)約束最優(yōu)化問(wèn)題的最優(yōu)性條件 3預(yù)頌圣鉉儐歲齦訝驊糴。1.2 收斂概念滲釤嗆儼勻諤鱉調(diào)硯錦。1.3 Wolfe準(zhǔn)則和 Armijo準(zhǔn)則洗誅臥

10、瀉噦圣騁貺頂廡。第2章擬牛頓法算法設(shè)計(jì) 8擁締鳳襪備訊顎輪爛薔。2.1擬牛頓法條件贓熱俁閫歲匱閶鄴鎵騷。2.2 算法設(shè)計(jì)壇搏鄉(xiāng)囂懺蔞鍥鈴氈淚。第3章收斂性證明1.1蠟變黲癟報(bào)倀鉉錨鈰贅。3.1總體收斂 11買(mǎi)鯛鴯譖曇膚遙閆擷凄。3.2 局部超線性收斂 1儀鏑鯛駕櫬鶘蹤韋轔糴。第4章數(shù)值驗(yàn)算2驅(qū)躓髏彥浹綏譎飴憂(yōu)錦。4.1 問(wèn)題模型2貓蠆驢繪燈鮒誅髏貺廡。4.2 數(shù)值結(jié)果2鍬籟饗逕瑣筆襖鷗婭薔。總 結(jié)2構(gòu)氽頑黌碩飩薺齦話騖。致謝2輒嶧陽(yáng)檉籪癤網(wǎng)儂號(hào)澩。參考文獻(xiàn)25堯側(cè)閆繭絳闕絢勵(lì)蜆贅。附 錄26識(shí)饒鎂錕縊灩筧嚌儼淒。無(wú)約束最優(yōu)化問(wèn)題的擬牛頓法摘要：擬牛頓法是求解無(wú)約束最優(yōu)化問(wèn)題最常用的方法之一，擬

11、牛頓法是在牛頓法的基礎(chǔ)上提出來(lái)的。牛頓法成功的關(guān)鍵是利用了Hesse矩陣提供的曲率信息，但計(jì)算Hesse矩陣工作量大，并且有的目標(biāo)函數(shù)的Hesse矩陣很難計(jì)算，甚至不 好求出。擬牛頓法通過(guò)函數(shù)的一階導(dǎo)數(shù)構(gòu)造出曲率的近似，從而避免了求函數(shù)的Hesse矩陣,不需要求函數(shù)的二階導(dǎo)數(shù),從而大大的減小了計(jì)算的復(fù)雜度。同時(shí)擬牛頓法還具有超線性收斂以及收斂速度快的優(yōu)點(diǎn)。擬牛頓算法在求解無(wú)約束優(yōu)化 問(wèn)題中占有不可取代的地位。同時(shí)也是很多學(xué)者研究的課題。本論文將依靠前人 的基礎(chǔ),對(duì)擬牛頓法進(jìn)行介紹并對(duì)其收斂性進(jìn)行證明,同時(shí)給出數(shù)值分析。凍鈹鋨勞 臘錯(cuò)癇婦脛糴。關(guān)鍵詞：擬牛頓法，無(wú)約束優(yōu)化，收斂性。A quasi

12、-newton method for Unconstrainedoptimization恥諤銪滅縈歡煬鞏鶩錦。Abstract: Newt on method is to solvi ng uncon stra ined optimizati on problem of one of the most commo nly used methods.Quasi-newt on method is in Newt on put forward on the basis of law.Newt on method the key to success is the use of the Hesse

13、matrix the curvature of the in formatio n but provide Hesse matrix calculati on workload is big, and some of the objective function Hesse matrix is difficult to calculate, even bad work out.Quasi-newt on method through the first derivative con structed out of the curvature approximate avoid a for th

14、e Hesse matrix could n't ask the sec ond order derivatives.Thus greatly reduced the complexity of the calculati on and quasi-newt on method also has superlinear convergenee and convergenee speed advantages quasi-newt on algorithms in sol ving uncon stra ined optimizati on has irreplaceable posit

15、ion in also many scholars research project of this paper will be depend on the basis of predecessors' to be Newt on method and the con verge nee proof and prese nts nu merical an alysis鯊腎鑰詘漣鉀溈懼統(tǒng)庫(kù)。Key words:Quasi-newt on ,U neon strai ned optimizati on ,Co nv erge nee碩癘鄴頏謅攆檸攜驤蘞。最優(yōu)化方法是近幾十年形成的，它主要運(yùn)

16、用數(shù)學(xué)方法研究各種系統(tǒng)的優(yōu)化 途徑及方案，為決策者提供科學(xué)決策的依據(jù)。最優(yōu)化方法的主要研究對(duì)象是各種 有組織系統(tǒng)的管理問(wèn)題及其生產(chǎn)經(jīng)營(yíng)活動(dòng)。最優(yōu)化方法的目的在于針對(duì)所研究 的系統(tǒng)，求得一個(gè)合理運(yùn)用人力、物力和財(cái)力的最佳方案，發(fā)揮和提高系統(tǒng)的效 能及效益，最終達(dá)到系統(tǒng)的最優(yōu)目標(biāo)。實(shí)踐表明，隨著科學(xué)技術(shù)的日益進(jìn)步和生 產(chǎn)經(jīng)營(yíng)的日益發(fā)展，最優(yōu)化方法已成為現(xiàn)代管理科學(xué)的重要理論基礎(chǔ)和不可缺 少的方法，被人們廣泛地應(yīng)用到公共管理、經(jīng)濟(jì)管理、工程建設(shè)、國(guó)防等各個(gè)領(lǐng) 域，發(fā)揮著越來(lái)越重要的作用。本章將介紹最優(yōu)化方法的研究對(duì)象、特點(diǎn)，以及 最優(yōu)化方法模型的建立和模型的分析、 求解、應(yīng)用。主要是線性規(guī)劃問(wèn)題的模

17、型、 求解（線性規(guī)劃問(wèn)題的單純形解法） 及其應(yīng)用一一運(yùn)輸問(wèn)題；以及動(dòng)態(tài)規(guī)劃的模 型、求解、應(yīng)用 資源分配問(wèn)題。 閿擻輳嬪諫遷擇植秘騖。無(wú)約束優(yōu)化問(wèn)題是最優(yōu)化問(wèn)題的基礎(chǔ)，是數(shù)值計(jì)算領(lǐng)域中十分活躍的研究 課題之一，歷時(shí)較長(zhǎng)，獲得的成果也較多，有關(guān)的方法和理論比較成熟。其中非 線性無(wú)約束最優(yōu)化方法在科學(xué)計(jì)算和工程分析中起著越來(lái)越重要的作用。牛頓法作為求解最優(yōu)化問(wèn)題最有效的方法之一。它的基本思想是利用目標(biāo)函數(shù)的二次泰 勒展開(kāi)，并將其極小化。在非線性無(wú)約束最優(yōu)化問(wèn)題中，對(duì)于正定的二次函數(shù)， 牛頓法一步即可達(dá)到最優(yōu)解。對(duì)于非二次函數(shù)，牛頓法并不能保證經(jīng)有限次迭代 求得最優(yōu)解，但由于目標(biāo)函數(shù)在極小點(diǎn)附近似于

18、二次函數(shù)，故當(dāng)初始點(diǎn)靠近極小點(diǎn)時(shí)，牛頓法的收斂速度一般是很快的，因此這種方法得到了很多人的認(rèn)可與利 用。但牛頓法中每次迭代都需要計(jì)算 Hessian矩陣，但計(jì)算Hessian矩陣工作量 大，并且有的很難計(jì)算，甚至不好求，而以擬牛頓方程為基礎(chǔ)構(gòu)造的擬牛頓算法 克服了牛頓法的這一不足。因此擬牛頓法被廣泛的認(rèn)可，她的應(yīng)用相當(dāng)廣泛?？?以剞劂很多問(wèn)題。并有很多人多擬牛頓法做了研究。氬嚕躑竄貿(mào)懇彈濾頷澩。對(duì)于擬牛頓法的算法設(shè)計(jì)，也已經(jīng)有不少學(xué)者提出過(guò)，早年袁亞湘與孫文 瑜合作最優(yōu)化理論與方法2一書(shū)中對(duì)其進(jìn)行了詳細(xì)的設(shè)計(jì)， 而后也有不少學(xué) 者對(duì)其進(jìn)行研究。釷鵒資贏車(chē)贖孫滅獅贅。對(duì)于擬牛頓法的收斂性證明，時(shí)

19、平平在2008年其碩士論文關(guān)于無(wú)約束最 優(yōu)化問(wèn)題的擬牛頓算法研究 中詳細(xì)的做了證明。慫闡譜鯪逕導(dǎo)嘯畫(huà)長(zhǎng)涼。第1章最優(yōu)化基礎(chǔ)在這一章里我們首先簡(jiǎn)要介紹判斷無(wú)約束最優(yōu)化問(wèn)題的最優(yōu)解常用的最優(yōu) 性條件，接著給出擬牛頓算法的概述，最后說(shuō)明本文的主要工作.諺辭調(diào)擔(dān)鈧諂動(dòng)禪瀉類(lèi)。1.1無(wú)約束最優(yōu)化問(wèn)題的最優(yōu)性條件最優(yōu)化理論與方法是一門(mén)應(yīng)用性很強(qiáng)的年輕學(xué)科，它研究某些數(shù)學(xué)上定義的 問(wèn)題的最優(yōu)解，即對(duì)于給出的實(shí)際問(wèn)題，從眾多的方案中找出最符合要求的最佳 方案在電子計(jì)算機(jī)的推動(dòng)下，最優(yōu)化理論與方法在經(jīng)濟(jì)計(jì)劃、工程設(shè)計(jì)、生產(chǎn) 管理、交通運(yùn)輸?shù)确矫娴玫搅藦V泛應(yīng)用，成為一門(mén)十分活躍的學(xué)科.嘰覲詿縲鐋囁偽純鉿錈。最優(yōu)化

20、問(wèn)題根據(jù)有無(wú)約束條件可分為約束和無(wú)約束最優(yōu)化問(wèn)題.現(xiàn)實(shí)生活中存 在的主要是有約束的問(wèn)題，但我們可以通過(guò)某些處理將有約束的問(wèn)題轉(zhuǎn)化為無(wú)約 束的問(wèn)題處理，并且無(wú)約束最優(yōu)化問(wèn)題的求解相對(duì)容易的多，而解法的基本思想又常?？梢酝茝V到一般有約束的情況，因此使得研究無(wú)約束最優(yōu)化問(wèn)題的計(jì)算方 法顯得尤為重要，人們對(duì)它的研究情況也十分重視.熒紿譏鉦鏌觶鷹緇機(jī)庫(kù)。對(duì)于無(wú)約束問(wèn)題min f (x), x Rn .(1.1 )的最優(yōu)性條件可以分為一階條件和二階條件.設(shè)f(x)的一階導(dǎo)數(shù)和二階導(dǎo)數(shù)存在，且分別表示為g(x)二 '、f (xGd)八2 f(x),則我們有以下定理.定理1.1( 一階必要條件)設(shè)f

21、: D Rn > R1寸R1在開(kāi)集； D上連續(xù)可微。若X： D (1 . 0)的局部極小點(diǎn)，貝Ug(x*) =0.定理1.2(二階必要條件)設(shè)f :Rn > R1在開(kāi)集X* D上二階連續(xù)可微，若x* D是(1 . O)的局部極小點(diǎn)，則g(x*) =O,G(x*) _0 .定理1.3(二階充分條件)設(shè)f :Rn > R1在開(kāi)集D上二階連續(xù)可微，則x*D是f的一個(gè)嚴(yán)格局部極小點(diǎn)充分條件是g(x ) = 0， G(x*)是正定矩陣.滿(mǎn)足g(x*)=O的點(diǎn)x*稱(chēng)為函數(shù)f的平穩(wěn)點(diǎn)或駐點(diǎn)，一般目標(biāo)函數(shù)的平穩(wěn)點(diǎn)不定是極小點(diǎn)，但若目標(biāo)函數(shù)是凸函數(shù)，則其平穩(wěn)點(diǎn)就是其極小點(diǎn)，且為總體極小 占八、

22、定理1.4 (凸充分性定理)設(shè)f : D Rn > R1是凸函數(shù)，且 f C1。則x*是總體極小點(diǎn)的充分必要條件是g(x*) =0.1.2收斂概念收斂速度是迭代方法的又一重要性質(zhì)。對(duì)于一個(gè)不可能在有限步內(nèi)找到最優(yōu) 解的最優(yōu)化方法，我們不僅要求它收斂，還要要求它有較快的收斂速度，這是因 為一個(gè)收斂很慢的方法往往需要很長(zhǎng)的時(shí)間才能得到滿(mǎn)足精度要求的最優(yōu)解的 近似。因而不是一個(gè)有效的方法。設(shè)向量序列x(k) Rn收斂于x*，定義誤差序列鶼漬螻偉閱劍鯫腎邏蘞。(k)39如果存在常數(shù)C和r使成立就說(shuō)序列x(k)以C為因子r階收斂于x*。最常見(jiàn)的為r=1和r=2的情形，當(dāng) r =1，0 C ：1時(shí)稱(chēng)

23、為線性收斂，這是的誤差序列具有以下性能:際呵e.1,如果C=0.5，則誤差序列依最簡(jiǎn)單的情形，在上式中取等號(hào)，設(shè)初始誤差為 為1，0.5，0.25，0.125, 0.0625，如果C =0.1，則誤差序列為1，0.1，0.01，0.001,，可以看出C越小，收斂越快。如果從同一初始點(diǎn)開(kāi)始，收斂快的算法可以用較少 的迭代次數(shù)達(dá)到預(yù)定的精度，而收斂慢的算法則需要較多的迭代次數(shù)才能得到相 同精度要求的點(diǎn)。 紂憂(yōu)蔣氳頑薟驅(qū)藥憫騖。當(dāng)r =1,C =0時(shí)，稱(chēng)序列X（k）超線性收斂于X*，超線性收斂是一種比線性收斂快的收斂，多數(shù)的最有化方法具有超線性收斂的特性，在上述收斂率的定義 中，所有r 1的收斂獨(dú)屬

24、于超線性收斂。事實(shí)上，由 穎芻莖峽餑億頓裊賠瀧。ek 1k_：:Xc-Jrkeee1-稱(chēng)r =2時(shí)的收斂為二次收斂，這時(shí)誤差序列的性能可以用下述不等式表示2d 1 _C ek -二次收斂是一種更快的收斂，還要考察上式取等式時(shí)的情形，設(shè)初始誤差為1，C =1,則誤差序列為1，0.01，0.0001，0.00000001,，可以看到，二次收斂的方法每一次迭代近似解得精度就增加一倍 一個(gè)理想的算法終止準(zhǔn)則為H.|l (k 十)v(k)|HX一x(k)*|llXx|-1然而由于X*是未知的，這樣的準(zhǔn)則并不具有任何實(shí)用價(jià)值。但是由于II (k_b*X-xX（宀-x（k）+x（k）-X*|(k)*II (

25、k)*|X-X卜_X|(k +)(k)(k)*|lX -x-Ilx 一X|II (k)*|HX一x|-0.在序列x(k)超線性收斂于x*時(shí)，我們可以得到(k(X上式表明對(duì)于一個(gè)超線性收斂的算法卜心-X畀|是|x(k)-X |的一個(gè)估計(jì)。因此對(duì)于超線性收斂速度的方法，(k 1)(k)X-X 八是一個(gè)比較合適的終止準(zhǔn)則。1.3Wolfe準(zhǔn)則和 Armijo準(zhǔn)則Wolfe準(zhǔn)則為f(xk akdQ 乞 f (xQ Skgldkg(Xk akdJTdk 一 丙®.其中,0：1。Armijo準(zhǔn)則為：1給定：(0,1)， - (0,-)，- 0，設(shè)mk是使得下述不等式A：f (Xk + P%dk)

26、蘭 f (Xk) + PP 叫g(shù)(xJTdk.( 1.2)成立的最小非負(fù)整數(shù)，令='叫。由于dk是下降方向，當(dāng)m充分大時(shí),不等式(1.2)總是成立的，因此上述mk總是存在的。由于mk是使得上述不等式成了的最小非負(fù)整數(shù)，因而:k不會(huì)太小，從而保證了目標(biāo)函數(shù)f(x)的充分下降，令 C )= f(x : dk)。實(shí)際上，不等式 (1.2就是充分下降條 件濫驂膽閉驟羥闈詔寢賻。(k)(0) L k '(0).( 1.3)如果上式滿(mǎn)足，則終止搜索，否則，我們可以縮小:k，或者在區(qū)間0, : k上用二次插值公式求近似極小點(diǎn)or(1.4 )廠4(0)魔a 一2(®k)®(

27、0)-叫O)Gk)將其作為一個(gè)新的:k 0第2章擬牛頓法算法設(shè)計(jì)2.1擬牛頓法條件考慮目標(biāo)函數(shù)f(x)在當(dāng)前點(diǎn)Xk處的二階模型1mk(d) = f(xO+g：d+dTBkd .( 2.1.)其中，Bk是n n對(duì)稱(chēng)正定矩陣，是 Hesse近似，它將在每次迭代中進(jìn)行校正。 極小化這個(gè)二次模型dk =-Bgk，( 2.2)從而新的迭代點(diǎn)為xk i 二 xk akdk 二 xk -akBkb .( 23)其中，ak是線性搜索步長(zhǎng)因子，上述迭代(2.3)稱(chēng)為擬牛頓迭代，他與牛頓迭 代的主要區(qū)別在于在(2.3)中我們用Hesse近似Bk代替了牛頓迭代中的 Hesse 矩陣Gk o銚銻縵嚌鰻鴻鋟謎諏涼。設(shè)f

28、 : Rn > R在開(kāi)集D Rn商二次連續(xù)可微，f (x)在xk .1附近的二次近似 為f(X)f(Xk 1)g：1(x-Xk 1) 1 t( 2.4)(x - Xk 1) Gk 1(x -Xk J2對(duì)上式兩邊求導(dǎo)，有g(shù)(x) : gk 1 Gk1(x-Xk 1) ，(2.5)令Sk二 Xk 1 -Xk, yk 二gk 1-gk(2.6)(2.6)成為Gk 何yk .(2.7)顯然，如果f（x）是正定二次函數(shù)，上述關(guān)系式（2.7）精確成立?，F(xiàn)在，我們要 求在擬牛頓法中構(gòu)造出來(lái)的 Hesse近似Bk 1滿(mǎn)足這種關(guān)系，從而得到 擠貼綬電麥結(jié)鈺（2.8）贖嘵類(lèi)。Bk 1Sk = yk上式稱(chēng)為擬

29、牛頓條件或擬牛頓方法。利用擬牛頓條件，我們可以得到BkSkSk BkSk Bk SkT yk yk Bk 1 = BkT_yk Sk上述公式成為BFGS校正公式（關(guān)于Bk）如果令Hk =Bk，則擬牛頓條件為Hk 必二 Sk，（ 2.9）擬牛頓迭代為Xk 1 二akkdk 二 Xk -akBkgk（2.10）或xk 1 = xk akdk = xk -akBk gk .（2.11）擬牛頓條件使二次模型具有如下插值性質(zhì)：如果Bk 1滿(mǎn)足擬牛頓條件（2.8），那么在Xk卅點(diǎn)的二次模型mk 1（x） = f（Xk J g：1（x-Xk1）1 t（ 2.12）（x - Xk J Bk 1（x-Xk J2

30、滿(mǎn)足mk 1（Xk 1）= f（Xk J' mk 1（Xk 1） = gkmk（Xk）二 gk.（2.13）上式中的第一、第二等式是顯然的，第三個(gè)等式是利用擬牛頓條件（2.8）得到的。2.2算法設(shè)計(jì)步 1.給出初始點(diǎn) X。 Rn，Bo （或 H0）- Rn n，:0,k =0。步2如果Igk ；，停止。步3解Bkd二gk，得搜索方向dk;（或計(jì)算dk二-HkgQ。步4.由wolfe準(zhǔn)則步長(zhǎng)因子ak，并令xk d = xk - akdk。步5是用BFGS校正公式校正Bk產(chǎn)生的（或校正Hk產(chǎn)生的H）,使得擬 牛頓條件（2.8）或（2.9）成立。步6.k k 1，轉(zhuǎn)步2。第3章收斂性證明3.

31、1總體收斂設(shè)x0是任意初始點(diǎn)，B0是對(duì)稱(chēng)正定矩陣的初始Hesse近似。假設(shè)3.1(a) f :Rn > R1在開(kāi)凸集D Rn上二次可微；(b) 水平集0 =xe Rn f(x)蘭f(x0)是凸的，存在正的常數(shù) m和M使得Hesse矩陣G(x)滿(mǎn)足2 2m ZztG(x)zM z ，一z Rn,xw ：. .(3.1)(c) 在x*的領(lǐng)域N(x*,；)內(nèi)，G(x)是Lipschitz連續(xù)的，即|g(x)G(x)| 蘭 L x-耳,Wx,xE N(x , e) .(3.2)上述假設(shè)條件(b)意味著Hesse矩陣G(x)式門(mén)上是正定的，f有唯一的極 小點(diǎn)x*。由Taylor定理，1g(Xk s

32、j 二 g(Xk) 0G(Xk sjd ,令1 1Gk = .0G(Xksjd =.0G(Xkakdjd，( 3.3)則yk 二 gk 1 gk 二 GkSk .(3.4)于是，利用(3.1)和(3.4)，有卒二-m .( 3.5)sk sksk sk1令 Zk - Gk 2sk，則Tyk SkSk 2*GkZk(3.6)注意矩陣A的跡trace (A)是A的對(duì)角元的和，也是 A的特征值的和，即nntrace(A)=、 a”，trace( A) _、；i£7(3.7)矩陣的行列式det (A)是A的特征值的乘積，即nd etAO ： | 丨；7(3.8)在下面的證明中，我們利用了這兩

33、個(gè)概念來(lái)估計(jì) Hesse近似的最大和最小特 征值的大小。定理3.2 設(shè)B。是任意初始對(duì)稱(chēng)正定矩陣，X。是初始點(diǎn)，使得假設(shè)3.1( a)(b)成立，則由算法3.1產(chǎn)生的序列xk收斂到f的極小點(diǎn)x* 。賠荊紳諮侖驟遼輩襪錈。證明 定義TykSk mk -Sk SkmkTyk ykTykSk(3.9)由(3.5)和(3.6)得(3.10)T由BFGS校正Bki二Bk 畢YkSkBkykykASk BkSk計(jì)算其跡和行列式，得T r a CBk -i) =T r a CQ _|BkSkJ|yk|Sk BkSkyk Sk(3.11)mk _ m， M k _ M .T(3.12)detBU "

34、etBU-Sk BkSk定義S _ Sk Bk SkCoSkCqkS BkSkT ，Sk Sk(3.13)這里A是Sk和BkSk之間的夾角，于是IBkskl2l|Bksk|sk|sk BkskqkT'Sk B.s.(sk Bk sk )|scok(3.14)又由(3.12) 和( 3.9),有TT(3.15)detBU "etBk)華 普detBk) .sk sk sk Bkskqk現(xiàn)在我們定義(3.16)' (B)二Trace(B) -1 n(det(B).其中l(wèi)n(*)表示自然對(duì)數(shù)。不難證明,'(B) 0。由(3.16), (3.12) (3.15),(B

35、kJ =TraCBk1) -ln(det(Bk)二T r a CBJ M kqkCOS2 vk-ln( det(Bk)-l ng lnqk(3.17)=' (Bk) (Mk -lnmk -1)1-2 ln2 lncoBk cos 日kcos 日k注意到對(duì)所有的t 0，h(t)=1-t lntO,上面方括號(hào)中的項(xiàng)是非正的，因而由(3.10),并反復(fù)利用(3.17), 得塤礙籟饈決穩(wěn)賽釙冊(cè)庫(kù)。k0 八(Bk 1) r (BJ ck 、Tncosj ,(3.18)jm其中 c = M -ln m -10。下面，我們利用Wolfe不精確線性搜索的總體收斂性定理證明結(jié)果。由于 Sk =akBgk

36、, BkSk =akgk，故 skks. = kafglBjgk =-akgkdk，這表 明由(3.13)定義的玉也是最速下降方向-gk和擬牛頓搜索方向d-Bgk之間 的夾角。于是，由于Wolfe不精確線性搜索的總體收斂性定理得 裊樣祕(mì)廬廂顫諺鍘羋藺。gk cosk > 0 .(3.19)為了證明lim inf gk =0，只要證明存在子序列kj，使得cosj-0假定coj > 0。則存在k1 0，使得對(duì)所有j k1，有(3.20)In c 0站：-2c.其中c = M -Inm 一1 .0是上面定義的常數(shù)。利用(3.18)得到:對(duì)所有k k,kik0 八(B) kc 'T

37、ncos2 j、 (_2c)j 土i 卅,、k( 3.21)2=(Bi) -二 Incosj 2kiC-kc.j4在(3.17 )中，第一項(xiàng)和第三項(xiàng)是正的，但有限，第二項(xiàng)小于零，第四項(xiàng)也小于零，且與k有關(guān)，故當(dāng)k充分大時(shí)，上式右邊是負(fù)的，從而給出矛盾。倉(cāng)嫗盤(pán)紲囑瓏詁鍬齊驚。(3.22)這矛盾表明存在子序列kJ，使得cosj _ 0，從而Lmnfg=0 .由假設(shè)3.1 (b),問(wèn)題是強(qiáng)凸的，這表明XkT x*上述定理證明了：采用Wolfe不精確線性搜索的BFGS擬牛頓算法是總體收 斂的。這個(gè)結(jié)果可推廣到所有 0,1)的Broyden族，即不包括DFP校正。綻萬(wàn)璉轆娛閬蟶鬮綰瀧。下面，我們研究BF

38、GS方法的局部超線性收斂。首先我們給出擬牛頓法超線 性收斂的充分必要條件。3.2局部超線性收斂定理3.3 設(shè)f : Rn，R，滿(mǎn)足假設(shè)3.1 (a) (b)成立。考慮迭代xk廠xk dk，dk =Bgk。設(shè) Xk收斂到解點(diǎn)x*。則當(dāng)且僅當(dāng)訕冒浮=0.宀dk(3.23)時(shí)，序列 xk超線性收斂到x證明 設(shè)擬牛頓步為dk =-Bgk，牛頓步為=-Ggk，由于G(x*)是正定 的，故當(dāng)Xk充分靠近x*時(shí)，Gk4是上有界的。我們先證明(3.23)等價(jià)于dk -d" =o(dk ) .(3.24)假定（3.1）成立，則(3.25)dk dk =GiT(Gkdk gk) 二Gk'(Gk

39、-Bk)dk=0( G -BJdk )=o( dk ).最后一個(gè)等式來(lái)自（3.23）反之，設(shè)（3.24）成立，則由Gk左乘以（3.24）兩邊，得Gkdk -Gkdo（dk）.（3.26）注意到-Gkd, =gk 二-Bkdk，從而（2.2.44）成為G-BJdk=o（|dk|）.此即（3.23）。下面，借助牛頓發(fā)的二次收斂性結(jié)果來(lái)完成證明。|dk|xk - / 乞 Xk dk x*乞 Xk dN -x*- dk d,=0（ Xk -x*| ） o dk."3.27）從上式易知|dk| =O（|xk -x*|），代入（3.27），得到IX十-x*| =|xk +dk -x*| =o|x

40、k -x*|這表明Xk是超線性收斂的。這個(gè)定理告訴我們?nèi)c(diǎn)：（1）超線性收斂的充要條件使（3.23）成立，即Bk只要沿搜索方向dk收斂到 Hesse矩陣G（x*），則擬牛頓法超線性收斂。驍顧燁鶚巰瀆蕪領(lǐng)鱺賻。（2）（3.24）也是擬牛頓法超線性收斂的充要條件，即當(dāng)且僅當(dāng)擬牛頓步dk在長(zhǎng)度和方向上都趨向于牛頓步dN，則擬牛頓法超線性收斂。瑣釙濺曖惲錕縞馭篩涼。如果將（3.23）用“m害凹 j lldd代替，定理仍然成立。這個(gè)定理是基本的和一般的，當(dāng)我們討論每個(gè)具體的擬牛頓法的超線性收斂性時(shí)，都要驗(yàn)證充要條件(3.23)。鎦詩(shī)涇艷損樓紲鯗餳類(lèi)。定理3.4設(shè)f : R“ ； Rn，滿(mǎn)足Xk 1 =

41、Xk - bJ f (Xk)，設(shè)Bk是非奇異矩陣序列。假定對(duì)某個(gè)D，由Xk 1 = Xk - akBk f (xk)，( 3.28)產(chǎn)生的序列Xk都在D中且收斂到X*。如果(2.23)成立，那么Xk超線性 收斂到X*且f (x*) =0的充要條件是ak收斂到1.證明 先假定 Xk超線性收斂到X*且f (x*) = 0。必有意- 1)Bk(Xk 1Hklimk_.aEf(x*) Xk) =0 ,Xk 1 -Xk|(3.29) Xk ) / Xk 卅一 X=0.由于Bk(Xk彳-兀)=-ak f(Xk)，故上式可寫(xiě)成km(a： -1)f 區(qū))|/収心-X=0 .(3.30)由于f '(x*

42、)非奇異。故存在:0，使得f(xj 一 ： Xk-x*，又因 Xk超線 性收斂。又有m_-Xk卞-xk / xk -x* =1，從而有(3.2.23)得ak收斂到1.下面我們進(jìn)一步闡述擬牛頓法超線性收斂的幾何意義。設(shè)Sk =兀4 - Xk，又該序列的牛頓校正為 S = -f (xk)J * f (xk)。由于 f (Xk)二-BkSk，則Sk=Sk f'(Xk)4f (Xk)二 f'(Xk)"f'(Xk) - Bk)Sk.因此lim:二0等價(jià)于Bk - f(X )( Xk 1 -Xk)Xk 1 _Xkl(3.31)上式表明當(dāng) Xk 超線性收斂時(shí)，Q作為sN的近

43、似向量，其對(duì)稱(chēng)誤差應(yīng)趨于零。容易證明這等價(jià)于要求Sk無(wú)論在長(zhǎng)度上還是方向上都趨向于 £。為此，我 們建立以下弓I理。櫛緶歐鋤棗鈕種鵑瑤錟。引理 3.5 設(shè)u , v e Rn , u , v 護(hù)0且口乏（0,1）。如果|u - 寸"|u|，則u ,v 為正且(3.32)反之，如果u,v為正且（3.32）成立，則u -v|3 |u .(3.33)證明首先假設(shè)|u - v _ U，則于是（3.32）中第一個(gè)不等式成立。記 =u,v/（|u|v），注意到u-v2-2u vv2_u2（1- ）這證明了（ 3.32）中第二個(gè)不等式。此外，若 0，則由上面的等式部分可知u-v“|u，從

44、而篇汽1。因此，若爲(wèi)”1，則必有VU ,v 為正。轡燁棟剛殮攬瑤麗鬮應(yīng)。反之，若u,v為正且（3.32）成立，則|u-v|2=（|uHM）2+2（i）MM "2忖21+2（1*）由于:-1，故得（3.33）。由這個(gè)引理可得，若（）成立，即對(duì)任意給定的（0,1），當(dāng)kko時(shí),NSk Sk根據(jù)引理3.5，應(yīng)有c sk,Sk »0且當(dāng)k>k）時(shí)有sN和N31( -Sk, Sk、2 .2Sk sN|)這表明(3.31)等價(jià)于鬧| .Sk sNlimlimN - 1.(3.34)k>：SkSk |sN從而我們有結(jié)論：擬牛頓法超線性收斂的充分必要條件是其位移 Sk在長(zhǎng)度和方

45、向上都漸進(jìn)的趨向于牛頓方向SkN。定理3.6設(shè)f : Rj R滿(mǎn)足假設(shè)條件3.1中的（a）和（b）,又設(shè)Bk為一 非奇異矩陣序列。假定對(duì)某X。，D，迭代序列Xki二Xk-akBk'gk產(chǎn)生的xk都在 D中且xk = x* （-k _0）。又設(shè)該序列收斂到x*。 ak由不精確線性搜索 Wolfe準(zhǔn)則 |Bk -燈2f（x*）sJ產(chǎn)生，若lim j1 =0成立，則當(dāng)k充分大時(shí)，ak =1，從而序列XkY|Sk超線性收斂至U x*。峴揚(yáng)爛滾澗輻灄興渙藺。證明 本定理要證明對(duì)于一切充分大的 k，Wolfe準(zhǔn)則成立，從而ak =1，余下的結(jié)果直接從定理3.3得到。由于Bksk二-akgk故由li

46、m.Bkf(x*)SkSki=0可彳得詩(shī)叁撻訥燼憂(yōu)毀厲鋨驁。所以gjBFgk -(Bkpk八 2f (x*)(BFgQ2* d T = (gk -' f (x )Bk gk) (Bk gk)=o( Bk1 g)glBFk =做©円2心*）何©）+0（|浄山）.（3.35）由于i 2f（x*）正定，故存在0，使得對(duì)于充分大的k,gkAFk B,gk【成立，從而有泰勒展式和（2.12）有心-Bk'gQ-f-gWgk 扣如七（皿如(3.36)乞-呵：Bgk其中；位于xk與Xk-Bkgk之間。又由泰勒展式可得g(Xk -BkgQT B/gk -glBfgk (Bgk

47、)T' 2f (x*)(BgQ=0( Bk gk )利用(3.36)，有1 T _1II _12t _1g(XkBkgQ Bkgk=o(|Bkgk )"gkBkgk(3.37)g(x -Bk4gk)TBk4g rgk'Bk'g由(3.36)和(3.37)可知 f(xk _Bk gk) ' f(xk)gkBk gk成立，從而對(duì)于充分大的k， ak =1第4章數(shù)值驗(yàn)算這里將給出6個(gè)例題用以驗(yàn)算算法的的可行性。在迭代過(guò)程中Armijo準(zhǔn)則中的參數(shù)= 0.4，匸=0.6。6個(gè)例題的數(shù)值結(jié)果將列表記錄。從這些結(jié)果中我們可以看到算法的可行性和有效性。則鯤愜韋瘓賈暉

48、園棟瀧4.1問(wèn)題模型問(wèn)題1yi 二1.5 -咅(1 - x2)2討2 二 2.25 - x(1 - X?)?2y3 2.625 -片(1 - x?)22 2min y 二 y1y2y3x R初始迭代點(diǎn)為Xo=1,1問(wèn)題22 2 2min y = 100(X2 - 為)(1 - xj初始迭代點(diǎn)為x°=-1.2 ,1問(wèn)題30.10-0.1x,丄q1x,-(e1-5e七e4)比=x3e 1 _ x4e 2 x6 e-0.2x1亠-0.2 x,丄亠-0.2x5-(ed2-5e2 七e8)y2 二花 e 1 _ % e 2x6e 5ye0.3x x ” e_0.3x'x ” e&quo

49、t;0.%5 "“3 不3 32)-0.4x-0.4x0.4x (e-0.4 -5e4 "3e丄6)y4 = x3e- x4e 灼e5-0.5x1亠-0.5程 丄亠-0.5x5-(ed'-ge5 七e2)y5 = x3e_ x4 exey6_0.6x1=x3 e _0.6x,-xe 骨x6 e_0.7為-0.7 x2y7=滄 e-x4ex6 e_0.8x1-0.8x2y二 X3e- ex6 e_0.9 X1亠.0.9x2y9* - e7 ex6 e_Q.6x5_(e26_5e6 3eZ4).0.8x5 _(e-.8 _5e8 3e22)_Q.7x5 _(e27 _5

50、e7 3e-2.8)_0.9x5 _(e-.9 _5e；3e-.6)y10 =E * e_x4 * e2+x6 * e仝-書(shū)e)yn n d"乜飛叫飛上化心®14）yi2_1.2Xi_1.2x2=x3e 1 - x4 e 2_1.2 x5 4e -12 _5e12 書(shū)e 48) x6eA.3x14.3x2,_1.3x -(3 -5e13 H3e -5;2 )%3 =X3e - X4e冷 e2丄 2丄 2丄 2丄 2丄丄 2丄 2丄 2min y 二 y1 N2紙牡 yn%2丫13 初始迭代點(diǎn)為x°=1,2,1,1,1,1(3.5 -O2(丄2 (33) 2問(wèn)題4y

51、12二 x1e2-0.00092y2 = x1e-0.0044(7(2.5 玉)2（丄2 （2 丄3）2y32=x1e2-0.01752y4 二"2-0.0540(心(1.5 丄3) 2(丄2(13) 2y52二 xe2-0.12952y6 ="-0.2420 (0.5 丄3)2（火（03）2y72=x1e2-0.35212討8 二"2-0.3989（和q5亠）2（丄2（f ）2y9=X1e2-0.3521ye = X1e2-0.2420(»2( 4.5 知)：2(»2( “3)2yn2-x1e2-0.12952%2 工 X©2-0.

52、0540(-2 ( 2.5 丄3 )2(f 3)2y132-x1e2-0.01752%4 二"2-0.0044(-2 ( 3.5 心3 ) 2y1x1e2- 0.00092 +2.2 +2 +2.2土 2+2miny1y2y3y4y5y6y7y82 2 2 2 2 2 2*y10yn%2%3%4%5初始迭代點(diǎn)x0=0.4,1,0問(wèn)題 5y1 =10(石-X；)y2 =1 F* =3,10(X4 -xf)y4 = 1 - X3y 10(x2 X4 -2)丫6 =丄卜2 - X4),10min y = y： y； yf y： yj y：初始迭代點(diǎn)為 Xo =-3,-1,-3,-119問(wèn)題6min y =(3 -2Xn)Xn -Xn1 ' (3 - 2Xn)Xn - Xn/ - 2Xn 1 1)n：4初始迭代點(diǎn)位 Xo=1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,14.