《最優(yōu)化方法》課程實(shí)施大綱

《最優(yōu)化方法》課程實(shí)施大綱目錄TOC\o"1-3"\h\u156641.教學(xué)理念 457592.課程介紹 4312583.教師簡介 4184034.先修課程 5243675．課程目標(biāo) 561456．課程內(nèi)容 5121207.課程實(shí)施 6107837.1教學(xué)單元一基本概念（10學(xué)時(shí)） 694287.2教學(xué)單元二線性規(guī)劃（12學(xué)時(shí)） 22110787.3教學(xué)單元三線性搜索與信賴域方法（14學(xué)時(shí)） 38197557.4教學(xué)單元四無約束最優(yōu)化方法（12學(xué)時(shí)） 67156097.5教學(xué)單元五最小二乘問題與二次規(guī)劃（6學(xué)時(shí)） 77198487.6教學(xué)單元六約束最優(yōu)化的理論與方法（4學(xué)時(shí)） 8368218．課程要求 9868849．課程考核方式及評分規(guī)程 993061010．學(xué)術(shù)誠信規(guī)定 991964211．課堂規(guī)范 991673312．課程資源 100974613．教學(xué)合約 1014932其他說明 1011.教學(xué)理念最優(yōu)化是從所有可能方案中選擇最合理的方案以達(dá)到最優(yōu)目標(biāo)的學(xué)科，是隨著計(jì)算機(jī)的普遍應(yīng)用而發(fā)展起來的，它已廣泛應(yīng)用于各個(gè)領(lǐng)域。通過這門課程的學(xué)習(xí)，使學(xué)生掌握整體優(yōu)化的基本思想，培養(yǎng)學(xué)生的邏輯思維能力和創(chuàng)新素質(zhì)；使學(xué)生掌握運(yùn)籌學(xué)的工作步驟，培養(yǎng)學(xué)生運(yùn)用模型和算法并借助計(jì)算機(jī)手段解決實(shí)際問題的能力；使學(xué)生了解本領(lǐng)域的發(fā)展動(dòng)態(tài)。

通過這門課程的學(xué)習(xí)，使學(xué)生獲得系統(tǒng)最優(yōu)化的基本知識、必要的基礎(chǔ)理論和常用的思維方式及運(yùn)算方法，培養(yǎng)學(xué)生的分析思維能力和比較熟練的運(yùn)算能力，為提高學(xué)生的基本素質(zhì)和后繼課程的學(xué)習(xí)以及進(jìn)一步擴(kuò)大應(yīng)用數(shù)學(xué)知識解決實(shí)際問題奠定良好的基礎(chǔ)。2.課程介紹最優(yōu)化方法是近代應(yīng)用數(shù)學(xué)的一個(gè)新的分支，廣泛應(yīng)用于工程技術(shù)、科學(xué)研究和經(jīng)濟(jì)管理等諸多領(lǐng)域。它主要研究在一定的限制條件下，對若干可供選擇的決策方案作出最滿意的決策去完成所要完成的任務(wù)。它的主要內(nèi)容就是尋求最滿意的決策的方法，建立這些方法所依據(jù)的理論以及如何在計(jì)算機(jī)上實(shí)現(xiàn)這些方法。本課程包含最優(yōu)化問題的總論和數(shù)學(xué)基礎(chǔ)、一維搜索法、常用無約束最優(yōu)化方法、常用約束最優(yōu)化方法以及最優(yōu)化程序設(shè)計(jì)的一般方法。 本課程從工程應(yīng)用角度出發(fā)，詳細(xì)介紹了各種常用最優(yōu)化方法及其理論基礎(chǔ)，結(jié)合實(shí)例具體介紹了從優(yōu)化數(shù)學(xué)模型的建立到優(yōu)化算法的形成，算法的程序?qū)崿F(xiàn)、算法的選擇及一些實(shí)際經(jīng)驗(yàn)與技巧。3.教師簡介4.先修課程數(shù)學(xué)分析（高等數(shù)學(xué)）高等代數(shù)（線性代數(shù)）數(shù)學(xué)實(shí)驗(yàn)5．課程目標(biāo)最優(yōu)化方法是近代應(yīng)用數(shù)學(xué)的一個(gè)新的分支，廣泛應(yīng)用于工程技術(shù)、科學(xué)研究和經(jīng)濟(jì)管理等諸多領(lǐng)域。它主要研究在一定的限制條件下，對若干可供選擇的決策方案作出最滿意的決策去完成所要完成的任務(wù)。它的主要內(nèi)容就是尋求最滿意的決策的方法，建立這些方法所依據(jù)的理論以及如何在計(jì)算機(jī)上實(shí)現(xiàn)這些方法。本課程包含最優(yōu)化問題的總論和數(shù)學(xué)基礎(chǔ)、一維搜索法、常用無約束最優(yōu)化方法、常用約束最優(yōu)化方法以及最優(yōu)化程序設(shè)計(jì)的一般方法。 本課程從工程應(yīng)用角度出發(fā)，詳細(xì)介紹了各種常用最優(yōu)化方法及其理論基礎(chǔ)，結(jié)合實(shí)例具體介紹了從優(yōu)化數(shù)學(xué)模型的建立到優(yōu)化算法的形成，算法的程序?qū)崿F(xiàn)、算法的選擇及一些實(shí)際經(jīng)驗(yàn)與技巧。本課程面向理工科大學(xué)試圖把最優(yōu)化技術(shù)與計(jì)算機(jī)技術(shù)結(jié)合起來融為一體，講授上突出對優(yōu)化模型的建立思想，優(yōu)化算法的形成過程，強(qiáng)調(diào)概念和方法的論述以及方法與應(yīng)用的有機(jī)結(jié)合。6．課程內(nèi)容第1章基本概念（10學(xué)時(shí)）最優(yōu)化問題簡介，主要講授優(yōu)化數(shù)學(xué)模型的建立，最優(yōu)化算法的一般形成思想以及迭代解法等。最優(yōu)化問題的數(shù)學(xué)基礎(chǔ)，主要講授優(yōu)化算法以及優(yōu)化理論所需要用到的數(shù)學(xué)基礎(chǔ)。凸集和凸函數(shù)，最優(yōu)性條件，最優(yōu)性方法概述第2章線性規(guī)劃（12學(xué)時(shí)）基本性質(zhì)，單純形方法，線性規(guī)劃的對偶與對偶單純形法，線性規(guī)劃的內(nèi)點(diǎn)算法。第3章線性搜索與信賴域方法（14學(xué)時(shí)）主要講授在尋優(yōu)的過程中如何確定最優(yōu)步長以及常用的幾種一維搜索算法的形成。線性搜索，0.618法和Fibonacci法，逐次插值逼近法，精確線性搜索方法的收斂性，不精確線性搜索方法，信賴域方法的思想和算法框架，信賴域方法的收斂性，解信賴域子問題。第4章無約束最優(yōu)化方法（12學(xué)時(shí)）常用無約束最優(yōu)化方法，主要講授無約束優(yōu)化算法中常用的幾種無約束算法的形成。最速下降法，牛頓法，共軛梯度法，擬牛頓法。第5章線性與非線性最小二乘問題（8學(xué)時(shí)）約束問題的最優(yōu)性條件，主要介紹約束優(yōu)化問題在最優(yōu)點(diǎn)應(yīng)滿足什么條件，反之滿足什么條件的點(diǎn)是最優(yōu)點(diǎn)。線性最小二乘問題的解法，非線性最小二乘的Gauss-Newton法，信賴域方法，對Gauss-Newton矩陣的擬牛頓修正。第6章二次規(guī)劃（4學(xué)時(shí)）研究二次規(guī)劃的理論與算法，二次規(guī)劃，等式約束二次規(guī)劃問題，凸二次規(guī)劃的有效集方法，小結(jié)。第7章約束最優(yōu)化的理論與方法（2學(xué)時(shí)）常用約束最優(yōu)化方法，本章介紹約束優(yōu)化問題的二種解法直接法和間接法。最優(yōu)化問題程序設(shè)計(jì)方法，本章介紹優(yōu)化模型建立的一般步驟、編程方法、算法選擇標(biāo)準(zhǔn)以及應(yīng)用實(shí)例。約束最優(yōu)化問題與最優(yōu)性條件，二次罰函數(shù)方法，內(nèi)點(diǎn)障礙罰函數(shù)法?？倧?fù)習(xí)2學(xué)時(shí)7.課程實(shí)施7.1教學(xué)單元一基本概念（10學(xué)時(shí)）教學(xué)目標(biāo)（1）了解最優(yōu)化問題的模型及分類；了解最優(yōu)化的基本術(shù)語。（2）理解最優(yōu)化的概念；掌握經(jīng)典最優(yōu)化中兩種類型的問題--無約束極值問題、具有等式約束的極值問題的求解方法；（3）掌握向量函數(shù)微分學(xué)的有關(guān)知識；（4）理解凸集的概念并掌握其性質(zhì)；理解凸函數(shù)的概念及性質(zhì)，掌握凸函數(shù)的判別方法；理解凸規(guī)劃的概念及基本性質(zhì)。（5）理解無約束最優(yōu)化問題的最優(yōu)性條件；理解不等式約束最優(yōu)化問題的最優(yōu)性條件；（6）了解下降迭代算法的基本格式；了解迭代算法收斂性與收斂速度的概念；了解迭代算法的實(shí)用終止準(zhǔn)則。教學(xué)內(nèi)容最優(yōu)化問題簡介，主要講授優(yōu)化數(shù)學(xué)模型的建立，最優(yōu)化算法的一般形成思想以及迭代解法等。最優(yōu)化問題的數(shù)學(xué)基礎(chǔ)，主要講授優(yōu)化算法以及優(yōu)化理論所需要用到的數(shù)學(xué)基礎(chǔ)。凸集和凸函數(shù)，最優(yōu)性條件，最優(yōu)性方法概述。教學(xué)重點(diǎn)及難點(diǎn)：（1）教學(xué)重點(diǎn)：向量函數(shù)微分學(xué)的有關(guān)知識。凸規(guī)劃的基本性質(zhì)。無約束最優(yōu)化問題的最優(yōu)性條件。下降迭代算法的基本格式。（2）教學(xué)難點(diǎn)：向量函數(shù)微分學(xué)的有關(guān)知識。一般約束最優(yōu)化問題的最優(yōu)性條件。下降迭代算法的基本格式。教學(xué)方法本單元主要采用任務(wù)驅(qū)動(dòng)和程序式思維相結(jié)合的教學(xué)方法，過程當(dāng)中輔以案例講解、啟發(fā)提問、自主學(xué)習(xí)和協(xié)作學(xué)習(xí)等方式。任務(wù)驅(qū)動(dòng)是實(shí)現(xiàn)本課教學(xué)目標(biāo)和完成教學(xué)內(nèi)容的主要方法，任務(wù)是師生活動(dòng)內(nèi)容的核心，在教學(xué)過程中，任務(wù)驅(qū)動(dòng)被多次利用。自主學(xué)習(xí)能提高學(xué)生的自主探究能力，競賽和協(xié)作學(xué)習(xí)調(diào)動(dòng)學(xué)生的積極性，激發(fā)學(xué)生參與的熱情。學(xué)生之間互幫互助，共同分享勞動(dòng)果實(shí)，從而激發(fā)了學(xué)生的團(tuán)隊(duì)意識，達(dá)到理想的教學(xué)效果。

