最優(yōu)化方法及控制應用第1頁，共109頁，2023年，2月20日，星期六參考書：1.實用最優(yōu)化方法R.Fleter著，游兆永等譯天津科技翻譯出版公司2.非線性規(guī)劃數(shù)值方法袁亞湘上?？茖W技術出版社19953.非線性最優(yōu)方法席少霖高等教育出版社4.工程優(yōu)化的算法分析張可村西安交大出版社19895.最優(yōu)化方法解文新，韓立興等天津大學出版社20016.最優(yōu)化方法施光燕，董加禮高等教育出版社2001第2頁，共109頁，2023年，2月20日，星期六最優(yōu)化方法及控制應用最優(yōu)化：在多種（有限種或無限種）決策中挑選最好決策的問題。最優(yōu)化方法：（也稱做運籌學方法）是近幾十年形成的，主要運用數(shù)學方法研究各種系統(tǒng)的優(yōu)化途徑及方案，為決策者提供科學決策的依據(jù)。最優(yōu)方案：是達到最優(yōu)目標的方案。最優(yōu)化理論：就是最優(yōu)化方法的理論。第3頁，共109頁，2023年，2月20日，星期六數(shù)學意義為了達到最優(yōu)化目的所提出的各種求解方法。從數(shù)學意義上說，最優(yōu)化方法是一種求極值的方法，即在一組約束為等式或不等式的條件下，使系統(tǒng)的目標函數(shù)達到極值，即最大值或最小值。從經(jīng)濟意義上說，是在一定的人力、物力和財力資源條件下，使經(jīng)濟效果達到最大（如產(chǎn)值、利潤），或者在完成規(guī)定的生產(chǎn)或經(jīng)濟任務下，使投入的人力、物力和財力等資源為最少。第4頁，共109頁，2023年，2月20日，星期六發(fā)展簡史公元前500年古希臘在討論建筑美學中就已發(fā)現(xiàn)了長方形長與寬的最佳比例為1.618，稱為黃金分割比。其倒數(shù)至今在優(yōu)選法中仍得到廣泛應用。在微積分出現(xiàn)以前，已有許多學者開始研究用數(shù)學方法解決最優(yōu)化問題。最優(yōu)化方法真正形成為科學方法則在17世紀以后。第5頁，共109頁，2023年，2月20日，星期六工作步驟①提出最優(yōu)化問題，收集有關數(shù)據(jù)和資料；②建立最優(yōu)化問題的數(shù)學模型,確定變量,列出目標函數(shù)和約束條件；③分析模型，選擇合適的最優(yōu)化方法；④求解，一般通過編制程序，用計算機求最優(yōu)解；⑤最優(yōu)解的檢驗和實施。第6頁，共109頁，2023年，2月20日，星期六模型的基本要素最優(yōu)化模型包括：變量、約束條件和目標函數(shù)①變量：指最優(yōu)化問題中待確定的某些量。變量可用x＝(x1，x2,…,xn)T表示。②約束條件:指在求最優(yōu)解時對變量的某些限制,包括技術上的約束、資源上的約束和時間上的約束等。約束條件可用gi(x)≤0表示i＝1,2，…，m，m表示約束條件數(shù)；③目標函數(shù)：最優(yōu)化有一定的評價標準。目標函數(shù)就是這種標準的數(shù)學描述，一般可用f(x)來表示，即f(x)=f(x1，x2,…,xn)。第7頁，共109頁，2023年，2月20日，星期六最優(yōu)化方法最優(yōu)化問題的求解方法可分成解析法、直接法、數(shù)值計算法和其他方法。①解析法：只適用于目標函數(shù)和約束條件有明顯的解析表達式的情況。求解方法是：先求出最優(yōu)的必要條件，得到一組方程或不等式，再求解這組方程或不等式，一般是用求導數(shù)的方法或變分法求出必要條件，通過必要條件將問題簡化，因此也稱間接法。第8頁，共109頁，2023年，2月20日，星期六②直接法：當目標函數(shù)較為復雜或者不能用變量顯函數(shù)描述時，無法用解析法求必要條件。可采用直接搜索的方法經(jīng)過若干次迭代搜索到最優(yōu)點。這種方法常常根據(jù)經(jīng)驗或通過試驗得到所需結果。對于一維搜索(單變量極值問題)，主要用消去法或多項式插值法；對于多維搜索問題(多變量極值問題)主要應用爬山法。第9頁，共109頁，2023年，2月20日，星期六③數(shù)值計算法：也是一種直接法。它以梯度法為基礎，所以是一種解析與數(shù)值計算相結合的方法。④其他方法：如網(wǎng)絡最優(yōu)化方法等第10頁，共109頁，2023年，2月20日，星期六最優(yōu)解的概念最優(yōu)化問題的解一般稱為最優(yōu)解。如果只考察約束集合中某一局部范圍內的優(yōu)劣情況，則解稱為局部最優(yōu)解。如果是考察整個約束集合中的情況，則解稱為總體最優(yōu)解。對于不同優(yōu)化問題，最優(yōu)解有不同的含意，因而還有專用的名稱。例如，在對策論和數(shù)理經(jīng)濟模型中稱為平衡解；在控制問題中稱為最優(yōu)控制或極值控制；在多目標決策問題中稱為非劣解（又稱帕雷托最優(yōu)解或有效解）。第11頁，共109頁，2023年，2月20日，星期六最優(yōu)化方法的應用最優(yōu)化可分為最優(yōu)設計、最優(yōu)計劃、最優(yōu)管理和最優(yōu)控制等四個方面。①最優(yōu)設計：世界各國工程技術界，尤其是飛機、造船、機械、建筑等部門都已廣泛應用最優(yōu)化方法于設計中，從各種設計參數(shù)的優(yōu)選到最佳結構形狀的選取等，結合有限元方法已使許多設計優(yōu)化問題得到解決。第12頁，共109頁，2023年，2月20日，星期六②最優(yōu)計劃：現(xiàn)代國民經(jīng)濟或部門經(jīng)濟的計劃，直至企業(yè)的發(fā)展規(guī)劃和年度生產(chǎn)計劃，尤其是農(nóng)業(yè)規(guī)劃、種植計劃、能源規(guī)劃和其他資源、環(huán)境和生態(tài)規(guī)劃的制訂，都已開始應用最優(yōu)化方法。一個重要的發(fā)展趨勢是幫助領導部門進行各種優(yōu)化決策。第13頁，共109頁，2023年，2月20日，星期六③最優(yōu)管理：一般在日常生產(chǎn)計劃的制訂、調度和運行中都可應用最優(yōu)化方法。隨著管理信息系統(tǒng)和決策支持系統(tǒng)的建立和使用，使最優(yōu)管理得到迅速的發(fā)展。④最優(yōu)控制：主要用于對各種控制系統(tǒng)的優(yōu)化。例如，導彈系統(tǒng)的最優(yōu)控制，能保證用最少燃料完成飛行任務，用最短時間達到目標;；再如飛機、船舶、電力系統(tǒng)等的最優(yōu)控制，化工、冶金等工廠的最佳工況的控制。第14頁，共109頁，2023年，2月20日，星期六一、組合最優(yōu)化TSP:（即旅行商問題）假設有n個城市，一個推銷員要在這n個城市推銷產(chǎn)品，要求經(jīng)過每個城市且僅有一次，如何選擇這條路徑，使路徑最短？二、動態(tài)規(guī)劃管道鋪設：有n個城市鋪設管道，要求管道到達每個城市，并且使總的費用最低。第15頁，共109頁，2023年，2月20日，星期六經(jīng)典極值問題包括：①無約束極值問題②約束條件下的極值問題第16頁，共109頁，2023年，2月20日，星期六1、無約束極值問題的數(shù)學模型2、約束條件下極值問題的數(shù)學模型

