機(jī)械優(yōu)化設(shè)計(jì)講義

《機(jī)械優(yōu)化設(shè)計(jì)》講義第一講第一課時(shí)：機(jī)械優(yōu)化設(shè)計(jì)概論課程的研究對(duì)象：根據(jù)最優(yōu)化原理和方法，利用計(jì)算機(jī)為計(jì)算工具，尋求最優(yōu)設(shè)計(jì)參數(shù)的一種現(xiàn)代設(shè)計(jì)方法。目標(biāo)：本課程目標(biāo)體系可以分為三大塊：理論基礎(chǔ)、算法的分析、理解和掌握，算法的設(shè)計(jì)、實(shí)現(xiàn)（編程）能力的培養(yǎng)。將主要是對(duì)算法的學(xué)習(xí)為主，并兼顧培養(yǎng)一定的解決實(shí)際問題能力、上機(jī)編程調(diào)試能力。首先，幾個(gè)概念：優(yōu)化（或最優(yōu)化原理、方法）、優(yōu)化設(shè)計(jì)、機(jī)械（工程）優(yōu)化設(shè)計(jì)?，F(xiàn)代的優(yōu)化方法，研究某些數(shù)學(xué)上定義的問題的，利用計(jì)算機(jī)為計(jì)算工具的最優(yōu)解。優(yōu)化理論本身是一種應(yīng)用性很強(qiáng)的學(xué)科，而工程優(yōu)化設(shè)計(jì)（特別是機(jī)械優(yōu)化設(shè)計(jì)）由于采用計(jì)算機(jī)作為工具解決工程中的優(yōu)化問題，可以歸入計(jì)算機(jī)輔助設(shè)計(jì)(CAD)的研究范疇。再，優(yōu)化方法的發(fā)展：源頭是數(shù)學(xué)的極值問題，但不是簡(jiǎn)單的極值問題，計(jì)算機(jī)算法和運(yùn)算的引入是關(guān)鍵。從理論與實(shí)踐的關(guān)系方面，符合實(shí)踐-理論-實(shí)踐的過程。優(yōu)化原理和方法的理論基礎(chǔ)歸根結(jié)底還是來源于實(shí)際生產(chǎn)生活當(dāng)中，特別是工程、管理領(lǐng)域?qū)ψ顑?yōu)方案的尋找，一旦發(fā)展為一種相對(duì)獨(dú)立系統(tǒng)、成熟的理論基礎(chǔ)，反過來可以指導(dǎo)工程、管理領(lǐng)域最優(yōu)方案的尋找（理論本身也在實(shí)踐應(yīng)用中不斷進(jìn)步、完善）。解決優(yōu)化設(shè)計(jì)問題的一般步驟：機(jī)械設(shè)計(jì)問題機(jī)械設(shè)計(jì)問題建立數(shù)學(xué)模型選擇或設(shè)計(jì)算法編碼調(diào)試計(jì)算結(jié)果的分析整理相關(guān)知識(shí)：數(shù)學(xué)方面：微積分、線性代數(shù)；計(jì)算機(jī)方面：編程語言、計(jì)算方法；專業(yè)領(lǐng)域方面：機(jī)械原理、力學(xué)等知識(shí)內(nèi)容：數(shù)學(xué)基礎(chǔ)、一維到多維、無約束到有約束數(shù)學(xué)模型三個(gè)基本概念：設(shè)計(jì)變量、目標(biāo)函數(shù)、約束條件設(shè)計(jì)變量：相對(duì)于設(shè)計(jì)常量（如材料的機(jī)械性能）在設(shè)計(jì)域中變量是否連續(xù)：連續(xù)變量、離散變量（齒輪的齒數(shù)，）。設(shè)計(jì)問題的維數(shù)，表征了設(shè)計(jì)的自由度。每個(gè)設(shè)計(jì)問題的方案（設(shè)計(jì)點(diǎn)）為設(shè)計(jì)空間中的一個(gè)對(duì)應(yīng)的點(diǎn)。設(shè)計(jì)空間：二維（設(shè)計(jì)平面）、三維（設(shè)計(jì)空間）、更高維（超設(shè)計(jì)空間）。目標(biāo)函數(shù)：設(shè)計(jì)變量的函數(shù)。單目標(biāo)、多目標(biāo)函數(shù)。等值面的概念：設(shè)計(jì)目標(biāo)為常量時(shí)形成的曲面（等值線、等值面、超等值面）。幾何意義：等值線（等值線的公共中心既是無約束極小點(diǎn)）、等值面。約束條件： 等式約束（約數(shù)個(gè)數(shù)小于設(shè)計(jì)問題的維數(shù)） 不等式約束 滿足約束條件的設(shè)計(jì)點(diǎn)的集合構(gòu)成可行域D：可行點(diǎn)、非可行點(diǎn)、邊界設(shè)計(jì)點(diǎn) 幾何意義（二維）：對(duì)于設(shè)計(jì)空間不滿足不等式約束的部分，用陰影表示。數(shù)學(xué)模型的一般形式：尋找一個(gè)滿足約束條件的設(shè)計(jì)點(diǎn)，使得目標(biāo)函數(shù)值最小。標(biāo)準(zhǔn)形式：SKIPIF1<0優(yōu)化問題的幾何描述第二章數(shù)學(xué)基礎(chǔ)和數(shù)值迭代法2.1函數(shù)的方向?qū)?shù)和梯度一、函數(shù)的方向?qū)?shù)SKIPIF1<0二、函數(shù)的梯度SKIPIF1<0令SKIPIF1<0為函數(shù)在X點(diǎn)的梯度，包含函數(shù)的一階導(dǎo)數(shù)信息。SKIPIF1<0即梯度方向是函數(shù)變化率最大的方向。2.2函數(shù)的泰勒展開與黑塞矩陣一、泰勒展開式SKIPIF1<0其中黑塞（hessian）矩陣:SKIPIF1<0包含函數(shù)的二階導(dǎo)數(shù)信息。2.3凸集、凸函數(shù)、凸規(guī)劃一、凸集SKIPIF1<0有SKIPIF1<0，則D為凸集.凸集的性質(zhì)：1.若D為凸集，λ為實(shí)數(shù)，則λD仍為凸集。（凸集的實(shí)數(shù)積為凸集） 2．若D、φ均為凸集，則二者的并集（和）為凸集。（凸集的和為凸集） 3．若D、φ均為凸集，則二者的交集（積）為凸集。（凸集的積為凸集）二、凸函數(shù)En的子集D為凸集，f為D上的函數(shù)，SKIPIF1<0恒有SKIPIF1<0，則f為D上的凸函數(shù)。反之為凹函數(shù)。凸函數(shù)的性質(zhì)：設(shè)f為D上的凸函數(shù)，λ為實(shí)數(shù)，則λf為D上的凸函數(shù)。設(shè)f1，f2為D上的凸函數(shù),則f=f1+f2為D上的凸函數(shù)。若f在En一階可微，則對(duì)SKIPIF1<0，f為凸函數(shù)的充要條件：SKIPIF1<0若f在En二階可微，則對(duì)SKIPIF1<0，f為凸函數(shù)的充要條件：黑塞矩陣半正定（若正定，嚴(yán)格凸函數(shù)）。三、凸規(guī)劃SKIPIF1<0其中目標(biāo)函數(shù)、不等式約束均為凸函數(shù)，則稱該問題為凸規(guī)劃。凸規(guī)劃的性質(zhì)：集合SKIPIF1<0為凸集?？尚杏?yàn)橥辜?。任何局部最?yōu)解即為全域最優(yōu)解。若目標(biāo)函數(shù)可微，則最優(yōu)解的充要條件：SKIPIF1<02.4無約束優(yōu)化的極值條件 1．一階導(dǎo)數(shù)（梯度）為零。 2．二階導(dǎo)數(shù)（黑塞矩陣）正定（極小點(diǎn)），或負(fù)定（極大點(diǎn)）。2.5有約束優(yōu)化的極值條件(Kuhn-Tucker條件)對(duì)優(yōu)化問題SKIPIF1<0庫恩-塔克條件描述為SKIPIF1<0，即約束極小點(diǎn)存在的必要條件是：目標(biāo)函數(shù)在該點(diǎn)的梯度可表示為諸約束面梯度的線性組合的負(fù)值。從幾何意義上來說，即約束極小點(diǎn)目標(biāo)函數(shù)梯度向量的反方向必須落在諸約束面所構(gòu)成的錐角范圍之內(nèi)。對(duì)于凸規(guī)劃問題，K-T條件是充要條件。只能作為驗(yàn)證條件，但到底是局部最優(yōu)點(diǎn)還是全域最優(yōu)點(diǎn)尚不能確定。2.6優(yōu)化問題的數(shù)值迭代法1．迭代過程SKIPIF1<0(k=0,1,2,…)迭代的基本思想：搜索、迭代、逼近。2．迭代終止條件：點(diǎn)距準(zhǔn)則：SKIPIF1<0函數(shù)值下降準(zhǔn)則：SKIPIF1<0梯度準(zhǔn)則：SKIPIF1<0第三章一維搜索的優(yōu)化方法一維優(yōu)化是多維優(yōu)化的基礎(chǔ)。包含兩個(gè)步驟 1．確定搜索區(qū)間（進(jìn)退法） 2．尋優(yōu)（黃金分割法、二次差值法）3.1進(jìn)退法——一維搜索區(qū)間的確定基本思想：對(duì)單峰函數(shù)（凸函數(shù)）f(x)，只要找到可行域內(nèi)三個(gè)點(diǎn)a<b<c，滿足函數(shù)值先減小再增大的趨勢(shì)，即f(a)>f(b)且f(b)<f(c)，則可以確定區(qū)間[a,c]內(nèi)必存在最優(yōu)點(diǎn)。

