第四章優(yōu)化設(shè)計(jì)

本章主要內(nèi)容

優(yōu)化設(shè)計(jì)概述優(yōu)化問(wèn)題的數(shù)學(xué)分析基礎(chǔ)一維探索優(yōu)化方法無(wú)約束多維問(wèn)題的優(yōu)化方法約束問(wèn)題的優(yōu)化方法多目標(biāo)函數(shù)的優(yōu)化方法第四章優(yōu)化設(shè)計(jì)4.1優(yōu)化設(shè)計(jì)概述所謂最優(yōu)化，通俗地說(shuō)就是在一定條件下，在所有可能的計(jì)劃、設(shè)計(jì)、安排中找出最好的一個(gè)來(lái)。換句話說(shuō)，也就是在一定的條件下，人們?nèi)绾我宰詈玫姆绞絹?lái)做一件事情。

最優(yōu)化：Optimization。簡(jiǎn)寫(xiě)：Opt.結(jié)論的唯一性是最優(yōu)化的特點(diǎn)，即公認(rèn)最好。例如：要求設(shè)一個(gè)防洪堤壩，能防洪同時(shí)省時(shí)、省力又省經(jīng)費(fèi)。

能防洪：高度保證洪水不會(huì)漫入堤岸強(qiáng)度保證巨浪不會(huì)沖垮堤壩省時(shí)省力省經(jīng)費(fèi)優(yōu)化過(guò)程就是求解一個(gè)付出的努力最小、獲得效益最大的方案。獲得設(shè)計(jì)方案的過(guò)程是一個(gè)決策的過(guò)程，也是優(yōu)化的過(guò)程。所作的努力或希望的效益在實(shí)際問(wèn)題中可以作為一些決策變量的函數(shù)。解析法數(shù)值計(jì)算法優(yōu)化方法微分求極值迭代逼近最優(yōu)值計(jì)算機(jī)優(yōu)化設(shè)計(jì)優(yōu)化設(shè)計(jì)方法是數(shù)學(xué)規(guī)劃和計(jì)算機(jī)技術(shù)相結(jié)合的產(chǎn)物,它是一種將設(shè)計(jì)變量表示為產(chǎn)品性能指標(biāo)、結(jié)構(gòu)指標(biāo)或運(yùn)動(dòng)參數(shù)指標(biāo)的函數(shù)(稱為目標(biāo)函數(shù)),然后在產(chǎn)品規(guī)定的性態(tài)、幾何和運(yùn)動(dòng)等其它條件的限制(稱為約束條件)的范圍內(nèi),尋找滿足一個(gè)目標(biāo)函數(shù)或多個(gè)目標(biāo)函數(shù)最大或最小的設(shè)計(jì)變量組合的數(shù)學(xué)方法。例1-1

設(shè)計(jì)一個(gè)體積為5cm3的薄板包裝箱，其中一邊的長(zhǎng)度不小于4m。要求使薄板耗材最少，試確定包裝箱的尺寸參數(shù)，即長(zhǎng)a，寬b和高h(yuǎn)。傳統(tǒng)設(shè)計(jì)方法:首先固定包裝箱一邊的長(zhǎng)度如。要滿足包裝箱體積為的設(shè)計(jì)要求，則有以下多種設(shè)計(jì)方案:該問(wèn)題可以用數(shù)學(xué)的方法描述為：在滿足包裝箱的體積，長(zhǎng)度的限制條件下，確定參數(shù)a,b和h的值，使得包裝箱的表面積達(dá)到最小。

根據(jù)這樣的描述，可以建立一個(gè)優(yōu)化的數(shù)學(xué)模型，然后選擇適當(dāng)?shù)膬?yōu)化方法和計(jì)算程序，在計(jì)算機(jī)進(jìn)行數(shù)值迭代、求解，最后得到這個(gè)數(shù)學(xué)模型的結(jié)果是優(yōu)化設(shè)計(jì)方法:優(yōu)化設(shè)計(jì)流程

傳統(tǒng)設(shè)計(jì)流程設(shè)計(jì)要求方案設(shè)計(jì)綜合與分析評(píng)價(jià)輸出圖文技術(shù)資料優(yōu)化設(shè)計(jì)數(shù)學(xué)模型優(yōu)選設(shè)計(jì)變量?jī)?yōu)化算法程序是否是否滿足要求輸出優(yōu)化設(shè)計(jì):就是借助計(jì)算機(jī)技術(shù)，應(yīng)用精確度較高的力學(xué)數(shù)值分析方法進(jìn)行分析計(jì)算，從滿足給定的設(shè)計(jì)要求的許多可行方案中，按照給定的指標(biāo)自動(dòng)地選出最優(yōu)的設(shè)計(jì)方案。

優(yōu)化設(shè)計(jì)與傳統(tǒng)設(shè)計(jì)相比，具有如下三個(gè)特點(diǎn)：

(1)設(shè)計(jì)的思想是最優(yōu)設(shè)計(jì)；(2)設(shè)計(jì)的方法是優(yōu)化方法；(3)設(shè)計(jì)的手段是計(jì)算機(jī)。傳統(tǒng)設(shè)計(jì)可行解優(yōu)化設(shè)計(jì)最優(yōu)解古典優(yōu)化思想：17世紀(jì)發(fā)明微積分中的極值問(wèn)題；經(jīng)典優(yōu)化設(shè)計(jì)：20世紀(jì)40年代起，數(shù)學(xué)規(guī)劃論和計(jì)算機(jī)技術(shù)的發(fā)展使做優(yōu)化設(shè)計(jì)計(jì)算成為可能；優(yōu)化設(shè)計(jì)從無(wú)約束----有約束優(yōu)化問(wèn)題；連續(xù)變量----離散變量；確定型-----隨機(jī)型模型；單目標(biāo)優(yōu)化----多目標(biāo)優(yōu)化；現(xiàn)代優(yōu)化設(shè)計(jì)：20世紀(jì)80年代出現(xiàn)許多現(xiàn)代優(yōu)化算法：模擬退火法、遺傳算法、人工神經(jīng)網(wǎng)絡(luò)法、蟻群優(yōu)化算法等；并從狹義優(yōu)化設(shè)計(jì)（零部件參數(shù)）轉(zhuǎn)向廣義優(yōu)化設(shè)計(jì)（面向產(chǎn)品的全系統(tǒng)、設(shè)計(jì)全過(guò)程、全生命周期）針對(duì)涉及多領(lǐng)域復(fù)雜系統(tǒng)的多學(xué)科設(shè)計(jì)優(yōu)化。優(yōu)化設(shè)計(jì)的發(fā)展概況

優(yōu)化設(shè)計(jì)就是借助最優(yōu)化數(shù)值計(jì)算方法與計(jì)算機(jī)技術(shù)，求取工程問(wèn)題的最優(yōu)設(shè)計(jì)方案。優(yōu)化設(shè)計(jì)包括：

（1）必須將實(shí)際問(wèn)題加以數(shù)學(xué)描述，形成數(shù)學(xué)模型；（2）選用適當(dāng)?shù)囊环N最優(yōu)化數(shù)值方法和計(jì)算程序運(yùn)算求解。案例外嚙合齒輪泵的優(yōu)化設(shè)計(jì)外嚙合齒輪泵是一種應(yīng)用廣泛的齒輪泵，在輸出壓力、輸出流量、轉(zhuǎn)速分別為25Mpa、100L/min和1500r/min的情況下，要求確定一臺(tái)具有流量均勻性好、體積小、壽命長(zhǎng)的外嚙合齒輪泵的幾何設(shè)計(jì)參數(shù)。設(shè)計(jì)參數(shù)：模數(shù)m,

齒數(shù)z，

變位系數(shù)x滿足：gu(m、z、x)的情況下尋找：一組設(shè)計(jì)參數(shù)m、z、x；（模數(shù)、齒數(shù)、變位系數(shù)）使得：設(shè)計(jì)目標(biāo)流量最均勻,體積最小,壽命最長(zhǎng)以齒輪泵為例，其優(yōu)化設(shè)計(jì)過(guò)程如下：已知：傳動(dòng)比i,轉(zhuǎn)速n,傳動(dòng)功率P，大小齒輪的材料，設(shè)計(jì)該齒輪副，使其重量最輕。分析：

（1）圓柱齒輪的體積(v)與重量(w)的表達(dá)；

（2）設(shè)計(jì)參數(shù)確定：模數(shù)（m），齒寬（b），齒數(shù)（z1）；

（3）設(shè)計(jì)約束條件：

（a）大齒輪滿足彎曲強(qiáng)度要求；（b）小齒輪滿足彎曲強(qiáng)度要求；

