第一章 數(shù)值最優(yōu)化方法 建模與數(shù)學(xué)預(yù)備知識

數(shù)學(xué)院碩士研究生

《數(shù)值最優(yōu)化方法》

張鴻雁計劃學(xué)時數(shù)：48學(xué)時主要參考書目：最優(yōu)化理論與方法，袁亞湘，孫文俞，科學(xué)出版社，1999.05[1]最優(yōu)化方法，解可新等，天津大學(xué)出版社，1997。[2]最優(yōu)化原理與方法（修訂版），薛嘉慶，冶金工業(yè)出版社，2003.6。[3]最優(yōu)化方法，何堅勇，清華大學(xué)出版社，2007.1。[4]最優(yōu)化方法，孫文瑜，徐成賢，朱德通，高等教育出版社，2005.3。[5]非線性規(guī)劃，胡毓達(dá)，高等教育出版社，1990。[6]微粒群優(yōu)化與調(diào)度算法，王凌，劉波，清華大學(xué)出版社，2008.5。[7]蟻群優(yōu)化算法，馬良等，科學(xué)出版社，2008.2。數(shù)值最優(yōu)化方法

第一章最優(yōu)化問題數(shù)學(xué)建模專題

§1引言

最優(yōu)化技術(shù)是一門較新的學(xué)科分支。它是在本世紀(jì)五十年代初在電子計算機(jī)廣泛應(yīng)用的推動下才得到迅速發(fā)展，并成為一門直到目前仍然十分活躍的新興學(xué)科。最優(yōu)化所研究的問題是在眾多的可行方案中怎樣選擇最合理的一種以達(dá)到最優(yōu)目標(biāo)。

將達(dá)到最優(yōu)目標(biāo)的方案稱為最優(yōu)方案或最優(yōu)決策，搜尋最優(yōu)方案的方法稱為最優(yōu)化方法，關(guān)于最優(yōu)化方法的數(shù)學(xué)理論稱為最優(yōu)化理論。最優(yōu)化問題至少有兩要素：一是可能的方案；二是要追求的目標(biāo)。后者是前者的函數(shù)。如果第一要素與時間無關(guān)就稱為靜態(tài)最優(yōu)化問題，否則稱為動態(tài)最優(yōu)化問題。本課程專門講授靜態(tài)最優(yōu)化問題。最優(yōu)化技術(shù)應(yīng)用范圍十分廣泛，在我們?nèi)粘Ｉ钪校诠まr(nóng)業(yè)生產(chǎn)、社會經(jīng)濟(jì)、國防、航空航天工業(yè)中處處可見其用途。比如我們自己所接觸過的課題有：結(jié)構(gòu)最優(yōu)設(shè)計、電子器件最優(yōu)設(shè)計、光學(xué)儀器最優(yōu)設(shè)計、化工工程最優(yōu)設(shè)計、運(yùn)輸方案、機(jī)器最優(yōu)配備、油田開發(fā)、水庫調(diào)度、飼料最優(yōu)配方、食品結(jié)構(gòu)優(yōu)化等等。

最優(yōu)化技術(shù)工作被分成兩個方面，一是由實(shí)際生產(chǎn)或科技問題形成最優(yōu)化的數(shù)學(xué)模型，二是對所形成的數(shù)學(xué)問題進(jìn)行數(shù)學(xué)加工和求解。對于第二方面的工作，目前已有一些較系統(tǒng)成熟的資料，但對于第一方面工作即如何由實(shí)際問題抽象出數(shù)學(xué)模型，目前很少有系統(tǒng)的資料，而這一工作在應(yīng)用最優(yōu)化技術(shù)解決實(shí)際問題時是十分關(guān)鍵的基礎(chǔ)，沒有這一工作，最優(yōu)化技術(shù)將成為無水之源，難以健康發(fā)展。因此，我們在學(xué)習(xí)本課程時要盡可能了解如何由實(shí)際問題形成最優(yōu)化的數(shù)學(xué)模型。為了便于大家今后在處理實(shí)際問題時建立最優(yōu)化數(shù)學(xué)模型，下面我們先把有關(guān)數(shù)學(xué)模型的一些事項(xiàng)作一些說明。

