非線性優化與動態規劃第一部分緒論最優化方法的定義、研究對象及研究方法2.最優化問題的基本概念3.梯度與Hesse矩陣4.凸函數與凸規劃非線性優化與動態規劃第一部分緒論內容簡介：最優化方法

近幾十年形成的.它主要運用數學方法研究各種系統的優化途徑及方案，為決策者提供科學決策的依據。最優化方法的主要研究對象是各種有組織系統的管理問題及其生產經營活動。最優化方法的目的在于針對所研究的系統，求得一個合理運用人力、物力和財力的最佳方案，發揮和提高系統的效能及效益，最終達到系統的最優目標。實踐表明，隨著科學技術的日益進步和生產經營的日益發展，最優化方法已成為現代管理科學的重要理論基礎和不可缺少的方法，被人們廣泛地應用到公共管理、經濟管理、國防等各個領域，發揮著越來越重要的作用。本門課程將介紹非線性最優化方法的研究對象、特點。主要是無約束優化計算、約束優化計算以及動態規劃的模型、求解。非線性優化與動態規劃第一部分緒論一、最優化方法的定義、研究對象及研究方法英國運籌學會給最優化方法下的定義是，最優化方法是一系列科學方法的應用。在工業、商業、政府及國防部門中，用這些方法處理大量的人員、機器、材料和資金等復雜問題。這種方法的特點是科學地建立系統模型，包括度量各種因素，例如分析機會和風險，以此預測和比較各種決策、策略或控制的結果，使管理機構科學地確定它的政策及行動。美國運籌學會下了一個比較簡短的、與上述相類似的定義：最優化方法的研究內容是，在需要對有限的資源進行分配的情況下，作出人機系統最優設計的操作的科學決策。

非線性優化與動態規劃第一部分緒論以上幾種定義中雖然每個定義所強調的側重點略有不同，但總的含義是一致的。一般說來，最優化方法的研究對象是各種有組織的系統（主要是經濟組織系統）的經營管理問題，最優化方法所研究的系統是在一定時空條件下存在，為人所能控制和操縱，有兩個以上行動方案可供選擇而需要人們作決策的系統。最優化方法研究的問題是能用數量表示與系統各項活動有關而帶有運用、策劃、使用、安排、控制和規劃等方面的問題。最優化方法的任務就是在現有條件下，根據問題的要求，對有關活動中的錯綜復雜的數量進行分析研究，并歸納為一定的模型，然后運用有關原理和方法求得解決問題的最優途徑和方案，以求實現預期目標。非線性優化與動態規劃第一部分緒論最優化問題的數學模型

數學模型是對實際問題的數學描述和概括,是進行最優化設計的基礎.根據設計問題的具體要求和條件建立完備的數學模型是最優化設計成敗的關鍵.這是因為最優化問題的計算求解完全是針對數學模型進行的.也就是說，最優化計算所得最優解實際上只是數學模型的解，至于是否是實際問題的解，則完全取決于數學模型與實際問題符合的程度.工程設計問題通常是相當復雜的，欲建立便于求解的數學模型，必須對實際問題加以適當的抽象和簡化.不同的簡化方法得到不同的數學模型和計算結果，而且一個完善的數學模型，往往需要在計算求解過程中進行反復地修改和補充才能最后得到.

非線性優化與動態規劃第一部分緒論通過幾個簡單的最優化設計簡例，說明數學模型的一般形式、結構及其有關的基本概念.

例1.用一塊邊長3m的正方形薄板，在四角各裁去一個大小相同的方塊，做成一個無蓋的箱子，試確定如何裁剪可以使做成的箱子具有最大的容積.

解:設裁去的4個小方塊的邊長為x，則做成的箱子的容積為:

于是，上述問題可描述為:求變量

x,使函數極大化.這樣就把該設計問題轉化成為一個求函數f(x)最大值的數學問題.其中,x是待定的求解參數,稱為決策變量;函數f(x)代表設計目標,稱為目標函數.由于目標函數是設計變量的三次函數,并且不存在任何限制條件,故稱此類問題為非線性無約束最優化問題.非線性優化與動態規劃第一部分緒論例2.某工廠生產甲、乙兩種產品，生產每種產品所需的材料、工時、用電量和可以獲得的利潤，以及每天能夠提供的材料、工時、用電量見表1—1，試確定該廠兩種產品每天的生產計劃，以使得每天獲得的利潤最大.表1-1生產條件基本數據產品材料/kg工時/h用電能量/kw—