（c）齒輪副滿足接觸疲勞強(qiáng)度要求；

（d）齒寬系數(shù)要求；（e）最小齒數(shù)要求。例題2：直齒圓柱齒輪副的優(yōu)化設(shè)計(jì)數(shù)學(xué)模型設(shè)計(jì)參數(shù)：設(shè)計(jì)目標(biāo)：約束條件：4.1.2優(yōu)化設(shè)計(jì)的數(shù)學(xué)模型優(yōu)化設(shè)計(jì)的問(wèn)題首先是建立數(shù)學(xué)模型，即把實(shí)際問(wèn)題轉(zhuǎn)化為數(shù)學(xué)模型的形式。例：平面四連桿機(jī)構(gòu)的優(yōu)化設(shè)計(jì)（a）x1、x2、x3、x4、是AB、BC、CD和AD的長(zhǎng)度；（b）φ是曲柄輸入角；（c）φ0是搖桿的右極限位置角

；一般規(guī)定x1=1.0，而這里x4是給定的，設(shè)x4=5.0，所以我們只要確定x2和x3是設(shè)計(jì)變量。例：平面四連桿機(jī)構(gòu)的優(yōu)化設(shè)計(jì)目標(biāo)函數(shù)為：期望輸出角與實(shí)際輸出角的平均誤差積分準(zhǔn)則（下式）。例：平面四連桿機(jī)構(gòu)的優(yōu)化設(shè)計(jì)如果規(guī)定x1=1.0，且設(shè)x4=5.0，可確定x2和x3的邊界條件為：和4.1.2優(yōu)化設(shè)計(jì)的數(shù)學(xué)模型優(yōu)化設(shè)計(jì)的問(wèn)題首先是建立數(shù)學(xué)模型，即把實(shí)際問(wèn)題轉(zhuǎn)化為數(shù)學(xué)模型的形式。

優(yōu)化模型三要素：設(shè)計(jì)變量，目標(biāo)函數(shù)，約束條件。1.設(shè)計(jì)變量

設(shè)計(jì)過(guò)程中，進(jìn)行選擇和調(diào)整，最終必須確定的獨(dú)立參數(shù)稱為設(shè)計(jì)變量；固定不變，需要事先給定的參數(shù)稱為設(shè)計(jì)常量。（1）維數(shù)：設(shè)計(jì)變量的個(gè)數(shù)稱為設(shè)計(jì)問(wèn)題的維數(shù)。設(shè)計(jì)變量愈多，設(shè)計(jì)自由度愈大，可供選擇方案愈多，設(shè)計(jì)愈靈活，難度愈大，求解愈復(fù)雜。（2）設(shè)計(jì)空間:

n個(gè)設(shè)計(jì)變量的坐標(biāo)軸所形成的n維實(shí)空間稱為設(shè)計(jì)空間，用Rn表示。設(shè)計(jì)空間中，n個(gè)設(shè)計(jì)變量的坐標(biāo)值組成一個(gè)設(shè)計(jì)點(diǎn)，并代表一個(gè)設(shè)計(jì)方案，可采用如下向量表示：其中，最優(yōu)設(shè)計(jì)方案用表示，稱為最優(yōu)點(diǎn)或優(yōu)化點(diǎn)。二維設(shè)計(jì)空間三維設(shè)計(jì)空間x2x1X=[x1

x2]Tx1x2x3X=[x1

x2x3]T2.約束條件（函數(shù)）

對(duì)任何設(shè)計(jì)都有若干不同的要求和限制，將這些要求和限制表示成設(shè)計(jì)變量的函數(shù)并寫(xiě)成一系列不等式和等式表達(dá)式，就構(gòu)成了設(shè)計(jì)的約束條件簡(jiǎn)稱約束。其作用是對(duì)設(shè)計(jì)變量的取值加以限制。（1）分類根據(jù)形式的不同：等式約束和不等式約束。根據(jù)性質(zhì)的不同：邊界約束和性能約束。邊界約束：直接限制每個(gè)設(shè)計(jì)變量的取值范圍或彼此相互關(guān)系的一些輔助的區(qū)域約束。性能約束：由產(chǎn)品性能或設(shè)計(jì)者要求推導(dǎo)出來(lái)的用以間接限制設(shè)計(jì)變量取值范圍的一種約束。

2.約束條件（函數(shù)）（2）可行域任何一個(gè)不等式約束都把設(shè)計(jì)空間分為兩部分，一部分是滿足約束條件的稱為可行域，另一部分是不滿足約束條件的稱為非可行域，這兩部分的分界是。在約束邊界上的點(diǎn)稱為邊界點(diǎn)兩個(gè)以上約束邊界的交點(diǎn)稱為角點(diǎn)(約束方程)不等式約束與等式約束的幾何意義：在一個(gè)優(yōu)化設(shè)計(jì)問(wèn)題的設(shè)計(jì)空間中，滿足所有約束條件的點(diǎn)構(gòu)成的子空間，稱為可行域。(2)等式約束(1)不等式約束【例1】作出下列約束條件構(gòu)成的可行域：【例2】根據(jù)下列約束條件畫(huà)出可行域。（3）起作用約束設(shè)X為設(shè)計(jì)空間中的一個(gè)點(diǎn)：滿足所有約束條件的點(diǎn)稱為可行點(diǎn)（內(nèi)點(diǎn)和邊界點(diǎn)）不滿足所有約束條件的點(diǎn)稱為非可行點(diǎn)（外點(diǎn)）X在某個(gè)約束邊界上，則這個(gè)約束條件稱為X的起作用約束X不在某個(gè)約束邊界上，則這個(gè)約束條件稱為X的不起作用約束起作用約束設(shè)計(jì)點(diǎn)X(k)的所有起作用約束的函數(shù)序號(hào)下標(biāo)集合用Ik表示，即3.目標(biāo)函數(shù)

優(yōu)化設(shè)計(jì)的任務(wù)是在許多可行的方案中找出最優(yōu)的方案，所謂最優(yōu)方案是在設(shè)計(jì)變量中能最好的滿足所追求的某些特點(diǎn)的目標(biāo)，而這些目標(biāo)又可表達(dá)為設(shè)計(jì)變量的函數(shù)，稱為目標(biāo)函數(shù)。目標(biāo)函數(shù)可用來(lái)評(píng)價(jià)設(shè)計(jì)方案的好壞，又稱為評(píng)價(jià)函數(shù)。常表示為：目標(biāo)函數(shù)表征的是設(shè)計(jì)的某項(xiàng)或某些最重要的特征。優(yōu)化設(shè)計(jì)就是要通過(guò)優(yōu)選設(shè)計(jì)變量使目標(biāo)函數(shù)達(dá)到最優(yōu)值。目標(biāo)函數(shù)總可以轉(zhuǎn)化成求最小值的統(tǒng)一形式。等值曲面:目標(biāo)函數(shù)值相等的所有設(shè)計(jì)點(diǎn)的集合稱為目標(biāo)函數(shù)的等值曲面。

二維：等值線；三維：等值面；三維以上：等超越面。z等值線族形象地反映了目標(biāo)函數(shù)值的變化規(guī)律，越靠近極值點(diǎn)的等值線，表示的目標(biāo)函數(shù)值越小，其分布也越密集。xyo等高線x*（中心極值點(diǎn)）等值線族

二維設(shè)計(jì)變量下的等值線從等值線上，可以清除地看到函數(shù)值的變化情況。其中F=40的等值線就是使F(x1,x2)=40的各點(diǎn)[x1,x2]T所組成的連線。如圖函數(shù)的等值線圖。一般形式：4.優(yōu)化設(shè)計(jì)的數(shù)學(xué)模型

用“max、min”表示極大、極小化，用“s.t”表示“滿足于”，“m、p”表示不等式約束與等式約束的個(gè)數(shù)，則表示如下形式：

本課程中，所有的優(yōu)化設(shè)計(jì)問(wèn)題都是求目標(biāo)函數(shù)的極小值。遇到求極大值的問(wèn)題，則先通過(guò)轉(zhuǎn)化變成極小值問(wèn)題。與此同時(shí)，所有的不等式約束都采用的形式。按目標(biāo)函數(shù)的多少：?jiǎn)文繕?biāo)優(yōu)化和多目標(biāo)優(yōu)化按所能求解的維數(shù)：一維優(yōu)化和多維優(yōu)化按約束情況：無(wú)約束優(yōu)化和約束優(yōu)化按求優(yōu)的途徑：數(shù)學(xué)迭代法、解析法、圖解法5、優(yōu)化設(shè)計(jì)的分類數(shù)值迭代法：利用已有信息及再生信息進(jìn)行試探及迭代求優(yōu)的方法，便于采用計(jì)算機(jī)進(jìn)行處理，是目前優(yōu)化設(shè)計(jì)中廣泛采用的方法。解析法：利用函數(shù)性態(tài)通過(guò)微分或變分求優(yōu)。圖解法：利用作圖求優(yōu)，主要用于不超過(guò)二維的優(yōu)化問(wèn)題。6.優(yōu)化設(shè)計(jì)問(wèn)題的求解（1）圖解法