所謂數(shù)學(xué)模型就是對現(xiàn)實(shí)事物或問題的數(shù)學(xué)抽象或描述。建立數(shù)學(xué)模型時要盡可能簡單，而且要能完整地描述所研究的系統(tǒng)，但要注意到過于簡單的數(shù)學(xué)模型所得到的結(jié)果可能不符合實(shí)際情況，而過于詳細(xì)復(fù)雜的模型又給分析計算帶來困難。因此，具體建立怎樣的數(shù)學(xué)模型需要豐富的經(jīng)驗(yàn)和熟練的技巧。即使在建立了問題的數(shù)學(xué)模型之后，通常也必須對模型進(jìn)行必要的數(shù)學(xué)簡化以便于分析、計算。一般的模型簡化工作包括以下幾類：（1）將離散變量轉(zhuǎn)化為連續(xù)變量。（2）將非線性函數(shù)線性化。（3）刪除一些非主要約束條件。建立最優(yōu)化問題數(shù)學(xué)模型的三要素：（1）決策變量和參數(shù)。決策變量是由數(shù)學(xué)模型的解確定的未知數(shù)。參數(shù)表示系統(tǒng)的控制變量，有確定性的也有隨機(jī)性的。（2）約束或限制條件。由于現(xiàn)實(shí)系統(tǒng)的客觀物質(zhì)條件限制，模型必須包括把決策變量限制在它們可行值之內(nèi)的約束條件，而這通常是用約束的數(shù)學(xué)函數(shù)形式來表示的。（3）目標(biāo)函數(shù)。這是作為系統(tǒng)決策變量的一個數(shù)學(xué)函數(shù)來衡量系統(tǒng)的效率，即系統(tǒng)追求的目標(biāo)?！?最優(yōu)化問題數(shù)學(xué)建模

最優(yōu)化在物資運(yùn)輸、自動控制、機(jī)械設(shè)計、采礦冶金、經(jīng)濟(jì)管理等科學(xué)技術(shù)各領(lǐng)域中有廣泛應(yīng)用。下面舉幾個專業(yè)性不很強(qiáng)的實(shí)例。

例1.把半徑為1的實(shí)心金屬球熔化后，鑄成一個實(shí)心圓柱體，問圓柱體取什么尺寸才能使它的表面積最小？

解：決定圓柱體表面積大小有兩個決策變量：圓柱體底面半徑r、高h(yuǎn)。問題的約束條件是所鑄圓柱體重量與球重相等。即

min即問題追求的目標(biāo)是圓柱體表面積最小。即則得原問題的數(shù)學(xué)模型：

利用在微積分學(xué)中所學(xué)的Lagrange乘子法可求解本問題分別對r、h、λ求偏導(dǎo)數(shù)，并令其等于零，有:

即

此時圓柱體的表面積為例2.多參數(shù)曲線擬合問題已知兩個物理量x和y之間的依賴關(guān)系為:

其中和待定參數(shù),為確定這些參數(shù),對x、y測解:很顯然對參數(shù)和任意給定的一組數(shù)值,就由上式確定了

y關(guān)于x

的一個函數(shù)關(guān)系式,在幾何上它對應(yīng)一條曲線,這條曲線不一定通過那m個測量點(diǎn),而要產(chǎn)生“偏差”.將測量點(diǎn)沿垂線方向到曲線的距離的平方和作為這種“偏差”的度量.即得m個實(shí)驗(yàn)點(diǎn):試將確定參數(shù)的問題表示成最優(yōu)化問題.

顯然偏差S越小,曲線就擬合得越好,說明參數(shù)值就選擇得越好，從而我們的問題就轉(zhuǎn)化為5維無約束最優(yōu)化問題。即：例3：兩桿桁架的最優(yōu)設(shè)計問題。由兩根空心圓桿組成的對稱兩桿桁架，其頂點(diǎn)承受負(fù)載為2p，兩支座之間的水平距離為2L，圓桿的壁厚為B，桿的比重為ρ，彈性橫量為E，屈服強(qiáng)度為δ。求在桁架不被破壞的情況下使桁架重量最輕的桁架高度h及圓桿平均直徑d。桁桿示意圖