其中，極大值問題可以轉化為極小值問題來進行求解。如求：

可以轉化為：第17頁，共109頁，2023年，2月20日，星期六1、無約束極值問題的求解例1：求函數(shù)y=2x3+3x2-12x+14在區(qū)間[-3,4]上的最大值與最小值。解：令f(x)=y=2x3+3x2-12x+14 f’(x)=6x2+6x-12=6(x+2)(x-1)

解方程f’(x)=0，得到x1=-2，x2=1，又 由于f(-3)=23，f(-2)=34，f(1)=7，f(4)=142，綜上得，函數(shù)f(x)在x=4取得在[-3,4]上得最大值f(4)=142，在x=1處取得在[-3,4]上取得最小值f(1)=7第18頁，共109頁，2023年，2月20日，星期六有約束最優(yōu)化最優(yōu)化方法分類（一）線性最優(yōu)化：目標函數(shù)和約束條件都是線性的則稱為線性最優(yōu)化。

非線性最優(yōu)化：目標函數(shù)和約束條件如果含有非線性的，則稱為非線性最優(yōu)化。

（二）靜態(tài)最優(yōu)化：如果可能的方案與時間無關，則是靜態(tài)最優(yōu)化問題。

動態(tài)最優(yōu)化：如果可能的方案與時間有關，則是動態(tài)最優(yōu)化問題第19頁，共109頁，2023年，2月20日，星期六有約束最優(yōu)化問題的數(shù)學建模有約束最優(yōu)化模型一般具有以下形式：或

其中f(x)為目標函數(shù)，省略號表示約束式子，可以是等式約束，也可以是不等式約束。第20頁，共109頁，2023年，2月20日，星期六