【例3】求解下列優(yōu)化問(wèn)題：最優(yōu)解是等值線在函數(shù)值下降方向上與可行域的最后一個(gè)交點(diǎn)?！纠?】求解下列優(yōu)化問(wèn)題：最優(yōu)解是等值線在函數(shù)值下降方向上與可行域的最后一個(gè)交點(diǎn)。非線性問(wèn)題的最優(yōu)解要么是一個(gè)內(nèi)點(diǎn)，要么是一個(gè)邊界點(diǎn)；非線性問(wèn)題的最優(yōu)解如果是一個(gè)邊界點(diǎn)，那么它必定是等值線（面）在函數(shù)值下降方向上與可行域的最后一個(gè)交點(diǎn)；線性問(wèn)題的最優(yōu)解必定是等值線（面）在函數(shù)值下降方向上與可行域的最后一個(gè)交點(diǎn)；一般情況下：（2）數(shù)值迭代法數(shù)值迭代法的基本思想：從一個(gè)初始點(diǎn)出發(fā)，按照一個(gè)可行的搜索方向和適當(dāng)?shù)牟介L(zhǎng)走一步，到達(dá)，再?gòu)某霭l(fā)，選一個(gè)可行的搜索方向和適當(dāng)?shù)牟介L(zhǎng)走一步，達(dá)到，并保證每一步函數(shù)值都是下降的，即必須滿足（這稱為新點(diǎn)的適用性），這樣一步一步地重復(fù)進(jìn)行數(shù)值計(jì)算，直至達(dá)到目標(biāo)函數(shù)的極小點(diǎn)。1)無(wú)約束優(yōu)化問(wèn)題初始點(diǎn)用某種優(yōu)化方法確定確定前進(jìn)步長(zhǎng)計(jì)算檢查若不滿足則改變步長(zhǎng)，滿足則進(jìn)入下一步從出發(fā)用某種優(yōu)化方法確定確定前進(jìn)步長(zhǎng)計(jì)算檢查若不滿足則改變步長(zhǎng)，滿足則進(jìn)入下一步從出發(fā)用某種優(yōu)化方法確定確定前進(jìn)步長(zhǎng)計(jì)算檢查若不滿足則改變步長(zhǎng)，滿足則進(jìn)入下一步從出發(fā)用某種優(yōu)化方法確定確定前進(jìn)步長(zhǎng)計(jì)算檢查若不滿足則改變步長(zhǎng)，滿足則進(jìn)入下一步——第k個(gè)迭代點(diǎn)——從第k個(gè)迭代點(diǎn)出發(fā)尋找下一個(gè)迭代點(diǎn)的搜索方向——沿前進(jìn)的步長(zhǎng)基本迭代公式

由于每次迭代求得的新點(diǎn)均為使函數(shù)值有所下降的適用點(diǎn)（如果不是適用點(diǎn)，可改變方向和步長(zhǎng)另行搜索適用點(diǎn)），則所得各點(diǎn)必將逐步向該函數(shù)的極小值點(diǎn)逼近，最后總可求得非常接近該函數(shù)理論最優(yōu)點(diǎn)的近似最優(yōu)點(diǎn)。2）約束優(yōu)化問(wèn)題

對(duì)于約束優(yōu)化問(wèn)題，除了檢查每個(gè)新點(diǎn)的適用性外，還要檢查其可行性，即是否滿足的約束條件，如果適用性和可行性兼?zhèn)?，再進(jìn)行下一次迭代，最終自然也能求得非常接近約束最優(yōu)點(diǎn)的近似最優(yōu)點(diǎn)。

綜上所述，采用數(shù)值法進(jìn)行迭代求優(yōu)時(shí)，除了選擇初始點(diǎn)以外，如何確定迭代方向和步長(zhǎng)成為非常重要的環(huán)節(jié)，他們將直接決定著搜索的效率、函數(shù)值逐步下降的穩(wěn)定性和優(yōu)化過(guò)程所需的時(shí)間等。A.點(diǎn)距準(zhǔn)則

根據(jù)相鄰兩迭代點(diǎn)與間的距離足夠小而建立的準(zhǔn)則，點(diǎn)距準(zhǔn)則可表示為或數(shù)值迭代終止準(zhǔn)則（計(jì)算精度的確定）

B.值差準(zhǔn)則

根據(jù)相鄰的兩迭代點(diǎn)的函數(shù)值下降量足夠小而建立的準(zhǔn)則。絕對(duì)下降量準(zhǔn)則：相對(duì)下降量準(zhǔn)則：C.梯度準(zhǔn)則

根據(jù)迭代點(diǎn)的函數(shù)梯度達(dá)到足夠小而建立的準(zhǔn)則，表示為或迭代法必須要解決的三個(gè)問(wèn)題迭代算法具有收斂性；在收斂性前提下，選擇比較好的初始點(diǎn)X(0)

和適宜的終止判據(jù)及收斂精度；選取使目標(biāo)函數(shù)值下降較快的迭代探索方向S(k)和最優(yōu)的迭代步長(zhǎng)α(k)

，確保較快的收斂速度。如何確定S(k)、α(k)優(yōu)化方法4.2優(yōu)化設(shè)計(jì)的數(shù)學(xué)分析基礎(chǔ)優(yōu)化設(shè)計(jì)的本質(zhì)：求極值。1.函數(shù)的泰勒展開(kāi)為便于對(duì)多變量問(wèn)題進(jìn)行數(shù)學(xué)分析和求解，往往需要采用線性函數(shù)和二次函數(shù)替代簡(jiǎn)化目標(biāo)函數(shù)。（1）一元函數(shù)的f(X)泰勒展開(kāi)：若f(x)在含有x(0)處的某個(gè)開(kāi)區(qū)間內(nèi)直到（n+1）階可導(dǎo)，只要開(kāi)區(qū)間（a,b）足夠小,則該函數(shù)在（a,b）內(nèi)x(0)點(diǎn)處的二階泰勒展開(kāi)式為：（2）二元函數(shù)f(x1，x2)的泰勒展開(kāi)：（3）多元函數(shù)f(x1，x2,…xn)的泰勒展開(kāi)：（3）多元函數(shù)f(x1，x2,…xn)的泰勒展開(kāi)：:目標(biāo)函數(shù)f(x)在點(diǎn)x(0)的所有一階偏導(dǎo)數(shù)組成的矩陣向量(一階導(dǎo)數(shù)矩陣向量或梯度）:目標(biāo)函數(shù)f(x)在點(diǎn)x(0)的所有二階偏導(dǎo)數(shù)組成的矩陣(二階導(dǎo)數(shù)矩陣或海色矩陣，記作H(x)），n×n階對(duì)稱矩陣函數(shù)梯度的特性：1、函數(shù)f(x)在給定點(diǎn)的梯度是一個(gè)向量，大小表示函數(shù)在改點(diǎn)的方向?qū)?shù)的最大值。2、函數(shù)在某點(diǎn)的梯度向量只給出了在改點(diǎn)極小領(lǐng)域內(nèi)函數(shù)的最快上升方向，具有一定局限性；3、函數(shù)在給定點(diǎn)的梯度方向函數(shù)等值線或等值面在該點(diǎn)法線方向。2.目標(biāo)函數(shù)極值的存在性優(yōu)化設(shè)計(jì)的首要工作是判斷極值的存在性，如不存在極值，優(yōu)化設(shè)計(jì)無(wú)意義。（1）無(wú)約束目標(biāo)函數(shù)極值的存在性目標(biāo)函數(shù)為一元函數(shù)f(x)

f(x)在點(diǎn)x(0)處有極值的充要條件為：時(shí)，有極小值；時(shí)，有極大值。一元函數(shù)的極值點(diǎn)極小值點(diǎn)0xyy=f(x)x00xyy=f(x)x00yy=f(x)x0極大值點(diǎn)不存在極值點(diǎn)目標(biāo)函數(shù)為多元函數(shù)f(x1，x2,…xn)

f(X)在點(diǎn)X(0)處有極值的充要條件為：（必要條件）（充分條件）正定時(shí)，有極小值；（必要條件）（充分條件）負(fù)定時(shí)，有極大值；【例

