最優(yōu)化方法第一章

第一頁(yè)，共三十五頁(yè)，編輯于2023年，星期三

或

解法：Lagrange乘子法1.2實(shí)例數(shù)據(jù)擬合問題原料切割問題運(yùn)輸問題營(yíng)養(yǎng)配餐問題分配問題1.3基本概念1.最優(yōu)化問題的向量表示法設(shè)則（1）

第二頁(yè)，共三十五頁(yè)，編輯于2023年，星期三

以向量為變量的實(shí)值函數(shù)定義向量間的序關(guān)系(定義1.1)：等于＝，小于，嚴(yán)格小于。由此（2）以向量為變量的實(shí)向量值函數(shù)最優(yōu)化問題的一般形式

（3）第三頁(yè)，共三十五頁(yè)，編輯于2023年，星期三

2.最優(yōu)化問題的分類試驗(yàn)問題：用于檢驗(yàn)、比較最優(yōu)化方法優(yōu)劣的一些最優(yōu)化問題。3.術(shù)語(yǔ)目標(biāo)函數(shù)等式約束

不等式約束容許解（點(diǎn)）容許集

第四頁(yè)，共三十五頁(yè)，編輯于2023年，星期三

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

意一點(diǎn)最優(yōu)點(diǎn)（極小點(diǎn)）最優(yōu)值最優(yōu)解嚴(yán)格極小點(diǎn)局部非嚴(yán)格極小點(diǎn)嚴(yán)格極小點(diǎn)非嚴(yán)格極小點(diǎn)全局，使得第五頁(yè)，共三十五頁(yè)，編輯于2023年，星期三

到目前為止，大多數(shù)最優(yōu)化算法求到的都是局部極小點(diǎn)。為了求得全局極小點(diǎn)，一種解決辦法是，先求出所有的局部極小點(diǎn)，然后再?gòu)闹姓页鋈謽O小點(diǎn)。

4.極大值問題與極小值問題的關(guān)系第六頁(yè)，共三十五頁(yè)，編輯于2023年，星期三

第七頁(yè)，共三十五頁(yè)，編輯于2023年，星期三

1.4二維問題圖解法二維極值問題有時(shí)可以用圖解的方式進(jìn)行求解，有明顯的幾何解釋。例求解第八頁(yè)，共三十五頁(yè)，編輯于2023年，星期三

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

③確定極值點(diǎn)位置，并用以往所學(xué)方法求之。

易知本題的極小值點(diǎn)。

再?gòu)?fù)雜點(diǎn)的情形見P13上的例1.7。雖然三維及以上的問題不便于在平面上畫圖，圖解法失效，但仍有相應(yīng)的等值面的概念，且等值面具有以下性質(zhì)：①有不同函數(shù)值的等值面互不相交（因目標(biāo)函數(shù)是單值函數(shù)的緣故）；②等值面不會(huì)在區(qū)域的內(nèi)部中斷，除了極值點(diǎn)所在的等值面以外。這是由于目標(biāo)函數(shù)是連續(xù)函數(shù)的緣故；①令第九頁(yè)，共三十五頁(yè)，編輯于2023年，星期三

⑶等值面稠密的地方，目標(biāo)函數(shù)值變化得比較快；等值面稀疏的地方，目標(biāo)函數(shù)值變化得比較慢；⑷在極值點(diǎn)附近，等值面（等值線）一般近似地呈現(xiàn)為同心橢球面族（橢圓線族）。1.5梯度和Hesse矩陣本段討論都基于對(duì)函數(shù)以下及今后的討論中還經(jīng)常要用到以下一些向量的知識(shí)?？晌⒌募俣ā５谑?yè)，共三十五頁(yè)，編輯于2023年，星期三

與。

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

（線性性）；ⅲ),當(dāng)且僅當(dāng)時(shí)，（正定性）；向量的內(nèi)積設(shè)則稱為向量的內(nèi)積，其實(shí)，第十一頁(yè)，共三十五頁(yè)，編輯于2023年，星期三

向量的長(zhǎng)單位向量向量的夾角，

向量的正交

（正交性）

1.可微定義1.7設(shè).如果存在維向量對(duì)于可任意小的維非零向量，總有在點(diǎn)那么稱函數(shù)處可微。第十二頁(yè)，共三十五頁(yè)，編輯于2023年，星期三

若令便得到（1.9）的等價(jià)形式

.（1.10）

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

定義1.8以函數(shù)的個(gè)偏導(dǎo)數(shù)為分量的向量稱為在點(diǎn)處的梯度，記為。。第十三頁(yè)，共三十五頁(yè)，編輯于2023年，星期三

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