根據(jù)目標函數(shù)，約束條件的特點將最優(yōu)化方法包含的主要內容大致如下劃分：線性規(guī)劃整數(shù)規(guī)劃非線性規(guī)劃動態(tài)規(guī)劃多目標規(guī)劃對策論最優(yōu)化方法主要內容第21頁，共109頁，2023年，2月20日，星期六兩個引例問題一：某工廠在計劃期內要安排生產(chǎn)I、II兩種產(chǎn)品，已知生產(chǎn)單位產(chǎn)品所需的設備臺時及A、B兩種原材料的消耗，如下表所示12kg40原材料B16kg04原材料A8臺時21設備III該工廠每生產(chǎn)一件產(chǎn)品I可獲利2元，每生產(chǎn)一件產(chǎn)品II可獲利3元。問應如何安排計劃使該工廠獲利最多？第22頁，共109頁，2023年，2月20日，星期六解：該工廠生產(chǎn)產(chǎn)品Ix1件，生產(chǎn)產(chǎn)品IIx2件，我們可建立如下數(shù)學模型：s.t.第23頁，共109頁，2023年，2月20日，星期六問題二：某廠每日8小時的產(chǎn)量不低于1800件.為了進行質量控制，計劃聘請兩種不同水平的檢驗員.一級檢驗員的標準為：速度25件/小時，正確率98%，計時工資4元/小時；二級檢驗員的標準為：速度15件/小時，正確率95%，計時工資3元/小時.檢驗員每錯檢一次，工廠要損失2元.為使總檢驗費用最省，該工廠應聘一級、二級檢驗員各幾名？解設需要一級和二級檢驗員的人數(shù)分別為x1、x2人,則應付檢驗員的工資為：因檢驗員錯檢而造成的損失為：第24頁，共109頁，2023年，2月20日，星期六故目標函數(shù)為：約束條件為：第25頁，共109頁，2023年，2月20日，星期六運用最優(yōu)化方法解決最優(yōu)化問題的一般方法步驟如下：①前期分析：分析問題，找出要解決的目標，約束條件，并確立最優(yōu)化的目標。②定義變量，建立最優(yōu)化問題的數(shù)學模型，列出目標函數(shù)和約束條件。③針對建立的模型，選擇合適的求解方法或數(shù)學軟件。④編寫程序，利用計算機求解。⑤對結果進行分析，討論諸如：結果的合理性、正確性，算法的收斂性，模型的適用性和通用性，算法效率與誤差等。第26頁，共109頁，2023年，2月20日，星期六線性規(guī)劃某豆腐店用黃豆制作兩種不同口感的豆腐出售。制作口感較鮮嫩的豆腐每千克需要0.3千克一級黃豆及0.5千克二級黃豆，售價10元；制作口感較厚實的豆腐每千克需要0.4千克一級黃豆及0.2千克二級黃豆，售價5元?，F(xiàn)小店購入9千克一級黃豆和8千克二級黃豆。問：應如何安排制作計劃才能獲得最大收益。第27頁，共109頁，2023年，2月20日，星期六一、問題前期分析該問題是在不超出制作兩種不同口感豆腐所需黃豆總量條件下合理安排制作計劃，使得售出各種豆腐能獲得最大收益。二、模型假設1．假設制作的豆腐能全部售出。2．假設豆腐售價無波動。第28頁，共109頁，2023年，2月20日，星期六變量假設：設計劃制作口感鮮嫩和厚實的豆腐各x1千克和x2千克，可獲得收益R元。目標函數(shù)：獲得的總收益最大?？偸找婵杀硎緸椋菏芤患夵S豆數(shù)量限制：受二級黃豆數(shù)量限制：第29頁，共109頁，2023年，2月20日，星期六綜上分析，得到該問題的線性規(guī)劃模型s.t.第30頁，共109頁，2023年，2月20日，星期六用Matlab編程求解程序如下：[X,FVAL,EXITFLAG,OUTPUT]=LINPROG(f,A,b)f=-[105];A=[0.30.4;0.50.2];B=[9;8];[X,FVAL,EXITFLAG,OUTPUT]=LINPROG(f,A,b)X=10.000015.0000FVAL=-175.0000第31頁，共109頁，2023年，2月20日，星期六用YALMIP編程求解程序如下：x=sdpvar(1,2);C=[105];a=[0.30.4;0.50.2];b=[98];f=C*x';F=set(0<=x<=inf);F=F+set(a*x'<=b');solvesdp(F,-f)double(f)double(x)

ans=175ans=1015第32頁，共109頁，2023年，2月20日，星期六線性規(guī)劃

設某工廠有甲、乙、丙、丁四個車間，生產(chǎn)A、B、C、D、E、F六種產(chǎn)品。根據(jù)機床性能和以前的生產(chǎn)情況，得知每單位產(chǎn)品所需車間的工作小時數(shù)、每個車間在一個季度工作小時的上限以及單位產(chǎn)品的利潤，如下表所示(例如，生產(chǎn)一個單位的A產(chǎn)品，需要甲、乙、丙三個車間分別工作1小時、2小時和4小時)問：每種產(chǎn)品各應該每季度生產(chǎn)多少，才能使這個工廠每季度生產(chǎn)利潤達到最大。

第33頁，共109頁，2023年，2月20日，星期六生產(chǎn)單位產(chǎn)品所需車間的工作小時數(shù)ABCDEF每個車間一個季度工作小時的上限甲111323500乙255500丙425500丁138500利潤(百元)4.02.45.55.04.58.5第34頁，共109頁，2023年，2月20日，星期六這是一個典型的最優(yōu)化問題，屬線性規(guī)劃。假設：產(chǎn)品合格且能及時銷售出去；工作無等待情況等變量說明：

