東北大學最優(yōu)化第一章(1)

開始

最優(yōu)化方法

（最優(yōu)化課件研制組）退出主講：張京最優(yōu)化方法

最優(yōu)化方法為了使系統(tǒng)達到最優(yōu)的目標所提出的各種求解方法稱為最優(yōu)化方法。最優(yōu)化方法是在第二次世界大戰(zhàn)前后，在軍事領(lǐng)域中對導彈、雷達控制的研究中逐漸發(fā)展起來的。最優(yōu)化方法解決問題一般步驟：（1）提出需要進行最優(yōu)化的問題，開始收集有關(guān)資料和數(shù)據(jù)；（2）建立求解最優(yōu)化問題的有關(guān)數(shù)學模型，確定變量，列出目標函數(shù)和有關(guān)約束條件；（3）分析模型，選擇合適的最優(yōu)化方法；（4）求解方程。一般通過編制程序在電子計算機上求得最優(yōu)解；（5）最優(yōu)解的驗證和實施。隨著系統(tǒng)科學的發(fā)展和各個領(lǐng)域的需求，最優(yōu)化方法不斷地應用于經(jīng)濟、自然、軍事和社會研究的各個領(lǐng)域。

第1章預備知識1.1經(jīng)典極值問題

1.例子，

2.數(shù)學模型

第一，無約束極值問題或

解法：解方程組第二，僅含等式約束的極值問題

或

解法：Lagrange乘子法1.2實例數(shù)據(jù)擬合問題原料切割問題運輸問題營養(yǎng)配餐問題分配問題1.3基本概念

1.最優(yōu)化問題的向量表示法設(shè)

則（1）

以向量為變量的實值函數(shù)定義向量間的序關(guān)系(定義1.1)：

等于＝，小于，嚴格小于。由此（2）以向量為變量的實向量值函數(shù)最優(yōu)化問題的一般形式

（3）

2.最優(yōu)化問題的分類試驗問題：用于檢驗、比較最優(yōu)化方法優(yōu)劣的一些最優(yōu)化問題。3.

術(shù)語目標函數(shù)等式約束

不等式約束容許解（點）容許集

求解問題（3）是指：在容許集中找一點目標函數(shù)在該點取極小值，即對于容許集中的任，總有

意一點最優(yōu)點（極小點）

最優(yōu)值

最優(yōu)解嚴格極小點局部

非嚴格極小點嚴格極小點非嚴格極小點全局，使得

到目前為止，大多數(shù)最優(yōu)化算法求到的都是局部極小點。為了求得全局極小點，一種解決辦法是，先求出所有的局部極小點，然后再從中找出全局極小點。

4.極大值問題與極小值問題的關(guān)系

1.4二維問題圖解法二維極值問題有時可以用圖解的方式進行求解，有明顯的幾何解釋。

例求解

圖解法的步驟：，顯然；②取并畫出相應的曲線（稱之為等值線）.

③確定極值點位置，并用以往所學方法求之。

易知本題的極小值點。

再復雜點的情形見P13上的例1.7。雖然三維及以上的問題不便于在平面上畫圖，圖解法失效，但仍有相應的等值面的概念，且等值面具有以下性質(zhì)：①有不同函數(shù)值的等值面互不相交（因目標函數(shù)是單值函數(shù)的緣故）；②等值面不會在區(qū)域的內(nèi)部中斷，除了極值點所在的等值面以外。這是由于目標函數(shù)是連續(xù)函數(shù)的緣故；①令

⑶等值面稠密的地方，目標函數(shù)值變化得比較快；等值面稀疏的地方，目標函數(shù)值變化得比較慢；⑷在極值點附近，等值面（等值線）一般近似地呈現(xiàn)為同心橢球面族（橢圓線族）。1.5梯度和Hesse矩陣本段討論都基于對函數(shù)以下及今后的討論中還經(jīng)常要用到以下一些向量的知識。可微的假定。

與。