算法流程：SKIPIF1<03.2一維優(yōu)化方法——黃金分割法一維搜索的基本思想：在確定了搜索區(qū)間的前提下，不斷縮小搜索區(qū)間，直到區(qū)間的寬度小于預(yù)定的精度。黃金分割法的基本思想：黃金分割點(diǎn)的計(jì)算：SKIPIF1<0算法流程：SKIPIF1<03.3一維優(yōu)化方法——二次插值法首先，10分鐘回顧上次課的內(nèi)容，并講解作業(yè)：進(jìn)退法、黃金分割法概要、 103頁作業(yè)（程序演示）30分鐘：基本思路：類似于二次曲線擬合。以搜索區(qū)間三個(gè)點(diǎn)構(gòu)造一個(gè)二次曲線（拋物線），并以該二次曲線的極值點(diǎn)替代目標(biāo)函數(shù)的最優(yōu)點(diǎn)，若不滿足迭代中止條件，縮短搜索區(qū)間，反復(fù)迭代，直到相近兩次二次曲線極值滿足精度要求（點(diǎn)距準(zhǔn)則）。3.3.1基本原理搜索區(qū)間[a1，a3]及其中間某一點(diǎn)（a2）這三個(gè)點(diǎn)構(gòu)造一個(gè)二次曲線。這三個(gè)點(diǎn)構(gòu)成一個(gè)三元線性方程組,可求得該二次曲線極值點(diǎn)a*p作為a4。其中a*p=0.5(a1+a3-C1/C2) C1=(f3-f1)/(a3-a1) C2=[(f2-f1)/(a2-a1)-C1]/(a2-a1)若a2與a4之間趨于重合，則迭代結(jié)束；否則比較這四點(diǎn)的函數(shù)值，并在其中選擇三點(diǎn)，滿足函數(shù)值“先遞增再遞減”的趨勢(shì)，構(gòu)成新的a1、a2、a3。開始新一輪迭代。3.3.2迭代過程和算法流程例題本周五，p24,p29本周五，p24,p29SKIPIF1<0

