數學院碩士研究生

《數值最優化方法》

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

第一章最優化問題數學建模專題

§1引言

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

將達到最優目標的方案稱為最優方案或最優決策，搜尋最優方案的方法稱為最優化方法，關于最優化方法的數學理論稱為最優化理論。最優化問題至少有兩要素：一是可能的方案；二是要追求的目標。后者是前者的函數。如果第一要素與時間無關就稱為靜態最優化問題，否則稱為動態最優化問題。本課程專門講授靜態最優化問題。最優化技術應用范圍十分廣泛，在我們日常生活中，在工農業生產、社會經濟、國防、航空航天工業中處處可見其用途。比如我們自己所接觸過的課題有：結構最優設計、電子器件最優設計、光學儀器最優設計、化工工程最優設計、運輸方案、機器最優配備、油田開發、水庫調度、飼料最優配方、食品結構優化等等。

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

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

最優化在物資運輸、自動控制、機械設計、采礦冶金、經濟管理等科學技術各領域中有廣泛應用。下面舉幾個專業性不很強的實例。

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

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

min即問題追求的目標是圓柱體表面積最小。即則得原問題的數學模型：

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

即

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

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

y關于x

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

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

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

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

0.01640.04630.1250解:根據前面介紹的建模要素得出此問題的數學模型如下:設是生產100磅混合飼料所須的石灰石、谷物、大豆粉的量（磅）。§3.最優化問題的基本概念

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

最優化問題模型統一化：在上述最優化問題的一般式中只是取極小值，如果遇到極大化問題，只須將目標函數反號就可以化為求極小的問題。

例如：函數在有極大值，將它改變符號后，在同一點處有極小值由此可見：有相同最優點。

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

在容許集中找一點，使目標函數在該點取最小值，即滿足：的過程即為最優化的求解過程。

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

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

=4

=9

=1

0ssL在平面上任給一點，就對應有一個目標函數值=這個值就是過點作平面的垂線與S曲面交點的縱坐標。

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

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

DE易見可行域為曲線段ABCD。當動點沿拋物曲線段ABCD由A點出發時，AB段目標函數值下降。過點B后，在BC段目標函數值上升。過C點后，在CD段目標函數值再次下降。D點是使目標函數值最小的可行點，其坐標可通過解方程組：得出=，=4

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

（1）不同值的等值面之間不相交，因為目標函數是單值函數。

（2）除了極值點所在的等值面外，不會在區域內部中斷，因為目標函數是連續的

（3）等值面稠的地方，目標函數值變化得較快，而稀疏的地方變化得比較慢。

（4）一般地，在極值點附近，等值面（線）近似地呈現為同心橢球面族（橢圓族）。5二次函數

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

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

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

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

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

A的所有主子式＞0

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

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

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

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

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

f:表示f是定義在中區域D上的n元實值函數。定義1：設f:,D,若l

，使P有：

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

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

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

=⑹

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

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

e為P方向上的單位向量。證明：利用方向導數定義并將中的P換成te有：

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

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

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

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

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

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

②

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

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

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

因為向量的極限是通過它所有分量的極限來定義的。則上式等價于：

從而由上面（8）可得：

其中：

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

這就是多元函數f（X）關于X的二階導數，稱為

f（X）的Hessian矩陣。

多元函數的一階導數即梯度。二階導數即Hesse陣。這兩個概念在最優化中是最常用的。在高等數學中我們已經證明過當f（X）的所有二階偏導數連續時，有j=1，2……n因此在這種情況下，Hesse矩陣是對稱的。例：求目標函數f（X）=的梯度和Hesse矩陣。解：因為故Hesse陣為：

又因為：

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

再對t求一次導數有：§7多元函數的Taylor

展開公式

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

其中而0＜θ＜1

證明：設于是

按一元函數Taylor展開定理把在t=0點展開。有：其中0＜θ＜1

而由前節（4）當時從而定理中Taylor公式可以寫成（*）式。

這是因為的每一個分量都是連續函數。則Taylor展開式還可寫成如下形式：

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

f例如：圖中一元函數f定義在區間[ab]上為嚴格局部極小點，

為非嚴格局部極小點。0Xa為全局嚴格極小點。ab

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

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

定理1：設具有連續的一階偏導數，若是f的局部極小點，且為D的內點，則證明：設e為任意單位向量。因為是f（Z）的局部極小點。由定義知：當|t|〈δ即時，

局部極小點是指在的某個鄰域內，f在處取極小值。全局極小點是指在整個定義域D中，f在處取極小值。全局極小點可能在某個局部極小點達到，也可能在邊界達到。我們希望知道的當然是全局極小點，而到目前為止的一些最優化算法卻基本上是求局部極小值點的。因此一般要先求出所有局部極小值點，再從中找出全局極小點。總有：令（一元輔助函數）則上式即為：而是D的內點。從而與之對應的t=0是的局部極小點。

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

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

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

定理2

設具有連續的二階偏導數，是D的內點，若且

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

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

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

因為極小值點。又是高階無窮小量。省略。則有：

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

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

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

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

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

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

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

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

一個自然的想法就是當小于預先給定的誤差時，即為所求的近似解。但未知，因而無法計算。然而很小時，自然也很小，于是想到用①作為算法的一個終止準則。其中是預先給定的一個判別算法終止的界限，稱為終止限。但僅用此作為終止準則是不可靠的。因為很小并不能保證很小。如圖（a）所示的一條一元目標函數曲線。

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