教學(xué)過程第一講最優(yōu)化問題簡介最優(yōu)化問題的一般形式給定目標(biāo)函數(shù)，滿足不等式約束及等式約束，記為：，其中滿足所有約束的向量稱為容許解或容許點(diǎn)，容許點(diǎn)集合稱為容許集。從最優(yōu)化問題的一般形式可以看出，最優(yōu)化要解決的問題就是在容許集中找一點(diǎn)，使目標(biāo)函數(shù)，在該點(diǎn)取極小。這樣稱為問題的最優(yōu)點(diǎn)，而相應(yīng)的目標(biāo)函數(shù)值稱為最優(yōu)值。2.最優(yōu)化問題分類最優(yōu)化問題可分為靜態(tài)問題和動(dòng)態(tài)問題兩大類，本書只討論靜態(tài)問題。靜態(tài)最優(yōu)化問題又可分為無約束問題和約束問題兩類。例：求Rosenbrock函數(shù)大極小點(diǎn)，即。這是一個(gè)無約束二維問題。例：求優(yōu)化問題的最優(yōu)解。這是一個(gè)約束最優(yōu)化問題。無約束問題又可分為一維問題及n維問題，求解一維問題的方法稱為一維搜索或直線搜索，在最優(yōu)化方法中起著十分重要的作用，故單獨(dú)列出。約束問題又分為線性規(guī)劃和非線性規(guī)劃。第二講預(yù)備知識1.二次函數(shù)1)二次函數(shù)的一般形它的矩陣形式是其中,這里是對稱矩陣。我們稱特殊的二次函數(shù)為二次型。（無一次項(xiàng)和常數(shù)項(xiàng)）2)正定矩陣設(shè)是階對稱矩陣。若且時(shí)都有，則稱矩陣是正定的；若都有，則稱矩陣是半正定的；若且時(shí)都有，則稱矩陣是負(fù)定的。若都有，則稱矩陣是半負(fù)定的。一個(gè)對稱矩陣是不是正定的，可用sylvester定理判定，該定理內(nèi)容是。一個(gè)階對稱矩陣是正定矩陣的充分必要條件是，矩陣的各階主子式都是正的。3)二次函數(shù)的最優(yōu)解析解如矩陣是正定矩陣，的等值面是同心橢球面族。其中心是，還可證明恰是二次目標(biāo)函數(shù)的唯一極小點(diǎn)。綜上所述，對于二次目標(biāo)函數(shù)有有效的求極小點(diǎn)的算法。該算法也可用于一般目標(biāo)函數(shù)小范圍內(nèi)的最優(yōu)解搜尋，即當(dāng)搜索區(qū)域位于最優(yōu)點(diǎn)附近時(shí)，該方法是一種有效算法。最優(yōu)化理論中判定一個(gè)算法的好壞標(biāo)準(zhǔn)之一，就是把該算法用于為正定的二次目標(biāo)函數(shù)，如果能迅速地找到極小點(diǎn)，那就是好的算法；否則就是不好的或不太好的算法。特別地，當(dāng)把一個(gè)算法應(yīng)用于為正定的二次目標(biāo)函數(shù)時(shí)，如果在有限步內(nèi)就能求出極小點(diǎn)來，那么這種算法稱為二次收斂算法，或具有二次收斂性。2.梯度與Hessian矩陣1)多元函數(shù)的可微性與梯度定義1:對于函數(shù)，如果存在n維向量，對于任意n維向量,有：，則稱在處可微。顯而易見，如在處可微，則有：實(shí)際上就是的偏導(dǎo)數(shù)向量證明如下：令；取，其中是無窮小變量，是第個(gè)坐標(biāo)軸上的單位向量，即：定義2:以的n個(gè)偏導(dǎo)數(shù)為分量的向量稱為在處的梯度，記為因此，這個(gè)公式與一元函數(shù)的Taylor展開式是相對應(yīng)的。2)方向?qū)?shù)定義:設(shè)是定義在中區(qū)域上的實(shí)值函數(shù)，在點(diǎn)處可微，是固定不變的常量，是方向上的單位向量，則稱極限為函數(shù)在點(diǎn)處沿方向的方向?qū)?shù)。若，則從出發(fā)在其附近沿方向是下降的。若，則從出發(fā)在其附近沿方向是上升。事實(shí)上，若，則當(dāng)且充分小時(shí)，必有，即，即是下降的。同理可說明，若，是上升的。定理：設(shè)是定義在中區(qū)域上的實(shí)值函數(shù)，在點(diǎn)處可微，則，其中是方向的單位向量。證明：因?yàn)橥普摚喝?，則方向是函數(shù)在點(diǎn)處的下降方向；若，則方向是函數(shù)在點(diǎn)處的上升方向；方向?qū)?shù)的正負(fù)決定了函數(shù)的升降，其絕對值的大小決定函數(shù)值升降的快慢。絕對值越大，升降的速度就越快。3)最速下降方向其中是梯度與方向的夾角。因此，函數(shù)負(fù)梯度方向就是函數(shù)的最速下降方向。4)梯度的性質(zhì)①函數(shù)在某點(diǎn)的梯度若不為零，則必與過該點(diǎn)的等值面垂直。②梯度方向是函數(shù)具有最大變化率的方向。③若，則，即④⑤⑥5)Hessian矩陣(1)向量值函數(shù)的導(dǎo)數(shù)設(shè)是定義在中區(qū)域上的向量值函數(shù),如果的所有分量在點(diǎn)都可微，那么向量值函數(shù)在點(diǎn)處稱為可微。若在點(diǎn)處可微，則對于任意的n維向量都有因?yàn)橄蛄康臉O限是通過它所有分量的極限來定義的，所以上式等價(jià)于其中稱為函數(shù)在點(diǎn)處的導(dǎo)數(shù)。也稱函數(shù)在點(diǎn)處的Jacobi矩陣。設(shè)，并且，其中是n元函數(shù)，假定它具有二階連續(xù)偏導(dǎo)數(shù)。則：在微積分中已經(jīng)證明過，當(dāng)?shù)乃卸A偏導(dǎo)數(shù)連續(xù)時(shí)，有，在這種情況下，Hessen矩陣是對稱的。(2)幾個(gè)特殊向量的導(dǎo)數(shù)①,其中是分量全為常數(shù)的維向量，是階零矩陣。②，③3)的一二階導(dǎo)數(shù)設(shè)5.多元函數(shù)的Taylor展開式定理:設(shè)是定義在中區(qū)域上的實(shí)值函數(shù)，具有二階連續(xù)偏導(dǎo)數(shù)，則：其中，而證明：設(shè)，于是按一元函數(shù)Taylor展開定理把在點(diǎn)展開，得到，其中。，因此，因此代入上式，即得證。多元函數(shù)的Taylor展開式還可寫為：6.極小點(diǎn)及其判定條件1)基本定義鄰域定義：對于任意給定的實(shí)數(shù),滿足不等式的的x的集合稱為點(diǎn)的鄰域，記為非嚴(yán)格局部極小點(diǎn)：設(shè)，若存在點(diǎn)和數(shù)，都有，則稱為的非嚴(yán)格局部極小點(diǎn)。嚴(yán)格局部極小點(diǎn)：：設(shè)，若存在點(diǎn)和數(shù)，但都有，則稱為的嚴(yán)格局部極小點(diǎn)。非嚴(yán)格全局極小點(diǎn)：設(shè)，若存在點(diǎn)和數(shù)，都有，則稱為的非嚴(yán)格全局極小點(diǎn)。嚴(yán)格全局極小點(diǎn)：設(shè)，若存在點(diǎn)和數(shù)，都有，則稱為的嚴(yán)格全局極小點(diǎn)。在求解最優(yōu)化問題時(shí)，要求求取全局極小點(diǎn)，可先求出所有的局部極小點(diǎn)，再求全局極小點(diǎn)。2)局部極小點(diǎn)的判定條件定理1:設(shè)具有連續(xù)的一階偏導(dǎo)數(shù)。若是的局部極小點(diǎn)并且是D的內(nèi)點(diǎn)，則。該條件僅僅是必要的，而不是充分的。定義:設(shè)，是D的內(nèi)點(diǎn)。若，則稱為的駐點(diǎn)。定理2:設(shè)具有連續(xù)的二階偏導(dǎo)數(shù)，是D的內(nèi)點(diǎn)。若并且是正定的，則是的嚴(yán)格局部極小點(diǎn)。一般說來，這個(gè)定理僅具有理論意義。因?yàn)閷τ趶?fù)雜的目標(biāo)函數(shù)，Hesse矩陣不易求得，它的正定性就更難判定了。論斷1:對于具有對稱正定矩陣二次函數(shù)，是它唯一的極小點(diǎn)7.下降迭代算法及其收斂性迭代算法的必要性：求解的問題可轉(zhuǎn)化為，一般地，這是一個(gè)非線性方程組，與原問題同等困難，為了避開這一難題，可對原有問題直接采用迭代法。1)下降迭代算法首先給定目標(biāo)函數(shù)的極小點(diǎn)一個(gè)初始估計(jì)點(diǎn)，然后按一定的規(guī)則產(chǎn)生一個(gè)序列，這種規(guī)則通常稱為迭代算法。2)降迭代算法的收斂性如果迭代算法產(chǎn)生的序列的極限恰好是函數(shù)的極小點(diǎn)，稱迭代算法產(chǎn)生的序列收斂于。3)迭代過程①選定初始點(diǎn)，置。②按某種規(guī)則確定搜索方向，使得。③按某種規(guī)則確定搜索步長，使得④計(jì)算⑤若滿足終止準(zhǔn)則，停機(jī)，否則置，轉(zhuǎn)②。4)迭代法中直線搜索求一元函數(shù)極小點(diǎn)的迭代法稱為直線搜索或一維搜索，即。記為，表示從點(diǎn)出發(fā)沿方向?qū)δ繕?biāo)函數(shù)作直線搜索得到的極小點(diǎn)是。定理：若目標(biāo)函數(shù)具有連續(xù)的偏導(dǎo)數(shù)，并且設(shè)，則。這個(gè)定理表明，梯度必與搜索方向正交。5)收斂速度定義1:對收斂于解的序列，若存在一個(gè)與無關(guān)的數(shù)，當(dāng)從某個(gè)開始使下式成立：則稱序列為線性(或一階)收斂。定義2:對收斂于解的序列，若存在一個(gè)與無關(guān)的數(shù)和，當(dāng)從某個(gè)開始使下式成立：則稱序列收斂的階為，或稱階收斂。當(dāng)時(shí)，稱為二階收斂。當(dāng)時(shí)，稱為超線性收斂。一般說來，線性收斂是比較慢的，而二階收斂則是很快的，超線性收斂居中，如果一個(gè)算法具有超線性以上的收斂速度，我們就認(rèn)為它是一個(gè)很好的算法了。6)計(jì)算終止準(zhǔn)則&&&&第三講凸函數(shù)與凸規(guī)劃一、凸集1.凸集的定義：一個(gè)n維向量空間的點(diǎn)集中任意兩點(diǎn)的連線仍屬于這個(gè)集合，即對，有則稱該點(diǎn)集為凸集。2.凸集的性質(zhì)：（1）凸集的交集仍是凸集；（2）數(shù)乘凸集仍是凸集；（3）凸集的和集仍是凸集特別規(guī)定，空集是凸集。3.超平面：設(shè)且，則集合稱為中的超平面，稱為該超平面的法向量，即；（是凸集）半空間：集合稱為中的一個(gè)半空間。超球：。4.凸組合：設(shè)為中的個(gè)點(diǎn)，若存在且，使得則稱為的凸組合。若均為正，則稱為嚴(yán)格凸組合。5.頂點(diǎn)（或極點(diǎn)）：設(shè)是凸集，，若不能用內(nèi)不同兩點(diǎn)和的凸組合表示，即，則稱為的頂點(diǎn)。二、凸函數(shù)凸函數(shù)：設(shè)，是凸集，若對及，都有則稱為凸集上的凸函數(shù)；若則稱為凸集上的嚴(yán)格凸函數(shù)。類似有凹函數(shù)的定義。2.幾何意義：函數(shù)圖形上連接任意兩點(diǎn)的線段處處都在函數(shù)圖形的上方。3.性質(zhì)性質(zhì)1：為凸集上的凸函數(shù)，，則也為上的凸函數(shù)。性質(zhì)2：兩個(gè)凸函數(shù)的和仍是凸函數(shù)。推論1：凸集上有限個(gè)凸函數(shù)的非負(fù)線性組合仍為上的凸函數(shù)。性質(zhì)3：若為凸集上的凸函數(shù)，則對，的水平集是凸集。性質(zhì)4：為凸集上的凹函數(shù)為凸集上的凸函數(shù)。4.凸函數(shù)的充分必要條件定理1（一階條件）設(shè)可微，是凸集，則（1）為凸函數(shù)對，恒有（2）為嚴(yán)格凸函數(shù)對，恒有定理2（二階條件）設(shè)具有二階連續(xù)偏導(dǎo)數(shù)，為開凸集，則（1）在內(nèi)為凸函數(shù)對，是半正定的；（2）若正定，則在內(nèi)為嚴(yán)格凸函數(shù)。特殊地，元二次函數(shù)為（為對稱矩陣）；若正定，則稱為正定二次函數(shù)。性質(zhì)：正定二次函數(shù)是嚴(yán)格凸函數(shù)。（因?yàn)椋?.凸函數(shù)的極值凸規(guī)劃問題：非空凸集上的凸函數(shù)的極小化問題。定理3設(shè)為凸集上的凸函數(shù)，則（1）的任一局部極小點(diǎn)為全局極小點(diǎn)；（2）若可微，且存在，使，則為在上的全局極小點(diǎn)；（3）若為嚴(yán)格凸函數(shù)，且全局極小點(diǎn)存在，則必唯一。注：關(guān)于凸函數(shù)的極值的性質(zhì)（即定理3）即是凸規(guī)劃問題的性質(zhì)第四講最優(yōu)性條件基本概念1.點(diǎn)的鄰域：2.局部極小點(diǎn)：設(shè).若存在點(diǎn)和數(shù)，對都有，則稱為在上的（非嚴(yán)格）局部極小點(diǎn)；若（），則稱為在上的嚴(yán)格局部極小點(diǎn)。全局極小點(diǎn)：設(shè).若存在點(diǎn)，對于都有，則稱為在上的（非嚴(yán)格）全局極小點(diǎn)；若（），則稱為在上的嚴(yán)格全局極小點(diǎn)。性質(zhì)：全局極小點(diǎn)必是局部極小點(diǎn)；但局部極小點(diǎn)不一定是全局極小點(diǎn)。類似有極大點(diǎn)的概念。因，本書主要給出極小問題。駐點(diǎn)：設(shè)可微，，若，則稱點(diǎn)為的駐點(diǎn)或臨界點(diǎn)。極值的條件定理1（一階必要條件）設(shè)具有一階連續(xù)偏導(dǎo)數(shù)，是的內(nèi)點(diǎn)，若是的局部極小點(diǎn)，則定理2（二階必要條件）設(shè)具有二階連續(xù)偏導(dǎo)數(shù)，若是的內(nèi)點(diǎn)且為的局部極小點(diǎn)，則是半正定的，即對恒有例定理3（二階充分條件）設(shè)具有二階連續(xù)偏導(dǎo)數(shù)，為的內(nèi)點(diǎn)，且，若正定，則為的嚴(yán)格局部極小點(diǎn)。第五講最優(yōu)化方法該素1.下降迭代算法的步驟（1）選擇一個(gè)初始點(diǎn)，令k：=0（2）檢驗(yàn)是否最優(yōu)？若是，則停止迭代；若不是，則（3）確定一個(gè)下降方向：存在，對，使得（4）從點(diǎn)出發(fā)，沿方向進(jìn)行直線搜索（一維搜索），即求步長使（5）計(jì)算，令k：=k+1，轉(zhuǎn)（2）2.直線搜索及其性質(zhì)（1）簡記：表示從點(diǎn)出發(fā)，沿方向進(jìn)行直線搜索，得到極小點(diǎn)。（2）定理：設(shè)目標(biāo)函數(shù)具有一階連續(xù)偏導(dǎo)數(shù)，若，則證明：（反正法）設(shè)，則1），此時(shí)是點(diǎn)的下降方向；2），此時(shí)是點(diǎn)的下降方向；與矛盾。3.收斂速度定義1：設(shè)序列是線性賦范空間中的點(diǎn)列，，若則稱序列收斂于，記為。定義2：設(shè)向量函數(shù)，，若當(dāng)時(shí)，總有，則稱在點(diǎn)連續(xù)；若在內(nèi)每一點(diǎn)都連續(xù)，則稱在內(nèi)連續(xù)。特別地，m=1時(shí)，為數(shù)量函數(shù)，則定義3：設(shè)序列收斂于，若存在與無關(guān)的數(shù)和，使得當(dāng)從某個(gè)開始，都有則稱序列收斂的階為，或?yàn)殡A收斂。當(dāng)，且時(shí)，稱線性收斂或一階收斂；當(dāng)時(shí)，稱二階收斂；當(dāng)時(shí)，稱超線性收斂。4.計(jì)算終止準(zhǔn)則計(jì)算終止準(zhǔn)則根據(jù)相繼兩次迭代的結(jié)果根據(jù)相繼兩次迭代的絕對誤差（不常用），b.根據(jù)相繼兩次迭代的相對誤差，c.根據(jù)目標(biāo)函數(shù)梯度的模足夠小為給定的足夠小的正數(shù)。以上準(zhǔn)則統(tǒng)稱為Himmelblau計(jì)算終止準(zhǔn)則，簡稱H終止準(zhǔn)則。作業(yè)：1.設(shè)目標(biāo)函數(shù)為其中為對稱正定陣。試證：從任意點(diǎn)(但)出發(fā)沿的方向?qū)ψ髦本€搜索所得的極小點(diǎn)恰是的極小點(diǎn)，而且最優(yōu)步長因子等于1。2.設(shè)在點(diǎn)處可微，并設(shè)是中線性無關(guān)向量組，試證：若，則。問這是否意味著是的局部極小。3.習(xí)題一：1,4,5,9,10,12,15,187.2教學(xué)單元二線性規(guī)劃（12學(xué)時(shí)）教學(xué)目標(biāo)（1）理解線性規(guī)劃的基本理論；（2）掌握線性規(guī)劃的單純形法；（3）理解線性規(guī)劃的對偶理論；（4）掌握線性規(guī)劃的對偶單純形法。教學(xué)內(nèi)容（1）線性規(guī)劃的基本理論；（2）線性規(guī)劃的單純形法；（3）線性規(guī)劃的對偶理論；（4）線性規(guī)劃的對偶單純形法。教學(xué)重點(diǎn)及難點(diǎn)：（1）教學(xué)重點(diǎn)：線性規(guī)劃的單純形法。（2）教學(xué)難點(diǎn)：線性規(guī)劃的對偶單純形法。教學(xué)方法本單元的教學(xué)主要包括課堂講授，學(xué)生自學(xué)，課堂討論、習(xí)題課，課外作業(yè)、輔導(dǎo)答疑等教學(xué)環(huán)節(jié)。通過各個(gè)教學(xué)環(huán)節(jié)的教學(xué)，重點(diǎn)培養(yǎng)學(xué)生的自學(xué)能力、動(dòng)手能力、創(chuàng)新能力、分析問題與解決問題的能力。提倡探索和推行研究性教學(xué)，通過啟發(fā)式教學(xué)、問題式教學(xué)、討論式教學(xué)等教學(xué)方法和合作式學(xué)習(xí)方式，積極引導(dǎo)學(xué)生進(jìn)行研究性學(xué)習(xí)。教學(xué)過程第一講線性規(guī)劃的基本性質(zhì)一、線性規(guī)劃的標(biāo)準(zhǔn)型繁寫形式：s.t.其中，（否則，等式兩端同乘以“-1”）?？s寫形式：s.t.向量形式：s.t.其中，，，，。矩陣形式：s.t.其中，：約束條件的系數(shù)矩陣，，，一般地，；：限定向量，一般地，；：價(jià)值向量；：決策向量，；通常，，為已知，未知。二、任一模型化為標(biāo)準(zhǔn)型1.極大化目標(biāo)函數(shù)：令，則問題轉(zhuǎn)化為約束條件為不等式若約束為“”型，則“左端+松弛變量=右端”（松弛變量0）如：，引入松弛變量，化為若約束為“”型，則“左端-剩余變量=右端”（剩余變量0）如：，引入剩余變量，化為若存在無非負(fù)要求的變量（稱為自由變量）令，其中，，代入目標(biāo)函數(shù)及約束條件即可。某變量有上、下界若，即，令，有。用代替即可。若，即，令，有。用代替即可。三、基本概念標(biāo)準(zhǔn)型（LP）：s.t.可行解（容許解）：滿足約束（2）、（3）的解。最優(yōu)解：滿足（1）的容許解?；涸O(shè)的秩為，若是中的階可逆矩陣，稱是線性規(guī)劃問題（LP）的一個(gè)基。若基是單位矩陣稱為標(biāo)準(zhǔn)基?；蛄浚夯械囊涣校ǎ┘礊橐粋€(gè)基向量。（共個(gè)）非基向量：基之外的一列（）即為一個(gè)非基向量。（共個(gè)）基變量：與基向量相應(yīng)的變量。（共個(gè)）非基變量：與非基向量相應(yīng)的變量。（共個(gè)）基本解：令所有非基變量為0，求出的滿足約束（2）的解?；救菰S解：滿足約束（3）的基本解。最優(yōu)基本容許解：滿足約束（1）的基本容許解。容許基：若是基，且存在關(guān)于的基本容許解，稱是容許基。若容許基是單位矩陣稱為標(biāo)準(zhǔn)容許基。非容許基：退化的基本解：若基本解中有基變量為0的基本解。退化的基本容許解：退化的最優(yōu)基本容許解：四、線性規(guī)劃問題的基本定理定理1若線性規(guī)劃問題存在容許域，則其容許域是凸集（也是凸多面體）。定理2線性規(guī)劃問題的基本容許解對應(yīng)于容許域的頂點(diǎn)。定理3若線性規(guī)劃問題存在有限最優(yōu)解，則其目標(biāo)函數(shù)最優(yōu)值一定可以在容許域的頂點(diǎn)達(dá)到。第二講單純形法一、單純形法原理單純形法的基本思路：根據(jù)問題的標(biāo)準(zhǔn)型，從容許域的一個(gè)基本容許解（一個(gè)頂點(diǎn)）開始，轉(zhuǎn)移到另一個(gè)基本容許解（頂點(diǎn)），并且使目標(biāo)函數(shù)值逐步下降；當(dāng)目標(biāo)函數(shù)達(dá)到最小值時(shí)，問題就得到了最優(yōu)解。二、單純形法的步驟（以“大M法”為例）數(shù)學(xué)描述例（大M法）：s.t.1.構(gòu)造初始容許基初始容許基是一個(gè)單位矩陣，它相應(yīng)的基本解是容許的，即標(biāo)準(zhǔn)容許基。1o引入附加變量，把數(shù)學(xué)模型化為標(biāo)準(zhǔn)型。2o若約束條件中附加變量系數(shù)為“-1”，或原約束即為等式，則一般須引入人工變量。3o目標(biāo)函數(shù)中，附加變量系數(shù)為0，而人工變量系數(shù)為M（很大的正數(shù)）。人工變量系數(shù)為大M：只要人工變量>0，使前后約束條件不等價(jià)，但由于目標(biāo)函數(shù)的修改，同時(shí)也使所求的目標(biāo)函數(shù)最小值是一個(gè)很大的數(shù)，也是對“篡改”約束條件的一種懲罰，因此，M叫做罰因子，大M法也叫做罰函數(shù)法。若對極大化問題，目標(biāo)函數(shù)中人工變量系數(shù)為（-M）。得到如下標(biāo)準(zhǔn)型：s.t.其中，表示基變量；表示非基變量。2.求出一個(gè)基本容許解1o用非基變量表示基變量和目標(biāo)函數(shù)。用非基變量表示基變量，即有用非基變量表示目標(biāo)函數(shù)，即其中，，而稱為非基變量的檢驗(yàn)數(shù)。上式中，規(guī)定各基變量的檢驗(yàn)數(shù)為0。其中，是基變量的價(jià)值系數(shù)，隨基的改變而改變。2o求出一個(gè)基本容許解及相應(yīng)的目標(biāo)函數(shù)值。令非基變量=0即得初始基本容許解：，初始目標(biāo)函數(shù)值：3.最優(yōu)性檢驗(yàn)1o檢驗(yàn)數(shù)：目標(biāo)函數(shù)式中，各非基變量的系數(shù)，即稱為各非基變量的檢驗(yàn)數(shù)。2o最優(yōu)解判別定理：若在極小化問題中，對于某個(gè)基本容許解，所有檢驗(yàn)數(shù)，且人工變量為0，則該基本容許解是最優(yōu)解。3o無窮多最優(yōu)解判別定理：若在極小化問題中，對于某個(gè)基本容許解，所有檢驗(yàn)數(shù)，又存在某個(gè)非基變量的檢驗(yàn)數(shù)為0，且人工變量為0，則該線性規(guī)劃問題有無窮多最優(yōu)解。4o無容許解判別定理：若在極小化問題中，對于某個(gè)基本容許解，所有檢驗(yàn)數(shù)，但人工變量不為0，則該線性規(guī)劃問題無容許解。4.基變換1o基本容許解的改進(jìn)定理：已知一個(gè)非退化的基本容許解具有目標(biāo)函數(shù)值，設(shè)某一個(gè)非基變量，其，則存在一個(gè)可行解具有目標(biāo)函數(shù)值；如果用代替原基中的某一列向量而產(chǎn)生一個(gè)新的基本容許解，則該新的解將有。2o換入變量的確定為換入變量，使。3o換出變量的確定——最小非負(fù)比值規(guī)則為換出變量，使4o無有限最優(yōu)解判別定理：若在極小化問題中，對于某個(gè)基本容許解，有一個(gè)非基變量的檢驗(yàn)數(shù)，但列中沒有正元素，且人工變量為0，則該線性規(guī)劃問題無有限最優(yōu)解。5.單純形法的矩陣描述標(biāo)準(zhǔn)型（LP）：s.t.其中，，，，基矩陣滿秩，非基矩陣，，，.則有s.t.基本容許解：（2）左乘得（4）目標(biāo)函數(shù)值：（4）代入（1）得（5）非基變量的檢驗(yàn)數(shù)向量：令，由（4）、（5）得這里，稱為單純形乘子。三、單純形法的表格形式1．構(gòu)造初始可行基，并計(jì)算檢驗(yàn)數(shù)2．從表中找出基本可行解和相應(yīng)的目標(biāo)函數(shù)值3．最優(yōu)性檢驗(yàn)4．基變換1o換入變量的確定2o換出變量的確定3o主元素的確定單純形表中，換入變量所在的列和換出變量所在的行交叉處的元素為主元素（即），標(biāo)“*”號。4o取主變換（基變換）即單純形法的一次迭代。在表中以主元素進(jìn)行旋轉(zhuǎn)變換（高斯消去法），把所對應(yīng)的列向量于是得到新一輪的單純形表。四、單純形法解極大化和極小化問題的區(qū)別原模型目標(biāo)函數(shù)標(biāo)準(zhǔn)型最優(yōu)性檢驗(yàn)換入變量的確定目標(biāo)函數(shù)中人工變量系數(shù)為大M所有，且人工變量為0目標(biāo)函數(shù)中人工變量系數(shù)為“-M”所有，且人工變量為0五、兩階段法1.第一階段：判斷原線性規(guī)劃問題是否有容許解。先求解以下線性規(guī)劃（人工變量之和）s.t.用單純形法對上述問題求解。若，則原問題有容許解； 若，則原問題無容許解，停止計(jì)算。2.第二階段：求原線性規(guī)劃問題的最優(yōu)解。以第一階段的最終單純形表為基礎(chǔ)，去掉其中的人工變量列，把目標(biāo)函數(shù)換成原問題的目標(biāo)函數(shù)，于是得到第二階段的初始單純形表，繼續(xù)迭代下去，得最優(yōu)解。第三講線性規(guī)劃的對偶問題一、對偶問題的提出對偶性是線性規(guī)劃的重要內(nèi)容之一，每一個(gè)線性規(guī)劃問題必然有與之相伴而生的另一個(gè)線性規(guī)劃問題，我們稱一個(gè)叫原問題，另一個(gè)叫對偶問題，這兩個(gè)問題有著非常密切的關(guān)系，讓我們先分析一個(gè)實(shí)際的線性規(guī)劃模型與其對偶線性規(guī)劃問題的經(jīng)濟(jì)意義．產(chǎn)品設(shè)備總工時(shí)限制/h甲/h21370乙/h42280丙/h30115丁/h22050單位利潤/千元8102解設(shè)分別為產(chǎn)品的產(chǎn)量，構(gòu)造此問題的線性規(guī)劃模型為現(xiàn)在從另一個(gè)角度來討論該問題．假設(shè)工廠考慮不安排生產(chǎn)，而準(zhǔn)備將所有設(shè)備出租，收取租費(fèi)．于是，需要為每種設(shè)備的臺時(shí)進(jìn)行估價(jià)．設(shè)分別表示甲、乙、丙、丁4種設(shè)備的臺時(shí)估價(jià)．由表3.6可知，生產(chǎn)一件產(chǎn)品需用各設(shè)備臺時(shí)分別為，如果將不用于生產(chǎn)產(chǎn)品，而是用于出租，那么將得到租費(fèi)．當(dāng)然，工廠為了不至于蝕本，在為設(shè)備定價(jià)時(shí)，保證用于生產(chǎn)產(chǎn)品的各設(shè)備臺時(shí)得到的租費(fèi)，不能低于產(chǎn)品的單位利潤8千元，即．按照同樣分析，用于生產(chǎn)一件產(chǎn)品的各設(shè)備臺時(shí)，，，所得的租費(fèi)，不能低于產(chǎn)品的單位利潤10千元，即．同理，還有．另外，價(jià)格顯然不能為負(fù)值，所以．企業(yè)現(xiàn)在設(shè)備的總以時(shí)數(shù)為70h，80h，15h，50h，如果將這些臺時(shí)都用于出租，企業(yè)的總收入為．企業(yè)為了能夠得到租用設(shè)備的用戶，使出租設(shè)備的計(jì)劃成交，在價(jià)格滿足上述約束的條件下，應(yīng)將設(shè)備價(jià)值定得盡可能低，因此取的最小值，綜合上述分析，可得到一個(gè)與之相對應(yīng)的線性規(guī)劃，即稱后一個(gè)規(guī)劃問題為前一個(gè)規(guī)劃問題的對偶問題，反之，也稱前一個(gè)規(guī)劃問題是后一個(gè)規(guī)劃問題的對偶問題．二、原問題與對偶問題的表達(dá)形式和關(guān)系在線性規(guī)劃的對偶理論中，把如下線性規(guī)劃形式稱為原問題的標(biāo)準(zhǔn)形式而把如下線性規(guī)劃形式稱為對偶問題的標(biāo)準(zhǔn)形式若用矩陣形式表示，則原問題和對偶問題分別可寫成如下形式：原問題對偶問題原問題與對偶問題的關(guān)系見表．原問題（對偶問題）對偶問題（原問題）minmax目標(biāo)函數(shù)系數(shù)右邊常數(shù)約束條件系數(shù)矩陣右邊常數(shù)目標(biāo)函數(shù)系數(shù)系數(shù)矩陣的轉(zhuǎn)置第個(gè)約束條件為“≥”型第個(gè)約束條件為“=”型第個(gè)約束條件為“≤”型第個(gè)變量≥0第個(gè)變量無限制第個(gè)變量≤0第個(gè)變量≥0第個(gè)變量無限制第個(gè)變量≤0第個(gè)約束條件為“≤”型第個(gè)約束條件為“=”型第個(gè)約束條件為“≥”型例求下面線性規(guī)劃問題的對偶問題解：根據(jù)可直接寫出上述問題的對偶問題三、對偶理論定理（弱對偶定理）對偶問題（max）的任何可行解，其目標(biāo)函數(shù)值總是不大于原問題（min）任何可行解的目標(biāo)函數(shù)值．定理（對偶定理）假如原問題或?qū)ε紗栴}之一具有有限的最優(yōu)解，則另一問題也具有有限的最優(yōu)解，且兩者相應(yīng)的目標(biāo)函數(shù)值相等．假如一個(gè)問題的目標(biāo)函數(shù)值是無界的，則另一問題沒有可行解．證明從略．定理（互補(bǔ)松馳定理）假如和分別是原問題和對偶問題的可行解，是原問題剩余變量的值，是對偶問題松馳變量的值，則、分別是原問題和對偶問題最優(yōu)解的充要條件是．根據(jù)互補(bǔ)松馳定理和決策變量滿足非負(fù)條件可知，在最優(yōu)解時(shí)，和同時(shí)等于0，所以有，．于是，互補(bǔ)松馳定理也可以這樣敘述：最優(yōu)化時(shí)，假如一個(gè)問題的某個(gè)變量取正數(shù)，則相應(yīng)的另一個(gè)問題的約束條件必取等式；或者一個(gè)問題中的約束條件不取等式，則相應(yīng)于另一問題中的變量必為零．例已知線性規(guī)劃問題已知其對偶問題的最優(yōu)解為，試用對偶理論找出原問題的最優(yōu)解．解：先寫出它的對偶問題將的值代入約束條件，得（2），（3），（4）為嚴(yán)格不等式，由互補(bǔ)松馳定理得，因，原問題的兩個(gè)約束條件應(yīng)取等式，故有，．求解后得到，故原問題的最優(yōu)解為．第四講對偶單純性法對偶單純形法是對偶問題的迭代算法，其基本思想是：從原問題的一個(gè)基本解出發(fā)，此基本解不一定是可行解，但它對應(yīng)著對偶問題的一個(gè)可行解；然后檢驗(yàn)原問題的基本解是否可行，即是否有負(fù)的分量．如果有小于零的分量，則進(jìn)行迭代，求另一個(gè)基本解，此基本解對應(yīng)著另一個(gè)對偶可行解．如果得到的基本解的分量皆非負(fù)，則該基本解為最優(yōu)解．也就是說，對偶單純形法在迭代過程中始終保持對偶解的可行解，使原問題的基本解由不可行逐步變?yōu)榭尚校?dāng)同時(shí)得到對偶問題與原問題的可行解時(shí)，便得到原問題的最優(yōu)解．對線性規(guī)劃問題的標(biāo)準(zhǔn)形式對偶單純形法的計(jì)算步驟如下：(1)找出原問題的一個(gè)基，構(gòu)成初始對偶基可行解，使所有檢驗(yàn)數(shù)，構(gòu)成初始對偶單純形表．(2)若所有，則當(dāng)前的解是最優(yōu)解，停止計(jì)算，否則計(jì)算，則行為主行，該行對應(yīng)的基變量為換出變量．(3)若所有，則對偶問題無界，原問題無解，停止計(jì)算，否則計(jì)算，則列為主列，該列對應(yīng)的基變量為換入變量．(4)以為主元素進(jìn)行迭代，然后轉(zhuǎn)回步驟(2)．對偶單純形法的流程圖如圖所示．原問題的基本解的檢驗(yàn)數(shù)開始原問題的基本解的檢驗(yàn)數(shù)開始以為主元素進(jìn)行迭代得到最優(yōu)解得到最優(yōu)解YYNYNY所有所有?計(jì)算計(jì)算例用對偶單純形法求解下述線性規(guī)劃問題建立初始單純形表，見表CBXBb23400x1x2x3x4x50x4－3－1－2－1100x5－4[－2]1－30123400從表看出，所有檢驗(yàn)數(shù)，則對應(yīng)對偶問題的解是可行的，因列數(shù)字為負(fù)，需進(jìn)行迭代，計(jì)算．所以為換出變量．又因?yàn)?，所以為換入變量，以換入、換出變量所在行列交叉處元素“－2”為主元素，按單純形法計(jì)算步驟進(jìn)行迭代，得表．CBXBb23400x1x2x3x4x50x4－10[－5/2]1/21－1/22x121－1/23/20－1/2041013x22/501－1/5－2/51/52x111/5107/5－1/5－2/5003/58/51/5由表的最后一行看出，所有檢驗(yàn)數(shù)，故原問題的最優(yōu)解為．若對應(yīng)兩個(gè)約束條件對偶變量為，，則可得對偶問題的最優(yōu)解為．7.3教學(xué)單元三線性搜索與信賴域方法（14學(xué)時(shí)）教學(xué)目標(biāo)（1）理解一維搜索的概念并掌握其性質(zhì)；（2）理解搜索區(qū)間的概念并掌握確定搜索區(qū)間的進(jìn)退法；（3）理解單谷函數(shù)的概念并掌握其性質(zhì)；（4）掌握0.618法與Fibonacci法；（5）掌握Newton切線法、割線法、二次插值法，了解Armijo-Goldstein法、Wolfe-Powell法、后退法。（6）了解信賴與方法。教學(xué)內(nèi)容主要講授在尋優(yōu)的過程中如何確定最優(yōu)步長以及常用的幾種一維搜索算法的形成。線性搜索，0.618法和Fibonacci法，逐次插值逼近法，精確線性搜索方法的收斂性，不精確線性搜索方法，信賴域方法的思想和算法框架，信賴域方法的收斂性，解信賴域子問題。教學(xué)重點(diǎn)及難點(diǎn)：（1）教學(xué)重點(diǎn)：0.618法。（2）教學(xué)難點(diǎn)：Armijo-Goldstein法。教學(xué)方法本單元的教學(xué)主要包括課堂講授，學(xué)生自學(xué)，課堂討論、習(xí)題課，課外作業(yè)（至少5次）、輔導(dǎo)答疑等教學(xué)環(huán)節(jié)。通過各個(gè)教學(xué)環(huán)節(jié)的教學(xué)，重點(diǎn)培養(yǎng)學(xué)生的自學(xué)能力、動(dòng)手能力、創(chuàng)新能力、分析問題與解決問題的能力。提倡探索和推行研究性教學(xué)，通過啟發(fā)式教學(xué)、問題式教學(xué)、討論式教學(xué)等教學(xué)方法和合作式學(xué)習(xí)方式，積極引導(dǎo)學(xué)生進(jìn)行研究性學(xué)習(xí)。教學(xué)過程第一講一維搜索一、精確與非精確一維搜索如前所述，最優(yōu)化算法的迭代格式為：因而算法的關(guān)鍵就是選擇合適的搜索方向，然后再確定步長因子。若設(shè)現(xiàn)在的問題是從出發(fā)，沿方向搜索，希望找到，使得，這就是所謂的一維搜索或稱為線搜索(linesearch)問題。⑴若求得的，使目標(biāo)函數(shù)沿方向達(dá)到最小，即使得或，則稱為最優(yōu)一維搜索，或精確一維搜索。相應(yīng)的稱為最優(yōu)步長因子。⑵如果選取，使目標(biāo)函數(shù)獲得可以接受的改善，即，則稱之為近似一維搜索，或非精確一維搜索。注：精確搜索與非精確搜索在最優(yōu)化算法中均廣泛應(yīng)用，它們存在各自的優(yōu)缺點(diǎn)。二、一維搜索的基本框架一維搜索實(shí)際上是一元函數(shù)的極值問題，其基本的解決框架是：⑴確定包含最優(yōu)解的初始搜索區(qū)間；⑵采用某些區(qū)間分割技術(shù)或插值方法不斷縮小搜索區(qū)間，最后得到解。注：值得注意的是，這樣得到的解大多數(shù)情況下均為近似解。因此，即便采用精確一維搜索策略，只要應(yīng)用了數(shù)值方法，最終得到的結(jié)果都不一定是真正數(shù)學(xué)意義上的最佳步長因子。初始搜索區(qū)間的確定設(shè)，是函數(shù)的最小值點(diǎn)，即。若存在閉區(qū)間，使，則稱為一維極小化問題的搜索區(qū)間。四、確定初始搜索區(qū)間的進(jìn)退法基本思想：從一點(diǎn)出發(fā)，按一定步長探測，試圖找到函數(shù)值呈高－低－高變化的三點(diǎn)。具體地，從初始點(diǎn)出發(fā)，取初始步長為。若，則下一步從新點(diǎn)出發(fā)，加大步長，再向前搜索。若，則下一步仍從出發(fā)，沿反方向搜索，直到上升，即為止。在確定了初始搜索區(qū)間后，剩下就是采用具體的一維搜索方法確定出。后面將分別介紹幾種常用的一維搜索方法，這些方法主要是針對所謂單峰函數(shù)設(shè)計(jì)的。五、單峰函數(shù)的定義定義設(shè)，。若存在，使得函數(shù)在上單調(diào)下降，而在上單調(diào)上升，則稱是函數(shù)的單峰區(qū)間，是上的單峰函數(shù)（準(zhǔn)確地說應(yīng)是單谷函數(shù)）。單峰函數(shù)還可以等價(jià)地定義如下定義如果存在唯一的，使得對于任意的且，有⑴若，則；⑵若，則。則稱是上的單峰函數(shù)。下面定理表明，對單峰函數(shù)，可以通過簡單地比較函數(shù)值，縮小搜索區(qū)間。定理設(shè)是上的一個(gè)單峰函數(shù)，，且。⑴若，則是的單峰區(qū)間；⑵若，則是的單峰區(qū)間。第二講0.618法與Fibonacci法下面介紹一些實(shí)現(xiàn)精確一維搜索常見方法。0.618法，F(xiàn)ibonacci法，二分法等基本思想都是通過取試探點(diǎn)并進(jìn)行函數(shù)值比較，然后不斷縮小搜索區(qū)間，當(dāng)區(qū)間長度縮到一定程度后，區(qū)間內(nèi)各點(diǎn)均可作為近似解。這類方法僅需計(jì)算函數(shù)值，十分簡便，尤其適合于非光滑及導(dǎo)數(shù)表達(dá)式復(fù)雜或?qū)懖怀龅那樾?，用途很廣。一、0.618法（黃金分割法）設(shè)是搜索區(qū)間上的單峰函數(shù)。記其在第次迭代時(shí)搜索區(qū)間為，現(xiàn)取兩個(gè)試探點(diǎn)，，且，計(jì)算和。根據(jù)前面關(guān)于單峰函數(shù)的性質(zhì)：⑴若，則令，⑵若，則令，對兩個(gè)試探點(diǎn)、，我們要求滿足下列條件：⑴和到搜索區(qū)間的端點(diǎn)等距，即⑵每次迭代，搜索區(qū)間長度的縮短率相同。即（是與無關(guān)的常數(shù)）因此有由此得，注意到第次計(jì)算的兩個(gè)點(diǎn)，中總有一個(gè)落入第次搜索區(qū)間中，若這個(gè)點(diǎn)可以被重復(fù)使用的話，將減少一次函數(shù)值的計(jì)算。為確定起見，設(shè)（此時(shí)含在中）。為進(jìn)一步縮短區(qū)間，需取試探點(diǎn)，，若取，使得，則這樣，新的試探點(diǎn)處的函數(shù)值就不必重新計(jì)算。對情形，有類似結(jié)論：若取，則。這表明當(dāng)區(qū)間縮短率取得滿足時(shí)，每次迭代僅需計(jì)算一個(gè)函數(shù)值即可。由，解方程得，再由，故。由此，0.618法的計(jì)算公式具體為：注：1）0.618法每次迭代實(shí)際只需計(jì)算一個(gè)點(diǎn)的函數(shù)值；2）經(jīng)過次迭代，搜索區(qū)間的長度縮短為，故0.618法的收斂速度是線性的；3）0.618法也稱黃金分割法，滿足，由于它還兼具美學(xué)意義與一些奇妙的性質(zhì)，故稱為黃金分割點(diǎn)，相應(yīng)的方法稱為黃金分割法。二、改進(jìn)的0.618法0.618法要求一維搜索的函數(shù)是單峰，而實(shí)際上很多情形都不是單峰。這個(gè)時(shí)候往往容易丟掉最優(yōu)點(diǎn)。(1976)提出了一種改進(jìn)措施。每次兩個(gè)內(nèi)點(diǎn)與兩個(gè)邊界點(diǎn)的函數(shù)值都進(jìn)行比較。當(dāng)函數(shù)值最小的點(diǎn)為左端點(diǎn)或第二個(gè)點(diǎn)時(shí)，丟棄右端點(diǎn)，否則丟棄左端點(diǎn)。經(jīng)過這樣修改后，算法要相對可靠些，即在縮短搜索區(qū)間時(shí)，丟掉極小點(diǎn)的可能性減小了。值得注意的是，即便如此，仍不能保證迭代過程不丟掉極小點(diǎn)。下圖所描述的情形給出了很好的解釋。按規(guī)則，首次就去掉右端點(diǎn)，剩下區(qū)間為，顯然極小點(diǎn)被丟掉了。這表明用0.618法進(jìn)行一維搜索并不是任何時(shí)候都能找到極小點(diǎn)。三、Fibonacci法（分?jǐn)?shù)法、優(yōu)選法）1．優(yōu)選法的基本思想通過選擇試探點(diǎn)，并利用試探點(diǎn)處的函數(shù)值信息，可以不斷縮短搜索區(qū)間。在函數(shù)值計(jì)算總次數(shù)一定的情況下，最初搜索區(qū)間與最終搜索區(qū)間長度的比值越大，說明選點(diǎn)方式越好，最優(yōu)的選點(diǎn)方式應(yīng)使這個(gè)比值達(dá)到最大。設(shè)函數(shù)值計(jì)算總次數(shù)為，最初區(qū)間長度為，最終區(qū)間長度為1，因此最優(yōu)取點(diǎn)方式應(yīng)使達(dá)到最大，下面先來估計(jì)的上確界。設(shè)的上確界為，（），即表示當(dāng)允許計(jì)算次函數(shù)值時(shí)，初始區(qū)間長度的上確界（當(dāng)然最終區(qū)間長度為1）。顯然，要縮短區(qū)間，至少需計(jì)算兩次函數(shù)值。也就是，如果只允許計(jì)算零次或一次函數(shù)值，區(qū)間不會(huì)得到縮短，故有下面考慮允許計(jì)算次函數(shù)值時(shí)，初始區(qū)間的長度的上確界。設(shè)最初的兩個(gè)試探點(diǎn)為，那么余下還可計(jì)算次函數(shù)值，而極小點(diǎn)可能位于或。⑴若極小點(diǎn)位于中，由于我們僅可在此區(qū)間中再計(jì)算次函數(shù)值。故有⑵若極小點(diǎn)位于中，由于除可再計(jì)算次函數(shù)值外，還可利用處的函數(shù)值。因而由此立即得于是有2．Fabonacci數(shù)列由下述遞歸關(guān)系式給出的數(shù)列稱為Fabonacci數(shù)列：，，由上一段分析，顯然有。因此若某種取點(diǎn)方式能保證在計(jì)算函數(shù)值次后，能將長度為的初始區(qū)間縮短為1，或等價(jià)地，把搜索區(qū)間縮減為最初區(qū)間的，那么就有理由認(rèn)為這種取點(diǎn)方式是最優(yōu)的。分?jǐn)?shù)法根據(jù)Fabonacci數(shù)列來構(gòu)造、選取試驗(yàn)點(diǎn)，它恰好具有上述所希望的性質(zhì)。因而是最優(yōu)選點(diǎn)方式，故稱之為優(yōu)選法。3．Fabonacci法中探測點(diǎn)的取法⑴每次迭代區(qū)間收縮率為，收縮率不為常數(shù)；⑵，關(guān)于區(qū)間的端點(diǎn)對稱；⑶，由此即知經(jīng)過次函數(shù)值計(jì)算后，最終區(qū)間縮為初始區(qū)間的，故為最優(yōu)選點(diǎn)方式；⑷每次僅需計(jì)算一個(gè)函數(shù)值。事實(shí)上，若（同樣考慮），可驗(yàn)證必有，因而處的函數(shù)值不必重復(fù)計(jì)算。而僅需計(jì)算處的函數(shù)值，故每次迭代，僅需計(jì)算一個(gè)函數(shù)值。4.Fibonacci法與0.618法的聯(lián)系令，將其帶入差分方程，得解之得。因而差分方程的通解為：。再利用邊界條件，得解得故有由此立即可得.這說明當(dāng)時(shí)，F(xiàn)ibonacci法與0.618法的區(qū)間收縮率相同，因而Fibonacci法也是線性收斂的。由于Fibonacci法選點(diǎn)方式是最優(yōu)的，而0.618法與其近似，故應(yīng)用上將它們統(tǒng)稱為優(yōu)選法。四、二分法二分法是求的根的一種簡單方法。它每次將區(qū)間對分，再利用連續(xù)函數(shù)的零點(diǎn)定理，確定應(yīng)該保留的半?yún)^(qū)間，區(qū)間收縮率為常數(shù)，因此它也具有線性收斂速度。但當(dāng)?shù)谋磉_(dá)式很難求，或不可微時(shí)，方法的應(yīng)用遇到困難。第三講插值法一、二次插值法1．牛頓插值法其基本思想是用在一點(diǎn)的二階展開式近似，而以二次展開式的極小點(diǎn)作為極小點(diǎn)近似。設(shè)。令，得解之得。因此，牛頓法的迭代公式為：牛頓法不僅算法簡單，而且具有較快的收斂速度（局部）。定理設(shè)三階連續(xù)可微，，則當(dāng)初始點(diǎn)充分靠近時(shí)，由牛頓迭代公式：產(chǎn)生的點(diǎn)列收斂，即。且即該算法具有局部二階收斂性質(zhì)。證明：由牛頓迭代公式有：再由及的連續(xù)性，必定存在，使得對任何，有。因而當(dāng)時(shí)，。從而當(dāng)時(shí)，有，由此可知收斂性得證。又由，這里由此可得。即有從而得，定理證畢。2.二點(diǎn)二次插值法1）設(shè)已給兩點(diǎn)，，利用、，以及或進(jìn)行插值。設(shè)二次插值函數(shù)形式為：。則解出，得的駐點(diǎn)為一般迭代格式為2）若利用，和進(jìn)行插值則解之得。一般迭代格式為.注：與牛頓法比較，在第一種公式中，逼近誤差為；而在第二個(gè)公式中，逼近誤差為?？梢姾笠环N逼近程度略差一些。二點(diǎn)二次插值法的收斂速度定理設(shè)三階連續(xù)可微，滿足，則二點(diǎn)二次插值公式產(chǎn)生的序列收斂到，且收斂速度的階為。證明：參見袁亞湘等著《最優(yōu)化理論與方法》（略）。3）三點(diǎn)二次插值法利用、、進(jìn)行二次均值，用插值多項(xiàng)式的駐點(diǎn)近似的駐點(diǎn)。一般迭代格式：。定理設(shè)四階連續(xù)可微，滿足，則上述插值法產(chǎn)生的序列收斂到，且收斂速度的階約為1.32。二、三次均值法用三次函數(shù)逼近被極小化的函數(shù)，需四個(gè)條件確定插值多項(xiàng)式的系數(shù)。這些條件可以是：1）四點(diǎn)函數(shù)值，2）三點(diǎn)函數(shù)值及一點(diǎn)導(dǎo)數(shù)值，3）兩點(diǎn)函數(shù)值及導(dǎo)數(shù)值。三次插值法得到的迭代點(diǎn)列具有較快的收斂速度（為二階收斂），但由于涉及更高階導(dǎo)數(shù)的計(jì)算，增加了應(yīng)用的困難。關(guān)于這方面的詳細(xì)討論，可參閱袁亞湘等著《最優(yōu)化理論與方法》。第四講精確一維搜索的收斂理論一、基于精確一維搜索的極小化算法無約束最優(yōu)化問題算法的基本框架：⑴給出初始點(diǎn)，允許誤差，置⑵計(jì)算下降方向⑶利用一維搜索，確定步長因子，使⑷令，若，則停止，輸出最優(yōu)解。否則，置，轉(zhuǎn)⑵。在上面算法中，采用了精確一維搜索。下面證明基于精確一維搜索的極小化算法的收斂性。二、算法收斂性定理設(shè)是的解，若，則有：證明：由定理假設(shè)，有，令（若要，則必須，即與成銳角），，定理證畢。注：⑴由證明過程可以看出，必須和成銳角。⑵給出了精確搜索前提下，每步迭代所得改進(jìn)量的估計(jì)式，顯然與有關(guān)。定理設(shè)是開集上的連續(xù)可微函數(shù)，若某一極小化算法滿足：，，又設(shè)是序列的聚點(diǎn)，是滿足的指標(biāo)集。假定存在，使得，有，又設(shè)是序列的任意聚點(diǎn)，則進(jìn)一步，若在上二次連續(xù)可微，則還有。證明：設(shè)是滿足的指標(biāo)集，下面用反證法證明。若定理結(jié)論不成立，即，由于，注意到時(shí)，，則有，因而必有。（﹡）于是存在的鄰域和指標(biāo)集，使得當(dāng)，時(shí)，有，（由（﹡）式可得）設(shè)是一個(gè)充分小的正數(shù)，使得對所有，及所有，都有，（由，有界可得）則，與為有限值矛盾，故必有。同樣地，若不成立，則必有。類似地，有此矛盾表明必有：，定理證畢。三、采用精確搜索的極小化算法的收斂速度引理1設(shè)函數(shù)在閉區(qū)間上二次連續(xù)可微，且。若在上的極小點(diǎn)，則。其中滿足，。證明：構(gòu)造輔助函數(shù)，它有唯一零點(diǎn)。注意到即的圖像總位于之下，再由是單調(diào)上升函數(shù)，由此可得：的零點(diǎn)必位于零點(diǎn)的右邊。即事實(shí)上，在零點(diǎn)的左邊，。由，有。故的零點(diǎn)不可能位于的左邊。故必有。引理2設(shè)在上二階連續(xù)可微，則對任意向量，和任意實(shí)數(shù)，有：.證明：（為積分變量）（再分部積分）.引理3設(shè)在極小點(diǎn)的鄰域內(nèi)二階連續(xù)可微，且存在，和，使得當(dāng)時(shí)，，.那么當(dāng)時(shí)，有，.證明：在引理2中取，再令，則注意到及引理?xiàng)l件即得:.又由，因此有由此即得.利用上述引理，可得下面的收斂速度定理。定理設(shè)極小化算法產(chǎn)生的序列收斂到的極小點(diǎn)，若在的某一鄰域內(nèi)二階連續(xù)可微，且存在，和，使得當(dāng)時(shí)，有，則線性收斂。證明：由。故當(dāng)充分大時(shí)，有，，因而，存在，使得(這是由于在每次迭代中，搜索方向可取為單位向量，故有界)。記由于，故當(dāng)時(shí)，有又注意到，由引理1知在上的極小點(diǎn)滿足（其中為夾角）（為的下限）若記，則有。令由于位于與決定的線段上，因而到的距離不會(huì)超過到與到中距離的最大者，即由引理2，（由的取法）（由引理3）（由引理3）因此，令，顯然且有再由引理3其中，.上式可進(jìn)一步改寫為由此即得迭代點(diǎn)列線性收斂。特別地，若在所討論的算法模式中，每次迭代均取為（即取為最速下降方向），則得到的算法稱為最速下降算法。值得指出的是：最速下降算法中相繼兩次迭代的搜索方向是正交的。事實(shí)上，第次迭代搜索方向?yàn)?，考慮，其最優(yōu)步長因子應(yīng)滿足，即，由于因此有，而恰好是第次迭代方向，故，即知相繼兩次迭代的搜索方向是正交的。鑒于這一特點(diǎn)，可以斷言基于精確一維搜索的最速下降法實(shí)際下降速度并不快（迭代點(diǎn)列呈鋸齒狀趨于最優(yōu)解）。第五講不精確線性搜索方法一維搜索是最優(yōu)化算法的基本組成部分。前述的精確一維搜索往往需要花費(fèi)大量計(jì)算量，導(dǎo)致整個(gè)算法不是十分有效。另外，在很多算法如牛頓算法和擬牛頓算法，其收斂速度也并不依賴于精確一維搜索。因此，另一種變通的方法是在每次一維搜索過程中，保證目標(biāo)函數(shù)都有滿意的下降就夠了，這就是所謂的不精確一維搜索。在進(jìn)行不精確一維搜索時(shí)，怎樣才叫達(dá)到了滿意的程度，從而結(jié)束一維以為搜索，必須要有便于操作的準(zhǔn)則。下面介紹一些最重要、最常用的準(zhǔn)則，為簡單計(jì)，仍以單峰函數(shù)為考察對象。但應(yīng)該指出的是：并不一定要求函數(shù)為單峰，這方面的詳細(xì)討論可參閱席少霖著《非線性最優(yōu)化方法》。一、Armijo-Goldstain準(zhǔn)則1），其中是給定的數(shù)。2）Armijo-Goldstain準(zhǔn)則的直觀意義是：避免取在區(qū)間的兩個(gè)端點(diǎn)附近，因?yàn)槿≡趦啥它c(diǎn)附近都會(huì)導(dǎo)致目標(biāo)函數(shù)的改進(jìn)量不大。從上圖可以看出，區(qū)間上的點(diǎn)都可取為可接受步長，故稱為可接受區(qū)間。若記，那么Armijo-Goldstain準(zhǔn)則可改寫為：注意到，因此當(dāng)時(shí)，上面兩個(gè)不等式互相矛盾。由此可見，的要求是自然的。一旦給定，圖中兩條直線就同時(shí)給定，可接受區(qū)間也隨之確定，而且越接近于0，可接受區(qū)間越大，而越趨近于，則可接受區(qū)間越小。二、Wolfe-Powell準(zhǔn)則Armijo-Goldstain準(zhǔn)則有時(shí)候會(huì)將最佳步長因子排斥在可接受區(qū)間之外。為此，Wolfe-Powell給出了一個(gè)簡單的替代準(zhǔn)則：1）2'）亦即：。注：1)準(zhǔn)則2'）的幾何解釋：在可接受點(diǎn)處的切線斜率大于或等于初始斜率的倍。由于，因而接收點(diǎn)處的切線更平坦些；2)可以證明：當(dāng)時(shí)，滿足Wolfe-Powell準(zhǔn)則的可接受步長因子是存在的；3)從另一個(gè)觀點(diǎn)看，，是精確一位搜索滿足的正交條件的某種近似。但這種近似，即使，也不能導(dǎo)致精確一維搜索。若將Wolfe-Powell準(zhǔn)則中第二式換為則當(dāng)時(shí)，接近精確搜索準(zhǔn)則。而且取得越小，越接近精確搜索，工作量也越大。應(yīng)該指出的是不精確搜索，不要求過小的，應(yīng)用上通常取，。Wolfe-Powell準(zhǔn)則下可接受步長因子的存在性定理設(shè)有下界，且，則必定存在步長因子，使得Wolfe-Powell準(zhǔn)則滿足。即存在步長因子，使得：1）2），或滿足。證明：令，則。令滿足，考慮集合。由于有下界，且故非空。事實(shí)上，若，即對所有，都有因而當(dāng)時(shí)，可推得，這與有下界矛盾，所以。令則顯然，這是因?yàn)楫?dāng)充分小時(shí)，。事實(shí)上，當(dāng)充分小時(shí)，，由此即得。故當(dāng)時(shí)，（*）由的定義必有（由的連續(xù)性）故（由及）再由的連續(xù)性，必定存在，當(dāng)時(shí)，有這也就是，。再由(*)式故有(由及)由的連續(xù)性，存在，當(dāng)時(shí)，此即。令，則當(dāng)時(shí)，同時(shí)有，。這表明，滿足Wolfe-Powell準(zhǔn)則的步長因子不僅存在，而且有很多。當(dāng)采用Wolfe-Powell方法準(zhǔn)則時(shí)，下述性質(zhì)成立。定理設(shè)函數(shù)連續(xù)可微，滿足Lipschitz條件：。若時(shí)，下有界，則對滿足Wolfe-Powell準(zhǔn)則的任何，均有證明：略三、Armijo-Goldstein和Wolfe—Powell不精確一維搜索方法前面介紹了幾種不精確一維搜索準(zhǔn)則，下面給出幾個(gè)具體的不精確一維搜索算法。1．Armijo-Goldstein方法當(dāng)試探的取得不合適時(shí)，用求區(qū)間中點(diǎn)的方法選取新的試探點(diǎn)，算法如下：算法迭代步驟在搜索區(qū)間（或）中取定初始點(diǎn)，計(jì)算，給出。令（或），。計(jì)算，若，轉(zhuǎn)3）；否則，令，轉(zhuǎn)4）。若，停止迭代，輸出；否則，，若，轉(zhuǎn)4）；否則，，轉(zhuǎn)2）。選取新的探索點(diǎn)。取。2．Wolfe—Powell方法當(dāng)試探的取得不合適時(shí)，用兩點(diǎn)插值公式確定新的試探點(diǎn)，見下面框圖：選取初始數(shù)據(jù)選取初始數(shù)據(jù)計(jì)算第一準(zhǔn)則是否成立？計(jì)算和第二準(zhǔn)則是否成立？令停利用二次插值公式計(jì)算利用二次插值公式計(jì)算NYYN四、簡單準(zhǔn)則和后退方法在實(shí)際計(jì)算中，有時(shí)僅采用Armijo-Goldstein準(zhǔn)則中的第一個(gè)準(zhǔn)則稱之為簡單準(zhǔn)則，而后退方法則是建立在這種準(zhǔn)則之下的一種不精確搜索算法。其基本思想是：開始令，若不可接受，則減少（后退），直到為可接受為止。后退算法的迭代步驟：給定，??；檢驗(yàn)。若上式不滿足，取，轉(zhuǎn)2）；若上式滿足，取，令上面介紹了三種最常見的不精確搜索準(zhǔn)則，利用這些準(zhǔn)則，可以構(gòu)造很多具體的不精確搜索方法（主要是試探點(diǎn)的不同選取方式，搜索區(qū)間的不同縮減方法）。五、不精確一維搜索的收斂性定理為了保證算法的下降性，我們總要求每次搜索方向與其梯度方向成銳角。并且要求其夾角滿足：，。采用不精確一維搜索的一般下降算法（模式算法）給出初始點(diǎn)，允許誤差，置；若，算法停止，；否則求出滿足的下降方向；求出步長因子，使其滿足Armijo-Goldstein準(zhǔn)則或Wolfe-Powell準(zhǔn)則；令，，轉(zhuǎn)2）。下面給出基于這些不精確一維搜索的一般下降算法的總體收斂性定理。定理若上述算法中，步長因子滿足Armijo-Goldstein準(zhǔn)則或Wolfe-Powell準(zhǔn)則，且，若在水平集上一致連續(xù)。那么，或者對某個(gè)，有，或者，或者。證明：1）若存在某個(gè)，使，或無下界，則結(jié)論已證。2）設(shè)，，且有下界，由單調(diào)下降，故存在，因而有。由Armijo-Goldstein準(zhǔn)則1，立即可得：，用反證法證明若不趨于零，那么存在和一個(gè)子序列，使得時(shí)，，由此可推得。事實(shí)上，由，有。再由即得。另一方面，由的一致連續(xù)性有：故有注意到，時(shí)，有（前一因子極限為0，后一因子有界）。事實(shí)上：。由此即得，這與矛盾。類似的，若采用Wolfe-Powell準(zhǔn)則，由的連續(xù)性，（）由此得：（由于當(dāng)時(shí)，）這與Wolfe—Powell第二準(zhǔn)則矛盾，從而定理得證。下面是另一形式的收斂定理：定理設(shè)函數(shù)連續(xù)可微，滿足Lipschitz條件：。又設(shè)算法采用Wolfe-Powell準(zhǔn)則，且與的夾角滿足那么由算法產(chǎn)生的點(diǎn)列，或者對某個(gè)，有，或者，或者。證明：不妨設(shè)，，且有下界。由定理2.13（用到Lipschitz條件），這里。于是：令，則有：由有從而級數(shù)收斂，故。下面定理給出不精確一維搜索條件下，每步迭代目標(biāo)函數(shù)下降量的估計(jì)式。定理2.16設(shè)滿足不精確一維搜索準(zhǔn)則中第一條，若函數(shù)還滿足：，則必有：。證明：1）若，則（最后一個(gè)不等式由得）2）若，由，則必存在使得。在處將函數(shù)展開，有又由，因而有解得：或再由滿足第一準(zhǔn)則，故有：，定理證畢。第六講信賴域算法一、信賴域算法1．牛頓法的基本思想在當(dāng)前迭代點(diǎn)附近用二次函數(shù)逼近，并以地極小點(diǎn)修正，得。如果不限定的范圍，實(shí)際上是用在全空間逼近，而用的極小點(diǎn)代替地極小點(diǎn)。容易理解，這樣得到的迭代點(diǎn)往往不能使有較大的改進(jìn)，有時(shí)不僅不能得到改進(jìn)，反而變得更糟。2．信賴域方法的基本思想信賴域方法是上世紀(jì)70年代提出的一種重要的優(yōu)化方法，它針對上面提及的牛頓方法的缺陷，在子問題中，明確要求必須位于當(dāng)前迭代點(diǎn)的鄰域（信賴域）內(nèi)。在算法每次迭代中，求解下述信賴域子問題：注:1)由于從信賴域子問題求出的必須滿足，故稱為有限步長方法；2）范數(shù)沒有特別限制，可根據(jù)需要隨意選取，但多數(shù)情形用或兩種范數(shù)；3）可用有限差分近似，也可用后面即將介紹的擬牛頓方法構(gòu)造其近似。在信賴域算法中，信賴域半徑采用自適應(yīng)方式調(diào)整，若與近似程度好，則盡可能取大，否則將其縮小。而通常采用下述方式評價(jià)與的逼近程度：在算法迭代的第步，定義稱實(shí)際下降量稱預(yù)估下降量定義比值：越接近1，表明近似程度好，應(yīng)加大，否則相反。3．信賴域算法（算法模式）1）初始步：給出初始點(diǎn)，令2）第步：給出和，計(jì)算和解信賴域模型（子問題），求出求和的值如果，令（縮減信賴域半徑）如果且，令（增大信賴域半徑）否則，置（信賴域半徑不變）若，置；否則置。注：求解信賴域子問題得到的稱為試探步。由可見，求出的試探步最后是否移動(dòng)，取決是否大于0。在有些信賴域算法中，將中的替換成了。二、信賴域算法的收斂性定理設(shè)是中的一個(gè)有界集，信賴域算法產(chǎn)生的點(diǎn)列。若進(jìn)一步假設(shè)且在上滿足：。則存在一個(gè)滿足一階和二階必要條件的聚點(diǎn)。三、折線步與雙折線步方法（TheDoubleDoglegStepMethod）1．Powell（1970）的折線步方法為了求，并且滿足，Powell用一條折線來近似。其做法是將柯西點(diǎn)（即由最速下降法產(chǎn)生的極小點(diǎn)）和牛頓點(diǎn)（即由牛頓算法產(chǎn)生的極小點(diǎn)）的連線與邊界的交點(diǎn)取為(即下圖中的)，而當(dāng)時(shí)，直接取牛頓點(diǎn)，顯然它沒有精確求解信賴域子問題，但算法卻相當(dāng)簡便。2．Dennis和Mei（1979）雙折線步方法Dennis和Mei發(fā)現(xiàn)：若由信賴域方法產(chǎn)生的點(diǎn)從一開始就讓其偏向于牛頓方向，算法的性態(tài)將得到改善（關(guān)于其理論分析可參考原論文）。據(jù)此，他們提出了一種改進(jìn)的雙折線步方法。我們將稱為單折線。而將各點(diǎn)的相繼連線稱為雙折線。C.P.C.P.折線步方法與雙折線步方法7.4教學(xué)單元四無約束最優(yōu)化方法（12學(xué)時(shí)）教學(xué)目標(biāo)（1）掌握最速下降法并理解其收斂性與收斂速度；（2）掌握Newton切線法并理解其收斂性與收斂速度；（3）了解阻尼Newton法；（4）掌握共軛梯度法并理解其收斂性；教學(xué)內(nèi)容：（1）最速下降法及其收斂性與收斂速度；（2）Newton切線法及其收斂性與收斂速度；（3）阻尼Newton法；（4）共軛梯度法及其收斂性；教學(xué)重點(diǎn)及難點(diǎn)：（1）教學(xué)重點(diǎn)：最速下降法。（2）教學(xué)難點(diǎn)：變度量法。教學(xué)方法本課主要采用任務(wù)驅(qū)動(dòng)和程序式思維相結(jié)合的教學(xué)方法，過程當(dāng)中輔以案例講解、啟發(fā)提問、自主學(xué)習(xí)和協(xié)作學(xué)習(xí)等方式。任務(wù)驅(qū)動(dòng)是實(shí)現(xiàn)本課教學(xué)目標(biāo)和完成教學(xué)內(nèi)容的主要方法，任務(wù)是師生活動(dòng)內(nèi)容的核心，在教學(xué)過程中，任務(wù)驅(qū)動(dòng)被多次利用。自主學(xué)習(xí)能提高學(xué)生的自主探究能力，競賽和協(xié)作學(xué)習(xí)調(diào)動(dòng)學(xué)生的積極性，激發(fā)學(xué)生參與的熱情。學(xué)生之間互幫互助，共同分享勞動(dòng)果實(shí)，從而激發(fā)了學(xué)生的團(tuán)隊(duì)意識，達(dá)到理想的教學(xué)效果。教學(xué)過程第一講最速下降法(2學(xué)時(shí)）

在極小化算法中，若每次都以迭代點(diǎn)處的負(fù)梯度方向?yàn)樗阉鞣较?，產(chǎn)生的算法稱為最速下降法，它是無約束最優(yōu)化算法中最簡單、最基本的算法，是最古老的一種算法。1.基本思想最速下降法，又稱梯度法。在每次迭代中，沿最速下降方向進(jìn)行搜索。假定我們已經(jīng)迭代了次，獲得了第個(gè)迭代點(diǎn)。從出發(fā)，顯然應(yīng)沿下降方向進(jìn)行，由于負(fù)梯度方向是最速下降方向，因此沿負(fù)梯度方向應(yīng)該是有利的。因此，取搜索方向。此時(shí)有：如將該方法應(yīng)用于二次函數(shù)，則可求出的顯式表達(dá)式。2.算法描述：給出初始點(diǎn)，允許誤差，；計(jì)算，若，Stop令；由一維搜索確定步長因子，使得令，，goto2).3.算例（略）第二講Newton法一、牛頓算法的基本思路牛頓算法的基本思路是：利用目標(biāo)函數(shù)在當(dāng)前迭代點(diǎn)處的二次近似的極小點(diǎn)作為的近似極小點(diǎn)?？紤]從到的迭代過程,設(shè)是當(dāng)前迭代點(diǎn)，正定，在點(diǎn)處用二次函數(shù)來逼近,即：二、牛頓法的收斂性定理設(shè)，充分靠近極小點(diǎn)，而，正定，若進(jìn)一步假設(shè)Hessian矩陣滿足Lipschitz條件。則由牛頓法產(chǎn)生的序列收斂于，且具有二階的收斂速度。關(guān)于算法的評價(jià)適用條件：如果目標(biāo)函數(shù)在上具有連續(xù)的二階偏導(dǎo)數(shù)，其Hesse矩陣正定。1）優(yōu)點(diǎn)：當(dāng)初始點(diǎn)離最優(yōu)解很近時(shí)，收斂速度快；算法簡單；不需要用一維搜索。2)缺點(diǎn)：局部收斂，不正定時(shí)，不能保證牛頓方向是下降方向。事實(shí)上，當(dāng)為正定時(shí)，牛頓方向滿足：（下降方向），但若非正定，則不能保證是下降方向。由以上分析可知，固定的步長因子不能保證目標(biāo)函數(shù)有合理的改善，甚至不能保證算法下降，因此有必要對牛頓算法作一些改進(jìn)，一個(gè)最直接的改進(jìn)是：在牛頓算法中加入一維搜索。三、帶步長因子的牛頓法——阻尼牛頓法1．算法1）取初始點(diǎn)，允許誤差，置；2）計(jì)算，若，停止迭代，；否則goto3)；3)構(gòu)造牛頓方向：從求出；4）沿進(jìn)行一維搜索，使得滿足：；5）令，轉(zhuǎn)2）。2．總體收斂性定理設(shè)二階連續(xù)可微，且對任意的，存在常數(shù)，使得在水平集上滿足，，，則在精確一維搜索條件下，帶步長因子的牛頓法產(chǎn)生的迭代點(diǎn)列滿足：當(dāng)為有窮點(diǎn)列時(shí)，對某個(gè)，有；當(dāng)為無窮點(diǎn)列時(shí)，收斂到的唯一極小點(diǎn)。四、算例（略）第三講共軛方向法與共軛梯度法共軛方向法是無約束最優(yōu)化問題的一類重要算法。它一方面克服了最速下降法中，迭代點(diǎn)列呈鋸齒形前進(jìn)，收斂慢的缺點(diǎn)，同時(shí)又不像牛頓法中計(jì)算牛頓方向耗費(fèi)大量的工作量，尤其是共軛方向法具有所謂二次收斂性質(zhì)，即當(dāng)將其用于二次函數(shù)時(shí)，具有有限終止性質(zhì)。