第四章（多維）無約束優(yōu)化方法概述：工程優(yōu)化問題通常都是多維有約束優(yōu)化問題，但需從一維無約束問題到多維無約束優(yōu)化問題再到多維約束優(yōu)化問題的由簡(jiǎn)單到復(fù)雜的循序漸進(jìn)的學(xué)習(xí)研究過程。無約束優(yōu)化問題數(shù)學(xué)模型：SKIPIF1<0分類，從是否利用目標(biāo)函數(shù)的導(dǎo)數(shù)信息，分直接法和間接法直接法：坐標(biāo)輪換法、共軛方向法、鮑威爾法直接法：坐標(biāo)輪換法、共軛方向法、鮑威爾法間接法：梯度法、牛頓法、變尺度法4.1坐標(biāo)輪換法4.1.1坐標(biāo)輪換法基本原理將多維無約束優(yōu)化問題分解、轉(zhuǎn)化為一系列一維優(yōu)化問題，輪換沿各個(gè)坐標(biāo)軸一維搜索，直到求得最優(yōu)點(diǎn)。在每次迭代內(nèi)部，要依次沿各坐標(biāo)軸進(jìn)行N次（N為優(yōu)化問題的維數(shù)）一維搜索。這種一維搜索是固定其它N-1維變量，視為常量，然后進(jìn)行一維搜索，SKIPIF1<0，對(duì)于第k輪迭代，須重復(fù)N次該式的一維搜索，搜索的參數(shù)為ajk（即要優(yōu)化的參數(shù)是ajk），為相對(duì)第j維變量的搜索步長(zhǎng)，搜索方向?yàn)榈趈維空間坐標(biāo)的方向。當(dāng)k輪迭代結(jié)束后，本輪搜索的重點(diǎn)作為下一輪的起點(diǎn)，即SKIPIF1<0，然后投入下一輪迭代。4.1.2該方法特點(diǎn)不考慮目標(biāo)函數(shù)本身的變化情況（函數(shù)特點(diǎn)），簡(jiǎn)單、效率低、收斂速度慢。4.2共軛方向法4.2.1共軛方向?qū)τ贜維正定二次函數(shù)SKIPIF1<0(當(dāng)N=2，為同心橢圓族)，[H]為函數(shù)f的黑塞矩陣(正定對(duì)稱陣)。若存在兩個(gè)方向向量SKIPIF1<0，SKIPIF1<0，滿足SKIPIF1<0，則稱SKIPIF1<0與SKIPIF1<0為共軛方向。如何構(gòu)造共軛方向（二維）？對(duì)于某兩點(diǎn)SKIPIF1<0，沿方向SKIPIF1<0（SKIPIF1<0不平行）一維搜索得到兩個(gè)最優(yōu)點(diǎn)SKIPIF1<0，構(gòu)成方向SKIPIF1<0，則可以證明SKIPIF1<0與SKIPIF1<0為共軛方向，即SKIPIF1<0（對(duì)于二維問題，可以簡(jiǎn)單證明）當(dāng)然，這個(gè)結(jié)論可以從2維推廣到N維。同樣，說明對(duì)于N維函數(shù)，有N個(gè)共軛方向。對(duì)于二次函數(shù)，只要經(jīng)過N個(gè)一維搜索即可到達(dá)最優(yōu)點(diǎn)（即N維空間內(nèi)完成一輪迭代）。對(duì)于大于二次的函數(shù)，則可能需要將上一輪迭代的終點(diǎn)作為新一輪迭代的起點(diǎn)。在構(gòu)造迭代方程式時(shí)，可以用二次泰勒展開式來近似目標(biāo)函數(shù)的等值面。第二課時(shí)：4.2.2共軛方向法基本原理第一輪迭代與坐標(biāo)輪換法相同。將起點(diǎn)和N次一維搜索的末點(diǎn)組成一個(gè)新的方向，沿這個(gè)方向一維搜索，得到本輪迭代的終點(diǎn)。從第二輪起，舍去前一輪的第一個(gè)一維搜索方向，將前一輪的后N個(gè)一維搜索方向作為本輪迭代的前N個(gè)方向，這N個(gè)方向的一維搜索終點(diǎn)與本輪搜索的起點(diǎn)構(gòu)成第N+1個(gè)一維搜索方向，沿這個(gè)方向做一維搜索，得到本輪搜索的終點(diǎn)。若不滿足精度要求，則重復(fù)迭代。4.2.3共軛方向法的特點(diǎn)收斂速度比坐標(biāo)輪換法有明顯的提高，但前提是每次迭代所產(chǎn)生的新的方向與原來的N-1個(gè)方向之間要保持線性無關(guān)，若這些方向之間線性相關(guān)，則降低了搜索空間的維數(shù)，導(dǎo)致不能完全窮盡對(duì)設(shè)計(jì)空間每個(gè)方向的搜索，從而不能收斂于真正的最優(yōu)解。