5】試證明函數(shù)在點(diǎn)處具有極小值。解：將代入得H(X(0))正定，目標(biāo)函數(shù)在（2,4）處具有極小值。（2）目標(biāo)函數(shù)的凸性目標(biāo)函數(shù)的極值點(diǎn)一般是相對(duì)于它附近的局部區(qū)域中的各點(diǎn)而言的，目標(biāo)函數(shù)在其整個(gè)可行區(qū)域中，有時(shí)可能存在許多個(gè)極值點(diǎn)，優(yōu)化設(shè)計(jì)時(shí)應(yīng)力求找到多個(gè)極值點(diǎn)中的最小值點(diǎn)，即全局最優(yōu)點(diǎn)或整體最優(yōu)點(diǎn)，其它非最小值的極值點(diǎn)稱為局部最優(yōu)點(diǎn)或相對(duì)最優(yōu)點(diǎn)。凸性：?jiǎn)畏逍?，目?biāo)函數(shù)若為凸性，極值點(diǎn)只有一個(gè)，即為全局最優(yōu)點(diǎn)。

凸集：假設(shè)在n維歐式空間Rn

中有一個(gè)集合D

，即，若D內(nèi)任意兩點(diǎn)X(1),X(2)

之間的連接直線都屬于集合D

,則D為n維歐式空間內(nèi)的一個(gè)凸集，否則為非凸集。如果將X(1),X(2)

之間的連接直線用表達(dá)，則凸集的數(shù)學(xué)表達(dá)式為：若則x2x1x(2)x(1)x2x1x(2)x(1)凸集非凸集凸集的幾何特征：其任意兩點(diǎn)連線上的一切點(diǎn)都位于這個(gè)幾何內(nèi)。凸函數(shù)：凸函數(shù)的數(shù)學(xué)表達(dá)式為：f(x)x2x1xf(x2)f(x1)判斷函數(shù)f(x)為凸函數(shù)的充要條件：方法1：若函數(shù)f(x)在D上具有一階的連續(xù)導(dǎo)數(shù)，對(duì)任意兩點(diǎn)x(1),x(2)

,

f(x)為凸函數(shù)的充要條件是:恒成立方法2：若函數(shù)f(X)在D上具有二階的連續(xù)導(dǎo)數(shù)，則f(X)為凸函數(shù)的充要條件是:

H(X)處處半正定

凸性形態(tài)表現(xiàn)為下凸時(shí)，函數(shù)為凸函數(shù)；凸性表現(xiàn)為上凸時(shí)，函數(shù)為凹函數(shù)。（3）有約束目標(biāo)函數(shù)極值的存在性目標(biāo)函數(shù)有約束極值還是無(wú)約束極值，主要取決于約束條件對(duì)極值和極值點(diǎn)的影響。同樣的目標(biāo)函數(shù)對(duì)于不同的約束條件，可能出現(xiàn)不同的最優(yōu)值和最優(yōu)點(diǎn)，其原因在于不同的約束條件限制了設(shè)計(jì)變量不同的取值范圍。有約束最優(yōu)問(wèn)題需要解決的問(wèn)題

判斷約束極值點(diǎn)存在的條件；判斷找到的極值點(diǎn)是全局最優(yōu)點(diǎn)還是局部最優(yōu)點(diǎn)。A.無(wú)約束最優(yōu)點(diǎn)為可行域的內(nèi)點(diǎn)，此時(shí)目標(biāo)函數(shù)的最優(yōu)點(diǎn)就是約束問(wèn)題的最優(yōu)點(diǎn)；約束最優(yōu)點(diǎn)和無(wú)約束最優(yōu)點(diǎn)的相互關(guān)系：B.無(wú)約束最優(yōu)點(diǎn)在可行域外，約束問(wèn)題的最優(yōu)點(diǎn)是約束邊界上的一點(diǎn)，該點(diǎn)是約束邊界與目標(biāo)函數(shù)一條等值線（面）的切點(diǎn)；對(duì)于等式約束問(wèn)題等式約束的極值條件可以建立拉格朗日函數(shù)這就是等式約束問(wèn)題在點(diǎn)X*取得極值的必要條件，它的含義是：

在等式約束問(wèn)題的極值點(diǎn)上，目標(biāo)函數(shù)的負(fù)梯度等于諸約束函數(shù)在該點(diǎn)梯度的線性組合。對(duì)于不等式約束問(wèn)題不等式約束的極值條件可以通過(guò)引入m個(gè)松弛變量將不等式約束變成等式約束然后類似地建立拉格朗日函數(shù)K-T（Kuhn-Tucker)條件：例題：試用K-T條件判定點(diǎn)X=[1，0]T是否為下列優(yōu)化問(wèn)題的極值點(diǎn)。解：畫(huà)出該優(yōu)化問(wèn)題的目標(biāo)函數(shù)等值線和可行域解：畫(huà)出該優(yōu)化問(wèn)題的目標(biāo)函數(shù)等值線和可行域。找出起作用約束。求出目標(biāo)函數(shù)和約束函數(shù)在點(diǎn)

出的梯度將上述梯度代入K-T條件式，即得解得：為非負(fù)乘子，滿足K-T條件，所以點(diǎn)為條件極值點(diǎn)。3.3一維探索優(yōu)化方法

一維搜索的數(shù)學(xué)形式一維搜索的幾何意義常用一維搜索方法：進(jìn)退法

黃金分割法

一、概述數(shù)值迭代過(guò)程中，任何一次迭代，總是從某個(gè)已知點(diǎn)出發(fā)，沿著給定的方向（用某種優(yōu)化方法確定）搜索到目標(biāo)函數(shù)在該方向上的極小值點(diǎn)，這個(gè)過(guò)程稱為一維搜索。一維搜索不僅可以求解一維優(yōu)化問(wèn)題，同時(shí)也是求解多維優(yōu)化問(wèn)題的基本步驟。1.一維搜索的概念

怎么理解“一維”的含義？對(duì)“一維”的理解尋找目標(biāo)函數(shù)在指定方向上的極小點(diǎn)，在計(jì)算上就是從沿前進(jìn)多少的問(wèn)題，即求步長(zhǎng)因子的問(wèn)題。從這個(gè)意義上講，一維搜索是一個(gè)求解關(guān)于的單元目標(biāo)函數(shù)的過(guò)程。一維搜索尋找合適的，使最小“一維”是指“一個(gè)方向”（）；任一次迭代，都是求使得即其中：表示步長(zhǎng)因子表示最優(yōu)步長(zhǎng)因子2.一維搜索的數(shù)學(xué)形式

3.一維搜索的幾何意義

從出發(fā)，沿方向一維搜索，就是求方向與等值線的切點(diǎn)，此時(shí)的步長(zhǎng)因子即為最優(yōu)步長(zhǎng)因子。分為兩步：1、在搜索方向上確定一一個(gè)包含極小點(diǎn)的初始區(qū)域2、縮小區(qū)間，確定最優(yōu)步長(zhǎng)。4.單峰區(qū)間

對(duì)于所有的一維搜索方法，首先遇到的共同問(wèn)題是：如何確定一個(gè)初始搜索區(qū)間，使該區(qū)間內(nèi)含有函數(shù)的極小點(diǎn)，且在該區(qū)間內(nèi)函數(shù)有唯一的極小點(diǎn)，這個(gè)初始搜索區(qū)間就是單峰區(qū)間。

設(shè)函數(shù)f(x)在區(qū)間內(nèi)有定義，且(1)在區(qū)間內(nèi)存在極小點(diǎn)，即有

(2)區(qū)間上的任意x，均滿足；區(qū)間上的任意x，有用解析法給單峰區(qū)間下一個(gè)定義：則稱閉區(qū)間為函數(shù)f(x)的單峰區(qū)間。單峰區(qū)間的特點(diǎn)：?jiǎn)畏鍏^(qū)間內(nèi)，在極小點(diǎn)的左邊，函數(shù)是嚴(yán)格減少的，在極小點(diǎn)的右邊，函數(shù)是嚴(yán)格增加的；如果區(qū)間是一個(gè)單峰區(qū)間，x是區(qū)間內(nèi)的一點(diǎn)，則兩個(gè)不等式中必有一個(gè)成立；單峰區(qū)間內(nèi)的函數(shù)圖形表現(xiàn)為“高－低－高”的形態(tài)。應(yīng)用這一特征可以確定單峰區(qū)間。如果函數(shù)具有多個(gè)極小點(diǎn)，則表現(xiàn)為多峰函數(shù)。此時(shí)，需要對(duì)變量取值范圍進(jìn)行適當(dāng)?shù)膭澐郑姑恳粋€(gè)子空間只包含一個(gè)極小點(diǎn)，才能進(jìn)行一維搜索。一維搜索時(shí)，同樣需要在每個(gè)子空間內(nèi)尋找單峰區(qū)間。注意：假設(shè)第k次得到的區(qū)間，若，則可取作為極小點(diǎn)。5.一維搜索的基本思想