記作。向量也常用希臘字母等表示。向量內(nèi)積的性質(zhì)：ⅰ)（對稱性）；ⅱ)

（線性性）；ⅲ),當且僅當時，（正定性）；向量的內(nèi)積

設(shè)則稱為向量的內(nèi)積，其實，

向量的長單位向量

向量的夾角，

向量的正交

（正交性）

1.可微定義1.7設(shè).如果存在維向量對于可任意小的維非零向量，總有在點那么稱函數(shù)處可微。

若令便得到（1.9）的等價形式

.（1.10）

2.梯度定理1.1若在點處可微，則在該點關(guān)于各個變量的一階偏導數(shù)存在，并且

定義1.8以函數(shù)的個偏導數(shù)為分量的向量稱為在點處的梯度，記為。。

梯度也稱為函數(shù)關(guān)于變量于是，（1.10）可寫為這個公式與一元函數(shù)展開到兩項的Taylor公式是相對的。

梯度的性質(zhì)：當梯度連續(xù)時，

第一，若，則必垂直于過點處的等值面；的一階偏導數(shù)。

第二，梯度方向是函數(shù)具有最大變化率的方向。

下面以為例來解釋這個性質(zhì)。

上圖是該函數(shù)的等值線圖。

今考慮一點，不妨取坐標為。設(shè)想有出發(fā)沿某個方向移動到了點，其坐標，那么目標函數(shù)值將產(chǎn)生如下變化量一動點從設(shè)為假定。試問：動點沿哪個方向移動會使目標函數(shù)值有最多的下降或上升？從圖上看，這相當于問：在以點為圓心、以1為半徑的圓周上，哪一個點具有最大的或最小的目標函數(shù)值。

為了一般地描述函數(shù)在點處沿情況及變化速度，須引入上升方向和下降方向及方向?qū)?shù)的概念。方向的變化函數(shù)在點處沿方向的變化反映的是函數(shù)在一條直線上的變化，空間中由一點和一方向所確定的直線方程為

上升方向和下降方向設(shè)是連續(xù)函數(shù)。

若存在，對于都有，則稱方向是在點處的上升方向；若存在對于都有，則稱方向是在點處的下降方向。定義1.9設(shè)在點處可微，是非方向上的單位向量。如果極限零向量存在，則稱其為函數(shù)在點處沿方向的方向?qū)?shù)，。記作思考：與的異同。

若，則方向是在點處的上升方向；

根據(jù)極限理論，易見若，則方向是在點處的下降方向。因此，方向?qū)?shù)的正負決定了函數(shù)值的升降。定理1.2設(shè)在點處可微，則，其中是非零向量方向上的單位向量。定理1.2又表明：只要，則方向是在點處的上升方向；只要，則方向是在點處的下降方向。

函數(shù)值升降的快慢則是由方向?qū)?shù)絕對值的大小決定的。絕對值越大，升或降的速度就越快；絕對值越小，升或降的速度就越慢。這是因為據(jù)此有

ⅰ)等號成立當且僅當與同方向或與同方向。且當與同方向時，

取到最大值

。當與同方向時，

取到最小值

ⅱ)

若是銳角，則;若是鈍角，則。

因此，方向?qū)?shù)又可以稱為函數(shù)在點處沿方向的變化率。使函數(shù)值下降最快的方向稱為最速下降方向。

最速下降方向為例1.8P19

幾個常用函數(shù)的梯度公式（1）若，則，即（2）（3）；（4）.；；2.Hesse矩陣問：函數(shù)關(guān)于變量的二階導數(shù)又是什么？

先來看什么是向量值函數(shù)的可微。定義1.11設(shè)。

若的所有分量

在點都可微，則稱向量值函數(shù)在點處可微。

定義表明，在點處可微，則成立，其用向量形式可簡單地表示為其中稱為向量值函數(shù)在點處的導數(shù)，

而稱為向量值函數(shù)在點處的Jacobi矩陣。設(shè)具有二階連續(xù)偏導數(shù)，且則矩陣稱為函數(shù)關(guān)于變量的二階導數(shù)，簡記為。也稱為多元實值函數(shù)的Hesse矩陣。例1.9P21