受力分析圖圓桿截面圖由此得穩(wěn)定約束：解：桁桿的截面積為：桁桿的總重量為：負(fù)載2p在每個桿上的分力為：于是桿截面的應(yīng)力為：此應(yīng)力要求小于材料的屈服極限，即圓桿中應(yīng)力小于等于壓桿穩(wěn)定的臨界應(yīng)力。由材料力學(xué)知：壓桿穩(wěn)定的臨界應(yīng)力為

例4.（混合飼料配合）以最低成本確定滿足動物所需營養(yǎng)的最優(yōu)混合飼料。下面舉一個簡化了的例子予以說明。設(shè)每天需要混合飼料的批量為100磅，這份飼料必須含：至少0.8%而不超過1.2%的鈣;至少22%的蛋白質(zhì);至多5%的粗纖維。假定主要配料包括石灰石、谷物、大豆粉。這些配料的主要營養(yǎng)成分為：另外還要考慮到設(shè)計變量d和h有界。從而得到兩桿桁架最優(yōu)設(shè)計問題的數(shù)學(xué)模型：配料每磅配料中的營養(yǎng)含量鈣蛋白質(zhì)纖維每磅成本（元）石灰石谷物大豆粉0.3800.000.000.0010.090.020.0020.500.08

0.01640.04630.1250解:根據(jù)前面介紹的建模要素得出此問題的數(shù)學(xué)模型如下:設(shè)是生產(chǎn)100磅混合飼料所須的石灰石、谷物、大豆粉的量（磅）?！?.最優(yōu)化問題的基本概念

其中是向量變量實(shí)值函數(shù)則有m個式約束的最優(yōu)化問題為：n維歐氏空間向量向量變量實(shí)值函數(shù)：無約束最優(yōu)問題：向量變量向量值函數(shù)：其中均為向量Z的實(shí)值連續(xù)函數(shù)，有二階連續(xù)偏導(dǎo)數(shù)，采用向量表示法即為：其中這就是最優(yōu)化問題的一般形式，又稱非線性規(guī)劃。注意集約束通常可用不等式約束表示出來，有時在本課程我們討論的是如下形式的靜態(tài)最優(yōu)化問題：

最優(yōu)化問題模型統(tǒng)一化：在上述最優(yōu)化問題的一般式中只是取極小值，如果遇到極大化問題，只須將目標(biāo)函數(shù)反號就可以化為求極小的問題。

例如：函數(shù)在有極大值，將它改變符號后，在同一點(diǎn)處有極小值由此可見：有相同最優(yōu)點(diǎn)。

因此后面專門研究最小化問題。因此，一般不考慮集約束。稱滿足所有約束條件的向量Z為容許解或可行解，容許點(diǎn)的集合稱為容許集或可行集。

在容許集中找一點(diǎn)，使目標(biāo)函數(shù)在該點(diǎn)取最小值，即滿足：的過程即為最優(yōu)化的求解過程。

稱為問題的最優(yōu)點(diǎn)，稱為最優(yōu)值，稱為最優(yōu)解。如果約束條件中有“小于等于“的，即則轉(zhuǎn)化為，另外，等式約束可以由下面兩個不等式來代替：因而最優(yōu)化問題的一般形式又可寫成：對于最優(yōu)化問題一般可作如下分類：其中求解一維無約束問題的方法稱為一維搜索或直線搜索，這在最優(yōu)化方法中起十分重要的作用。§4.二維問題的圖解法這是定義在平面上的無約束極小化問題，其目標(biāo)函數(shù)在三維空間中代表一個曲面。

二維最優(yōu)化問題具有鮮明的幾何解釋，并且可以象征性地把這種解釋推廣到n維空間中去。因此我們簡要介紹一下圖解法，這對于以后理解和掌握最優(yōu)化的理論和方法是很有益處的。例1.求解

=4

=9

=1

0ssL在平面上任給一點(diǎn)，就對應(yīng)有一個目標(biāo)函數(shù)值=這個值就是過點(diǎn)作平面的垂線與S曲面交點(diǎn)的縱坐標(biāo)。