梯度的性質(zhì)：當(dāng)梯度連續(xù)時(shí)，第一，若，則必垂直于過點(diǎn)處的等值面；的一階偏導(dǎo)數(shù)。第十四頁(yè)，共三十五頁(yè)，編輯于2023年，星期三

第二，梯度方向是函數(shù)具有最大變化率的方向。下面以為例來解釋這個(gè)性質(zhì)。上圖是該函數(shù)的等值線圖。今考慮一點(diǎn)，不妨取坐標(biāo)為。設(shè)想有出發(fā)沿某個(gè)方向移動(dòng)到了點(diǎn)，其坐標(biāo)，那么目標(biāo)函數(shù)值將產(chǎn)生如下變化量一動(dòng)點(diǎn)從設(shè)為假定。試問：動(dòng)點(diǎn)沿哪個(gè)方向移動(dòng)會(huì)使目標(biāo)函數(shù)值有最多的下降或上升？從圖上看，這相當(dāng)于問：在以點(diǎn)為圓心、以1為半徑的圓周上，哪一個(gè)點(diǎn)具有最大的或最小的目標(biāo)函數(shù)值。第十五頁(yè)，共三十五頁(yè)，編輯于2023年，星期三

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

上升方向和下降方向設(shè)是連續(xù)函數(shù)。第十六頁(yè)，共三十五頁(yè)，編輯于2023年，星期三

若存在，對(duì)于都有，則稱方向是在點(diǎn)處的上升方向；若存在對(duì)于都有，則稱方向是在點(diǎn)處的下降方向。定義1.9設(shè)在點(diǎn)處可微，是非方向上的單位向量。如果極限零向量存在，則稱其為函數(shù)在點(diǎn)處沿方向的方向?qū)?shù)，。記作思考：與的異同。第十七頁(yè)，共三十五頁(yè)，編輯于2023年，星期三

若，則方向是在點(diǎn)處的上升方向；根據(jù)極限理論，易見若，則方向是在點(diǎn)處的下降方向。因此，方向?qū)?shù)的正負(fù)決定了函數(shù)值的升降。定理1.2設(shè)在點(diǎn)處可微，則，其中是非零向量方向上的單位向量。定理1.2又表明：只要，則方向是在點(diǎn)處的上升方向；只要，則方向是在點(diǎn)處的下降方向。第十八頁(yè)，共三十五頁(yè)，編輯于2023年，星期三

函數(shù)值升降的快慢則是由方向?qū)?shù)絕對(duì)值的大小決定的。絕對(duì)值越大，升或降的速度就越快；絕對(duì)值越小，升或降的速度就越慢。這是因?yàn)閾?jù)此有ⅰ)等號(hào)成立當(dāng)且僅當(dāng)與同方向或與同方向。且當(dāng)與同方向時(shí)，取到最大值

。當(dāng)與同方向時(shí)，取到最小值

第十九頁(yè)，共三十五頁(yè)，編輯于2023年，星期三

ⅱ)若是銳角，則;若是鈍角，則。因此，方向?qū)?shù)又可以稱為函數(shù)在點(diǎn)處沿方向的變化率。使函數(shù)值下降最快的方向稱為最速下降方向。最速下降方向?yàn)槔?.8P19第二十頁(yè)，共三十五頁(yè)，編輯于2023年，星期三

幾個(gè)常用函數(shù)的梯度公式（1）若，則，即（2）（3）；（4）.；；2.Hesse矩陣問：函數(shù)關(guān)于變量的二階導(dǎo)數(shù)又是什么？先來看什么是向量值函數(shù)的可微。定義1.11設(shè)。若的所有分量

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

第二十一頁(yè)，共三十五頁(yè)，編輯于2023年，星期三

定義表明，在點(diǎn)處可微，則成立，其用向量形式可簡(jiǎn)單地表示為其中稱為向量值函數(shù)在點(diǎn)處的導(dǎo)數(shù)，第二十二頁(yè)，共三十五頁(yè)，編輯于2023年，星期三

而稱為向量值函數(shù)在點(diǎn)處的Jacobi矩陣。設(shè)具有二階連續(xù)偏導(dǎo)數(shù)，且則矩陣稱為函數(shù)關(guān)于變量的二階導(dǎo)數(shù)，簡(jiǎn)記為。也稱為多元實(shí)值函數(shù)的Hesse矩陣。例1.9P21第二十三頁(yè)，共三十五頁(yè)，編輯于2023年，星期三