xj：第j種產(chǎn)品的生產(chǎn)量（j=1,2,……,6）

aij：第i車間生產(chǎn)單位第j種產(chǎn)品所需工作小時數(shù)（i=1,2,3,4;j=1,2,……,6）

bi：第i車間的最大工作上限

cj：第j種產(chǎn)品的單位利潤則：cjxj為第j種產(chǎn)品的利潤總額；

aijxj表示第i車間生產(chǎn)第j種產(chǎn)品所花時間總數(shù)；第35頁，共109頁，2023年，2月20日，星期六于是，我們可建立如下數(shù)學模型：s.t.計算結果：Z(百元)x1x2x3x4x5x6132000604010040第36頁，共109頁，2023年，2月20日，星期六運輸問題

要從甲城調出蔬菜2000噸，從乙城調出蔬菜2500噸，從丙地調出3000噸，分別供應A地2000噸，B地2300噸、C地1800噸、D地1400噸，已知每噸運費如下表：供應單位調出單位ABCD甲21271340乙45513720丙32352030問：如何調撥才能使運費最省？第37頁，共109頁，2023年，2月20日，星期六可以建立如下模型：s.t.第38頁，共109頁，2023年，2月20日，星期六整數(shù)規(guī)劃

最優(yōu)化問題中的所有變量均為整數(shù)時，這類問題稱為整數(shù)規(guī)劃問題。如果線性規(guī)劃中的所有變量均為整數(shù)時，稱這類問題為線性整數(shù)規(guī)劃問題。整數(shù)規(guī)劃可分為線性整數(shù)規(guī)劃和非線性整數(shù)規(guī)劃，以及混合整數(shù)規(guī)劃等。如果決策變量的取值要么為0，要么為1，則這樣的規(guī)劃問題稱為0－1規(guī)劃。第39頁，共109頁，2023年，2月20日，星期六例1某鋼廠兩個煉鋼爐同時各用一種方法煉鋼。第一種煉法每爐用a小時，第二種用b小時（包括清爐時間）。假定這兩種煉法，每爐出鋼都是k公斤，而煉1公斤鋼的平均燃料費第一法為m元，第二法為n元。若要求在c小時內煉鋼公斤數(shù)不少于d，試列出燃料費最省的兩種方法的分配方案的數(shù)學模型。第40頁，共109頁，2023年，2月20日，星期六設用第一種煉法煉鋼x1爐，第二種煉鋼x2爐s.t.第41頁，共109頁，2023年，2月20日，星期六引例2.資源分配問題：某個中型的百貨商場要求售貨人員每周工作5天，連續(xù)休息2天，工資200元/周，已知對售貨人員的需求經(jīng)過統(tǒng)計分析如下表，問如何安排可使配備銷售人員的總費用最少？星期一二三四五六日所需售貨員人數(shù)18151216191412開始休息的人數(shù)x1x2x3x4x5x6x7

設決策變量如上，可建立如下模型：第42頁，共109頁，2023年，2月20日，星期六第43頁，共109頁，2023年，2月20日，星期六非線性規(guī)劃非線性規(guī)劃問題的一般數(shù)學模型：其中，，為目標函數(shù)，為約束函數(shù)，這些函數(shù)中至少有一個是非線性函數(shù)。第44頁，共109頁，2023年，2月20日，星期六應用實例：供應與選址

某公司有6個建筑工地要開工，每個工地的位置（用平面坐標系a，b表示，距離單位：km）及水泥日用量d(t)由下表給出．目前有兩個臨時料場位于A(5,1)，B(2,7)，日儲量各有20t．假設從料場到工地之間均有直線道路相連．（1）試制定每天的供應計劃，即從A，B兩料場分別向各工地運送多少水泥，可使總的噸千米數(shù)最?。?）為了進一步減少噸千米數(shù)，打算舍棄兩個臨時料場，改建兩個新的，日儲量各為20t，問應建在何處，節(jié)省的噸千米數(shù)有多大？第45頁，共109頁，2023年，2月20日，星期六（一）建立模型

記工地的位置為(ai，bi)，水泥日用量為di，i=1,…,6;料場位置為(xj，yj)，日儲量為ej，j=1,2；料場j向工地i的運送量為Xij．當用臨時料場時決策變量為：Xij，當不用臨時料場時決策變量為：Xij，xj，yj．第46頁，共109頁，2023年，2月20日，星期六多目標規(guī)劃引例1.投資問題某公司在一段時間內有a(億元)的資金可用于建廠投資。若可供選擇的項目記為1,2,…,m。而且一旦對第i個項目投資就用去ai億元；而這段時間內可得收益ci億元。問如何確定最佳的投資方案？