上機(jī)調(diào)試內(nèi)容：SKIPIF1<04.3鮑威爾法4.3.1鮑威爾法基本原理共軛方向法的前提是每一輪迭代中新生成的第N+1個(gè)方向（共軛方向）與其它方向線性無關(guān)，如果出現(xiàn)線性相關(guān)，則導(dǎo)致算法不能正確收斂。鮑威爾為了解決該問題，加入了對(duì)共軛方向的判斷，如果線性無關(guān)則采用該方向，但并不是機(jī)械的替換上一輪第一個(gè)方向，而是替換函數(shù)值下降最多的方向；如果相關(guān)，則還是用上一輪迭代的方向。對(duì)于共軛方向法的判別準(zhǔn)則。SKIPIF1<0（4-2）其中：f1 ——本輪迭代起點(diǎn)函數(shù)值f2 ——本輪迭代終點(diǎn)函數(shù)值f3 ——映射點(diǎn)函數(shù)值Δkm——函數(shù)值下降最大的一步一維搜索SKIPIF1<0若滿足公式（4-2）則去掉第m個(gè)方向，下一輪的m到N方向采用本輪次第m+1到N+1個(gè)方向；若不滿足，則本輪迭代結(jié)束，以本輪終點(diǎn)為下一輪起點(diǎn)，仍采用本輪的N個(gè)方向進(jìn)行迭代。4.3.2迭代步驟（1）給定初始點(diǎn)和計(jì)算精度。（2）置k=1，取N個(gè)坐標(biāo)軸的單位向量為搜索方向SKIPIF1<0（i=0,1,…,N-1），,SKIPIF1<0（3）從SKIPIF1<0出發(fā)，沿SKIPIF1<0一維搜索，得到N個(gè)極小點(diǎn)SKIPIF1<0（i=1,2,…,N）,找到函數(shù)值下降最快的一次一維搜索的函數(shù)下降值和方向，記作Δkm，SKIPIF1<0（4）計(jì)算反射點(diǎn)SKIPIF1<0，計(jì)算f1，f2，f3。（5）若滿足（4-2）式，構(gòu)造本輪迭代第N+1個(gè)方向SKIPIF1<0，由N次一維搜索的終點(diǎn)沿SKIPIF1<0一維搜索得到本輪迭代終點(diǎn)，作為下一輪迭代（k+1輪）起點(diǎn)；去掉SKIPIF1<0方向，將SKIPIF1<0作為下一輪迭代的第N個(gè)方向。 否則，保留前N個(gè)搜索方向到下一輪迭代，取min(f2，f3)對(duì)應(yīng)的點(diǎn)作為下一輪起點(diǎn)。（6）若滿足迭代終止條件SKIPIF1<0，終止迭代，輸出優(yōu)化結(jié)果，否則kk+1,返回（3）。4.3.3算法流程（見下頁）共軛方向法習(xí)題課：用共軛方向法和鮑威爾法求解優(yōu)化問題SKIPIF1<0，初始點(diǎn)[0,0]T,精度ε=0.01。解：共軛方向法： 鮑威爾法：

