1、2021/6/161最優化模型最優化模型一、最優化模型的概述一、最優化模型的概述二、最優化模型的分類二、最優化模型的分類三、最優化模型的建立及求解三、最優化模型的建立及求解四、最優化模型的評價分析四、最優化模型的評價分析2021/6/162 數學家對最優化問題的研究已經有很多年的數學家對最優化問題的研究已經有很多年的歷史。歷史。 以前解決最優化問題的數學方法只限于古典以前解決最優化問題的數學方法只限于古典求導方法和變分法，拉格朗日（求導方法和變分法，拉格朗日（LagrangeLagrange）乘數）乘數法解決等式約束下的條件極值問題。法解決等式約束下的條件極值問題。 計算機技術的出現，使得數學

2、家研究出了許計算機技術的出現，使得數學家研究出了許多最優化方法和算法用以解決以前難以解決的問多最優化方法和算法用以解決以前難以解決的問題。題。一、最優化模型的概述一、最優化模型的概述 解決最優生產計劃、最優設計、最優策略解決最優生產計劃、最優設計、最優策略.2021/6/163 運用最優化方法解決最優化問題的一般方運用最優化方法解決最優化問題的一般方法步驟如下：法步驟如下：前期分析：分析問題，找出要解決的目標，約束條件，前期分析：分析問題，找出要解決的目標，約束條件，并確立最優化的目標。并確立最優化的目標。定義變量，建立最優化問題的數學模型，列出目標函定義變量，建立最優化問題的數學模型，列出目

3、標函數和約束條件。數和約束條件。針對建立的模型，選擇合適的求解方法或數學軟件。針對建立的模型，選擇合適的求解方法或數學軟件。編寫程序，利用計算機求解。編寫程序，利用計算機求解。對結果進行分析，討論諸如：結果的合理性、正確性，對結果進行分析，討論諸如：結果的合理性、正確性，算法的收斂性，模型的適用性和通用性，算法效率與算法的收斂性，模型的適用性和通用性，算法效率與誤差等。誤差等。2021/6/164 最優化模型分類方法有很多，可按變量、約最優化模型分類方法有很多，可按變量、約束條件、目標函數個數、目標函數和約束條件的束條件、目標函數個數、目標函數和約束條件的是否線性是否依賴時間等分類。是否線性是

4、否依賴時間等分類。 根據目標函數，約束條件的特點將最優化模根據目標函數，約束條件的特點將最優化模型包含的主要內容大致如下劃分：型包含的主要內容大致如下劃分： 線性規劃線性規劃 整數規劃整數規劃 非線性規劃非線性規劃 多目標規劃多目標規劃 動態動態規劃規劃 對策論對策論二、最優化模型的分類二、最優化模型的分類2021/6/165最優化模型的求解方法分類最優化模型的求解方法分類圖克定理庫恩極值原理有約束變分法微分法無約束解析法-. 1. 5. 4網絡優化方法多目標優化法隨機搜索法單純形法方向加速法步長加速法坐標輪換法多維搜索法插值法黃金分割法裴波那契法一維搜索法數值算法. 2復形法法法化有為無梯度

5、法梯度投影法可行方向法有約束梯度法變尺度法共軛梯度法擬牛頓法最速下降法無約束梯度法梯度算法SWIFTSUMT. 32021/6/166最優化數學模型形式最優化數學模型形式 min( )xf x. .( )0,1,2,.,( )0,1,2,.,iistg ximh xin 其中，極大值問題可以轉化為極小值問題來其中，極大值問題可以轉化為極小值問題來進行求解。如求：進行求解。如求：max( )xf x 可以轉化為：可以轉化為：min( )xf x三、最優化模型的建立三、最優化模型的建立目標：求函數極值或最值，求取得極值時變量的取值。目標：求函數極值或最值，求取得極值時變量的取值。2021/6/16

6、7問題問題：某工廠在計劃期內要安排生產：某工廠在計劃期內要安排生產I、II兩種產品，已兩種產品，已知生產單位產品所需的設備臺時及知生產單位產品所需的設備臺時及A、B兩種原材料的消兩種原材料的消耗，如下表所示耗，如下表所示 12kg40原材料原材料B16kg04原材料原材料A8臺時臺時21設備設備III該工廠每生產一件產品該工廠每生產一件產品I可獲利可獲利2元，每生產一件產品元，每生產一件產品II可獲利可獲利3元。問應如何安排計劃使該工廠獲利最多？元。問應如何安排計劃使該工廠獲利最多？ 2021/6/168解解：該工廠生產產品：該工廠生產產品I x1件，生產產品件，生產產品II x2件，件，我們

