一維優(yōu)化方法（課堂PPT）

1、1l結(jié)構(gòu)設(shè)計：結(jié)構(gòu)設(shè)計：要在滿足強(qiáng)度要求等條件下，要在滿足強(qiáng)度要求等條件下，使所用的材料的總重量最輕：使所用的材料的總重量最輕：l資源分配：資源分配：要使各用戶利用有限資源產(chǎn)要使各用戶利用有限資源產(chǎn)生的總效益最大；生的總效益最大；l安排運(yùn)輸方案：安排運(yùn)輸方案：要在滿足物質(zhì)需求和裝要在滿足物質(zhì)需求和裝載條件下使運(yùn)輸費(fèi)用最低：載條件下使運(yùn)輸費(fèi)用最低：l編制生產(chǎn)計劃：編制生產(chǎn)計劃：要按照產(chǎn)品工藝流程和要按照產(chǎn)品工藝流程和顧客需求，盡量降低人力、設(shè)備、原材顧客需求，盡量降低人力、設(shè)備、原材料等成本使總利潤最高。料等成本使總利潤最高。2l最優(yōu)化設(shè)計的目的：最優(yōu)化設(shè)計的目的：l 機(jī)械設(shè)計師追求其設(shè)計的方案

2、是機(jī)械設(shè)計師追求其設(shè)計的方案是l 尺寸最小尺寸最?。ú牧舷淖钌倩蛑亓孔钶p）（材料消耗最少或重量最輕）l 成本最低成本最低（ 運(yùn)輸、資源分配、安排生產(chǎn)等）運(yùn)輸、資源分配、安排生產(chǎn)等）l 性能最好性能最好（零件、部件、產(chǎn)品）（零件、部件、產(chǎn)品）l每一產(chǎn)品設(shè)計、制造過程中，都含有很多因素每一產(chǎn)品設(shè)計、制造過程中，都含有很多因素如何優(yōu)化。如何優(yōu)化。l因此，最優(yōu)化理論和技術(shù)必將在社會的諸多方因此，最優(yōu)化理論和技術(shù)必將在社會的諸多方面起著越來越大的作用。面起著越來越大的作用。3l目前，科研院所、大型企業(yè)在設(shè)計中均把目前，科研院所、大型企業(yè)在設(shè)計中均把優(yōu)化思想融入其中，例如：優(yōu)化思想融入其中，例如：l1、

3、汽車行業(yè)、汽車行業(yè)（排氣量優(yōu)化問題，車型等）（排氣量優(yōu)化問題，車型等）l2、航空航天、航空航天（電子吊艙（電子吊艙TTC環(huán)控制系統(tǒng)環(huán)控制系統(tǒng)的優(yōu)化設(shè)計、衛(wèi)星、安全等問題的優(yōu)化設(shè)計、衛(wèi)星、安全等問題45l1什么是最優(yōu)化設(shè)計什么是最優(yōu)化設(shè)計l 是根據(jù)給定的設(shè)計要求，在現(xiàn)有的工程技是根據(jù)給定的設(shè)計要求，在現(xiàn)有的工程技術(shù)條件下，應(yīng)用專業(yè)理論和數(shù)學(xué)規(guī)劃的理論及術(shù)條件下，應(yīng)用專業(yè)理論和數(shù)學(xué)規(guī)劃的理論及方法，在計算機(jī)上進(jìn)行的半自動或自動設(shè)計，方法，在計算機(jī)上進(jìn)行的半自動或自動設(shè)計，以選出在現(xiàn)有工程條件下的最好設(shè)計方案的一以選出在現(xiàn)有工程條件下的最好設(shè)計方案的一種現(xiàn)代設(shè)計方法。種現(xiàn)代設(shè)計方法。l設(shè)計原則：設(shè)計