幾個(gè)特殊的向量值函數(shù)的導(dǎo)數(shù)公式：（1）；（2）；（3）；（4）設(shè)，其中。則利用（4），可得多元函數(shù)展開到三項(xiàng)的Taylor公式（1.29）或（1.31）這個(gè)公式與一元函數(shù)展開到三項(xiàng)的Taylor公式是相對(duì)應(yīng)的。多元函數(shù)的Taylor展開式在最優(yōu)化方法中十分重要，許多方法及其收斂性的證明都是從它出發(fā)的。第二十四頁(yè)，共三十五頁(yè)，編輯于2023年，星期三

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

對(duì)于使得，則稱是的一個(gè)凸組合。第二十五頁(yè)，共三十五頁(yè)，編輯于2023年，星期三又若是滿足的正實(shí)數(shù)，則稱是的一個(gè)嚴(yán)格凸組合。兩點(diǎn)的凸組合恰是連接兩點(diǎn)的的線段。線段，而嚴(yán)格凸組合是不含端點(diǎn)定義1.13設(shè)集合。如果中任意兩點(diǎn)的，那么集合稱為凸集。任意凸組合仍然屬于規(guī)定：空集是凸集。

思考：空間中三個(gè)不同點(diǎn)的凸組合的集合，空間中四個(gè)不同點(diǎn)的凸組合的集合.常見的凸集有超平面，直線，球.定理1.5凸集的交集是凸集。第二十六頁(yè)，共三十五頁(yè)，編輯于2023年，星期三2.凸函數(shù)定義1.16設(shè)，其中為凸集。若對(duì)于中的任意互異兩點(diǎn)和任意一對(duì)滿足的非負(fù)實(shí)數(shù)，

總有則稱是定義在凸集上的凸函數(shù)。又若對(duì)于任意的正實(shí)數(shù)，總有一對(duì)滿足則稱是定義在凸集上的嚴(yán)格凸函數(shù)。第二十七頁(yè)，共三十五頁(yè)，編輯于2023年，星期三若是凸集上的（嚴(yán)格）凸函數(shù)，則稱是凸集上的（嚴(yán)格）凹函數(shù)。凸函數(shù)有以下重要性質(zhì)。定理1.6

（1）若是定義在凸集上的凸函數(shù)，是也是上的凸函數(shù)。任意的非負(fù)實(shí)數(shù)，則（2）若是定義在凸集上的凸函數(shù)，則也是上的凸函數(shù)。由定理1.6易見，定義在凸集上的任意有限個(gè)凸函數(shù)的任意非負(fù)組合仍然是凸函數(shù)。例1.10第二十八頁(yè)，共三十五頁(yè)，編輯于2023年，星期三定理1.7設(shè)，其中為非空凸集，若是凸函數(shù)，則對(duì)于任意實(shí)數(shù)，

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

。又設(shè)但，根據(jù)的凸性，必有即。因此，是凸集。判斷一個(gè)函數(shù)是否為凸函數(shù)，一般說來，是比較困難的。但當(dāng)函數(shù)可微時(shí)，有以下幾個(gè)判定定理。定理1.7設(shè)第二十九頁(yè)，共三十五頁(yè)，編輯于2023年，星期三定理1.8設(shè)是可微函數(shù)，其中為凸集。則ⅰ)

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

為嚴(yán)格凸函數(shù)的充要條件是對(duì)于中的任意都有兩個(gè)互異點(diǎn)定理1.8有明顯直觀的幾何解釋。可微函數(shù)為凸函數(shù)的充要條件是在其定義域凸集中任一點(diǎn)處的切平面（切線）都不在曲面（曲線）的上方。右圖畫出了一維的情形。第三十頁(yè)，共三十五頁(yè)，編輯于2023年，星期三定理1.9設(shè)是二次可微函數(shù)，為非空開凸集。則為上凸函數(shù)的充要條件是Hesse矩陣在上處處半正定。定理1.10設(shè)是二次可微函數(shù)，為非空凸集，若的Hesse矩陣在上處處正定，則是上的嚴(yán)格凸函數(shù)。這個(gè)命題的逆命題不真。例如，在上為嚴(yán)格凸函數(shù)，在處是半正定的。但是它的Hesse矩陣第三十一頁(yè)，共三十五頁(yè)，編輯于2023年，星期三3.凸規(guī)劃設(shè)是定義在非空凸集上的凸函數(shù)，則形式為（1.36）的最優(yōu)化問題稱為凸規(guī)劃問題，簡(jiǎn)稱凸規(guī)劃。換言之，定義在凸集上的凸函數(shù)的極小化問題是凸規(guī)劃問題。若都是上的凹函數(shù)，都是上