7、可建立如下數學模型：我們可建立如下數學模型：2132maxxxz0,12416482212121xxxxxxs.t. 2, 41421xxz2021/6/169 最優化問題中的所有變量均為整數時，這類最優化問題中的所有變量均為整數時，這類問題稱為整數規劃問題。問題稱為整數規劃問題。 整數規劃可分為線性整數規劃和非線性整數整數規劃可分為線性整數規劃和非線性整數規劃規劃 ，以及混合整數規劃等。，以及混合整數規劃等。 如果決策變量的取值要么為如果決策變量的取值要么為0 0，要么為，要么為1 1，則，則這樣的規劃問題稱為這樣的規劃問題稱為0 01 1規劃。規劃。2021/6/1610問題：問題：某班級

8、準備從某班級準備從5名名游泳隊員中選擇游泳隊員中選擇4人人組成接力隊，組成接力隊，參加學校的參加學校的4*100m混合泳接力比賽。混合泳接力比賽。5名隊員名隊員4種泳姿種泳姿的百的百米平均成績如表米平均成績如表2-1，問應如何選拔隊員組成接力隊？，問應如何選拔隊員組成接力隊？隊員隊員甲甲已已丙丙丁丁戊戊蝶泳蝶泳仰泳仰泳蛙泳蛙泳自由泳自由泳66.866.8秒秒57.257.27878707067.467.475.675.66666878758.658.666.466.4535367.867.874.274.2717184.684.659.459.469.669.657.257.283.883.8

9、62.462.4表表2-12-12021/6/1611問題分析：問題分析：記甲、乙、丙、丁、戊分別為記甲、乙、丙、丁、戊分別為i i=1,2,3,4,5; =1,2,3,4,5; 記泳姿記泳姿j j=1,2,3,4.=1,2,3,4.記隊員記隊員 i i 的第的第 j j 種泳姿的百米最好種泳姿的百米最好成績為成績為c_c_ijij(s),(s),則表則表2-12-1可以表示成表可以表示成表2-2.2-2.c_iji=1i=2i=3i=4i=5j=1j=2j=3j=466.866.857.257.27878707067.467.475.675.66666878758.658.666.466.4

10、535367.867.874.274.2717184.684.659.459.469.669.657.257.283.883.862.462.4表表2-22-22021/6/1612 決策變量：決策變量：引入引入0-1變量變量 ，若選擇隊員，若選擇隊員i參加泳姿參加泳姿j的的比賽比賽, 記，記， ，否則記，否則記 。 目標函數：目標函數：當隊員當隊員i入選泳姿入選泳姿j時，時， 表示該隊員的成表示該隊員的成績，否則績，否則 。于是接力隊的成績可表示為。于是接力隊的成績可表示為 約束條件：約束條件：根據接力隊要求，根據接力隊要求， 滿足約束條件滿足約束條件a. 每人最多只能入選每人最多只能入選4

11、種泳姿之一，即種泳姿之一，即b. 每種泳姿必須有每種泳姿必須有1人而且只能有一人入選，即人而且只能有一人入選，即ijx0ijx1ijx. 151iijx. 141jijxijx.4151jiijijxcf0ijijxcijijxc2021/6/1613 綜上所述，這個問題的優化模型可寫作：綜上所述，這個問題的優化模型可寫作：.1 , 0ijx. 4 , 3 , 2 , 1, 151jxiij. 5 , 4 , 3 , 2 , 1, 1. .41ixtsjij4151minjiijijxcf2021/6/1614非線性規劃問題的一般數學模型：非線性規劃問題的一般數學模型：其中，其中， ， 為目標