4、原則：是優(yōu)化設(shè)計是優(yōu)化設(shè)計l設(shè)計方法：設(shè)計方法：是采用最優(yōu)化數(shù)學(xué)方法是采用最優(yōu)化數(shù)學(xué)方法l設(shè)計手段：設(shè)計手段：一是靠經(jīng)驗的積累，憑主觀作出判一是靠經(jīng)驗的積累，憑主觀作出判斷；二是做試驗選方案，比較優(yōu)劣定決策；三斷；二是做試驗選方案，比較優(yōu)劣定決策；三是建立數(shù)學(xué)模型，求解最優(yōu)策略。（電子計算是建立數(shù)學(xué)模型，求解最優(yōu)策略。（電子計算機(jī)及計算程序）這種方法應(yīng)該是符合時代潮流機(jī)及計算程序）這種方法應(yīng)該是符合時代潮流和形勢發(fā)展需要。和形勢發(fā)展需要。6l目前國內(nèi)外設(shè)計方法目前國內(nèi)外設(shè)計方法l常規(guī)設(shè)計：常規(guī)設(shè)計：用人工手算幾種方法選其較好者用人工手算幾種方法選其較好者l計算機(jī)輔助優(yōu)化設(shè)計：用近代的優(yōu)化數(shù)學(xué)方

5、法計算機(jī)輔助優(yōu)化設(shè)計：用近代的優(yōu)化數(shù)學(xué)方法 和理論編制計算機(jī)程序，用計算機(jī)輔助計算千和理論編制計算機(jī)程序，用計算機(jī)輔助計算千萬種方案，有規(guī)律最速得其最優(yōu)方案。萬種方案，有規(guī)律最速得其最優(yōu)方案。l國際情況：國際情況：先進(jìn)國家以采用后種方法為主先進(jìn)國家以采用后種方法為主l國內(nèi)情況：國內(nèi)情況：兩種方法并行，但趨向國際情況，兩種方法并行，但趨向國際情況，目前國內(nèi)大型企業(yè)（如汽車、航空、航天和科目前國內(nèi)大型企業(yè)（如汽車、航空、航天和科研院所）均采用計算機(jī)輔助優(yōu)化設(shè)計研院所）均采用計算機(jī)輔助優(yōu)化設(shè)計7l2、最優(yōu)化設(shè)計工作包含內(nèi)容、最優(yōu)化設(shè)計工作包含內(nèi)容l （1）將設(shè)計問題的物理模型轉(zhuǎn)化為數(shù)學(xué)模型，）將設(shè)計

6、問題的物理模型轉(zhuǎn)化為數(shù)學(xué)模型，建立數(shù)學(xué)模型時要選取建立數(shù)學(xué)模型時要選取設(shè)計變量設(shè)計變量、列出、列出目標(biāo)函目標(biāo)函數(shù)數(shù)，給出，給出約束條件約束條件，目標(biāo)函數(shù)是設(shè)計問題所要，目標(biāo)函數(shù)是設(shè)計問題所要求的最優(yōu)化指標(biāo)與設(shè)計變量之間的函數(shù)關(guān)系式。求的最優(yōu)化指標(biāo)與設(shè)計變量之間的函數(shù)關(guān)系式。l（2）采用最適當(dāng)?shù)淖顑?yōu)化方法，求解數(shù)學(xué)模）采用最適當(dāng)?shù)淖顑?yōu)化方法，求解數(shù)學(xué)模型?？蓺w結(jié)為在給定的條件（例如約束條件）型?？蓺w結(jié)為在給定的條件（例如約束條件）下求目標(biāo)函數(shù)的極值或最優(yōu)化值問題。下求目標(biāo)函數(shù)的極值或最優(yōu)化值問題。8l3、優(yōu)化設(shè)計的步驟及計算過程、優(yōu)化設(shè)計的步驟及計算過程l （1）優(yōu)化設(shè)計的步驟）優(yōu)化設(shè)計的步驟l

7、 A.根據(jù)設(shè)計問題建立數(shù)學(xué)模型根據(jù)設(shè)計問題建立數(shù)學(xué)模型,既將實際問既將實際問題表達(dá)為數(shù)學(xué)規(guī)劃問題題表達(dá)為數(shù)學(xué)規(guī)劃問題l 選取設(shè)計變量選取設(shè)計變量,確定目標(biāo)函數(shù)確定目標(biāo)函數(shù),建立約束條件建立約束條件l B 根據(jù)數(shù)學(xué)模型選擇尋優(yōu)方法（優(yōu)化算法）根據(jù)數(shù)學(xué)模型選擇尋優(yōu)方法（優(yōu)化算法）l C 編制程序編制程序l D 利用計算機(jī)計算利用計算機(jī)計算,選出最優(yōu)方案選出最優(yōu)方案l E 對選出的最優(yōu)方案進(jìn)行分析和判斷對選出的最優(yōu)方案進(jìn)行分析和判斷,首先看看是否符合工程實際首先看看是否符合工程實際,然后進(jìn)行參然后進(jìn)行參數(shù)分析數(shù)分析.9l(2) 計算過程計算過程l 各種工程設(shè)計問題的優(yōu)化設(shè)計原理大體上各種工程設(shè)計問題