h利潤/元甲乙供應量943603103004520060120解:這是一個簡單的生產計劃問題,可歸結為在滿足各項生產條件的基礎上,合理安排兩種產品每天的生產量,以使利潤最大化的最優化設計問題.非線性優化與動態規劃第一部分緒論設每天生產甲產品x1件,乙產品x2件,每天獲得的利潤用函數f(x1,x2)表示,即:每天實際消耗的材料、工時和電力分別用函數表示，即于是，該問題可歸結為以下數學模型：求變量x1,x2,使函數極大化并滿足條件:稱此類問題為線性約束最優化問題.非線性優化與動態規劃第一部分緒論二、最優化問題的基本概念

1.最優化問題的向量表示研究最優化問題，一般都采用向量表示，例如決策變量可以看作是n維向量空間Rn中的一個向量x的n個分量，即或例如，例1、例2中的目標函數都可以寫成設x是n維向量變量，則如下函數稱為向量值函數,如果它的定義域為D,則簡記為MTAP-D-18-02390

非線性優化與動態規劃第一部分緒論2.向量的范數約定：取向量為列向量，即n維Euclid空間Rn中的一個向量

x可表示為：或矩陣相等：設如果對一切都有則稱向量x與y相等，記作類似可定義兩向量小于等于或小于關系。非線性優化與動態規劃第一部分緒論矩陣的正定性質及對稱矩陣的判定：設A為n階對稱矩陣，x為任意非零n維向量(1)若xTAx>0,則稱A為正定矩陣，記作A>0;(2)若xTAx0,則稱A為半正定矩陣，記作A0;(3)若xTAx<0,則稱A為負定矩陣，記作A<0;(4)若xTAx0,則稱A為半負定矩陣，記作A0.除此之外，稱A為不定矩陣.非線性優化與動態規劃第一部分緒論判定方法：設A為

n階對稱矩陣A>0A的特征值都大于0A的各階順序主子式都大于0A0A的特征值都大于等于0A的各階順序主子式都大于等于0A<0A的特征值都小于0A的奇階順序主子式都小于0,A的偶階順序主子式都大于0A0A的特征值都小于等于0A的奇階順序主子式都小于等于0,A的偶階順序主子式都大于等于0A為不定矩陣A既有正的特征值,又有負的特征值非線性優化與動態規劃第一部分緒論兩向量內積：設稱為向量x和y的內積.向量x的Euclid范數(向量x的長度)稱為向量x的Euclid范數(向量x的長度).關于Euclid范數及內積的兩個重要不等式(1)三角不等式(2)Cauchy不等式非線性優化與動態規劃第一部分緒論3.最優化問題的一般形式非線性優化與動態規劃第一部分緒論概括地說，后面大部分章節要討論的問題是如下的最優化問題:其中是subjectto的縮寫，表示“滿足于”.其中f,si

,hj

都是x的實值連續函數，通常假定它們都具有二階連續偏導數.上面的模型也可以用向量來表示.常用術語:

f(x)稱為目標函數,或求它的極小,或求它的極大;被稱為不等式約束，稱為等式約束.稱為集約束.在（1.1）中,集約束一般為（1.1）非線性優化與動態規劃第一部分緒論不然的話,可以用不等式約束出來,因此，后面一般不考慮集約束.滿足所有約束的向量x稱為可行解或容許解,可行解的集合稱為可行域（容許域）.全局極小點與局部極小點：若存在則稱x*為f(x)在D上的全局極小點.這里的“”改為“”，則稱x*為f(x)在D上的全局嚴格極小點.x*組成的集合稱為最優解集.若存在并對有則稱x*為問題（1.1）