幾個特殊的向量值函數(shù)的導數(shù)公式：（1）；（2）；（3）；（4）設(shè)，其中。則利用（4），可得多元函數(shù)展開到三項的Taylor公式（1.29）或（1.31）這個公式與一元函數(shù)展開到三項的Taylor公式是相對應的。多元函數(shù)的Taylor展開式在最優(yōu)化方法中十分重要，許多方法及其收斂性的證明都是從它出發(fā)的。

1.凸集1.6凸函數(shù)與凸規(guī)劃直觀上，凸集就是空間中內(nèi)部無“洞”，邊界又不向內(nèi)凹的一些點的集合，其基本特征是該集合中任意兩點間的線段仍然屬于這個集合。非凸集凸集空間中兩點間的線段是由點的凸組合定義的。定義1.12設(shè)是中的個已知點。

點，若存在滿足的非負實數(shù)

對于使得，則稱是的一個凸組合。

又若是滿足的正實數(shù)，則稱是的一個嚴格凸組合。兩點的凸組合恰是連接兩點的的線段。

線段，而嚴格凸組合是不含端點定義1.13設(shè)集合。如果中任意兩點的，那么集合稱為凸集。任意凸組合仍然屬于規(guī)定：空集是凸集。

思考：空間中三個不同點的凸組合的集合，空間中四個不同點的凸組合的集合.常見的凸集有超平面，直線，球.定理1.5凸集的交集是凸集。2.凸函數(shù)定義1.16設(shè)，其中為凸集。若對于中的任意互異兩點和任意一對滿足的非負實數(shù)，

總有則稱是定義在凸集上的凸函數(shù)。又若對于任意的正實數(shù)，總有一對滿足則稱是定義在凸集上的嚴格凸函數(shù)。若是凸集上的（嚴格）凸函數(shù)，則稱是凸集上的（嚴格）凹函數(shù)。凸函數(shù)有以下重要性質(zhì)。定理1.6

（1）若是定義在凸集上的凸函數(shù)，是也是上的凸函數(shù)。任意的非負實數(shù)，則（2）若是定義在凸集上的凸函數(shù)，則也是上的凸函數(shù)。由定理1.6易見，定義在凸集上的任意有限個凸函數(shù)的任意非負組合仍然是凸函數(shù)。例1.10定理1.7

設(shè)，其中為非空凸集，若是凸函數(shù)，則對于任意實數(shù)，

水平集是凸集。證

若是空集，則是凸集。以下設(shè)非空。任取，則

。又設(shè)但，根據(jù)的凸性，必有即。因此，是凸集。判斷一個函數(shù)是否為凸函數(shù)，一般說來，是比較困難的。但當函數(shù)可微時，有以下幾個判定定理。定理1.7設(shè)定理1.8設(shè)是可微函數(shù)，其中為凸集。則ⅰ)

為凸函數(shù)的充要條件是對于中的任意兩點，都有ⅱ)

為嚴格凸函數(shù)的充要條件是對于中的任意都有兩個互異點定理1.8有明顯直觀的幾何解釋?？晌⒑瘮?shù)為凸函數(shù)的充要條件是在其定義域凸集中任一點處的切平面（切線）都不在曲面（曲線）的上方。右圖畫出了一維的情形。定理1.9設(shè)是二次可微函數(shù)，為非空開凸集。則為上凸函數(shù)的充要條件是Hesse矩陣在上處處半正定。定理1.10設(shè)是二次可微函數(shù)，為非空凸集，若的Hesse矩陣在上處處正定，則是上的嚴格凸函數(shù)。這個命題的逆命題不真。例如，在上為嚴格凸函數(shù)，在處是半正定的。但是它的Hesse矩陣3.凸規(guī)劃

設(shè)是定義在非空凸集上的凸函數(shù)，則形式為（1.36）的最優(yōu)化問題稱為凸