8、的優(yōu)化設(shè)計原理大體上相似如下圖相似如下圖:文件編輯整理初始設(shè)計方案已知數(shù)據(jù)約束條件數(shù)學(xué)模型評比尋優(yōu)方法人工監(jiān)控10lA 初始設(shè)計方案初始設(shè)計方案lB 數(shù)學(xué)模型數(shù)學(xué)模型lC 評比評比lD 尋優(yōu)方法尋優(yōu)方法lE 人工監(jiān)控人工監(jiān)控(打印中間結(jié)果等打印中間結(jié)果等)lF 文件編輯整理文件編輯整理11l1、設(shè)計變量：、設(shè)計變量：在設(shè)計過程中進(jìn)行選擇并在設(shè)計過程中進(jìn)行選擇并最終必須確定的各項獨(dú)立參數(shù)（變量）最終必須確定的各項獨(dú)立參數(shù)（變量）l 如結(jié)構(gòu)的總體尺寸、零件的幾何尺寸、如結(jié)構(gòu)的總體尺寸、零件的幾何尺寸、物理特性等物理特性等lA:表示表示 N維設(shè)計變量可表示為維設(shè)計變量可表示為XnTnRXxxxX,.

9、,2112lB維數(shù)維數(shù)：設(shè)計變量的數(shù)目稱為最優(yōu)化設(shè)計維數(shù)：設(shè)計變量的數(shù)目稱為最優(yōu)化設(shè)計維數(shù)lC：Rn表示設(shè)計變量存在的空間表示設(shè)計變量存在的空間l 既以既以n個獨(dú)立變量為坐標(biāo)軸組成的個獨(dú)立變量為坐標(biāo)軸組成的n維向量維向量空間是一個空間是一個n 維實空間維實空間lD設(shè)計空間：設(shè)計空間：每一個分量都是互相獨(dú)立的，所每一個分量都是互相獨(dú)立的，所有各個分量構(gòu)成了一個空間，即各設(shè)計變量的有各個分量構(gòu)成了一個空間，即各設(shè)計變量的坐標(biāo)軸所描述的空間稱之為設(shè)計空間坐標(biāo)軸所描述的空間稱之為設(shè)計空間lE超越空間：超越空間： n3時是用圖很難表達(dá)的空間為時是用圖很難表達(dá)的空間為13l例例:某車間生產(chǎn)甲、乙兩種產(chǎn)品。

10、生產(chǎn)甲種產(chǎn)某車間生產(chǎn)甲、乙兩種產(chǎn)品。生產(chǎn)甲種產(chǎn)品每件需要用材料品每件需要用材料9kg、3個工時、個工時、4kw電，電，可獲利可獲利60元。生產(chǎn)乙種產(chǎn)品每件需要用材料元。生產(chǎn)乙種產(chǎn)品每件需要用材料4kg、10個工時、個工時、5kw電，可獲利電，可獲利120元。若元。若每天能供應(yīng)材料每天能供應(yīng)材料360kg、有、有300個工時、能供個工時、能供200kw電，問每天生產(chǎn)甲、乙兩種產(chǎn)品各多電，問每天生產(chǎn)甲、乙兩種產(chǎn)品各多少件，才能夠獲得最大的利潤。少件，才能夠獲得最大的利潤。14l選擇設(shè)計變量:l分別以生產(chǎn)甲乙兩種產(chǎn)品數(shù)為nTRXxxX21,15l2目標(biāo)函數(shù)：設(shè)計中預(yù)期要達(dá)到的目標(biāo)目標(biāo)函數(shù)：設(shè)計中預(yù)期