最佳投資方案：投資最少，收益最大！第47頁，共109頁，2023年，2月20日，星期六投資最少：約束條件為：收益最大：第48頁，共109頁，2023年，2月20日，星期六引例2：生產(chǎn)問題某工廠生產(chǎn)兩種產(chǎn)品，產(chǎn)品A每單位利潤為10元，而產(chǎn)品B每單位利潤為8元；產(chǎn)品A每單位需3小時裝配時間而B為2小時，每周總裝配有效時間為120小時。工廠允許加班，但加班生產(chǎn)出來的產(chǎn)品利潤要減去1元。根據(jù)最近的合同，廠商每周最少的向用戶提供兩種產(chǎn)品各30單位。要求：①必須遵守合同；②盡可能少加班；③利潤最大。問應怎樣安排生產(chǎn)？x1：每周正常時間生產(chǎn)得A產(chǎn)品的數(shù)量；x2：每周加班時間生產(chǎn)得A產(chǎn)品的數(shù)量；x3：每周正常時間生產(chǎn)得B產(chǎn)品的數(shù)量；x4：每周加班時間生產(chǎn)得B產(chǎn)品的數(shù)量；第49頁，共109頁，2023年，2月20日，星期六目標函數(shù)（有兩個）：第50頁，共109頁，2023年，2月20日，星期六常用無約束最優(yōu)化方法常用約束最優(yōu)化方法第51頁，共109頁，2023年，2月20日，星期六最優(yōu)化問題的迭代解法

（一）迭代方法

在經(jīng)典極值問題中，解析法雖然具有概念簡明,計算精確等優(yōu)點，但因只能適用于簡單或特殊問題的尋優(yōu),對于復雜的工程實際問題通常無能為力，所以極少使用。最優(yōu)化問題的迭代算法是指：從某一選定的初始點出發(fā)，根據(jù)目標函數(shù)、約束函數(shù)在該點的某些信息，確定本次迭代的一個搜索方向和適當?shù)牟介L，從而到達一個新點，用式子表示即為第52頁，共109頁，2023年，2月20日，星期六

式中,——前一次已取得的迭代點，在開始計算時為迭代初始點；

——新的迭代點；

——第k次迭代計算的搜索方向；

——第k次迭代計算的步長因子．(1.2)第53頁，共109頁，2023年，2月20日，星期六

按照式（1.2）進行一系列迭代計算所根據(jù)的思想是所謂的“爬山法”，就是將尋求函數(shù)小點（無約束或約束極小點）的過程比喻為向“山”的頂峰攀登的過程，始終保持向“高”的方向前進，直至達到“山頂”。當然“山頂”可以理目標函數(shù)的極大值，也可以理解為極小值，前者稱為上升算法，后者稱為下降算法。這兩種算法都有一個共同的特點，就是每前進一步都應該使目標函數(shù)有所改善，同時還要為下一步移動的搜索方向提供有用的信息。如果是下降算法，則序列迭代點的目標函數(shù)值必須滿足下列關系第54頁，共109頁，2023年，2月20日，星期六如果是求一個約束的極小點，則每一次迭代的新點都應該在約束可行域內，即下圖為迭代過程第55頁，共109頁，2023年，2月20日，星期六（二）收斂速度與計算終止準則（1）收斂速度作為一個算法A，能夠收斂于問題的最優(yōu)解當然是必要的，但光能收斂還不夠，還必須能以較快的速度收斂，這才是好的算法．定義1.1設由算法A產(chǎn)生的迭代點列在某種“||·||”的意義下收斂于點，即,若存在實數(shù)及一個與迭代次數(shù)無關的常數(shù)使得則算法A產(chǎn)生的迭代點列叫做具有階收斂速度，或算法A叫做是階收斂的，特別地：第56頁，共109頁，2023年，2月20日，星期六①當，迭代點列稱為具有線性收斂速度或算法A稱為線性收斂的．②當，或時，迭代點列叫做具有超線性收斂速度或稱算法A是超線性收斂．③當時，迭代點列叫做具有二階收斂速度或算法A是二階收斂的．一般認為，具有超線性收斂或二階收斂的算法是較快速的算法．第57頁，共109頁，2023年，2月20日，星期六(2)計算終止準則用迭代方法尋優(yōu)時，其迭代過程總不能無限制地進行下去，那么什么時候截斷這種迭代呢？這就是迭代什么時候終止的問題。從理論上說，當然希望最終迭代點到達理論極小點，或者使最終迭代點與理論極小點之間的距離足夠小時才終止迭代．但是這在實際上是辦不到的．因為對于一個待求的優(yōu)化問題，其理論極小點在哪里并不知道．所知道的只是通過迭代計算獲得的迭代點列，因此只能從點列所提供的信息來判斷是否應該終止迭代。對于無約束優(yōu)化問題通常采用的迭代終止準則有以下幾種：第58頁，共109頁，2023年，2月20日，星期六①點距準則相鄰兩迭代點之間的距離已達到充分小，即式中是一個充分小正數(shù)，代表計算精度．②函數(shù)下降量準則相鄰兩迭代點的函數(shù)值下降量已達到充分?。敃r，可用函數(shù)絕對下降量準則當時，可用函數(shù)相對下降量準則③梯度準則目標函數(shù)在迭代點的梯度已達到充分小，即這一準則對于定義域上的凸函數(shù)是完全正確的．若是非凸函數(shù)，有可能導致誤把駐點作為最優(yōu)點。對于約束優(yōu)化問題，不同的優(yōu)化方法有各自的終止準則．第59頁，共109頁，2023年，2月20日，星期六綜上所述，優(yōu)化算法的基本迭代過程如下：①選定初始點，置．②按照某種規(guī)則確定搜索方向．③按某種規(guī)則確定使得④計算⑤判定是否滿足終止準則．若滿足，則打印和,停機；否則置,轉②．第60頁，共109頁，2023年，2月20日，星期六NYX是否滿足終止準則輸出X，f(X)開始結束選定X0確定P確定t，使得f(X0+tP)<f(X0)X=X0+tPX0=X上述算法框圖如右圖第61頁，共109頁，2023年，2月20日，星期六一維搜索法§搜索區(qū)間及其確定方法§對分法§Newton切線法§黃金分割法§拋物線插值法第62頁，共109頁，2023年，2月20日，星期六由前面關于求解最優(yōu)化問題概述中我們知道，從已知迭代點出發(fā)按照基本迭代格式來求解最優(yōu)化問題，其關鍵在于如何構造一個搜索方向和確定一個步長使下一迭代點處的目標函數(shù)值下降，即?，F(xiàn)在我們來討論，當搜索方向已經(jīng)確定的情況下，如何來確定步長？步長因子的選取有多種方法，如取步長為常數(shù)，但這樣選取的步長并不最好，如何選取最好步長呢？實際計算通常采用一維搜索來確定最優(yōu)步長。一維搜索法第63頁，共109頁，2023年，2月20日，星期六對無約束最優(yōu)化問題當已知迭代點和下降方向時，要確定適當?shù)牟介L使比有所下降，即相當于對于參量的函數(shù)要在區(qū)間上選取使即．由于這種從已知點出發(fā)，沿某一下降的探索方向來確定步長的問題，實質上是單變量函數(shù)關于變量的一維搜索選取問題，故通常叫做一維搜索．