SKIPIF1<04.4梯度法（最速下降法）4.4.1梯度法基本原理無約束優(yōu)化的直接法（坐標(biāo)輪換法和共軛方向法、鮑威爾法）沒有考慮無約束優(yōu)化最優(yōu)解存在的必要條件（梯度為零），使用這一條件，可以設(shè)計(jì)出更為高效的算法，所謂間接法（梯度法、牛頓法、變尺度法）。梯度方向是函數(shù)值變化最快的方向，那么負(fù)梯度方向便是函數(shù)值下降最快的方向。從這一點(diǎn)受啟發(fā)，可以使迭代方向沿梯度方向進(jìn)行一維搜索來再多維空間尋優(yōu)。即搜索方向?yàn)樘荻确较颍篠KIPIF1<0，或SKIPIF1<0，則迭代公式為SKIPIF1<0。4.4.2梯度法的特點(diǎn)前提是梯度存在。優(yōu)點(diǎn)是算法簡(jiǎn)單。相鄰兩次迭代的搜索方向垂直。即SKIPIF1<0證明：SKIPIF1<0，即k輪迭代經(jīng)過一次一維搜索由k點(diǎn)到達(dá)k+1點(diǎn)，那么SKIPIF1<0，對(duì)于一維優(yōu)化有SKIPIF1<0，所以SKIPIF1<0可見，相鄰兩輪迭代的搜索方向并不一致，為相互垂直的鋸齒形過程。剃度法對(duì)于迭代出發(fā)點(diǎn)目標(biāo)函數(shù)等值面偏心率為零時(shí)很有效，但對(duì)于有偏心的其效率就低了，隨偏心率的增加，迭代終止的難度也在增加?？梢娺@種搜索在接近目標(biāo)時(shí)的收斂是比較慢（缺點(diǎn)）的，效率也就不會(huì)高了。剃度法一般并不作為工程中實(shí)際應(yīng)用的方法，常用于其他方法的初始迭代（類似于坐標(biāo)輪換法）。4.5牛頓法4.5.1牛頓法基本原理類似二次插值法，將目標(biāo)函數(shù)在某一點(diǎn)附近二階泰勒展開，用這個(gè)二次函數(shù)的最優(yōu)點(diǎn)近似目標(biāo)函數(shù)的最優(yōu)點(diǎn)；若不滿足精度要求，在上一輪得到的最優(yōu)點(diǎn)最為本輪起點(diǎn)，再次用上述方法求最優(yōu)點(diǎn)；直到滿足精度要求。4.5.2牛頓法迭代公式目標(biāo)函數(shù)在的二次展開SKIPIF1<0，求近似目標(biāo)函數(shù)的最優(yōu)解，即SKIPIF1<0，有SKIPIF1<0即SKIPIF1<0，所以牛頓法迭代公式為SKIPIF1<0。從牛頓法的原理分析，如果目標(biāo)函數(shù)為二次函數(shù)，有SKIPIF1<0，即牛頓法一輪迭代的終點(diǎn)就是最優(yōu)解，而且是精確解。因此，牛頓法解決了二次函數(shù)非球面時(shí)的搜索方向問題，找到了一個(gè)可以消除偏心存在對(duì)采用梯度方向?yàn)樗阉鞣较驎r(shí)的影響，直接給出了搜索二次函數(shù)最優(yōu)點(diǎn)的方向?；蛘哒f，牛頓法對(duì)偏心率進(jìn)行了變化，消除了二次曲面的偏心率，對(duì)于更高次曲面，也可以減小這種偏心。從而在一定程度上解決了梯度發(fā)收斂慢的缺點(diǎn)。4.5.3牛頓法的特點(diǎn)（1）由于采用了目標(biāo)函數(shù)二階導(dǎo)數(shù)信息，收斂速度比梯度法快。（2）牛頓法迭代公式與一般迭代公式的區(qū)別在于，沒有步長(zhǎng)系數(shù)。這使得在接近最優(yōu)點(diǎn)時(shí)由于步長(zhǎng)不能調(diào)節(jié)，可能會(huì)錯(cuò)過最優(yōu)點(diǎn)，造成算法的穩(wěn)定性欠佳，甚至造成不能收斂而導(dǎo)致計(jì)算失敗。為了克服這一點(diǎn)提出阻尼牛頓法，添加阻尼因子，迭代公式為SKIPIF1<0。（3）需要計(jì)算黑塞矩陣及其逆矩陣，內(nèi)存占用、計(jì)算量大；此外二階導(dǎo)數(shù)不存在，或者逆矩陣不存在的情況不能應(yīng)用。4.6變尺度法4.6.1變尺度法基本原理牛頓法的缺點(diǎn)集中在黑塞矩陣及其逆的計(jì)算上，解決的方法是保留牛頓迭代法的迭代公式的形式，但不計(jì)算黑塞矩陣的逆，而是用一個(gè)矩陣去近似和逼近[H]-1,以減少計(jì)算量。4.6.2變尺度法迭代公式SKIPIF1<0[Ak]——稱為變尺度矩陣對(duì)第一輪迭代，[A0][I],即SKIPIF1<0，也就是梯度法當(dāng)?shù)^程逼近最優(yōu)點(diǎn)，[Ak][H]-1,迭代公式變成SKIPIF1<0，也就是阻尼牛頓法。所以，可以把變尺度法看作梯度法和牛頓法的改進(jìn)算法。或者梯度法和牛頓法是變尺度法的特例。至于變尺度矩陣[Ak]如何構(gòu)造，才能達(dá)到預(yù)期的效果，方法很多，主要介紹DFP法和BFGS法。思路為：為了使變尺度矩陣隨著迭代過程逐漸逼近黑塞矩陣的逆，構(gòu)造SKIPIF1<0，其中SKIPIF1<0為k次迭代的修正矩陣。4.6.2DFP變尺度法變尺度矩陣的修正是變尺度法區(qū)別于牛頓法之處：修正矩陣SKIPIF1<0其中SKIPIF1<0，相鄰兩迭代點(diǎn)之間的變化量 SKIPIF1<0，相鄰兩迭代點(diǎn)之間梯度的變化量4.6.3BFGS變尺度法修正矩陣SKIPIF1<04.6.4變尺度法迭代步驟和算法流程迭代步驟（1）給定初始點(diǎn)，精度，維數(shù)N；（2）置k0，[Ak][I],計(jì)算初始點(diǎn)梯度；（3）計(jì)算搜索方向SKIPIF1<0；（4）從k點(diǎn)開始一維搜索，得到k+1點(diǎn)；（5）迭代終止條件SKIPIF1<0，若滿足，輸出最優(yōu)點(diǎn)和最優(yōu)解；否則下一步；（6）檢驗(yàn)迭代次數(shù)，若為N,置k+1點(diǎn)為初始點(diǎn)，轉(zhuǎn)（2）重新構(gòu)造變尺度矩陣；否則下一步；（7）計(jì)算SKIPIF1<0、SKIPIF1<0，修正矩陣SKIPIF1<0、變尺度矩陣SKIPIF1<0，置kk+1,轉(zhuǎn)（3）。算法流程圖：SKIPIF1<0