一維搜索就是要在初始單峰區(qū)間中求單峰函數(shù)的極小點(diǎn)。所以找初始單峰區(qū)間是一維搜索的第一步，然后將初始單峰區(qū)間逐步縮小，直至包括極小點(diǎn)的區(qū)間長(zhǎng)度小于給定的一個(gè)正數(shù)，此稱為收斂精度或迭代精度?？s小區(qū)間的區(qū)間消去法6.探索區(qū)間(初始單峰區(qū)間）的確定方法

一維問(wèn)題的探索方向是確定的，一維探索實(shí)際是求可行域內(nèi)的最優(yōu)步長(zhǎng)(k),使目標(biāo)函數(shù)值達(dá)到最小，首先必須確定包含最優(yōu)點(diǎn)的可行域[s,e]。進(jìn)退試算法包含最優(yōu)點(diǎn)的單峰區(qū)間[s,e]內(nèi)，目標(biāo)函數(shù)值呈現(xiàn)“大—小—大”的U字形。假設(shè)(1)<(2)<(3)為三個(gè)相鄰點(diǎn)，若

f((1))>f((2))<f((3))

則[(1),(3)]是一個(gè)包含極小點(diǎn)的區(qū)間。

前進(jìn)算法：將(k)和(k)+h代入目標(biāo)函數(shù)，如果f((k))>f((k)+h)，則將步長(zhǎng)增加一倍(2h)；得到下一個(gè)點(diǎn)(k)+3h。比較相鄰三點(diǎn)函數(shù)值：如果f((k)+h)<f((k)+3h)，則探索區(qū)間[s,e]為[(k),(k)+3h]

否則，再將將步長(zhǎng)增加一倍，重復(fù)上述運(yùn)算。前進(jìn)方向

后退算法：將(k)和(k)+h代入目標(biāo)函數(shù)，如果f((k))<f((k)+h)，將步長(zhǎng)反號(hào)，即令h=-h，得到下一個(gè)點(diǎn)(k)-h。比較相鄰三點(diǎn)函數(shù)值：如果f((k)-h)>f((k))，則探索區(qū)間[s,e]為[(k)-h,(k)+h]，否則將步長(zhǎng)加倍并按前進(jìn)算法重復(fù)上述運(yùn)算。后退方向進(jìn)退法的程序框圖【例7】試用進(jìn)退算法確定函數(shù)的初始搜索區(qū)間，設(shè)初始點(diǎn)，初始步長(zhǎng)h=1。采用不同的初始點(diǎn)、不同的初始步長(zhǎng)得到的初始單峰區(qū)間可能不一樣，但只要這個(gè)單峰區(qū)間包含極小點(diǎn)，就是正確的。1.黃金分割法1)基本原理

對(duì)于目標(biāo)函數(shù)f(x)，在區(qū)間[a,b]內(nèi)，適當(dāng)插入兩個(gè)內(nèi)分點(diǎn)x1和x2(x1<x2),它們把[a,b]分成三段。計(jì)算并比較x1和x2兩點(diǎn)的函數(shù)值f(x1)和f(x2)，因?yàn)閇a,b]是單峰區(qū)間，故當(dāng)f(x1)>f(x2)時(shí)，極小點(diǎn)必在[x1,b]中；當(dāng)f(x1)≤f(x2)時(shí)，極小點(diǎn)必在[a,x2]中。二、一維搜索方法無(wú)論發(fā)生在那種情況，都將包含極小點(diǎn)的區(qū)間縮小，即可刪去最左段或最右段，然后在保留下來(lái)的區(qū)間上做同樣的處理，如此迭代下去，將使搜索區(qū)間逐步減小，直到滿足預(yù)先給定的精度（終止準(zhǔn)則）時(shí)，即獲得一維優(yōu)化問(wèn)題的近似最優(yōu)解。消去函數(shù)值大的內(nèi)分點(diǎn)到同一側(cè)端點(diǎn)之間的區(qū)間黃金分割法要求在區(qū)間[a,b]中插入的兩點(diǎn)位置是對(duì)稱的，如圖所示，ax1=x2b。設(shè)區(qū)間長(zhǎng)為L(zhǎng)，插入的兩個(gè)點(diǎn)把區(qū)間分成較長(zhǎng)的一段α和較短的一段(L

–

α)，如圖所示，，，這樣，無(wú)論刪去那一段，保留的區(qū)間長(zhǎng)度總是α，在每次迭代中，整個(gè)區(qū)間的長(zhǎng)度α與較長(zhǎng)一段長(zhǎng)度的比等于較長(zhǎng)一段長(zhǎng)度與較短長(zhǎng)度的比。2）黃金分割法的迭代步驟

（1）給定初始單峰區(qū)間[a,b]及允許誤差ε>0；（2）計(jì)算內(nèi)分點(diǎn)及其函數(shù)值（3）比較函數(shù)值f1和f2的大?。桓鶕?jù)比較結(jié)果縮短搜索區(qū)間A.當(dāng)f1≤f2時(shí)，極小點(diǎn)必在[a,x2]中，則B.當(dāng)f1>f2時(shí)，極小點(diǎn)必在[x1,b]中，則（4）判斷是否滿足精度要求。若新區(qū)間已縮短至預(yù)定精度要求，即，則轉(zhuǎn)第5）步；否則轉(zhuǎn)第3）步，進(jìn)行下一次迭代計(jì)算。（5）輸出最終區(qū)間的中點(diǎn)作為近似最優(yōu)點(diǎn)，其對(duì)應(yīng)的函數(shù)值即為最優(yōu)值，他們組成的最優(yōu)解為：黃金分割法的程序框圖【例2】試用0.618法求函數(shù)的極小點(diǎn)，設(shè)初始單峰區(qū)間初始點(diǎn)，給定計(jì)算機(jī)精度

。2.二次插值法適于目標(biāo)函數(shù)易求一階或二階導(dǎo)數(shù)的情形。插值法：當(dāng)目標(biāo)函數(shù)比較復(fù)雜，不易通過(guò)

limf(x(k)+(k)s)=f(*)使目標(biāo)函數(shù)達(dá)到極小值時(shí)，可以采用一個(gè)容易求解極小值的較低次函數(shù)p(x)，在滿足一定的條件下來(lái)近似代替f(x)。

p(x)為二次函數(shù)時(shí)稱為二次插值法，p(x)為三次函數(shù)時(shí)稱為三次插值法。插值法的原理1(k)02(k)3(k)f(1(k))f(2(k))f(3(k))f()p()f()p()p()=A+B+C2二次插值法的程序框圖優(yōu)化問(wèn)題一維優(yōu)化問(wèn)題（1個(gè)設(shè)計(jì)變量）多維優(yōu)化問(wèn)題（多個(gè)設(shè)計(jì)變量）無(wú)約束多維問(wèn)題單目標(biāo)函數(shù)的優(yōu)化問(wèn)題多目標(biāo)函數(shù)的優(yōu)化問(wèn)題有約束多維問(wèn)題3.4無(wú)約束多維問(wèn)題的優(yōu)化方法

無(wú)約束優(yōu)化方法的核心是確定探索方向（能使目標(biāo)函數(shù)值下降的方向），有了方向，沿這個(gè)方向應(yīng)該走多遠(yuǎn)（最優(yōu)探索步長(zhǎng)），則可采用一維搜索方法解決。

多維無(wú)約束優(yōu)化問(wèn)題的一般數(shù)學(xué)表達(dá)式：一、坐標(biāo)輪換法（變量輪換法）基本原理：沿著多維優(yōu)化設(shè)計(jì)空間的每一個(gè)坐標(biāo)軸作一維探索，求得最小值。坐標(biāo)輪換法的基本原理x1x2X*X(0,1)X(1)X(2)X(3)X(0)0x1(0)x1(1)x1(2)x1(3)x1*x2(0)x2(1)x2(2)x2(3)x2*迭代步驟：（1）第1次迭代時(shí)，先固定x2=x2(0)

變量值不動(dòng)，由初始點(diǎn)X(0)沿x1軸向進(jìn)行一維探索，得到該軸方向上的最優(yōu)點(diǎn)X(0,1)=[x1(1),

x2(0)]；（2）固定x1=x1(1)

變量值不動(dòng)，由初始點(diǎn)X(0,1)

沿x2軸向進(jìn)行一維探索，得到該軸方向上的最優(yōu)點(diǎn)X(1)=[x1(1),

x2(1)]（3）將X