反之，任給一個值,使目標(biāo)函數(shù)取值為的點(diǎn)Z個數(shù)就不相同了。可能沒有，可能只有一個，可能有多個。這一事實(shí)的幾何意義是：過f軸上坐標(biāo)為的點(diǎn)作坐標(biāo)平面的平行平面L，可能與曲面S無交點(diǎn)（〈0時），可能與S有一個交點(diǎn)（=0時），可能與S交成一條曲線（〉0）。

我們感興趣的是至少有一個交點(diǎn)（≥0）的情形。此時用平面L截曲面S得到一個圓，將它投影到平面上，仍為同樣大小的圓。在這個圓上每一點(diǎn)的目標(biāo)函數(shù)值均為,若一條曲線上任何一點(diǎn)的目標(biāo)函數(shù)值等于同一常數(shù)，則稱此曲線為目標(biāo)函數(shù)的等值線。易見，變動f的值，得到不同等值線，這是一組同心圓，對應(yīng)f=0的等值線縮為一點(diǎn)G，對應(yīng)f<0的等值線為空集。易見，隨著f值變小，等值線圓半徑變小，最后縮為一點(diǎn)，即為問題的最小值點(diǎn)G，=解：先畫出目標(biāo)函數(shù)等值線，再畫出約束曲線，本處約束曲線是一條直線，這條直線就是容許集。而最優(yōu)點(diǎn)就是容許集上使等值線具有最小值的點(diǎn)。由圖易見約束直線與等值線的切點(diǎn)是最優(yōu)點(diǎn)，利用解析幾何的方法得該切點(diǎn)為=，對應(yīng)的最優(yōu)值為=2(圖一）。例2用圖解法求解=2=10例3：用圖解法求解解：①先畫出等式約束曲線的圖形。這是一條拋物線，如圖②再畫出不等式約束區(qū)域，如圖（怎樣選定哪側(cè)區(qū)域）③最后畫出目標(biāo)函數(shù)等值線，特別注意可行集邊界點(diǎn)，以及等值線與可行集的切點(diǎn)。==●

DE易見可行域?yàn)榍€段ABCD。當(dāng)動點(diǎn)沿拋物曲線段ABCD由A點(diǎn)出發(fā)時，AB段目標(biāo)函數(shù)值下降。過點(diǎn)B后，在BC段目標(biāo)函數(shù)值上升。過C點(diǎn)后，在CD段目標(biāo)函數(shù)值再次下降。D點(diǎn)是使目標(biāo)函數(shù)值最小的可行點(diǎn)，其坐標(biāo)可通過解方程組：得出=，=4

由以上三個例子可見，對二維最優(yōu)化問題。我們總可以用圖解法求解，而對三維或高維問題，已不便在平面上作圖，此法失效。在三維和三維以上的空間中，使目標(biāo)函數(shù)取同一常數(shù)值的是{Z|f(Z)=r,r是常數(shù)}稱為目標(biāo)函數(shù)的等值面。等值面具有以下性質(zhì)：

（1）不同值的等值面之間不相交，因?yàn)槟繕?biāo)函數(shù)是單值函數(shù)。

（2）除了極值點(diǎn)所在的等值面外，不會在區(qū)域內(nèi)部中斷，因?yàn)槟繕?biāo)函數(shù)是連續(xù)的

（3）等值面稠的地方，目標(biāo)函數(shù)值變化得較快，而稀疏的地方變化得比較慢。

（4）一般地，在極值點(diǎn)附近，等值面（線）近似地呈現(xiàn)為同心橢球面族（橢圓族）。5二次函數(shù)

二次函數(shù)的一般形式為其中均為常數(shù)?；騠(z)=az+c，外，最簡單最重要的一類就是二次函數(shù)。在n元函數(shù)中，除了線性函數(shù)：

定義：設(shè)Q為n×n對稱矩陣若，Z≠0，均有＞0，則稱矩陣Q是正定的。若，均有≥0，則稱矩陣Q是半正定的。若，且Z≠0，均有＜0，則稱Q是負(fù)定的。

