最優(yōu)化方法及控制應(yīng)用

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

其中，極大值問題可以轉(zhuǎn)化為極小值問題來進(jìn)行求解。如求：

可以轉(zhuǎn)化為：第十七頁，共一百零九頁，2022年，8月28日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第十八頁，共一百零九頁，2022年，8月28日有約束最優(yōu)化最優(yōu)化方法分類（一）線性最優(yōu)化：目標(biāo)函數(shù)和約束條件都是線性的則稱為線性最優(yōu)化。

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

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

動(dòng)態(tài)最優(yōu)化：如果可能的方案與時(shí)間有關(guān)，則是動(dòng)態(tài)最優(yōu)化問題第十九頁，共一百零九頁，2022年，8月28日有約束最優(yōu)化問題的數(shù)學(xué)建模有約束最優(yōu)化模型一般具有以下形式：或

其中f(x)為目標(biāo)函數(shù)，省略號(hào)表示約束式子，可以是等式約束，也可以是不等式約束。第二十頁，共一百零九頁，2022年，8月28日

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

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

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

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

aij：第i車間生產(chǎn)單位第j種產(chǎn)品所需工作小時(shí)數(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í)間總數(shù)；第三十五頁，共一百零九頁，2022年，8月28日于是，我們可建立如下數(shù)學(xué)模型：s.t.計(jì)算結(jié)果：Z(百元)x1x2x3x4x5x6132000604010040第三十六頁，共一百零九頁，2022年，8月28日運(yùn)輸問題

要從甲城調(diào)出蔬菜2000噸，從乙城調(diào)出蔬菜2500噸，從丙地調(diào)出3000噸，分別供應(yīng)A地2000噸，B地2300噸、C地1800噸、D地1400噸，已知每噸運(yùn)費(fèi)如下表：供應(yīng)單位調(diào)出單位ABCD甲21271340乙45513720丙32352030問：如何調(diào)撥才能使運(yùn)費(fèi)最省？第三十七頁，共一百零九頁，2022年，8月28日可以建立如下模型：s.t.第三十八頁，共一百零九頁，2022年，8月28日整數(shù)規(guī)劃

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

設(shè)決策變量如上，可建立如下模型：第四十二頁，共一百零九頁，2022年，8月28日第四十三頁，共一百零九頁，2022年，8月28日非線性規(guī)劃非線性規(guī)劃問題的一般數(shù)學(xué)模型：其中，，為目標(biāo)函數(shù)，為約束函數(shù)，這些函數(shù)中至少有一個(gè)是非線性函數(shù)。第四十四頁，共一百零九頁，2022年，8月28日應(yīng)用實(shí)例：供應(yīng)與選址

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

記工地的位置為(ai，bi)，水泥日用量為di，i=1,…,6;料場位置為(xj，yj)，日儲(chǔ)量為ej，j=1,2；料場j向工地i的運(yùn)送量為Xij．當(dāng)用臨時(shí)料場時(shí)決策變量為：Xij，當(dāng)不用臨時(shí)料場時(shí)決策變量為：Xij，xj，yj．第四十六頁，共一百零九頁，2022年，8月28日多目標(biāo)規(guī)劃引例1.投資問題某公司在一段時(shí)間內(nèi)有a(億元)的資金可用于建廠投資。若可供選擇的項(xiàng)目記為1,2,…,m。而且一旦對第i個(gè)項(xiàng)目投資就用去ai億元；而這段時(shí)間內(nèi)可得收益ci億元。問如何確定最佳的投資方案？

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

（一）迭代方法

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

式中,——前一次已取得的迭代點(diǎn)，在開始計(jì)算時(shí)為迭代初始點(diǎn)；

——新的迭代點(diǎn)；

——第k次迭代計(jì)算的搜索方向；

——第k次迭代計(jì)算的步長因子．(1.2)第五十三頁，共一百零九頁，2022年，8月28日

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