f(x)的局部極小點（最優解）.非線性優化與動態規劃第一部分緒論從以上定義可以看出，x*是局部極小點，是指在以x*為中心的一個小鄰域中f(x)在點x*處取得極小值；而x*是全局極小點，是指在定義域中，f(x)在點x*處取得極小值.全局最小點必定是局部極小點.實際問題通常是求全局極小點，但直到目前為止，最優化中絕大多數方法都是求局部極小點的.解決這類問題的方法是，先求出所有的局部極小點，然后再求全局極小點.在模型(1.1)中,設向量均在D的內部，則稱h為x的一個可行方向.結論:設在(1.1)中,對于x*的任意可行方向h,均有則x*為(1.1)的嚴格局部最優解.非線性優化與動態規劃第一部分緒論4.最優化問題分類最優化問題可做如下分類：最優化問題靜態問題動態問題無約束非線性規劃問題約束問題一維問題n維問題線性規劃非線性規劃沒有約束的問題：稱為無約束問題.如決策變量只有一個，稱為一維問題.求解一維問題的方法稱為一維搜索或線性搜索，在最優化中起著十分重要的作用.非線性優化與動態規劃第一部分緒論一維問題n維問題三、多元函數的梯度、Hesse矩陣及Taylor公式可微函數f(x)的梯度，記為▽f(x)，它是以f(x)對xi(i=1,2,…,n）的偏導數為元素的n維向量(本書規定為列向量)，即也可以把梯度稱為函數關于向量x的一階導數.函數在某一點x(1)的梯度可表示為：1.梯度非線性優化與動態規劃第一部分緒論

定義1:

設f:Rn→R，xRn，如果存在n維向量p，對任意的非零向量Δx，使得則稱f(x)在點x處可微分，記作定理1：設f:Rn→R，xRn，如果f(x)在x點可微，則f(x)在x點的梯度存在，且稱為f(x)在x點的微分.非線性優化與動態規劃第一部分緒論

定義2:設f:Rn→R，x

Rn，d是給定的n維非零向量，則稱該極限為f(x)在點x處沿d的方向導數，記作定理２：設f:Rn→R，x∈Rn，如果f(x)在x點可微，則在x處沿任何非零向量d的方向導數存在，且如果下面的極限存在非線性優化與動態規劃第一部分緒論

定義3

設f(x)是Rn上的連續函數，x0Rn，d是給定的n維非零向量，如果存在δ>0，使得則稱d為f(x)在x0點的下降方向，若定理3設f:Rn→R，x

Rn，且f(x)在x點可微，如果存在非零向量d

Rn，使得f(x)Td<0，則d是下降方向，若f(x)Td>0，則d是上升方向。則稱d為f(x)在x0點的上升方向。非線性優化與動態規劃第一部分緒論此定理說明，與f在x0處的梯度方向交成銳角的任何方向都是f在x0處的上升方向；相反，與f在x0處的梯度梯度方向交成鈍角的任何方向都是f在x0處的下降方向。可以證明：梯度方向是函數值上升最快的方向，梯度負方向是函數值下降最快的方向。因此我們把負梯度方向叫做最速下降方向.還可以證明：f(x)在x0處的梯度與f(x)過x0處等值面上任一曲線l在該點的切線垂直，即與過該點的切平面垂直?；蛘呖梢哉ff(x0)是曲面f(x)=f(x0)在點x0處的一個法線向量。注：過x0的等值面方程為：f(x)=f(x0)=c.非線性優化與動態規劃第一部分緒論2.海賽（Hesse）矩陣假設函數f(x)二階可微，則以其二階偏導數為元素構成的下述n×n矩陣稱為f(x)的海賽矩陣，記為即當f(x)在x處的所有二階偏導數連續時，有這時的Hesse矩陣為對稱矩陣.非線性優化與動態規劃第一部分緒論向量函數的導數定義4設如果對于自變量的各分量的偏導數都存在，則稱向量函數h在處是一階可導的，并且稱矩陣為h(x)在處的一階導數或Jacobi矩陣，簡記為非線性優化與動態規劃第一部分緒論n元函數的梯度是向量函數由上面定義知，f(x)的一階導數或Jacobi矩陣為：非線性優化與動態規劃第一部分緒論即函數梯度的Jacobi矩陣即為該函數的Hesse矩陣.非線性優化與動態規劃第一部分緒論

例1求函數在任意點的梯度和海賽矩陣。

解:先求f(x)的各階偏導數，有非線性優化與動態規劃第一部分緒論例2求二次齊次函數的Hesse矩陣解：非線性優化與動態規劃第一部分緒論非線性優化與動態規劃第一部分緒論3.Taylor展式設n元實函數f(x)在某點x(0)

的某一鄰域內有連續二階偏導數，則可寫出它在x(0

)處的泰勒（Taylor）展開式如下：若在上式中略去高階無窮小項，則有相應的近似關系式：非線性優化與動態規劃第一部分緒論四、凸函數與凸規劃

求解非線性規劃問題的算法很多，但一般情況下求出的都是局部最優解。而我們的目的是求問題的全局最優解。為了達到這個目的，我們一般可以從兩個方面著手考慮，一是尋求求全局極值的計算方法，二是從理論上說明在何種情況下，求出的局部極值一定是問題的全局極值。實際上，研究結果表明，對于凸規劃來說，局部最優解一定是全局最優解（對極值問題而言）。本部分首先介紹凸函數的概念和性質，再介紹凸規劃的概念與性質。非線性優化與動態規劃第一部分緒論凸集的線段都全部包含在該集合內，就稱該點集為凸集，否則為非凸集。一個點集（或區域），如果連接其中任意兩點非線性優化與動態規劃第一部分緒論1.凸函數及其性質定義5若對任意的及D中任意兩點和有（1.2）

成立，則稱f（X）為D上的凸函數，或稱f（X）在D上是凸的.設f(X)為定義在非空凸集上的函數。（1.3）

成立,則稱f(X)為D上的嚴格凸函數，或稱f(X)在D上是嚴格凸的.若對任意的及任意兩點有非線性優化與動態規劃第一部分緒論注1：

若f是D上的（嚴格）凸函數，則稱-f是D上的(嚴格)凹函數，或稱-f在D上是（嚴格）凹的。實際上，我們也可以仿照定義2來定義凹函數，只要令式（1.2）和（1.3）不等號反向.當n=1時，如圖1.1所示凸（凹）函數的函數曲線上任意兩點間的連線總在函數曲線的上(下)圖1.1（a）凸函數非線性優化與動態規劃第一部分緒論圖1.1（b）凹函數注2：由凸（凹）函數的定義，可知線性函數既是凸函數也是凹函數。非線性優化與動態規劃第一部分緒論根據凸函數的定義，易證凸函數有如下的基本性質.性質1.1設f（X）是凸集D上的凸函數，為實數，則也是D上的凸函數。性質1.2設和均為凸集D上的凸函數，則也是D上的凸函數.性質1.3也是D上的凸函數.設均為凸集D上的凸函數，且則線性組合非線性優化與動態規劃第一部分緒論性質1.4集合設f(X)是凸集D上的凸函數，對任一實數,也是凸集.證明：

任取則且任取因為D為凸集，所以又因為f（X）為D上的凸函數，所以由集合的定義知，證畢.根據凸集的定義知為凸集.我們稱集合為f（X）在集合D上關于數的水平集.非線性優化與動態規劃第一部分緒論2.凸函數的判定我們可以根據凸函數的定義來判定一個函數是否為凸函數,但如果該函數是可微函數，那么可按下述法則判別.定理4（函數凸性的一階條件）設D是En的非空開凸集,函數具有一階連續的偏導數，則函數f為凸函數的充要條件是,恒有（1.4）其中為函數f在處的梯度向量.非線性優化與動態規劃第一部分緒論證明：必要性。因為D是的非空開凸集，所以因為函數f為凸函數，所以從而有由于上式不等式兩邊同除以得非線性優化與動態規劃第一部分緒論由于f具有一階連續的偏導數，故有所以于是得到非線性優化與動態規劃第一部分緒論充分性。因為D是的非空開凸集，則由充分性條件式（1.4）得以和分別乘以上述兩個不等式的兩邊，并相加整理得由定義知函數為凸函數.證畢.非線性優化與動態規劃第一部分緒論定理5（函數凸性的二階條件）設D是的非空開凸集，函數的偏導數，則函數f為凸函數的充要條件是函數f的Hesse矩陣H(X)在D上為半正定矩陣.函數f為嚴格凸函數的充要條件是函數f的Hesse矩矩陣H(X)在D上為正定矩陣.具有二階連續證明：必要性。因為D是的非空開凸集，所以有f為嚴格凸函數，因為D是Rn的非空開凸集所以存在當時，由定理4得非線性優化與動態規劃第一部分緒論因為函數f具有二階連續的偏導數，由Taylor展式得所以由上兩式得上式兩邊同除以注意到則有即Hesse矩陣H(X)在D上為半正定矩陣。充分性。由Taylor展式得，非線性優化與動態規劃第一部分緒論其中因為D是凸集，所以由充分性的條件知Hesse矩陣H（X）在D上為半正定矩陣，從而為半正定矩陣，即有所以由定理4知函數為的凸函數.第二個結論的證明只要把上述的不等號換成嚴格的不等號即知成立.證畢.非線性優化與動態規劃第一部分緒論例3判斷是否為凸函數.解：用二階條件.從而有因為順序主子式所以H(X)正定，故f(X)為嚴格凸函數.非線性優化與動態規劃第一部分緒論定理6若f(X)是凸集DRn上的凸函數,則它的任一局證明：設是任一局部極小點，為其充分小的鄰域,則有充分小，則有所以部極小點就是它在D上的全局極小點，而且它的極小點全體形成一個凸集.因為f(X)是凸集DRn上的凸函數,所以將上兩式相加并除以

,即得所以結論成立.證畢.非線性優化與動態規劃第一部分緒論定理7設f（X）在凸集DRn

上可微且為凸函數，若存在點都有（1.5）則是f（X）在D上的全局極小點；若f（X）為可微的嚴格凸函數，則即是f（X）的唯一全局極小點.證明：由定理4知由條件知所以若f（X）為可微的嚴格凸函數，則(1.5)成立嚴格不等號,即是f（X）在D上的全局極小點.由X的任意性知由定理知結論成立.證畢.非線性優化與動態規劃第一部分緒論定理7的含義可參考圖1.2圖1.2非線性優化與動態規劃第一部分緒論3.凸規劃及其性質考慮非線性規劃問題