一維搜索法第64頁，共109頁，2023年，2月20日，星期六按這種方法確定的步長又稱為最優(yōu)步長，這種方法的優(yōu)點是：它使目標函數(shù)值在搜索方向上下降得最多．今后為了簡便起見，我們用記號

表示從點出發(fā)沿方向對目標函數(shù)作直線搜索所得到的極小點是其中l(wèi)和s分別是Linearsearch(直線搜索)兩詞的詞首,在目標函數(shù)已確定的條件下(4.1)等價于如下兩式：一維搜索法第65頁，共109頁，2023年，2月20日，星期六下面進一步解釋迭代點的空間位置。容易證明，若從出發(fā)，沿方向進步一維搜索得極小點則該點處的梯度方向與搜索方向之間應滿足事實上，設對求導有令即所以一維搜索法第66頁，共109頁，2023年，2月20日，星期六式（4.2）的幾何意義是明顯的:從某一點出發(fā)沿方向對目標函數(shù)作直線搜索,所得到的極小點為式（4.2）指出，梯度必與搜索方向正交.又因為與目標函數(shù)過點的等值面正交，所以進一步看到，搜索方向與這個等值面在點處相切（如圖所示）．

一維搜索法第67頁，共109頁，2023年，2月20日，星期六搜索區(qū)間及其確定方法一、搜索區(qū)間

設一維最優(yōu)化問題為為了求解問題(4.3),我們引入如下的搜索區(qū)間概念．定義4.1若存在閉區(qū)間使則稱是問題(4.3)的搜索區(qū)間．簡言之，一個一維最優(yōu)化問題的搜索區(qū)間，就是包含該問題最優(yōu)解的一個閉區(qū)間．通常，在進行一維搜索時，一般要先確定出問題的一個搜索區(qū)間，然后再此區(qū)間中進行搜索求解．第68頁，共109頁，2023年，2月20日，星期六二、加步探索法下面，介紹一個確定問題(4.3)的搜索區(qū)間的簡單方法．這個方法的思想是：先選定一個初始點或和初始步長然后，沿著軸的正方向探索前進一個步長，得到新點若目標函數(shù)在新點處的值是下降了，即則下一步就從新點出發(fā)加大步長，再向前探索。若目標函數(shù)在新點處的值上升，即則下一步仍以為出發(fā)點以原步長開始向軸的負方向同樣探索。當達到目標函數(shù)上升的點時，就停止探索，這時便得到問題（4.3）的一個搜索區(qū)間．這種以加大步長進行探索來尋找探索區(qū)間的方法叫加步探索法。

搜索區(qū)間及其確定方法第69頁，共109頁，2023年，2月20日，星期六加步探索法算法的計算步驟：(1)選取初始數(shù)據(jù)．選取初始點計算給出初始步長加步系數(shù)令(2)比較目標函數(shù)值．令計算，若轉(3)。否則轉(4)。(3)加大探索步長,令同時令轉(2)．(4)反向探索,若轉換探索方向,令轉(2);否則,停止迭代,令輸出搜索區(qū)間及其確定方法第70頁，共109頁，2023年，2月20日，星期六

加步探索法算法的流程圖如圖所示