12、函數，為目標函數， 為約束函數，這些函數中至少有為約束函數，這些函數中至少有一個是非線性函數。一個是非線性函數。min( ). .( )0,1,2,( )0,1,2, .ijf xstg ximh xjlnEx)(xf)(),(xhxgji2021/6/1615應用實例：應用實例： 供應與選址供應與選址 某公司有某公司有6個建筑工地要開工，每個工地的位置（用平面坐標系個建筑工地要開工，每個工地的位置（用平面坐標系a，b表示，距離單位：表示，距離單位：km）及水泥日用量）及水泥日用量d(t)由下表給出目前有由下表給出目前有兩個臨時料場位于兩個臨時料場位于A(5,1)，B(2,7)，日儲量，日儲量

13、各有各有20t假設從料場到假設從料場到工地之間均有直線道路相連工地之間均有直線道路相連 （1）試制定每天的供應計劃，即從）試制定每天的供應計劃，即從A，B兩料場兩料場分別向各工地運分別向各工地運送多少水泥，可使總的送多少水泥，可使總的噸千米數最小噸千米數最小 （2）為了進一步減少噸千米數，打算舍棄兩個臨時料場，改建兩）為了進一步減少噸千米數，打算舍棄兩個臨時料場，改建兩個新的，日儲量各為個新的，日儲量各為20t，問應建在何處，節省的噸千米數有多大？，問應建在何處，節省的噸千米數有多大？2021/6/1616建立模型建立模型 記工地的位置為記工地的位置為(ai，bi)，水泥日用量為，水泥日用量為

14、di，i=1,6;料場位置為料場位置為(xj，yj)，日儲量為，日儲量為ej，j=1,2；料場；料場j向工地向工地i的運送量為的運送量為Xij當用臨時料場時決策變量為：當用臨時料場時決策變量為：Xij，當不用臨時料場時決策變量為：當不用臨時料場時決策變量為：Xij，xj，yj2021/6/1617 事實上，客觀世界中的大多問題都是非線性的，給事實上，客觀世界中的大多問題都是非線性的，給予線性化處理是近似的，是在作了科學的假設和簡化后予線性化處理是近似的，是在作了科學的假設和簡化后得到的得到的. . 另一方面，有一些是不能進行線性化處理的，另一方面，有一些是不能進行線性化處理的，否則將嚴重影響模

15、型對實際問題近似的可依賴型否則將嚴重影響模型對實際問題近似的可依賴型. . 由于非線性規劃問題在理論分析和計算上通常是很由于非線性規劃問題在理論分析和計算上通常是很困難的，也不能像線性規劃那樣給出簡潔的結果形式和困難的，也不能像線性規劃那樣給出簡潔的結果形式和全面透徹的結論全面透徹的結論. . 所以，在數學建模時，要進行認真的所以，在數學建模時，要進行認真的分析，對實際問題進行合理的假設、簡化，首先考慮用分析，對實際問題進行合理的假設、簡化，首先考慮用線性規劃模型，線性規劃模型，若線性近似誤差較大時若線性近似誤差較大時，則考慮用非線，則考慮用非線性規劃性規劃. .2021/6/1618 在約在

16、約1萬米的高空的某邊長為萬米的高空的某邊長為160km的正方的正方形區域內，經常有若干架飛機作水平飛行，區形區域內，經常有若干架飛機作水平飛行，區域內每架飛機的位置和速度向量均由計算機記域內每架飛機的位置和速度向量均由計算機記錄其數據，以便進行飛行管理。當一架欲進入錄其數據，以便進行飛行管理。當一架欲進入該區域的飛機到達區域邊緣時，計算機記錄其該區域的飛機到達區域邊緣時，計算機記錄其數據后，要立即計算并判斷是否會發生碰撞。數據后，要立即計算并判斷是否會發生碰撞。若會發生碰撞，則應計算若會發生碰撞，則應計算如何調整如何調整各架飛機各架飛機（包括新進入的飛機）飛行的方向角，以避免（包括新進入的飛機

17、）飛行的方向角，以避免碰撞，且使飛機的調整的幅度盡量小，碰撞，且使飛機的調整的幅度盡量小，例例1 1995年全國數學建模年全國數學建模A題：飛行管理問題題：飛行管理問題例題講解例題講解2021/6/1619該題比較有意思的一句話是：該題比較有意思的一句話是： “使調整弧度最小使調整弧度最小”開放性的一句話，沒有限制得很死，較靈活，開放性的一句話，沒有限制得很死，較靈活，給參賽者的創新空間比較大一些，使得構建模型給參賽者的創新空間比較大一些，使得構建模型的目標函數表現形式很多，再加上模型求解方法的目標函數表現形式很多，再加上模型求解方法（算法）的多樣性，從而可以呈現出五花八門的（算法）的多樣性，

18、從而可以呈現出五花八門的論文。論文。2021/6/1620 不碰撞的標準為任意兩架飛機的距離大于不碰撞的標準為任意兩架飛機的距離大于8km;假設條件：假設條件：30 飛機飛行的方向角調整幅度不應超過飛機飛行的方向角調整幅度不應超過 ； （因飛機飛行的速度變化不大）所有飛機的飛行（因飛機飛行的速度變化不大）所有飛機的飛行 速度速度 v 均為均為800km/h;有時需要通過查閱文獻、資料給出合理假設有時需要通過查閱文獻、資料給出合理假設注：注：2021/6/1621 進入該區域的飛機在到達區域邊緣時，與區域內進入該區域的飛機在到達區域邊緣時，與區域內 飛機的距離應在飛機的距離應在60km以上；以上

19、； 最多需考慮六架飛機；最多需考慮六架飛機； 不必考慮飛機離開此區域后的狀況。不必考慮飛機離開此區域后的狀況。根據當年競賽題目給出的數據，可以驗證根據當年競賽題目給出的數據，可以驗證新進入的飛機與區域內的飛機的距離超過新進入的飛機與區域內的飛機的距離超過60公里。公里。根據當年競賽題目給出的數據，可以驗證根據當年競賽題目給出的數據，可以驗證區域內的飛機不超過架區域內的飛機不超過架(包括新進入的包括新進入的)。2021/6/1622 個人的想法不同，隊友之間爭執不下的情況下，個人的想法不同，隊友之間爭執不下的情況下，若時間允許，都可一一寫到論文中去，建立的模若時間允許，都可一一寫到論文中去，建立

20、的模型一、模型二型一、模型二；或者經討論后，選擇一個認或者經討論后，選擇一個認為更合理的。為更合理的。 現在看來，無論是構建模型，還是計算，都不太現在看來，無論是構建模型，還是計算，都不太難。難。 本例題未給出數據，將重點放在如何構建模型上本例題未給出數據，將重點放在如何構建模型上2021/6/1623解：解：(1)不考慮飛機的尺寸，用點代表飛機；不考慮飛機的尺寸，用點代表飛機；(2)已在區域內的已在區域內的5架飛機按給定的方向角作架飛機按給定的方向角作 直線飛行，則必不會碰撞，也不會發生直線飛行，則必不會碰撞，也不會發生 意外；意外；(應該根據題目中所給出的數據簡應該根據題目中所給出的數據簡

21、 單的單的 驗證一下驗證一下)(3)飛機調整方向角的過程可在瞬間完成飛機調整方向角的過程可在瞬間完成,(不不 計調整方向所花費的時間計調整方向所花費的時間)。為解決該問題，補充假設：為解決該問題，補充假設：2021/6/1624變量、參數的符號假設變量、參數的符號假設（為了建模）（為了建模） 00,1 26)iixyii 第第 架架機機的的初初始始位位置置, (，, (， ，01 26)iii 第第 架架機機的的整整前前的的方方向向角角, , ( (， ，1 26)iii 第第 架架機機的的整整后后的的方方向向角角, , ( (， ， 在區域內飛行在區域內飛行iiTi 第第 架架 機機按按方方

22、向向角角飛飛時間（可以根據數據算出來）時間（可以根據數據算出來）2021/6/1625四種情況：四種情況：四個象限，易用四個象限，易用4個表達式表示個表達式表示說明：說明：用初等數學的知識即可完成，用初等數學的知識即可完成，思考：思考：在哪個時間段某兩架飛機可能相撞？在哪個時間段某兩架飛機可能相撞？?ijTTor otherelseIn fact, 我們只需考慮兩架飛機我們只需考慮兩架飛機同時同時在區域內在區域內飛行時的情況，也就是說，飛行時的情況，也就是說， min,ijT T才是同在區域內的狀況。才是同在區域內的狀況。記為記為ijT2021/6/1626 00002202,mincosco

23、ssinsinijijijijijt Tijijdxxvtyyvt 根據題目條件，需計算第根據題目條件，需計算第 架飛機之間架飛機之間的的最短距離最短距離, i j2021/6/1627為此，我們可以給出原問題的模型如下：為此，我們可以給出原問題的模型如下： 00612min,60, ,1,2,6,. .,1,2,6.6iiiijijiidi jijs ti 思考：思考：是否還有其他的表達形式？是否還有其他的表達形式？非線性非線性規劃模規劃模型型分別從目標函數和約束條件角度思考分別從目標函數和約束條件角度思考2021/6/1628首先思考一下目標函數是否有其它的表達？首先思考一下目標函數是否有

24、其它的表達？ 061miniii 同學們首先想到的可能是同學們首先想到的可能是Oh, Sorry!有正有負有正有負抵消抵消2021/6/1629061miniii 0621miniii 最小一最小一乘乘 法法最小二最小二乘乘 法法 因最小一乘法帶絕對值，不好計算，以上兩式，因最小一乘法帶絕對值，不好計算，以上兩式，比較而言，后者較好。比較而言，后者較好。為了避免抵消為了避免抵消or2021/6/1630有的隊員這樣考慮：有的隊員這樣考慮：016min maxiii 令為令為 ,轉化為二次規劃轉化為二次規劃用到經驗模型中確定參數的近似準則用到經驗模型中確定參數的近似準則:就所有飛機而言，就所有飛

25、機而言， 讓調整弧度最大的讓調整弧度最大的即即盡可能小，盡可能小，Chebshavf 準則準則2021/6/1631其次討論一下約束條件是否有其它表達？其次討論一下約束條件是否有其它表達？ 若考慮區域內不發生碰撞（若時間允許，也若考慮區域內不發生碰撞（若時間允許，也可以考慮出了區域的情況，另外建模）、錯層可以考慮出了區域的情況，另外建模）、錯層飛行（飛高或者飛低避免碰撞），進行模型的飛行（飛高或者飛低避免碰撞），進行模型的進一步改進，重點應放在解決問題的方法上。進一步改進，重點應放在解決問題的方法上。 如如 02,1,2,6,6,60, ,1,2,6,iiijijidi jij 2021/6/

26、1632 無論選擇哪一種表達，怎樣考慮約束條件，無論選擇哪一種表達，怎樣考慮約束條件，目標函數都不可能是線性的。目標函數都不可能是線性的。 現在看來，那年的題目建模只是在條件的現在看來，那年的題目建模只是在條件的考慮上和建模中目標函數的表達方面較難一點。考慮上和建模中目標函數的表達方面較難一點。 是一個帶不等式約束的非線性規劃問題。是一個帶不等式約束的非線性規劃問題。 而且不可能轉化成線性的形式。而且不可能轉化成線性的形式。2021/6/1633非線性規劃模型按約束條件可分為以下三類：非線性規劃模型按約束條件可分為以下三類： 無約束非線性規劃模型：無約束非線性規劃模型： 等式約束非線性規劃模型

27、：等式約束非線性規劃模型：min ( )nf xxRmin ( ). . ( )0,1,2,jf xst h xjr 不等式約束非線性規劃模型：不等式約束非線性規劃模型：min ( ). . ( )0,1,2,if xst g xim2021/6/1634如如數據擬合的最小二乘問題就是一個無約束極值問數據擬合的最小二乘問題就是一個無約束極值問題。題。 其思想是：觀察點（實驗數據點）到曲線的距其思想是：觀察點（實驗數據點）到曲線的距離的平方之和最小離的平方之和最小 無約束非線性規劃模型：無約束非線性規劃模型：2021/6/1635理論上無約束極值問題可化成求解理論上無約束極值問題可化成求解 0g

28、rad fx 即解一個即解一個 n 元方程組，且往往是非線性方程組。元方程組，且往往是非線性方程組。 而一般說來，非線性方程組的求解并不比求無而一般說來，非線性方程組的求解并不比求無約束極值容易。約束極值容易。2021/6/1636求解無約束極值問題的基本方法：求解無約束極值問題的基本方法：迭代法迭代法 從一個給定的初始可行點從一個給定的初始可行點 出發，依次出發，依次0 x產生一個可行點列產生一個可行點列12,kxxx的一個極小值點的一個極小值點,恰好是恰好是使得某個使得某個kx fx基本思路：基本思路：或或 kx收斂于收斂于x , 稱具有這種性質的算法稱具有這種性質的算法是是收斂的收斂的.

29、2021/6/1637由由kx迭代到迭代到1kx 時時,1,kkkkxxp 記記即即1,kkkkxxp kp其中向量其中向量為為搜索方向搜索方向, 實數實數k 稱為稱為步長步長,確定以后確定以后,kkp kx由由可唯一地確定可唯一地確定1,kx 從從0 x出發就可確定點列出發就可確定點列 .kx2021/6/1638迭代的方法很多迭代的方法很多, 各種迭代法的區別在于選取各種迭代法的區別在于選取,kkp 的方式不同的方式不同, 而而kp尤為關鍵尤為關鍵.一般要求一般要求 kfx遞減遞減, 具有這種性質的算法叫做具有這種性質的算法叫做下降下降算法算法.2021/6/1639若已得若已得,kx下降

30、得最多下降得最多,并確定了并確定了kx的可行下降方向的可行下降方向,kp上選取步長上選取步長則在射線則在射線 0kkxp ,k 使使 ,kkkkfxpfx 且使且使 kfx 00minmin,kkkkkfxpfxp 即求即求求求k 的過程稱為的過程稱為一維搜索一維搜索.1. 下降算法下降算法2021/6/1640于是一維搜索歸結為求解一維無約束極值問題于是一維搜索歸結為求解一維無約束極值問題: min,xxR 其算法有其算法有Newton法、平分法、黃金分割法法、平分法、黃金分割法（0.618法）、分數法（法）、分數法（Fibonacci法）、拋法）、拋物線法（二次插值法）等，物線法（二次插值

31、法）等， 前兩種算法需計算前兩種算法需計算 x 的導數，的導數，后三種算法只需計算后三種算法只需計算 x 的函數值。的函數值。下面僅介紹下面僅介紹Newton法，對其他方法的了解可法，對其他方法的了解可參考有關書籍。參考有關書籍。2021/6/1641按按0,1,2,k 給定初始可行點給定初始可行點 和控制誤差和控制誤差 ，0 x0 迭代格式迭代格式 1kkkkxxxx 迭代，迭代，當當1kkxx 時，時， x 即求得即求得的最優解的近似解的最優解的近似解1,kxx 停止計算。停止計算。Newton 法介紹法介紹2021/6/1642 一個好的算法必須以較快的速度收斂到一個好的算法必須以較快的

32、速度收斂到最優解。最優解。 kx設算法產生的點列設算法產生的點列收斂于最優解收斂于最優解,x 1p 若存在若存在及及1lim,kpkkxxCxx 0,C 使使 kx則稱則稱為為 p 階收斂的。階收斂的。該算法也是該算法也是 p 階收斂的。階收斂的。2021/6/1643 稱為稱為線性收斂；線性收斂；1lim,kpkkxxCxx 1p 當當且且01C時，時， 稱為稱為超線性收斂；超線性收斂；12p當當時，時， 稱為稱為平方收斂；平方收斂；2p 當當時，時，2021/6/1644一個算法是否收斂，一個算法是否收斂，0 x往往與往往與的選取有關的選取有關 若當若當0 x充分接近充分接近x 時，時，由

33、算法產生的點列由算法產生的點列 kx才收斂于才收斂于,x 則稱該算法為具有局部收斂則稱該算法為具有局部收斂性的算法；性的算法； 若對若對0,xD則稱該算法為具有全局收斂性的算法。則稱該算法為具有全局收斂性的算法。由算法產生由算法產生 的點列的點列 kx均收斂均收斂,x 于于2021/6/1645 Newton法是平方收斂的，具有局部收斂法是平方收斂的，具有局部收斂性；拋物線法是超線性收斂的，具有全局收斂性；拋物線法是超線性收斂的，具有全局收斂性；平分法、黃金分割法、分數法是線性收斂性；平分法、黃金分割法、分數法是線性收斂的，具有全局收斂性。的，具有全局收斂性。常見一維搜索算法的收斂性常見一維搜

34、索算法的收斂性2021/6/1646當當 x 具有多個極小值點時，具有多個極小值點時， 則算法求得則算法求得的往往是的往往是 x 的一個局部極小值點。的一個局部極小值點。此時可此時可改變改變0 x的取值，重新迭代求解。的取值，重新迭代求解。 若求得多個極小值點，則從中選擇一個若求得多個極小值點，則從中選擇一個較滿意的結果。較滿意的結果。 說明：說明：2021/6/1647 1847年年Cauchy提出了第一個無約束極值問提出了第一個無約束極值問題的算法題的算法梯度法或最速下降法：梯度法或最速下降法：2. 梯度法梯度法. 00)(0kX，令，允許誤差越接近最優點越好步驟一：選定初始點).(),(

35、,kkkkXfPXfX選取搜索方向計算梯度優點步驟二：假定已得非最.11返回繼續搜索令不滿足給定精度要求，如果kkXk).(min)( ,k0kkkk1PXfPXfPXXkkkkk，滿足：步驟三：選定搜索步長.1*1kkXXX搜索完成，近似最優點滿足給定精度要求，則如果.)()()(.1111kkkkkkXXXfXfXfX或或斷準則：檢驗是否滿足收斂性判根據精度要求，要求的近似解是否是最優點或是滿足步驟四：判斷2021/6/1648例題：應用梯度法求解例題：應用梯度法求解. 0:2 . 0)2 , 2(0kX，令，允許誤差步驟一：選定初始點.100, 4)(),(kkkXfPXf選取搜索方向步

36、驟二：計算梯度.02. 0,)1002(25)42()().(min)( ,02200000kkkk1解得優步長第一點搜索計算：求最，滿足：步驟三：選定搜索步長PXfPXfPXfPXXkkkk.02. 031.100)()(),0 ,92. 1 (.)()()(.0111111不滿足，繼續搜索且第一點搜索計算：或或斷準則：檢驗是否滿足收斂性判根據精度要求，要求的近似解是否是最優點或是滿足步驟四：判斷XfXfXXXXfXfXfXkkkkkk.25)(min2221xxXf解：解：2021/6/1649 該算法具有全局收斂性，是線性收斂的，該算法具有全局收斂性，是線性收斂的，但有時是很慢的線性收斂

37、，這似乎與但有時是很慢的線性收斂，這似乎與“最速下最速下降降”矛盾。其實不然，最速下降方向函數在某矛盾。其實不然，最速下降方向函數在某點處的局部性質，對局部來說是最速下降方向，點處的局部性質，對局部來說是最速下降方向，對全局來說卻不一定是最速下降方向，故梯度對全局來說卻不一定是最速下降方向，故梯度法不是有效的實用算法。法不是有效的實用算法。 通過對它改進或利用它與其他收斂快的算通過對它改進或利用它與其他收斂快的算法相結合可得法相結合可得Newton法、法、Fletcher-Reeves共軛梯度法、變尺度法和共軛梯度法、變尺度法和Powell法法等有效算等有效算法。法。2021/6/1650 下

38、面僅介紹前兩者，對后兩者的了解可參下面僅介紹前兩者，對后兩者的了解可參閱有關書籍。閱有關書籍。 121,kkkkxxfxg 當當1kkxx 時，時，則則 。1kxx 其中其中 1112121222122,nnnnnnx xkx xkx xkx xkx xkx xkkx xkx xkx xkfxfxfxfxfxfxfxfxfxfx 稱為稱為 fx在在 處的處的Hesse矩陣。矩陣。kxNewton法法2021/6/1651 該算法是平方收斂的，具有局部收斂性。該算法是平方收斂的，具有局部收斂性。 對對Newton法進行改進，可得具有超線性法進行改進，可得具有超線性收斂的且具有全局收斂性的收斂的且

39、具有全局收斂性的阻尼阻尼Newton法法或或修正修正Newton法法： 121102min,kkkkkkkkfxfxgfxgfxfx 當當1kkxx 時，時，有有 。1kxx 2021/6/1652 Fletcher-Reeves共軛梯度法共軛梯度法當當1kkxx 時，時，有有 。1kxx 該算法的收斂速度介于梯度法和該算法的收斂速度介于梯度法和Newton法法其中其中00,Pg 之間，既克服了前者的慢收斂性，又避免了之間，既克服了前者的慢收斂性，又避免了111TkkkkkTkkg gPgPgg 10min,kkkkkkfxfxpfxp 后者計算量大和僅具有局部收斂性的缺陷。后者計算量大和僅具

40、有局部收斂性的缺陷。2021/6/1653（2 2）只有等式約束的非線性規劃問題通常可用只有等式約束的非線性規劃問題通常可用消元法、拉格朗日乘子法，將其化為無約束問消元法、拉格朗日乘子法，將其化為無約束問題求解題求解. .（3 3）具有不等式約束的非線性規劃問題解起來具有不等式約束的非線性規劃問題解起來很復雜，求解這一類問題，通常將不等式化很復雜，求解這一類問題，通常將不等式化為等式約束，再將約束問題化為無約束問題，為等式約束，再將約束問題化為無約束問題，用線性逼近的方法將非線性規劃問題化為線用線性逼近的方法將非線性規劃問題化為線性規劃問題性規劃問題. 下面先介紹一個簡單的非線性規劃問題下面先

41、介紹一個簡單的非線性規劃問題的例子，其中的一些約束條件是等式，這類非的例子，其中的一些約束條件是等式，這類非線性規劃問題可用拉格朗日方法求解線性規劃問題可用拉格朗日方法求解.2021/6/16542021/6/16552021/6/16562021/6/16572021/6/1658Kuhn-Tucker定理：對于不等式約束非線性最優化 極值問題若 ， 均可微，則其極值點存在的必要條件是：注：更詳細的結論參閱有關書籍注：更詳細的結論參閱有關書籍.()fX()igX 不等式約束非線性規劃模型不等式約束非線性規劃模型2021/6/1659注：1、庫-圖條件是判別有約束極值點的必要條件，并非充分條件

42、。但是對于凸函數、凸集問題也是判別其極值點的充分條件。固此時的局部最優解也必為全局的最優解。2、庫-圖乘子與拉格朗日乘子類似。但拉格朗日乘子的符號不是確定的，可正可負；而庫-恩乘子的符號是確定的，其規律為： a、求 ， 時，則 b、求 ， 時，則 c、求 ， 時，則 d、求 ， 時，則m in ( )f Xm in ( )f X( ) 0ig X ( ) 0ig X ()0ig X ( ) 0ig X 0i0i0i0ima x ( )f Xma x ( )f X2021/6/1660罰函數法罰函數法:約束最優化問題化為無約束最優化問題的一種求解方法約束最優化問題化為無約束最優化問題的一種求解方

43、法2021/6/16612021/6/1662罰函數法的步驟：（等式約束最優化問題罰函數法）罰函數法的步驟：（等式約束最優化問題罰函數法）2021/6/16632021/6/16642021/6/16652021/6/1666罰函數法步驟：（不等式約束最優化問題罰函數法）罰函數法步驟：（不等式約束最優化問題罰函數法）2021/6/16672021/6/16682021/6/1669注：罰函數法更多的詳細改進工作，需參閱相關書籍注：罰函數法更多的詳細改進工作，需參閱相關書籍2021/6/1670 在許多實際問題中，衡量一個方案的好壞標準往往不止一個，例如設計一個導彈，既要射程最遠，又要燃料最省，

44、還要精度最高. 這一類問題統稱為多目標最優化問題或多目標規劃問題. 我們先來看一個投資計劃的例子.2021/6/1671例：例： 投資問題投資問題 某公司在一段時間內有某公司在一段時間內有a(億元億元)的資金可用于建廠投資。的資金可用于建廠投資。若可供選擇的項目記為若可供選擇的項目記為1,2,m。而且一旦對第。而且一旦對第i個項目投個項目投資就用去資就用去ai億元；而這段時間內可得收益億元；而這段時間內可得收益ci億元。問如何億元。問如何確定最佳的投資方案？確定最佳的投資方案？1i0iix對第 個項目投資不對第 個項目投資 最佳投資方案：投資最少，收益最大！最佳投資方案：投資最少，收益最大！2021/6/1672投資最少：投資最少：1121min( ,.,)mniiif x xxa x2121max( ,.,)mniiifx xxc x約束條件為：約束條件為：1(1)0,1,2,.miiiiia xaxxim收益最大：收益最大：2021/6/16732021/6/16742021/6/16752021/6/16762021/6/16772021/6/16782021/6/16792021/6/16802021/6/16812021/6/16822021/6/16832021/6/16842021/6/16852021