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

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

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

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

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

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