開始選取初始點t0，初始步長h0>0，加步系數(shù)α>1，令k=0φ0=φ(t0)，比較目標函數(shù)值tk+1=tk+hk,φk+1=φ(tk+1)a=min{t，tk+1}b=max{t，tk+1}結束NYNYφk+1<φkhk+1=hk,t=tk,tk=tk+1,φk=φk+1,k=k+1k=0hk=－h(huán)k,k=k+1第71頁，共109頁，2023年，2月20日，星期六

在加步探索法中，一般建議若能估計問題（4.3）的最優(yōu)解的大體位置的話，初始點要盡量取接近于問題（4.3）的最優(yōu)解.在具體運用上述加步探索法時，有時還要考慮一些細節(jié)問題．例如，當探索得到新點處的目標函數(shù)值和出發(fā)點處相同時，以及初始步長應如何選取等，都需作適當處理．搜索區(qū)間及其確定方法第72頁，共109頁，2023年，2月20日，星期六三、單谷區(qū)間與單谷函數(shù)由于以后要介紹的一些維搜索方法，主要適用于問題（4.3）在搜索區(qū)間中只有唯一的最優(yōu)解的情況，為此，我們再給出下面單谷區(qū)間與單谷函數(shù)概念．定義4.2設閉區(qū)間若存在點使得在上嚴格遞減，在上嚴格遞增，則稱是函數(shù)的單谷區(qū)間，是上單谷函數(shù)．

搜索區(qū)間及其確定方法第73頁，共109頁，2023年，2月20日，星期六由定義4.2易知，一個區(qū)間是某函數(shù)的單谷區(qū)間意味著，在該區(qū)間中函數(shù)只有一個“凹谷”（極小值）．例如，左圖中的是的單谷區(qū)間，也即是上的單谷函數(shù)．右圖中的不是的單谷區(qū)間，即不是上的單谷函數(shù)．

搜索區(qū)間及其確定方法第74頁，共109頁，2023年，2月20日，星期六另外，從定義4.2還可知，某區(qū)間上的單谷函數(shù)在該區(qū)間上不一定是連續(xù)函數(shù)，而凸函數(shù)在所給區(qū)間上必然是單谷函數(shù)（如左圖所示）．由定義4.1和定義4.2知，函數(shù)的單谷區(qū)間總是相應問題（4.3）的一個搜索區(qū)間（如左圖所示），但反之不然（如右圖所示）．搜索區(qū)間及其確定方法第75頁，共109頁，2023年，2月20日，星期六單谷區(qū)間和單谷函數(shù)有如下有用的性質：定理4.1

設是的單谷區(qū)間，任取并且．（1）若有，則是的單谷區(qū)間．（2）若有，則是的單谷區(qū)間．定理4.1說明，經(jīng)過函數(shù)值的比較可以把單谷區(qū)間縮短為一個較小的單谷區(qū)間．換句話說利用這個定理可以把搜索區(qū)間無限縮小，從而求到極小點.以下介紹的幾種一維搜索方法都是利用這個定理通過不斷地縮短搜索區(qū)間的長度，來求得一維最優(yōu)化問題的近似最優(yōu)解．搜索區(qū)間及其確定方法第76頁，共109頁，2023年，2月20日，星期六一、對分法基本原理求解一維最優(yōu)化問題一般可先確定它的一個有限搜索區(qū)間，把問題化為求解問題，然后通過不斷縮短區(qū)間的長度，最后求得最優(yōu)解．對分法第77頁，共109頁，2023年，2月20日，星期六設在已獲得的搜索區(qū)間內具有連續(xù)的一階導數(shù)．因為在上可微，故在上連續(xù)，由此知在上有最小值．令，總可求得極小點．不妨設在上是單減函數(shù)；在上是單增函數(shù)。所以時，，故；當時，亦即．對分法的原理如圖．

對分法第78頁，共109頁，2023年，2月20日，星期六二、對分法迭代步驟已知，表達式，終止限．確定初始搜索區(qū)間，要求(2)計算的中點．(3)若，則，轉(4)；若，則，轉(5)；若，則，轉(4)．(4)若，則，轉(5)；否則轉(2)．(5)打印，停機．對分法第79頁，共109頁，2023年，2月20日，星期六Y開始確定[ab],要求c=(a+b)/2b=ct*=(a+b)/2輸出t*結束T*=cNa=cNYNY對分法的計算流程如圖所示第80頁，共109頁，2023年，2月20日，星期六三、對分法有關說明對分法每次迭代都取區(qū)間的中點a.若這點的導數(shù)值小于零，說明的根位于右半?yún)^(qū)間中，因此去掉左半?yún)^(qū)間；b.若中點導數(shù)值大于零，則去掉右半?yún)^(qū)間；c.若中點導數(shù)值正好等于零，則該點就是極小點．因為每次迭代都使原區(qū)間縮短一半，所以稱為對分法或二分法．對分法第81頁，共109頁，2023年，2月20日，星期六Newton切線法一、Newton切線法基本原理設在已獲得的搜索區(qū)間內具有連續(xù)二階導數(shù)，求．因為在上可微，故在上有最小值，令．第82頁，共109頁，2023年，2月20日，星期六下面不妨設在區(qū)間中經(jīng)過次迭代已求得方程的一個近似根。過作曲線的切線,其方程是