在代數(shù)學(xué)中將特殊的二次函數(shù)稱為二次型。對于二次函數(shù)，我們更關(guān)心的是Q為正定矩陣的情形。其向量矩陣表示形式是：其中Q=為對稱矩陣，b=

若，均有≤0，則稱Q是半負(fù)定的。判定一個對稱矩陣Q是不是正定的，可以用Sylvester定理來判定。Sylvester定理：一個n×n對稱矩陣Q是正定矩陣的充要條件是矩陣Q的各階主子式都是正的。例：判定矩陣Q=是否正定

解：對稱矩陣Q的三個主子式依次為：A是正定矩陣非奇異矩陣A=A的所有特征根大于零有高矩陣G，使A=（矩陣秩等于矩陣列：高矩陣）

A的所有主子式＞0

=6＞0，=3＞0，=10＞0因此知矩陣Q是正定的。定理：若二次函數(shù)中Q正定，則它的等值面是同心橢球面族，且中心為=

證明：作變換Z=Y，代入二次函數(shù)式中：

根據(jù)解析幾何知識，Q為正定矩陣的二次型的等值面是以坐標(biāo)原點(diǎn)=0為中心的同心橢球面族。由于上式中的

另外，這族橢球面的中心=恰是二次目標(biāo)函數(shù)的唯一極小點(diǎn)。前面已說過，一般目標(biāo)函數(shù)的等值面在極小點(diǎn)附近近似地呈現(xiàn)為橢球面族。由此可見對于二次目標(biāo)函數(shù)有效的求極小點(diǎn)的算法，當(dāng)用于一般目標(biāo)函數(shù)時，至少在極小點(diǎn)附近同樣有效。因此在最優(yōu)化理論中判定一個算法好壞的標(biāo)準(zhǔn)之一，是把該算法用于Q為正定的二次目標(biāo)函數(shù)，如能迅速找到極小點(diǎn)，就是好算法；否則就不是太好的算法。是常數(shù)，所以的等值面也是以=0為中心的同心橢球面族，回到原坐標(biāo)系中去，原二次函數(shù)就是以=為中心的同心橢球面族。

特別地若算法對于Q為正定的二次目標(biāo)函數(shù)能在有限步內(nèi)找出極小點(diǎn)來，就稱此算法為二次收斂算法，或具有二次收斂性。例：把二次函數(shù)化為矩陣向量形式并檢驗(yàn)Q是否正定，如正定，試用公式=求這個函數(shù)的極小點(diǎn)。與題中函數(shù)比較各項(xiàng)系數(shù)為：Q=b=極小點(diǎn)是==解：展開==由前例知Q正定

f:表示f是定義在中區(qū)域D上的n元實(shí)值函數(shù)。定義1：設(shè)f:,D,若l

，使P有：

=0⑴則稱f(Z)在處可微。

若令=則f在處可微時，有=0，即是無窮小量。從而⑵§6梯度與Hesse矩陣一、多元函數(shù)的可微性和梯度以后我們研究的最優(yōu)化問題涉及的均是多元函數(shù)，并要求它們的可微性，下面先給出定義。其中表示的高階無窮小，與一元函數(shù)可微性定義類似（即）定理：若f(Z)在處可微，則f(Z)在該點(diǎn)處關(guān)于各變量的一階偏導(dǎo)數(shù)存在，且⑶證明：令，依次取P=,為任意無窮小變量，是第i個坐標(biāo)軸上的單位向量，即由f在處可微，則⑵對P=成立，即兩邊除以并取的極限有：定義2

以f(Z)的n個偏導(dǎo)數(shù)為分量的向量稱為f(Z)在Z處的梯度。記為=⑷梯度也可稱為函數(shù)f(Z)關(guān)于向量Z的一階導(dǎo)數(shù)。若f在處可微,將⑶代入⑵得⑸這與一元函數(shù)展開到兩項(xiàng)的Taylor公式是相對應(yīng)的。二、梯度的性質(zhì)設(shè)f(Z)在定義域內(nèi)有連續(xù)偏導(dǎo)數(shù)，即有連續(xù)梯度，則梯度有以下兩個重要性質(zhì)：性質(zhì)一函數(shù)在某點(diǎn)的梯度不為零，則必與過該點(diǎn)的等值面垂直性質(zhì)二梯度方向是函數(shù)具有最大變化率的方向。性質(zhì)一的證明：過點(diǎn)的等值面方程為：=或=，