1)共軛方向法定義1:設(shè)是對稱正定矩陣。若維空間中非零向量系滿足，,則稱是共軛的，或稱的方向是共軛方向。定理1:若非零向量系是共軛的，則這個(gè)向量線性無關(guān)。推論：在維空間中，互相共軛的非零向量的向量個(gè)數(shù)不超過。定義2:設(shè)是線性無關(guān)的向量系，是任意實(shí)數(shù)。對于任意指定的，稱形式為的向量集合稱為由點(diǎn)和向量系所生成的線性流形，記為。定理2:假設(shè)：①為對稱正定矩陣②非零向量是共軛向量系；③對二次目標(biāo)函數(shù)順次進(jìn)行如下次直線搜索：，，其中是任意選定的初始點(diǎn)。則①,②是二次函數(shù)在線性流形上的極小點(diǎn)。證明①：前面已經(jīng)證明由條件③可知上式左乘后再在兩邊加上，得：即：由上式有，將所得等式兩邊左乘，有證明②:按條件③，，則存在一組數(shù)使得同樣，對于任意上面兩式相減得由結(jié)論①可知由于是正定的，因此是在線性流行上的極小點(diǎn)。當(dāng)時(shí)，線性流行就是整個(gè)維空間了，因此此時(shí)就是中的極小點(diǎn)。共軛方向法：已知：具有正定矩陣的二次目標(biāo)函數(shù)和終止限。①選定初始點(diǎn)和具有下降方向的向量；置。②作直線搜索。③判別是否滿足：若滿足，停機(jī)。④提供共軛方向，使得，⑤k=k+1二次函數(shù)的直線搜索：共軛向量系的構(gòu)造方法：先選定個(gè)線性無關(guān)的向量系，令設(shè)已求得共軛向量，現(xiàn)在來求令為使與共軛，應(yīng)有：，由此解得：于是共軛方向法的適用范圍：可用于非二次函數(shù)，首先通過Taylor公式用二次函數(shù)來逼近非二次函數(shù)。其次，可用來構(gòu)造共軛向量系，這要求充分地靠近。2)共軛梯度法初始共軛向量恰好取為初始點(diǎn)處的負(fù)梯度，以下各共軛方向由第迭代點(diǎn)處的負(fù)梯度與已得到的共軛向量的線性組合來確定。因?yàn)樵摲椒恳粋€(gè)共軛向量都是依賴于迭代點(diǎn)處的負(fù)梯度構(gòu)造出來的，所以稱為共軛梯度法。設(shè)已求得共軛向量，現(xiàn)在來求由，知和是線性無關(guān)的，取考慮與共軛，需滿足：于是有：現(xiàn)在證明除與共軛外，還與共軛。對依次計(jì)算由于是共軛向量，因此，因?yàn)橛忠驗(yàn)?從共軛向量系構(gòu)建方法可以看出，迭代點(diǎn)處的梯度是共軛向量系的線性組合。，，因此有：，,從而證明了與共軛。共軛梯度法在非二次函數(shù)中的應(yīng)用：為了把共軛梯度法應(yīng)用在非二次函數(shù)中，有必要消去表達(dá)式中的。由于因?yàn)?，根?jù)表達(dá)式的不同，可得到四種共軛梯度算法。最常采用的是第二種表達(dá)方式。第四講變尺度法1)基本想法考慮Newton迭代公式，變尺度法就是要消除這個(gè)迭代公式中的Hesse逆矩陣，為此擬采用某種近似矩陣來替換它，即構(gòu)造一個(gè)矩陣序列去逼近。因此，迭代公式為其中可通過從出發(fā)沿作直線搜索來確定。為使確實(shí)與近似并具有容易計(jì)算的特點(diǎn)，對附加下列條件。①要求對稱正定，保證迭代公式具有下降性質(zhì)。如對稱正定，則，保證迭代公式具有下降性質(zhì)。②要求之間的迭代具有簡單的形式。，其中稱為校正矩陣，上式稱為校正公式。③必須滿足擬Newton條件對于二次函數(shù)而言,有:上面兩式相減有:如的逆存在,則有成立,表明能很好近似。如記，，于是擬Newton條件可寫為：擬牛頓法算法：已知：目標(biāo)函數(shù)及其梯度，終止準(zhǔn)則。①選定初始點(diǎn)；計(jì)算，選定初始矩陣。②計(jì)算搜索方向。③作直線搜索。④如滿足終止準(zhǔn)則，停機(jī)。⑤計(jì)算。⑥，轉(zhuǎn)②。2)校正公式(1)對稱秩1算法(SR1法)校正公式取為其中是維待定非零向量，是待定常數(shù)，由于校正公式必須滿足擬牛頓條件，于是有：。取，于是校正公式為：對稱秩1算法的性質(zhì)：性質(zhì)1:設(shè)將SR1法施用于具有對稱正定矩陣的二次函數(shù)，如果①初始矩陣是對稱的。②迭代點(diǎn)是互異的。③當(dāng)時(shí)，那么有：(Ⅰ)此算法所生成的搜索方向是互相共軛的。(Ⅱ)對，性質(zhì)2:若性質(zhì)1的條件都滿足，并且經(jīng)過次迭代才求到極小點(diǎn)，則。(2)DFP算法考慮如下形式的校正公式由于校正公式必須滿足擬牛頓條件，于是有：取，再令，