11、要達(dá)到的目標(biāo)l如（重量最輕、或尺寸最小，性能最好等）如（重量最輕、或尺寸最小，性能最好等） l目標(biāo)函數(shù)應(yīng)表示為各設(shè)計變量的函數(shù)目標(biāo)函數(shù)應(yīng)表示為各設(shè)計變量的函數(shù)la單目標(biāo)函數(shù)單目標(biāo)函數(shù):最優(yōu)化問題僅有一個單目標(biāo)函數(shù)最優(yōu)化問題僅有一個單目標(biāo)函數(shù)lb多目標(biāo)函數(shù)：在同一設(shè)計中有多個目標(biāo)函數(shù)多目標(biāo)函數(shù)：在同一設(shè)計中有多個目標(biāo)函數(shù)l 對于多目標(biāo)函數(shù)可以獨(dú)立地列出幾個目標(biāo)函對于多目標(biāo)函數(shù)可以獨(dú)立地列出幾個目標(biāo)函 數(shù)式數(shù)式lC綜合目標(biāo)函數(shù)：把幾個目標(biāo)函數(shù)綜合到一起綜合目標(biāo)函數(shù)：把幾個目標(biāo)函數(shù)綜合到一起),.,()(21nxxxFXF16l目標(biāo)函數(shù)可以通過等值線（面）在設(shè)計空間中目標(biāo)函數(shù)可以通過等值線（面）在設(shè)

12、計空間中表示出來。表示出來。以二維為例，如圖以二維為例，如圖在設(shè)計平面上的點在設(shè)計平面上的點X(1) ,X(2), X(3)存在有存在有：1)3()2()1()()()(cXFXFXF17l例例:某車間生產(chǎn)甲、乙兩種產(chǎn)品。生產(chǎn)甲種產(chǎn)某車間生產(chǎn)甲、乙兩種產(chǎn)品。生產(chǎn)甲種產(chǎn)品每件需要用材料品每件需要用材料9kg、3個工時、個工時、4kw電，電，可獲利可獲利60元。生產(chǎn)乙種產(chǎn)品每件需要用材料元。生產(chǎn)乙種產(chǎn)品每件需要用材料4kg、10個工時、個工時、5kw電，可獲利電，可獲利120元。若元。若每天能供應(yīng)材料每天能供應(yīng)材料360kg、有、有300個工時、能供個工時、能供200kw電，問每天生產(chǎn)甲、乙兩種產(chǎn)

13、品各多電，問每天生產(chǎn)甲、乙兩種產(chǎn)品各多少件，才能夠獲得最大的利潤。少件，才能夠獲得最大的利潤。18xxxxf212112060,19l3約束條件：在設(shè)計中對設(shè)計變量取值的限制約束條件：在設(shè)計中對設(shè)計變量取值的限制條件條件l（1）邊界約束或區(qū)域約束）邊界約束或區(qū)域約束l（2）性能約束）性能約束l（3）顯約束和隱約束）顯約束和隱約束l（4）約束的表達(dá)式形式：按表達(dá)式約束分為）約束的表達(dá)式形式：按表達(dá)式約束分為等式和不等式約束等式和不等式約束pvXhmuXgvu, 10)(, 10)(20l約束函數(shù)的約束函數(shù)的幾何意義幾何意義是它將設(shè)計空間一分為二，是它將設(shè)計空間一分為二，形成了可行域和不可行域。形

14、成了可行域和不可行域。如圖，優(yōu)化設(shè)計點應(yīng)當(dāng)落在可行域內(nèi)，即：nRDX21l例例:某車間生產(chǎn)甲、乙兩種產(chǎn)品。生產(chǎn)甲種產(chǎn)某車間生產(chǎn)甲、乙兩種產(chǎn)品。生產(chǎn)甲種產(chǎn)品每件需要用材料品每件需要用材料9kg、3個工時、個工時、4kw電，電，可獲利可獲利60元。生產(chǎn)乙種產(chǎn)品每件需要用材料元。生產(chǎn)乙種產(chǎn)品每件需要用材料4kg、10個工時、個工時、5kw電，可獲利電，可獲利120元。若元。若每天能供應(yīng)材料每天能供應(yīng)材料360kg、有、有300個工時、能供個工時、能供200kw電，問每天生產(chǎn)甲、乙兩種產(chǎn)品各多電，問每天生產(chǎn)甲、乙兩種產(chǎn)品各多少件，才能夠獲得最大的利潤。少件，才能夠獲得最大的利潤。22002005430

15、01033604921212121xxxxxxxx23l4數(shù)學(xué)模型：數(shù)學(xué)模型：首先把工程問題用數(shù)學(xué)方法來描述，建立一個數(shù)學(xué)首先把工程問題用數(shù)學(xué)方法來描述，建立一個數(shù)學(xué)模型。機(jī)械優(yōu)化設(shè)計的數(shù)學(xué)模型已模式化了，可寫模型。機(jī)械優(yōu)化設(shè)計的數(shù)學(xué)模型已模式化了，可寫成：成：最優(yōu)方案最優(yōu)方案)(,.,*2*1*XFxxxXTx最優(yōu)值最優(yōu)值qvXhpuXgtsRDXXFvun,.2 , 10)(,.2 , 10)(. .)(min 求24l例例:某車間生產(chǎn)甲、乙兩種產(chǎn)品。生產(chǎn)甲種產(chǎn)某車間生產(chǎn)甲、乙兩種產(chǎn)品。生產(chǎn)甲種產(chǎn)品每件需要用材料品每件需要用材料9kg、3個工時、個工時、4kw電，電，可獲利可獲利60元。生

16、產(chǎn)乙種產(chǎn)品每件需要用材料元。生產(chǎn)乙種產(chǎn)品每件需要用材料4kg、10個工時、個工時、5kw電，可獲利電，可獲利120元。若元。若每天能供應(yīng)材料每天能供應(yīng)材料360kg、有、有300個工時、能供個工時、能供200kw電，問每天生產(chǎn)甲、乙兩種產(chǎn)品各多電，問每天生產(chǎn)甲、乙兩種產(chǎn)品各多少件，才能夠獲得最大的利潤。少件，才能夠獲得最大的利潤。25xxxxf212112060,00200543001033604921212121xxxxxxxx26l5連續(xù)變量連續(xù)變量l6離散變量離散變量l7約束優(yōu)化與非約束優(yōu)化約束優(yōu)化與非約束優(yōu)化l8線性優(yōu)化與非線性優(yōu)化線性優(yōu)化與非線性優(yōu)化l例要用薄鋼板制造一體積為例要用薄

17、鋼板制造一體積為 的貨箱的貨箱,由于運(yùn)輸裝卸要求其長度不小于由于運(yùn)輸裝卸要求其長度不小于4m,問為了問為了使耗費(fèi)的鋼板最少并減輕重量使耗費(fèi)的鋼板最少并減輕重量,應(yīng)如何選取應(yīng)如何選取貨箱的長、寬、和高？貨箱的長、寬、和高？l解：解：m2527l9可行域與可行設(shè)計點可行域與可行設(shè)計點l非可行域與非可行設(shè)計點非可行域與非可行設(shè)計點l例如：例如：44)(min12221xxxxfRn21 Txxx00010224132212211xgxgxxgxxgxxxx28l將約束函數(shù)值為零時所得的曲線所包圍的圖形，將約束函數(shù)值為零時所得的曲線所包圍的圖形，在此圖形內(nèi)取點為可行設(shè)計點，在圖形外取點在此圖形內(nèi)取點為

18、可行設(shè)計點，在圖形外取點為非可行設(shè)計點。既滿足約束條件所形成的圖為非可行設(shè)計點。既滿足約束條件所形成的圖形內(nèi)取點。形內(nèi)取點。l10 局部最優(yōu)和全局最優(yōu)局部最優(yōu)和全局最優(yōu)l 目標(biāo)函數(shù)不是單峰函數(shù)時，有若干個極小點目標(biāo)函數(shù)不是單峰函數(shù)時，有若干個極小點l 對應(yīng)有函數(shù)值稱為局部最優(yōu)解，其中函數(shù)對應(yīng)有函數(shù)值稱為局部最優(yōu)解，其中函數(shù)值最小的點稱為全域最優(yōu)解值最小的點稱為全域最優(yōu)解29l數(shù)學(xué)基礎(chǔ)：數(shù)學(xué)基礎(chǔ)：l梯度梯度lHessian 海賽矩陣海賽矩陣l函數(shù)的凸集與凸函數(shù)函數(shù)的凸集與凸函數(shù)l在優(yōu)化設(shè)計中應(yīng)注意局部區(qū)域的極小點并不一在優(yōu)化設(shè)計中應(yīng)注意局部區(qū)域的極小點并不一定就是整個可行域的最優(yōu)點（最大值或最小

19、定就是整個可行域的最優(yōu)點（最大值或最小值）。在整個可行域中對任一值）。在整個可行域中對任一x都有都有l(wèi)時，時，x就是全域最優(yōu)點或整體最優(yōu)點，如果就是全域最優(yōu)點或整體最優(yōu)點，如果x是是局部可行域中有極小值時，稱局部或相對最優(yōu)局部可行域中有極小值時，稱局部或相對最優(yōu)點，函數(shù)的凸性表現(xiàn)為單峰性。點，函數(shù)的凸性表現(xiàn)為單峰性。 xfxf30l結(jié)論：多元函數(shù)若有連續(xù)的二階偏導(dǎo)數(shù)，且結(jié)論：多元函數(shù)若有連續(xù)的二階偏導(dǎo)數(shù)，且H（X）正定。如果正定。如果F是是D內(nèi)的凸函數(shù)，且存在極內(nèi)的凸函數(shù)，且存在極小點小點X，那么那么X必為必為F在在D上的全局極小點，且上的全局極小點，且是唯一的，如是凸函數(shù)，駐點就是極小點是唯

20、一的，如是凸函數(shù)，駐點就是極小點l優(yōu)化中常用。優(yōu)化中常用。31l根據(jù)設(shè)計變量的類型可分為根據(jù)設(shè)計變量的類型可分為n連續(xù)變量優(yōu)化方法連續(xù)變量優(yōu)化方法n離散變量優(yōu)化方法離散變量優(yōu)化方法l在連續(xù)變量優(yōu)化方法中，又可分為：在連續(xù)變量優(yōu)化方法中，又可分為：n非線性無約束優(yōu)化方法非線性無約束優(yōu)化方法n直接算法直接算法n梯度算法梯度算法n非線性約束優(yōu)化方法非線性約束優(yōu)化方法n直接算法直接算法n間接算法間接算法32l 直接搜索法：通過函數(shù)值的計算和直接搜索法：通過函數(shù)值的計算和比較，確定搜索的方向和步長。如：黃比較，確定搜索的方向和步長。如：黃金分割法、二次插值、復(fù)合形法等。金分割法、二次插值、復(fù)合形法等。l

21、 間接搜索法：利用函數(shù)的一階或二間接搜索法：利用函數(shù)的一階或二階偏導(dǎo)數(shù)矩陣確定搜索方向和步長。如階偏導(dǎo)數(shù)矩陣確定搜索方向和步長。如梯度法、牛頓法等。梯度法、牛頓法等。33l最優(yōu)化設(shè)計的任務(wù)：一是找到最優(yōu)解，最優(yōu)化設(shè)計的任務(wù)：一是找到最優(yōu)解，二是如何提高求優(yōu)過程的效率。二是如何提高求優(yōu)過程的效率。 對對n維的非線性目標(biāo)函數(shù)，用常規(guī)的解法求極維的非線性目標(biāo)函數(shù)，用常規(guī)的解法求極值，往往是很困難的。有效的辦法使用值，往往是很困難的。有效的辦法使用迭代算迭代算法法。34l特點：按照一定的邏輯結(jié)構(gòu)進(jìn)行反復(fù)的數(shù)值計特點：按照一定的邏輯結(jié)構(gòu)進(jìn)行反復(fù)的數(shù)值計算，尋求函數(shù)值不斷下降的設(shè)計點，直到最后算，尋求函數(shù)

22、值不斷下降的設(shè)計點，直到最后獲得足夠精度的近似解時就截斷計算。獲得足夠精度的近似解時就截斷計算。l一、迭代過程一、迭代過程:從一個選定的初始點從一個選定的初始點X出發(fā)出發(fā),沿沿某種優(yōu)化方法所規(guī)定的方向某種優(yōu)化方法所規(guī)定的方向S,確定適當(dāng)?shù)牟介L確定適當(dāng)?shù)牟介La.產(chǎn)生一個新的設(shè)計點產(chǎn)生一個新的設(shè)計點.l l l滿足滿足l a-第第k步迭代計算的步長步迭代計算的步長)()()()1( : kkkkSXX即 xxkkff)(135l二、迭代計算的終止條件二、迭代計算的終止條件l 1.點距準(zhǔn)則點距準(zhǔn)則:l 相鄰兩迭代點之間的距離已達(dá)到充分小相鄰兩迭代點之間的距離已達(dá)到充分小既：既：l 1)()1(kkX

23、X36如果如果F(X(k+1)1可采用相對可采用相對來判斷。判別式：來判斷。判別式： 21xxkkFF3)()()1()()()(kkkXFXFXF37l3.梯度準(zhǔn)則梯度準(zhǔn)則l 目標(biāo)函數(shù)在迭代點的梯度已達(dá)到充分小目標(biāo)函數(shù)在迭代點的梯度已達(dá)到充分小 既：既：41XKF44531411010；一般取判斷精度38l三、變量的坐標(biāo)變換三、變量的坐標(biāo)變換l 原因：變量間的數(shù)值大小相差極大，無法用原因：變量間的數(shù)值大小相差極大，無法用統(tǒng)一步長尋優(yōu)，為此采用坐標(biāo)變換便于尋優(yōu)的統(tǒng)一步長尋優(yōu)，為此采用坐標(biāo)變換便于尋優(yōu)的統(tǒng)一步長。統(tǒng)一步長。l設(shè)計變量的標(biāo)準(zhǔn)化處理，是將設(shè)計變量值用變設(shè)計變量的標(biāo)準(zhǔn)化處理，是將設(shè)計變

24、量值用變量區(qū)間內(nèi)的相對坐標(biāo)來表示，將設(shè)計變量的真量區(qū)間內(nèi)的相對坐標(biāo)來表示，將設(shè)計變量的真實值化為變量區(qū)間的相對值，使變量的變化范實值化為變量區(qū)間的相對值，使變量的變化范圍均在圍均在01區(qū)間內(nèi)。區(qū)間內(nèi)。39l坐標(biāo)變換：坐標(biāo)變換：lXtr-變量的真實坐標(biāo)值變量的真實坐標(biāo)值lXr-變量的標(biāo)準(zhǔn)坐標(biāo)值變量的標(biāo)準(zhǔn)坐標(biāo)值lA-變量變化的下限變量變化的下限lB-變量變化的上限變量變化的上限nixABAxxriiiitrri,.2 , 1 ) 10 ( 40 對于一維目標(biāo)函數(shù) f ( x ),尋找它的最優(yōu)點x 和最優(yōu)值 x （k+1)= x （k ) + （k ) S （k ) S-方向矢量：由某種優(yōu)化方法規(guī)定