(1)

作為第1次迭代的改進(jìn)點(diǎn)，之后，完全依照第1次的步驟進(jìn)行第2、3、…、k次的坐標(biāo)輪換迭代，直到滿足精度要求后停止迭代。二、特點(diǎn)

1）計(jì)算量小，程序簡(jiǎn)單，計(jì)算效率低，易于掌握。2）搜索路線長(zhǎng)，計(jì)算效率較低，所以只能用于低維（n<10)優(yōu)化問(wèn)題求解。3）若目標(biāo)函數(shù)具有脊線，算法將出現(xiàn)病態(tài)：沿兩個(gè)坐標(biāo)方向均不能使函數(shù)數(shù)值下降，誤認(rèn)為最優(yōu)點(diǎn)。x1x2X(1)X*X(0)0x1x2X*X(0)X(1)X(2)X(3)X(4)0X(0)0x1x2X*X(1)二、梯度法（最速下降法）1.基本思想

梯度方向是函數(shù)值增加最快的方向，而負(fù)梯度方向是函數(shù)下降最快的方向，所以梯度法以負(fù)梯度方向?yàn)樗阉鞣较颍看蔚佳刂?fù)梯度方向一維搜索，直到滿足精度要求為止。因此，梯度法又稱為最速下降法迭代格式：迭代終止條件：最優(yōu)解：2.迭代步驟1）任選初始點(diǎn)X(0)，計(jì)算精度ε，令k=0

；2）計(jì)算和；3）收斂判斷，

A.若，則X(k)為近似最優(yōu)點(diǎn)，停止迭代，輸出最優(yōu)解和；

B.若，則轉(zhuǎn)下一步繼續(xù)迭代；4）令5）確定最優(yōu)步長(zhǎng)因子，使6）計(jì)算；7）令k=k+1，轉(zhuǎn)2）。解：（1）

如果轉(zhuǎn)（2），否則轉(zhuǎn)（5）?！纠?】用梯度法求目標(biāo)函數(shù)f(X)=x12+4x22

在初始點(diǎn)X(0)=[22]T，迭代精度=10-2

下的最優(yōu)解。（2）（3），并轉(zhuǎn)（1）。（4）第7次迭代后，成立，停止迭代。（5）取時(shí)，

f(X*)=2.596×10-6≈0梯度法的特點(diǎn)：負(fù)梯度方向只是函數(shù)值在點(diǎn)X(k)的鄰域內(nèi)下降最快的方向，離開(kāi)該鄰域以后函數(shù)值不一定下降最快。因此，采用負(fù)梯度方向，從局部看函數(shù)值下降快，從全局看卻要走很多彎路。因此，梯度法的收斂速度較慢。梯度法的迭代過(guò)程，每相鄰兩步的搜索方向是垂直的，也就是說(shuō)梯度法的迭代路線是呈鋸齒形前進(jìn)的。梯度法迭代過(guò)程中，當(dāng)?shù)c(diǎn)離理論極小點(diǎn)較遠(yuǎn)時(shí)，一次迭代的函數(shù)值下降量大。迭代點(diǎn)離極小點(diǎn)越近，函數(shù)值下降的速度就越慢。因此，梯度法常與其它優(yōu)化方法結(jié)合使用。即第一步采用梯度法，后面采用其它的方法確定搜索方向。梯度法的收斂速度與目標(biāo)函數(shù)的性質(zhì)有關(guān)。如果目標(biāo)函數(shù)的等值線（面）為同心圓（球），則無(wú)論從哪里出發(fā)，只需要一次搜索就能達(dá)到極小點(diǎn)。三、牛頓法1.基本思想在X(k)的鄰域內(nèi)，用二次泰勒多項(xiàng)式近似原目標(biāo)函數(shù)F(X)，以該二次多項(xiàng)式的極小點(diǎn)作為F(X)的下一個(gè)迭代點(diǎn)X(k+1)，并逐漸逼近F(X)的極小點(diǎn)X*。要求：F(X)連續(xù)，且存在一、二階偏導(dǎo)數(shù)。三、牛頓法1.迭代過(guò)程設(shè)目標(biāo)函數(shù)是連續(xù)二階可微的，將函數(shù)在X(k)點(diǎn)按泰勒級(jí)數(shù)展開(kāi)后，取到二次項(xiàng)將上式展開(kāi)，得對(duì)X求導(dǎo)，設(shè)X(K+1)是極小點(diǎn)，并令一階導(dǎo)數(shù)為0，得上式即為基本牛頓法的迭代公式，其中S(k)稱為牛頓方向?！纠?】用牛頓法求目標(biāo)函數(shù)的極小值。初始點(diǎn)解：對(duì)目標(biāo)函數(shù)求偏導(dǎo)數(shù)可得到：牛頓法的特點(diǎn)：對(duì)于二次函數(shù)而言，取到二次項(xiàng)的泰勒展開(kāi)式就是目標(biāo)函數(shù)本身。如果二階導(dǎo)數(shù)矩陣正定，那么按牛頓法求出的X(1)就是目標(biāo)函數(shù)的精確極小點(diǎn)。因此，對(duì)正定二次函數(shù)而言，牛頓法只需一次迭代就可以達(dá)到精確極小點(diǎn)。牛頓法迭代時(shí)步長(zhǎng)總是為1，對(duì)非二次函數(shù)、非正定函數(shù)而言，一次迭代并不能達(dá)到極小點(diǎn)，有時(shí)還可能失效（即總是不能收斂）。坐標(biāo)輪換法將n維問(wèn)題轉(zhuǎn)化為依次沿n個(gè)坐標(biāo)方向輪回進(jìn)行一維搜索。收斂速度較慢，適合n≤10的小型無(wú)約束優(yōu)化問(wèn)題，若目標(biāo)函數(shù)具有“脊線”，算法將出現(xiàn)病態(tài)：沿兩個(gè)坐標(biāo)方向均不能使函數(shù)數(shù)最速下降法(梯度法)搜索方向?yàn)槟繕?biāo)函數(shù)負(fù)梯度方向。計(jì)算效率優(yōu)于坐標(biāo)輪換法。開(kāi)始幾步搜索下降快，但愈接近極值點(diǎn)下降愈慢。對(duì)初始點(diǎn)的選擇要求不高，適合與其它方法結(jié)合使用（開(kāi)始采用最速下降法，接近極值點(diǎn)時(shí)采用其它方法，如牛頓法）。牛頓法（Newton-Raphson法）用泰勒二次多項(xiàng)式近似原目標(biāo)函數(shù)，以該二次多項(xiàng)式的極小點(diǎn)近似目標(biāo)函數(shù)的極小點(diǎn)并逐漸逼近該極小點(diǎn)（搜索方向?yàn)榕ｎD方向，步長(zhǎng)為1）。要求目標(biāo)函數(shù)連續(xù)，存在一、二階偏導(dǎo)數(shù)，且海賽（Hessian）矩陣非奇異。初始點(diǎn)選擇適當(dāng)時(shí)，是收斂最快的算法；對(duì)初始點(diǎn)選擇要求高。計(jì)算量大。3.5約束問(wèn)題的優(yōu)化方法

在實(shí)際工程中優(yōu)化設(shè)計(jì)問(wèn)題，絕大多數(shù)都是約束優(yōu)化問(wèn)題，其數(shù)學(xué)模型為：