一維搜索法第六十四頁，共一百零九頁，2022年，8月28日按這種方法確定的步長又稱為最優(yōu)步長，這種方法的優(yōu)點(diǎn)是：它使目標(biāo)函數(shù)值在搜索方向上下降得最多．今后為了簡便起見，我們用記號(hào)

表示從點(diǎn)出發(fā)沿方向?qū)δ繕?biāo)函數(shù)作直線搜索所得到的極小點(diǎn)是其中l(wèi)和s分別是Linearsearch(直線搜索)兩詞的詞首,在目標(biāo)函數(shù)已確定的條件下(4.1)等價(jià)于如下兩式：一維搜索法第六十五頁，共一百零九頁，2022年，8月28日下面進(jìn)一步解釋迭代點(diǎn)的空間位置。容易證明，若從出發(fā)，沿方向進(jìn)步一維搜索得極小點(diǎn)則該點(diǎn)處的梯度方向與搜索方向之間應(yīng)滿足事實(shí)上，設(shè)對求導(dǎo)有令即所以一維搜索法第六十六頁，共一百零九頁，2022年，8月28日式（4.2）的幾何意義是明顯的:從某一點(diǎn)出發(fā)沿方向?qū)δ繕?biāo)函數(shù)作直線搜索,所得到的極小點(diǎn)為式（4.2）指出，梯度必與搜索方向正交.又因?yàn)榕c目標(biāo)函數(shù)過點(diǎn)的等值面正交，所以進(jìn)一步看到，搜索方向與這個(gè)等值面在點(diǎn)處相切（如圖所示）．

一維搜索法第六十七頁，共一百零九頁，2022年，8月28日搜索區(qū)間及其確定方法一、搜索區(qū)間

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

搜索區(qū)間及其確定方法第六十九頁，共一百零九頁，2022年，8月28日加步探索法算法的計(jì)算步驟：(1)選取初始數(shù)據(jù)．選取初始點(diǎn)計(jì)算給出初始步長加步系數(shù)令(2)比較目標(biāo)函數(shù)值．令計(jì)算，若轉(zhuǎn)(3)。否則轉(zhuǎn)(4)。(3)加大探索步長,令同時(shí)令轉(zhuǎn)(2)．(4)反向探索,若轉(zhuǎn)換探索方向,令轉(zhuǎn)(2);否則,停止迭代,令輸出搜索區(qū)間及其確定方法第七十頁，共一百零九頁，2022年，8月28日

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

開始選取初始點(diǎn)t0，初始步長h0>0，加步系數(shù)α>1，令k=0φ0=φ(t0)，比較目標(biāo)函數(shù)值tk+1=tk+hk,φk+1=φ(tk+1)a=min{t，tk+1}b=max{t，tk+1}結(jié)束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第七十一頁，共一百零九頁，2022年，8月28日

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

搜索區(qū)間及其確定方法第七十三頁，共一百零九頁，2022年，8月28日由定義4.2易知，一個(gè)區(qū)間是某函數(shù)的單谷區(qū)間意味著，在該區(qū)間中函數(shù)只有一個(gè)“凹谷”（極小值）．例如，左圖中的是的單谷區(qū)間，也即是上的單谷函數(shù)．右圖中的不是的單谷區(qū)間，即不是上的單谷函數(shù)．

搜索區(qū)間及其確定方法第七十四頁，共一百零九頁，2022年，8月28日另外，從定義4.2還可知，某區(qū)間上的單谷函數(shù)在該區(qū)間上不一定是連續(xù)函數(shù)，而凸函數(shù)在所給區(qū)間上必然是單谷函數(shù)（如左圖所示）．由定義4.1和定義4.2知，函數(shù)的單谷區(qū)間總是相應(yīng)問題（4.3）的一個(gè)搜索區(qū)間（如左圖所示），但反之不然（如右圖所示）．搜索區(qū)間及其確定方法第七十五頁，共一百零九頁，2022年，8月28日單谷區(qū)間和單谷函數(shù)有如下有用的性質(zhì)：定理4.1

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