25、 -步長 min f （ x （k+1) ） = f （x （k ) + （k ) S （k ) ）1. 確定搜索區(qū)間2.求最優(yōu)步長 ，使目標(biāo)函數(shù)達(dá)到最小。xff*41有兩種方法：進(jìn)退法有兩種方法：進(jìn)退法 外推法外推法進(jìn)退法：分為三步進(jìn)退法：分為三步a. 試探計算試探計算 初選一個初始點初選一個初始點 和初始步長和初始步長 前進(jìn)點前進(jìn)點并計算函數(shù)值并計算函數(shù)值 f f（x x 1 1）= y= y1 1 f f（x x2 2）= y= y2 2（1 1）當(dāng)）當(dāng)y y2 2 y y y1 1時，則極小點必在時，則極小點必在x x 1 1左方，應(yīng)再做左方，應(yīng)再做后退運(yùn)算后退運(yùn)算x1hxx012h0

26、42b. y y2 2 y y1 1 ( (前進(jìn)計算）前進(jìn)計算）令令 并前進(jìn)步長倍增如（給定并前進(jìn)步長倍增如（給定，讓讓=2=2）計算第三個前進(jìn)點（新點計算第三個前進(jìn)點（新點 ）x x 3 3 = x = x 2 2+h+h x x 3 3 = x = x 2 2+ +h h0 0 = = （ x x 1 1 + + h h0 0 ）+2+2h h0 0 = x = x 1 1 +3+3 h h0 0計算計算 f f（x x 3 3）= y= y3 3比較比較f f（x x 3 3），）， f f（x x 2 2）既比較既比較y y2 2 ，y y3 3的大小的大小此時又有兩種情況：此時又有兩

27、種情況： hh0hh243（1 1） y y2 2 y y3 3 則應(yīng)繼續(xù)做則應(yīng)繼續(xù)做前進(jìn)計算，對各點作如下置換：前進(jìn)計算，對各點作如下置換：l并再次將前進(jìn)步長倍增，并再次將前進(jìn)步長倍增， 計算新點及其函數(shù)計算新點及其函數(shù)值值l x x 3 3 = x = x 2 2+h f+h f（x x 3 3）= y= y3 3l重復(fù)上述過程，直到函數(shù)出現(xiàn)大重復(fù)上述過程，直到函數(shù)出現(xiàn)大小小大的情況大的情況為止。為止。yxx2121y yxx3232y hh246C. y y2 2 y y1 1 ( (后退運(yùn)算）后退運(yùn)算） 若在步驟（若在步驟（2 2）中，）中， y y2 2 y y1 1 ，則應(yīng)做后退運(yùn)

28、算，將步長則應(yīng)做后退運(yùn)算，將步長改變?yōu)樨?fù)值改變?yōu)樨?fù)值 h h （h h0 0）置換點號使它自右向左置換點號使它自右向左反向排列。反向排列。yxxyxxyxx323221211313yyy 47l再將后退步長加倍再將后退步長加倍l計算第三后退點（新點）及其函數(shù)值計算第三后退點（新點）及其函數(shù)值l x x 3 3 = x = x 2 2+h f+h f（x x 3 3）= y= y3 3比較函數(shù)值比較函數(shù)值f f（x x 3 3），）， f f（x x 2 2）既比較既比較y y2 2 ，y y3 3的大小的大小此時又有兩種情況此時又有兩種情況hh248（1 1） y y2 2 y y3 3 則應(yīng)