=⑹

設(shè)是過點(diǎn)同時又完全在等值面⑹上的任一條光滑曲線L的方程，θ為參數(shù)。點(diǎn)對應(yīng)的參數(shù)是把此曲線方程代入⑹兩邊同時在處關(guān)于θ求導(dǎo)數(shù)，根據(jù)復(fù)合函數(shù)微分法有：⑺向量恰為曲線L在處的切向量，由⑷、⑺有：,即函數(shù)f(Z)在處的梯度與過該點(diǎn)在等值面上的任一條曲線L在此點(diǎn)的切線垂直。從而與過該點(diǎn)的切平面垂直，從而性質(zhì)一成立。=為說明第二條性質(zhì)，先引進(jìn)下面方向?qū)?shù)定義：定義設(shè)在點(diǎn)Z處可微，P為固定向量，e為向量P方向的單位向量，則稱極限：為函數(shù)f(Z)在點(diǎn)處沿方向P的方向?qū)?shù)，其中為其記號，由定義及極限性質(zhì)可知：若＜0，則f(Z)從出發(fā)在附近沿P方向是下降的(∵＜0，則t＞0充分小時＜0即＜，)

若＞0，則f(Z)從出發(fā)在附近沿方向P是上升的。定理：若在點(diǎn)處可微，則，其中

e為P方向上的單位向量。證明：利用方向?qū)?shù)定義并將中的P換成te有：

==※推論：若＜0，則P是函數(shù)f(Z)在處的下降方向。若＞0，則P是函數(shù)f(Z)在處的上升方向。（∵P=te，t＞0，則＜0，有＜0，由前面證明即知P為下降方向。）（同樣可證明后者）

以上我們看到方向?qū)?shù)正負(fù)決定了函數(shù)升降，而升降速度的快慢由方向?qū)?shù)絕對值大小來決定，絕對值越大升降速度越大。因此又將方向?qū)?shù)稱為f(Z)在處沿方向P的變化率。由于

（β為方向P與的夾角）為使取最小值，β應(yīng)取，即P=-，可見負(fù)梯度方向即為函數(shù)的最速下降方向；同樣梯度方向即為函數(shù)的最速上升方向。這樣我們就說明了性質(zhì)二。上升方向變化率為0方向下降方向-我們有結(jié)論：

函數(shù)在與其梯度正交的方向上變化率為0

函數(shù)在與其梯度成銳角的方向上是上升的函數(shù)在與其梯度成鈍角的方向上是下降的解：由于則函數(shù)在處的最速下降方向是這個方向上的單位向量是：例1

試求目標(biāo)函數(shù)在點(diǎn)處的最速下降方向，并求沿這個方向移動一個單位長度后新點(diǎn)的目標(biāo)函數(shù)值。幾個常用的梯度公式：新點(diǎn)是故②故①

②

解：①例2：求下列函數(shù)的梯度：三、Hesse矩陣：

下面我們來考察多元函數(shù)關(guān)于X的二階導(dǎo)數(shù)。首先定義向量變量值函數(shù)的導(dǎo)數(shù)：定義：設(shè)如果g（x）的所有分量在點(diǎn)均可微，則向量值函數(shù)g（x）在處稱為可微。根據(jù)前面多元函數(shù)定義，若g（x）在點(diǎn)X0

處可微，則對任意n維向量P均有：

因?yàn)橄蛄康臉O限是通過它所有分量的極限來定義的。則上式等價于：

從而由上面（8）可得：

其中：

稱之為向量值函數(shù)g（x）在處的導(dǎo)數(shù)，也稱向量值函數(shù)g（x）在點(diǎn)處的Jacobi矩陣。設(shè)m=n。且其中為n元函數(shù)，有二階連續(xù)偏導(dǎo)數(shù)。