第五章約束優(yōu)化方法前言：實(shí)際工程優(yōu)化問題大多數(shù)為設(shè)計(jì)空間多維且?guī)в屑s束條件的非線性優(yōu)化問題。其數(shù)學(xué)模型為SKIPIF1<0根據(jù)對(duì)約束條件處理方法的不同：直接法（約束坐標(biāo)輪換法、隨機(jī)方向法、復(fù)合形法、可行方向法）間接法（簡(jiǎn)約梯度法、懲罰函數(shù)法等）。直接法可以直接從可行域中找到最優(yōu)解；將問題分解為一系列比較簡(jiǎn)單的子問題，用子問題的解逼近原問題的解。直接法簡(jiǎn)單直觀、對(duì)目標(biāo)函數(shù)要求不高；計(jì)算量大、收斂慢，因此效率低。5.1約束隨機(jī)方向搜索法（隨機(jī)方向法）5.1.1基本原理從可行域內(nèi)某一點(diǎn)出發(fā)，沿某一給定步長(zhǎng)，并隨機(jī)產(chǎn)生搜索方向，直到該方向同時(shí)滿足可行性和下降性要求，沿著這個(gè)方向以該步長(zhǎng)繼續(xù)搜索，直到不滿足可行性及下降性條件為止。把上述滿足要求的終點(diǎn)作為新的起點(diǎn)，重新產(chǎn)生隨機(jī)方向，如果能夠找到一個(gè)合適的方向，同時(shí)滿足條件，則沿該方向以原步長(zhǎng)繼續(xù)搜索；如若找不到適合的方向，則將步長(zhǎng)減半，仍以該點(diǎn)為起點(diǎn)隨機(jī)搜索，如果能找到新的方向，則沿該方向繼續(xù)，如果不能，步長(zhǎng)再減半。直到找不到新的搜索方向，且步長(zhǎng)滿足精度要求，則以該起點(diǎn)為最優(yōu)點(diǎn)。一個(gè)需要說明的問題：從某一點(diǎn)出發(fā)，如何判斷沿某一給定步長(zhǎng)找不到可行的方向呢？如果不靠目標(biāo)函數(shù)和約束條件中隱含的指引信息，那么只有對(duì)搜索空間進(jìn)行機(jī)械的排查，對(duì)隨機(jī)方向搜索法而言，就是在產(chǎn)生并搜索了足夠多方向之后，認(rèn)為可以近似的得出這個(gè)結(jié)論。那么，到底隨機(jī)搜索了多少個(gè)方向才能得出結(jié)論呢？一般取50~500個(gè)方向，當(dāng)然，如果不考慮計(jì)算的速度和效率，這個(gè)最大的方向數(shù)大一些更好，而且設(shè)計(jì)空間維數(shù)越大，這個(gè)數(shù)也應(yīng)越大。5.1.2初始點(diǎn)的選取SKIPIF1<0其中ri為隨機(jī)數(shù)，對(duì)C語言，有函數(shù)rand()產(chǎn)生一個(gè)0到RAND_MAX的偽隨機(jī)整數(shù)，則SKIPIF1<05.1.3隨機(jī)搜索方向的產(chǎn)生SKIPIF1<0。通過該變換，使搜索方向的每個(gè)分量為-1到1之間的隨機(jī)值，從而確保對(duì)每個(gè)坐標(biāo)方向的正負(fù)兩方向的搜索。之后可以進(jìn)行標(biāo)準(zhǔn)化處理SKIPIF1<05.1.4算法流程（下一頁）5.1.5隨機(jī)法的特點(diǎn)算法簡(jiǎn)單，對(duì)目標(biāo)函數(shù)要求不高；由于隨機(jī)搜索帶有盲目性，效率低，速度慢，可能不收斂。

SKIPIF1<0

5.2復(fù)合形法5.2.1基本原理在設(shè)計(jì)空間找到K個(gè)可行點(diǎn)構(gòu)成多面體（復(fù)合形），一般N+1≤K≤2N。不斷使復(fù)合形向著約束內(nèi)最優(yōu)點(diǎn)移動(dòng)和收縮。更具體一些，根據(jù)目標(biāo)函數(shù)值的大小找出這K個(gè)點(diǎn)中的最壞