29、繼續(xù)做后退則應(yīng)繼續(xù)做后退計算，對各點作如下置換：計算，對各點作如下置換：l并再次將并再次將后退后退步長倍增，步長倍增， 計算新點及其函數(shù)計算新點及其函數(shù)值值l x x 3 3 = x = x 2 2+h f+h f（x x 3 3）= y= y3 3l重復(fù)上述過程，直到函數(shù)值出現(xiàn)大重復(fù)上述過程，直到函數(shù)值出現(xiàn)大小小大的情大的情況為止。況為止。取其左右兩端點為區(qū)間取其左右兩端點為區(qū)間 x x k k，x x 1 1 a,ba,bhh2yxx2121y yxx3232y 50l例：試用進(jìn)退法確定函數(shù)例：試用進(jìn)退法確定函數(shù)l的一維優(yōu)化初始搜索區(qū)間的一維優(yōu)化初始搜索區(qū)間 a a ， bbl初始點初始點

30、x x 1 1 =0，初始進(jìn)退距，初始進(jìn)退距h 0 0 =1 962xxfx51l格點法是一種思路極為簡單的一維求優(yōu)法格點法是一種思路極為簡單的一維求優(yōu)法l設(shè)函數(shù)設(shè)函數(shù)f(x)的初始搜索區(qū)間的初始搜索區(qū)間 a a ， bb，在此區(qū)間在此區(qū)間內(nèi)取內(nèi)取n個內(nèi)等分點個內(nèi)等分點x x 1 1，x x 2 2 x x n n ，并計算函數(shù)值并計算函數(shù)值ly y 1 1，y y 2 2 y y n n l并比較取出最小并比較取出最小y y m m= =minmin（y y i i i=1i=1，2n)2n)l并取并取x x m m左右兩相鄰點左右兩相鄰點x x m-1 m-1 ，x x m+1 m+1 為

31、為新區(qū)間新區(qū)間l判斷判斷x m+1 m+1- -x x m-1 m-1 精度值精度值 , 成立成立l則則: : x x m m x x* * y y m m y y* * l不不成立成立(x x m-1 m-1 ，x x m+1 m+1 ) )作為新的初始區(qū)間繼續(xù)進(jìn)作為新的初始區(qū)間繼續(xù)進(jìn)行行. .52l速度取決于區(qū)間縮短率速度取決于區(qū)間縮短率l區(qū)間縮短率區(qū)間縮短率=新區(qū)間新區(qū)間/舊區(qū)間舊區(qū)間l格點法每次區(qū)間縮短時取內(nèi)分點數(shù)為格點法每次區(qū)間縮短時取內(nèi)分點數(shù)為n則則l入入=2/(n+1)lN越多越多,入越小，區(qū)間縮短越快，但計算入越小，區(qū)間縮短越快，但計算次數(shù)越多次數(shù)越多53l例題：用格點法求一維目標(biāo)函數(shù)的最優(yōu)解例題：用格點法求一維目標(biāo)函數(shù)的最優(yōu)解l已知：初始區(qū)間已知：初始區(qū)間 a a ， b