這就是多元函數(shù)f（X）關(guān)于X的二階導(dǎo)數(shù)，稱為

f（X）的Hessian矩陣。

多元函數(shù)的一階導(dǎo)數(shù)即梯度。二階導(dǎo)數(shù)即Hesse陣。這兩個概念在最優(yōu)化中是最常用的。在高等數(shù)學(xué)中我們已經(jīng)證明過當(dāng)f（X）的所有二階偏導(dǎo)數(shù)連續(xù)時，有j=1，2……n因此在這種情況下，Hesse矩陣是對稱的。例：求目標(biāo)函數(shù)f（X）=的梯度和Hesse矩陣。解：因?yàn)楣蔋esse陣為：

又因?yàn)椋?/p>

則下面幾個Hesse矩陣公式是今后常用到的：（1）則（2）則（單位陣）（3）Q對稱。則（4）若其中f：則：證明（4）：對t求導(dǎo)，根據(jù)多元函數(shù)復(fù)合函數(shù)求導(dǎo)公式即得第一式。

再對t求一次導(dǎo)數(shù)有：§7多元函數(shù)的Taylor

展開公式

多元函數(shù)Taylor展開式在最優(yōu)化理論中十分重要。許多方法及其收斂性的證明都是從它出發(fā)的。下面就給出多元函數(shù)Taylor展開式及其證明：定理：設(shè)f：具有二階連續(xù)偏導(dǎo)數(shù)。則：

其中而0＜θ＜1

證明：設(shè)于是

按一元函數(shù)Taylor展開定理把在t=0點(diǎn)展開。有：其中0＜θ＜1

而由前節(jié)（4）當(dāng)時從而定理中Taylor公式可以寫成（*）式。

這是因?yàn)榈拿恳粋€分量都是連續(xù)函數(shù)。則Taylor展開式還可寫成如下形式：

代入上式并令t=1有：§8極小點(diǎn)及其判定條件一極小點(diǎn)概念：

f例如：圖中一元函數(shù)f定義在區(qū)間[ab]上為嚴(yán)格局部極小點(diǎn)，

為非嚴(yán)格局部極小點(diǎn)。0Xa為全局嚴(yán)格極小點(diǎn)。ab

定義1滿足不等式的點(diǎn)X的集合稱為的鄰域。記為：定義2：設(shè)若使（1）均有：則稱為f的非嚴(yán)格局部極小點(diǎn)。（2）。且有則稱為f的嚴(yán)格局部極小點(diǎn)。定義3：設(shè)若使（1）均有則稱為f在D上的非嚴(yán)格全局極小點(diǎn)。（2）有則稱為

f在D上的嚴(yán)格全局極小點(diǎn)。二、局部極小點(diǎn)的判定條件：為了求出函數(shù)的局部極小值點(diǎn)，我們首先希望知道函數(shù)f在局部極小點(diǎn)處滿足什么條件？以及滿足什么條件的點(diǎn)是局部極小點(diǎn)。

定理1：設(shè)具有連續(xù)的一階偏導(dǎo)數(shù)，若是f的局部極小點(diǎn)，且為D的內(nèi)點(diǎn)，則證明：設(shè)e為任意單位向量。因?yàn)槭莊（Z）的局部極小點(diǎn)。由定義知：當(dāng)|t|〈δ即時，

局部極小點(diǎn)是指在的某個鄰域內(nèi)，f在處取極小值。全局極小點(diǎn)是指在整個定義域D中，f在處取極小值。全局極小點(diǎn)可能在某個局部極小點(diǎn)達(dá)到，也可能在邊界達(dá)到。我們希望知道的當(dāng)然是全局極小點(diǎn)，而到目前為止的一些最優(yōu)化算法卻基本上是求局部極小值點(diǎn)的。因此一般要先求出所有局部極小值點(diǎn)，再從中找出全局極小點(diǎn)?？傆校毫睿ㄒ辉o助函數(shù)）則上式即為：而是D的內(nèi)點(diǎn)。從而與之對應(yīng)的t=0是的局部極小點(diǎn)。

注意：定理中條件僅為必要的，而不是充分的。（否則取則