根據(jù)處理約束條件的不同方式，求解這類問(wèn)題的方法分為直接法和間接法。直接法：在迭代過(guò)程中逐點(diǎn)考察約束的可行域，并使迭代點(diǎn)始終局限于可行域之內(nèi)的算法稱為直接法。常用的直接法有：隨機(jī)試驗(yàn)、隨機(jī)方向搜索法、復(fù)合形法、可行方向法、約束坐標(biāo)輪換法、網(wǎng)格法等；間接法：把約束條件引入目標(biāo)函數(shù)，使約束優(yōu)化問(wèn)題轉(zhuǎn)化為相對(duì)簡(jiǎn)單的二次規(guī)劃問(wèn)題或線性規(guī)劃問(wèn)題求解的算法稱為間接法，常用的間接法有消元法、拉格朗日乘子法、懲罰函數(shù)法和序列線性規(guī)劃法等。一、約束優(yōu)化問(wèn)題的直接法在可行域內(nèi)按照一定的準(zhǔn)則，直接探索出問(wèn)題的最優(yōu)點(diǎn)，而無(wú)須將約束問(wèn)題轉(zhuǎn)換成無(wú)約束問(wèn)題去求優(yōu)的方法，稱為約束優(yōu)化問(wèn)題的直接法。約束條件常常使得可行域非凸集出現(xiàn)眾多的局部極值點(diǎn)，不同的初始點(diǎn)往往會(huì)導(dǎo)致探索點(diǎn)逼近不同的局部極值點(diǎn)，因此需要多次變更初始點(diǎn)進(jìn)行多路探索。復(fù)合形法基本思想：是在n維設(shè)計(jì)空間可行域內(nèi)，選擇K個(gè)可行點(diǎn)(n+1≤k≤2n)構(gòu)成一個(gè)多面體（復(fù)合形），在復(fù)合多面體內(nèi)的每一個(gè)頂點(diǎn)都代表一個(gè)設(shè)計(jì)方案。對(duì)每一個(gè)頂點(diǎn)的目標(biāo)函數(shù)進(jìn)行比較，最大點(diǎn)為壞點(diǎn)，以其余各點(diǎn)的中心為映射軸心，在壞點(diǎn)和其余各點(diǎn)的中心連線上，尋找一個(gè)既滿足約束條件，又使目標(biāo)函數(shù)值有所改善的壞點(diǎn)映射點(diǎn)，并以映射點(diǎn)替換壞點(diǎn)而構(gòu)成新的復(fù)合形。按照上述步驟重復(fù)多次，不斷以映射點(diǎn)代替壞點(diǎn)，不斷構(gòu)成新的復(fù)合形時(shí)，使復(fù)合形不斷收縮。這時(shí)可輸出復(fù)合形各頂點(diǎn)的函數(shù)值最小的點(diǎn)作為近似最有點(diǎn)。復(fù)合形法g1(X)g2(X)g3(X)g4(X)g5(X)g4(X)壞點(diǎn)好點(diǎn)新點(diǎn)復(fù)合形法的原理示意圖復(fù)合形法迭代算法:1．形成初始復(fù)合形（1）在設(shè)計(jì)變量少，約束函數(shù)簡(jiǎn)單的情況下，由設(shè)計(jì)者決定k個(gè)可行點(diǎn)，構(gòu)成初始復(fù)合形。（2）當(dāng)設(shè)計(jì)變量較多或約束函數(shù)復(fù)雜時(shí)，由設(shè)計(jì)者決定k個(gè)可行點(diǎn)常常很困難。這時(shí)可采用以下方法生成初始復(fù)合形。選定一個(gè)可行點(diǎn)作為初始頂點(diǎn)（控制初始復(fù)合形的位置），其余的k-l個(gè)可行點(diǎn)用隨機(jī)法產(chǎn)生。各頂點(diǎn)按下式計(jì)算——復(fù)合形的第k個(gè)頂點(diǎn)；——設(shè)計(jì)變量的上、下限；——（0，1）區(qū)間內(nèi)的偽隨機(jī)數(shù)。b）用式(2-)計(jì)算得到的k-l個(gè)隨機(jī)點(diǎn)不一定都在可行域內(nèi)，因此要設(shè)法將非可行點(diǎn)移到可行域內(nèi)。

通常采用的方法如下。先求出可行域內(nèi)q個(gè)頂點(diǎn)的中心XC，然后將非可行點(diǎn)向中心點(diǎn)XC移動(dòng)，得新點(diǎn)

一般取。若某一點(diǎn)仍為不可行點(diǎn)，則利用上式，使其繼續(xù)向中心點(diǎn)移動(dòng)。只要中心點(diǎn)為可行點(diǎn)，k-l個(gè)點(diǎn)經(jīng)過(guò)上述的處理后，最終全部成為可行點(diǎn)，并構(gòu)成初始復(fù)合形。2)．復(fù)合形法的搜索方法和計(jì)算步驟（a）計(jì)算各頂點(diǎn)函數(shù)值，F(xiàn)i＝F(Xi)；比較函數(shù)值的大小，確定最好點(diǎn)XL、最差點(diǎn)XH、次差點(diǎn)XG

（b）計(jì)算XH點(diǎn)之外各點(diǎn)的“重心”XC

（3）如果XC在可行域內(nèi)，則沿XHXC方向上作XH點(diǎn)相對(duì)于XC點(diǎn)的反射點(diǎn)XR，XR＝XC＋α(XC－XH)式中α——反射系數(shù)，一般取α＝1.3。判別反射點(diǎn)XR是否為可行點(diǎn)，如在可行域外，則將α減半，重新計(jì)算反射點(diǎn)，直至滿足全部約束。（4）如果中心點(diǎn)XC不在可行域之內(nèi)，可行域則可能為非凸集。為了將XC移至可行域內(nèi)，以XC和XL為界的超正方體，重新利用偽隨機(jī)數(shù)產(chǎn)生k個(gè)新的頂點(diǎn)，構(gòu)成新的復(fù)合形（算法和計(jì)算步驟見(jiàn)形成初始復(fù)合形一節(jié)）。此時(shí)邊界值若xLi＜xCi（i＝1，2，…，n），

則（i＝1，2，…，n）否則相反。重復(fù)（1）、（2），直至XC及XH點(diǎn)相對(duì)于XC點(diǎn)的反射點(diǎn)XR都進(jìn)入可行域。（5）計(jì)算F(XR)，如果F(XR)＜F(XH)，則用XR代替XH構(gòu)成新單純形，轉(zhuǎn)入（1）開(kāi)始下一輪搜索；否則繼續(xù)（6）。（6）如果F(XR)＞F(XH)，則將α減半，重新計(jì)算XR，直至F(XR)＜F(XH)。若F(XR)＜F(XH)且XR為可行點(diǎn)，轉(zhuǎn)（5）；若經(jīng)過(guò)若干次α減半的計(jì)算，使α值小于給定的很小的正數(shù)ζ（ζ＝10-5）時(shí)，仍不能找到使正確的反射點(diǎn)，將最差點(diǎn)XH換為次差點(diǎn)XG并轉(zhuǎn)入（2）。當(dāng)復(fù)合形收縮到很小時(shí)

或各頂點(diǎn)目標(biāo)函數(shù)值滿足

時(shí)，停止迭代，X*＝XL即為最優(yōu)解。復(fù)合形法的程序框圖二、約束優(yōu)化問(wèn)題的間接求解法——懲罰函數(shù)法

懲罰函數(shù)法是求解約束優(yōu)化問(wèn)題的間接法的一種。它是將目標(biāo)函數(shù)和約束條件構(gòu)造成一個(gè)新的目標(biāo)函數(shù)，將約束最優(yōu)化問(wèn)題轉(zhuǎn)化為無(wú)約束最優(yōu)化問(wèn)題，然后利用各種有效的無(wú)約束最優(yōu)化解法求解而得到約束最優(yōu)化的近似解。這是一種使用廣泛的有效的間接解法。把其中不等式和等式約束函數(shù)值經(jīng)加權(quán)處理后，和原目標(biāo)函數(shù)結(jié)合新的目標(biāo)函數(shù):懲罰函數(shù)1.懲罰函數(shù)法的基本思路1.懲罰函數(shù)法的基本思路

將不等式約束、等式約束和待定系數(shù)（加權(quán)因子）經(jīng)加權(quán)轉(zhuǎn)化后，與原目標(biāo)函數(shù)f(X)一起組成一個(gè)新的目標(biāo)函數(shù)（懲罰函數(shù)），然后對(duì)它求最優(yōu)解?！c不等式約束有關(guān)的懲罰項(xiàng)——與等式約束有關(guān)的懲罰項(xiàng)——罰因子

懲罰函數(shù)中的后兩項(xiàng)稱為懲罰項(xiàng)。懲罰項(xiàng)滿足下列要求：當(dāng)滿足約束條件時(shí)，懲罰項(xiàng)的值很小或?yàn)?；當(dāng)不滿足約束條件時(shí)，懲罰項(xiàng)的值很大，即對(duì)不滿足約束條件的點(diǎn)的函數(shù)值進(jìn)行懲罰。

新目標(biāo)函數(shù)中，稱為懲罰因子或加權(quán)因子，它們是一系列的按一定規(guī)則變化的值。當(dāng)按照一定的法則改變的數(shù)值時(shí)，就構(gòu)成了一系列的無(wú)約束優(yōu)化問(wèn)題，求解這些優(yōu)化問(wèn)題可得到一系列的無(wú)約束的迭代點(diǎn)，使其一步步迭代，不斷地逼近原約束優(yōu)化問(wèn)題的最優(yōu)解。