對分法第七十八頁，共一百零九頁，2022年，8月28日二、對分法迭代步驟已知，表達(dá)式，終止限．確定初始搜索區(qū)間，要求(2)計(jì)算的中點(diǎn)．(3)若，則，轉(zhuǎn)(4)；若，則，轉(zhuǎn)(5)；若，則，轉(zhuǎn)(4)．(4)若，則，轉(zhuǎn)(5)；否則轉(zhuǎn)(2)．(5)打印，停機(jī)．對分法第七十九頁，共一百零九頁，2022年，8月28日Y開始確定[ab],要求c=(a+b)/2b=ct*=(a+b)/2輸出t*結(jié)束T*=cNa=cNYNY對分法的計(jì)算流程如圖所示第八十頁，共一百零九頁，2022年，8月28日三、對分法有關(guān)說明對分法每次迭代都取區(qū)間的中點(diǎn)a.若這點(diǎn)的導(dǎo)數(shù)值小于零，說明的根位于右半?yún)^(qū)間中，因此去掉左半?yún)^(qū)間；b.若中點(diǎn)導(dǎo)數(shù)值大于零，則去掉右半?yún)^(qū)間；c.若中點(diǎn)導(dǎo)數(shù)值正好等于零，則該點(diǎn)就是極小點(diǎn)．因?yàn)槊看蔚际乖瓍^(qū)間縮短一半，所以稱為對分法或二分法．對分法第八十一頁，共一百零九頁，2022年，8月28日Newton切線法一、Newton切線法基本原理設(shè)在已獲得的搜索區(qū)間內(nèi)具有連續(xù)二階導(dǎo)數(shù)，求．因?yàn)樵谏峡晌?，故在上有最小值，令．第八十二頁，共一百零九頁?022年，8月28日下面不妨設(shè)在區(qū)間中經(jīng)過次迭代已求得方程的一個(gè)近似根。過作曲線的切線,其方程是

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

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

黃金分割法第九十一頁，共一百零九頁，2022年，8月28日即要求接著計(jì)算與的值，并根據(jù)與的值的大小關(guān)系分情況討論：（1）若,說明是好點(diǎn)，于是把區(qū)間劃掉，保留，則內(nèi)有一保留點(diǎn)，置新的區(qū)間；（2）若，說明是好點(diǎn)，于是應(yīng)將劃掉，保留,則內(nèi)有保留點(diǎn),置新的區(qū)間．.黃金分割法第九十二頁，共一百零九頁，2022年，8月28日(3)若則應(yīng)具體分析,看極小點(diǎn)可能在哪一邊再?zèng)Q定取舍，在一般情況下，可同時(shí)劃掉和僅保留中間的重置新的區(qū)間．接下來是在留下的區(qū)間內(nèi)找好點(diǎn)．重復(fù)上面的步驟，直到搜索區(qū)間小于給定的允許誤差為止。這樣就得到黃金分割法迭代算法：黃金分割法第九十三頁，共一百零九頁，2022年，8月28日已知，常數(shù)0.382，終止限．(1)確定的初始搜索區(qū)間．(2)計(jì)算．(3)計(jì)算．(4)若,則打印，停機(jī)；否則，轉(zhuǎn)(5)．(5)判別是否滿足：若滿足，則置，然后轉(zhuǎn)(3)；否則，置然后轉(zhuǎn)(4)．

黃金分割法第九十四頁，共一百零九頁，2022年，8月28日黃金分割法算法流程如圖所示．第九十五頁，共一百零九頁，2022年，8月28日三、黃金分割法有關(guān)說明黃金分割法是通過所選試點(diǎn)的函數(shù)值而逐步縮短單谷區(qū)間來搜索最優(yōu)點(diǎn)．該方法適用于單谷區(qū)間上的任何函數(shù)，甚至可以是不連續(xù)函數(shù)，因此這種算法屬于直接法，適用相當(dāng)廣泛．

黃金分割法第九十六頁，共一百零九頁，2022年，8月28日拋物線插值法一、拋物線插值法基本原理考慮一維搜索問題假設(shè)其中是定義在區(qū)間上的單峰函數(shù)．首先用試探法在上找一點(diǎn)，使之滿足