矛盾。由單位向量任意性，即知則根據(jù)一元函數(shù)極小點(diǎn)必要性條件知：而由前述性質(zhì)知：證明：因正定，則使對均有：

將f在處按Taylor公式展開。注意有：f

定理2

設(shè)具有連續(xù)的二階偏導(dǎo)數(shù)，是D的內(nèi)點(diǎn)，若且

正定，則是f（X）的嚴(yán)格局部極小點(diǎn)。例：在處梯度為但只是雙曲拋物面的鞍點(diǎn)，而不是極小點(diǎn)。定義：設(shè)是D的內(nèi)點(diǎn)，若則稱為f的駐點(diǎn)。

當(dāng)X充分接近時，上式左端的符號取決于右端的一項(xiàng)（為正）。故（X充分接近時）。但我們實(shí)際中解最優(yōu)化問題時，一般難以求得目標(biāo)函數(shù)的Hesse矩陣。更難以判別其正定性了。因此定理又只具有理論上的意義。推論：①對于具有對稱正定矩陣的二次函數(shù)：

是它的唯一極小點(diǎn)。證明：求此二次函數(shù)的駐點(diǎn)：由知有唯一駐點(diǎn)而這點(diǎn)處的Hesse陣正定。故由定理又知：是其唯一極小點(diǎn)。②若多元函數(shù)在其極小點(diǎn)處的Hesse陣正定，則它在這個極小點(diǎn)附近的等值面近似地呈現(xiàn)為同心橢球面族。證明：設(shè)是多元函數(shù)f的極小點(diǎn)。并設(shè)f（X）=r是充分靠近極小點(diǎn)的一個等值面，即充分小。將f（X）在點(diǎn)展開為Taylor公式。

因?yàn)闃O小值點(diǎn)。又是高階無窮小量。省略。則有：

這是等值面f=（X）的一個近似曲面。由于假設(shè)正定，則

是以為中心的橢球面方程。

我們知道求解最優(yōu)化問題可以通過求出其全部駐點(diǎn)，即求解非線性方程組：達(dá)到。但求解此非線性方程組的難度并不比原最優(yōu)化問題求解難度小。因此一般不采用此法，而利用對原問題的直接迭代法。§9下降迭代算法及

其收斂性一、下降迭代算法：設(shè)是f的一個局部極小點(diǎn)。一般的尋找最優(yōu)點(diǎn)的方法是先找到極小點(diǎn)的一個初始估計點(diǎn)然后按一定規(guī)則即算法產(chǎn)生一個序列，如果：稱算法產(chǎn)生的序列收斂于。

最常見的最優(yōu)化算發(fā)是下降算法。即給定初始點(diǎn)之后，如果每迭代一步均使目標(biāo)函數(shù)有所下降，即在一般算法中，若已迭代到點(diǎn)那么下一次迭代有下面兩種情形之一發(fā)生：從出發(fā)沿任何方向移動，目標(biāo)函數(shù)不再下降。根據(jù)定義知，此點(diǎn)即為局部極小點(diǎn)。迭代終止。

如果算法在某步迭代時找到了極小點(diǎn)則稱算法是有限步終止的。這種情形極少見。

從出發(fā)至少有一個方向使目標(biāo)函數(shù)有所下降。這時從中選定一個下降方向再沿這個方向迭代一步。即在直線上適當(dāng)找一個新點(diǎn)使。此時我們說完成了一次迭代,其中稱為步長因子。

一個算法是有效的，如果它所產(chǎn)生的序列收斂于極小點(diǎn)。

一個自然的想法就是當(dāng)小于預(yù)先給定的誤差時，即為所求的近似解。但未知，因而無法計算。然而很小時，自然也很小，于是想到用①作為算法的一個終止準(zhǔn)則。其中是預(yù)先給定的一個判別算法終止的界限，稱為終止限。但僅用此作為終止準(zhǔn)則是不可靠的。因?yàn)楹苄〔⒉荒鼙ＷC很小。如圖（a）所示的一條一元目標(biāo)函數(shù)曲線。

在利用計算機(jī)求解時，總只能進(jìn)行有限次迭代，一般難求解精確的