然后用這條切線與橫軸交點的橫坐標作為根的新的近似（如圖）．它可由方程（4.4）在令的解出來，即這就是Newton切線法迭代公式．

Newton切線法第83頁，共109頁，2023年，2月20日，星期六二、Newton切線法迭代步驟已知，表達式，終止限．確定初始搜索區(qū)間，要求選定．計算．若，則，轉（3）；否則轉（5）．打印，停機．Newton切線法第84頁，共109頁，2023年，2月20日，星期六Newton切線法的計算流程如圖所示第85頁，共109頁，2023年，2月20日，星期六三、Newton切線法有關說明這種方法一旦用好，收斂速度是很高的．如果初始點選得適當，通常經(jīng)過幾次迭代就可以得到滿足一般精度要求的結果.但是它也有缺點：第一，需要求二階導數(shù)．如果在多維最優(yōu)化問題的一維搜索中使用這種方法，就要涉及Hesse矩陣，一般是難于求出的．Newton切線法第86頁，共109頁，2023年，2月20日，星期六第二，當曲線在上有較復雜的彎曲時，這種方法也往往失效．如圖(a)所示的迭代：結果跳出.迭代或者發(fā)散，或者找到的根并不是我們想要的結果．第三，即使曲線比較正常，在中或者上凹或者下凹，初始點的選取也必須適當．在圖（b）的情況下，曲線上凹，應選點b作為初始點；而在圖（c）的情況下，曲線下凹，應選點a為初始點．否則都可能失?。甆ewton切線法第87頁，共109頁，2023年，2月20日，星期六黃金分割法一、黃金分割法基本原理要介紹黃金分割法有必要回顧一下古老的黃金分割問題。所謂黃金分割就是將一線段分為二段的方法。這樣分后，要求整段長L與較長段x的比值正好等于較長段x與較短段的比值(如圖)第88頁，共109頁，2023年，2月20日，星期六于是則解得由此可見長段的長度應為全長的0.618倍，而短段的長度應為全長的0.382倍．因為古代的人們認為按0.618的比率來分割線段是最協(xié)調，勝似黃金，故稱之為黃金分割．黃金分割法第89頁，共109頁，2023年，2月20日，星期六用黃金分割法進行一維搜索，其基本思想是在單谷區(qū)間內適當插入兩點，由此把區(qū)間分為三段，然后再通過比較這兩點函數(shù)值大小，就可以確定是刪去最左段還是最右段，或者同時刪去左右兩段保留中間段．如此繼續(xù)下去可將單谷區(qū)間無限縮?。S金分割法第90頁，共109頁，2023年，2月20日，星期六二、黃金分割法迭代步驟現(xiàn)在提出一個問題，就在上如何選取二點使得迭代次數(shù)最小而區(qū)間縮短最快？要解決這個問題，人們想到對區(qū)間選二點等價于將區(qū)間長度進行黃金分割，也就是將第一個搜索點取在的0.618處，第二個搜索點取成的對稱點即的0.382處（如圖所示）

黃金分割法第91頁，共109頁，2023年，2月20日，星期六即要求接著計算與的值，并根據(jù)與的值的大小關系分情況討論：（1）若,說明是好點，于是把區(qū)間劃掉，保留，則內有一保留點，置新的區(qū)間；（2）若，說明是好點，于是應將劃掉，保留,則內有保留點,置新的區(qū)間．.黃金分割法第92頁，共109頁，2023年，2月20日，星期六(3)若則應具體分析,看極小點可能在哪一邊再決定取舍，在一般情況下，可同時劃掉和僅保留中間的重置新的區(qū)間．接下來是在留下的區(qū)間內找好點．重復上面的步驟，直到搜索區(qū)間小于給定的允許誤差為止。這樣就得到黃金分割法迭代算法：黃金分割法第93頁，共109頁，2023年，2月20日，星期六已知，常數(shù)0.382，終止限．(1)確定的初始搜索區(qū)間．(2)計算．(3)計算．(4)若,則打印，停機；否則，轉(5)．(5)判別是否滿足：若滿足，則置，然后轉(3)；否則，置然后轉(4)．

黃金分割法第94頁，共109頁，2023年，2月20日，星期六黃金分割法算法流程如圖所示．第95頁，共109頁，2023年，2月20日，星期六三、黃金分割法有關說明黃金分割法是通過所選試點的函數(shù)值而逐步縮短單谷區(qū)間來搜索最優(yōu)點．該方法適用于單谷區(qū)間上的任何函數(shù)，甚至可以是不連續(xù)函數(shù)，因此這種算法屬于直接法，適用相當廣泛．

黃金分割法第96頁，共109頁，2023年，2月20日，星期六拋物線插值法一、拋物線插值法基本原理考慮一維搜索問題假設其中是定義在區(qū)間上的單峰函數(shù)．首先用試探法在上找一點，使之滿足