懲罰函數(shù)法又稱序列無(wú)約束極小化方法，常稱SUMT（sequentialunconstrainedminimizationtechnique）。根據(jù)懲罰項(xiàng)的構(gòu)成形式，懲罰函數(shù)法可分為：內(nèi)點(diǎn)懲罰函數(shù)法外點(diǎn)懲罰函數(shù)法混合懲罰函數(shù)法。2.內(nèi)點(diǎn)懲罰函數(shù)法1）特征該法是求解不等式約束最優(yōu)化問(wèn)題的一種有效的方法，但不能處理等式約束，其特點(diǎn)是將新的無(wú)約束目標(biāo)函數(shù)——懲罰函數(shù)定義在可行域內(nèi)。在可行域內(nèi)，序列迭代點(diǎn)逐步逼近約束邊界上的最優(yōu)點(diǎn)。這樣，求解無(wú)約束問(wèn)題時(shí)的搜索點(diǎn)總是保持在可行域內(nèi)部。

內(nèi)點(diǎn)法求解時(shí)，懲罰函數(shù)的形式為懲罰項(xiàng)的特點(diǎn)：當(dāng)?shù)c(diǎn)在可行域內(nèi)且遠(yuǎn)離邊界時(shí)，兩種懲罰項(xiàng)和都是很小的正值，這時(shí)候懲罰作用很??；當(dāng)?shù)c(diǎn)靠近邊界時(shí)，則懲罰項(xiàng)的值急劇增大并趨向無(wú)窮大，于是懲罰函數(shù)值也隨之急劇增大并趨向無(wú)窮大。這樣等于在約束邊界筑起一道“屏障”，使迭代點(diǎn)始終不能超出可行域。懲罰因子的特點(diǎn)：內(nèi)點(diǎn)懲罰函數(shù)法的懲罰因子r(k)是一個(gè)遞減的正數(shù)序列，，c是懲罰因子的縮減系數(shù)，即當(dāng)懲罰因子時(shí)，才能求得在約束邊界上的最優(yōu)解。2）初始懲罰因子r(0)的選擇初始懲罰因子的選擇會(huì)影響到迭代計(jì)算能否正常進(jìn)行以及計(jì)算效率的高低，r(0)的值應(yīng)適當(dāng)。若r(0)太大，則開(kāi)始幾次構(gòu)造的懲罰函數(shù)的無(wú)約束極值點(diǎn)會(huì)離約束邊界很遠(yuǎn)，將增加迭代次數(shù)，使計(jì)算效率降低。若r(0)太小，懲罰函數(shù)中的障礙項(xiàng)的作用就會(huì)很小，使懲罰函數(shù)性態(tài)變壞，甚至難以收斂到原約束目標(biāo)函數(shù)的極值點(diǎn)。

目前，還沒(méi)有一定的有效方法，往往要經(jīng)過(guò)多次試算，才能確定一個(gè)適當(dāng)?shù)膔(0)。多數(shù)情況下，一般取r(0)＝1

～50，然后根據(jù)試算的結(jié)果，加以調(diào)整；或按經(jīng)驗(yàn)公式取值使懲罰項(xiàng)和原目標(biāo)函數(shù)在懲罰函數(shù)中的作用相當(dāng)。3）罰因子縮減系數(shù)C的選擇在構(gòu)造序列懲罰函數(shù)時(shí)，懲罰因子r(k)是一個(gè)逐次遞減到0的數(shù)列，相鄰兩次迭代的懲罰因子關(guān)系式為：其中，c是懲罰因子的縮減系數(shù)，通常取值為0.1~0.7。一般來(lái)說(shuō)，c值的大小對(duì)收斂速度無(wú)明顯影響，在迭代過(guò)程中不起決定性作用。4）收斂條件內(nèi)點(diǎn)法的收斂準(zhǔn)則為：5）內(nèi)點(diǎn)法的迭代步驟：步驟1

選，可行初始點(diǎn)不應(yīng)在邊界上，最好不要靠近任何一個(gè)約束邊界；步驟2

選，令k=0（迭代次數(shù)）；步驟3

構(gòu)造懲罰函數(shù)，選某一適當(dāng)?shù)臒o(wú)約束優(yōu)化方法，求，得到，令；步驟4

判斷迭代點(diǎn)是否收斂，若滿足收斂條件，迭代終止，約束最優(yōu)解為：否則，令，轉(zhuǎn)步驟三。3.外點(diǎn)懲罰函數(shù)法外點(diǎn)懲罰函數(shù)法構(gòu)造懲罰函數(shù)的形式為：對(duì)于約束優(yōu)化問(wèn)題分析：①對(duì)于不等式約束，當(dāng)滿足約束條件時(shí)，懲罰項(xiàng)為0；當(dāng)不滿足約束條件時(shí)，懲罰項(xiàng)大于0，這相當(dāng)于給不滿足約束條件的迭代點(diǎn)在函數(shù)值上給予懲罰，以此來(lái)使迭代點(diǎn)逐步向可行域邊界靠近；②對(duì)于等式約束，也可以得出類似的結(jié)論。外點(diǎn)法既可處理不等式約束，也可處理等式約束。

為了進(jìn)一步理解外點(diǎn)法，我們考慮一種只有不等式約束的情況，此時(shí)，懲罰函數(shù)1）特征

根據(jù)對(duì)懲罰項(xiàng)性質(zhì)的分析，懲罰項(xiàng)可分以下兩種情況：

可以清楚地看出，外點(diǎn)法的懲罰項(xiàng)是定義于可行域之外的。事實(shí)上，外點(diǎn)法的迭代過(guò)程是從可行域外一步步向可行域邊界逼近的。這正是外點(diǎn)法名稱的由來(lái)。2）選擇外點(diǎn)法懲罰因子按下式遞增：式中：C—懲罰因子遞增系數(shù)，通常C=5～10。外點(diǎn)法懲罰因子的合理取值很重要，若太大，懲罰項(xiàng)的作用就會(huì)很大，使懲罰函數(shù)的等值線變形或偏心，求極值將會(huì)很困難；若太小，將增加迭代次數(shù)，計(jì)算效率降低。

多數(shù)情況下，取，C=10時(shí)效果較好。

懲罰項(xiàng)的大小還與懲罰加權(quán)因子r(k)有關(guān)。當(dāng)懲罰因子按一個(gè)遞增的正數(shù)序列變化時(shí)，依次求解所對(duì)應(yīng)的無(wú)約束極小化問(wèn)題，將得到一個(gè)極小點(diǎn)序列隨著r(k)逐步增大，這個(gè)極小點(diǎn)序列將逐步逼近原約束優(yōu)化問(wèn)題的最優(yōu)解。3）迭代步驟步驟1

給定初始點(diǎn)、收斂精度、初始懲罰因子r(0)和懲罰因子遞增系數(shù)，約束容限δ，并置；步驟2

構(gòu)造懲罰函數(shù)步驟3

求解無(wú)約束優(yōu)化問(wèn)題，得,令

步驟4

判斷收斂精度：若滿足條件

則令，結(jié)束計(jì)算；否則，令，轉(zhuǎn)步驟2，繼續(xù)迭代?！纠咳缦聢D所示一對(duì)稱的二桿支架，在支架的頂點(diǎn)有一載荷2P=300000N，支座之間的水平距離為2B=152cm。若已選定壁厚T=0.25cm的鋼管，其彈性模量E=2.16×105MPa，比重β=8.30tm-3，屈服極限σs=703MP，先要設(shè)計(jì)滿足強(qiáng)度與穩(wěn)定性條件下最輕的桁架尺寸。解：1、建立數(shù)學(xué)模型取設(shè)計(jì)變量

其目標(biāo)函數(shù)

約束條件為：1）：鋼管的承壓強(qiáng)度必須滿足，即圓管桿件中的壓應(yīng)力σ應(yīng)≤材料的屈服極限σs，即：2）：鋼管的承壓穩(wěn)定性條件必須滿足，即圓管的壓應(yīng)力σ應(yīng)≤壓桿穩(wěn)定的臨界盈利σk，由材料力學(xué)可知：約束條件為：3）：支架的實(shí)用條件要求必須滿足，即：這是一個(gè)二維約束非線性規(guī)劃問(wèn)題。下圖描繪了設(shè)計(jì)空間中目標(biāo)函數(shù)等值線、約束面和設(shè)計(jì)變量的關(guān)系。2、選用求解方法和結(jié)果分用外點(diǎn)懲罰函數(shù)求解。此問(wèn)題的外點(diǎn)懲罰函數(shù)為：2、選用求解方法和結(jié)果分用外點(diǎn)懲罰函數(shù)求解。此問(wèn)題的外點(diǎn)懲罰函數(shù)為：取初始點(diǎn)：最優(yōu)解點(diǎn)：用外點(diǎn)閥函數(shù)求解二桿支架問(wèn)題：4.混合懲罰函數(shù)法

這種方法是將內(nèi)點(diǎn)法和外點(diǎn)法的懲罰函數(shù)形