6/26/2025第5章非線性規(guī)劃1CONTENTS目錄6/26/20255.1

非線性規(guī)劃問題的解5.2

凸函數(shù)和凸規(guī)劃5.4下降迭代算法5.4

一維搜索5.5

無約束極值問題的求解算法5.6

約束極值問題的最優(yōu)性條件5.7約束極值問題的求解算法5.8應(yīng)用舉例25.1非線性規(guī)劃問題的解例5.1曲線擬合問題

6/26/20255.1.1非線性規(guī)劃問題舉例

(1)46/26/20255.1.1非線性規(guī)劃問題舉例解:按題意，根據(jù)最小二乘原理，有

5例5.3構(gòu)件設(shè)計(jì)問題

6/26/20255.1.1非線性規(guī)劃問題舉例66/26/20255.1.1非線性規(guī)劃問題舉例

76/26/20255.1.2非線性規(guī)劃數(shù)學(xué)模型非線性規(guī)劃數(shù)學(xué)模型的一般形式是：—可行域

—特別當(dāng)R=En,稱為無約束優(yōu)化問題85.2非線性規(guī)劃問題的解6/26/20255.2.1解（極值點(diǎn)）的定義

106/26/20255.2.1解（極值點(diǎn)）的定義

116/26/20255.2.2多元函數(shù)極值點(diǎn)的存在條件

利用可行方向的定義，下面給出局部極小點(diǎn)所滿足的條件。126/26/20255.2.2多元函數(shù)極值點(diǎn)的存在條件

136/26/20255.2.2多元函數(shù)極值點(diǎn)的存在條件

(b)局部極大點(diǎn)(b)局部極大點(diǎn)(c)鞍點(diǎn)

014146/26/20255.2.2多元函數(shù)極值點(diǎn)的存在條件

156/26/20255.2.2多元函數(shù)極值點(diǎn)的存在條件

16例5.3

求下面函數(shù)的局部極小點(diǎn)：5.3凸函數(shù)和凸規(guī)劃6/26/20255.3.1凸函數(shù)的定義

若將上述式中的不等號反向，那么就得到凹函數(shù)（ConcaveFunction）和嚴(yán)格凹函數(shù)（StrictConcaveFunction）的定義。186/26/20255.3.1凸函數(shù)的定義196/26/20255.3.2凸函數(shù)的性質(zhì)

206/26/20255.3.2凸函數(shù)的性質(zhì)

216/26/20255.3.3凸函數(shù)的判定條件

要判定一個函數(shù)是否是凸函數(shù)，可以直接根據(jù)5.3.1節(jié)的定義。而如果函數(shù)

是可微的，則還有下面兩個性質(zhì)。226/26/20255.3.4凸規(guī)劃

性質(zhì)5.7凸規(guī)劃的最優(yōu)解具有下述特殊性質(zhì)：（1）如果最優(yōu)解存在，那么最優(yōu)解集為凸集；（2）任何局部最優(yōu)解也就是全局最優(yōu)解；（3）如果目標(biāo)函數(shù)為嚴(yán)格凸函數(shù)且最優(yōu)解存在，

那么最優(yōu)解唯一。235.4下降迭代算法6/26/20255.4.1下降迭代算法

256/26/20255.4.2下降迭代算法的步驟

265.5一維搜索6/26/2025黃金分割法（0.618法）

TheGoldenSectionSearchMethod基本思想：對稱取點(diǎn)，等比例的縮小區(qū)間，除第一次外，每次只需計(jì)算一次函數(shù)值，可使區(qū)間縮小。b0a0t11t12b1a1f(t11)<f(t12)t22t215.5.1斐波那契法和黃金分割法286/26/20255.5.1斐波那契法和黃金分割法特點(diǎn)：具有相同的區(qū)間縮短率0.618；精度不如Fobonacci分?jǐn)?shù)法；適用于不可微、不連續(xù)函數(shù)，可以先用“成功-失敗”法搜索到一個包含極小點(diǎn)的區(qū)間。296/26/2025斐波那契法

TheFibonacciSearchMethod問題：如何選擇實(shí)驗(yàn)點(diǎn)，計(jì)算n次函數(shù)值能得到多大的區(qū)間縮短率？換句話說，計(jì)算n次函數(shù)值能將多大的區(qū)間縮短到1。答案：若對稱取點(diǎn)，利用上次已有的實(shí)驗(yàn)點(diǎn)的函數(shù)值，計(jì)算n次函數(shù)值可獲得1/Fn區(qū)間縮短率。5.5.1斐波那契法和黃金分割法306/26/20255.5.1斐波那契法和黃金分割法Fibonacci數(shù)列(FibonacciSequence)F0=1,F1=1,F2=2,F3=3,F4=5,……Fk=Fk-1+Fk-2特點(diǎn)：需要預(yù)先確定迭代次數(shù)n;在計(jì)算n次函數(shù)值情況下，該方法獲得最大的區(qū)間縮短率，精度最高；適用于不可微、不連續(xù)函數(shù)。316/26/20255.5.2牛頓法（切線法）基本思想：適合二階連續(xù)可微的函數(shù)，求導(dǎo)數(shù)為0的方程根。特點(diǎn)適用于二階可微函數(shù)；最快的收斂速度，二階收斂速度；初始點(diǎn)要求接近極小點(diǎn)；可與“成功-失敗”法聯(lián)合使用。326/26/2025

5.5.3函數(shù)逼近法基本思想：在極小點(diǎn)附近以插值多項(xiàng)式來逼近目標(biāo)函數(shù)的一種方法。事實(shí)上，上面的牛頓法就是在附近用一階Taylor展式來近似目標(biāo)函數(shù)的。函數(shù)逼近法（插值法）335.6無約束極值問題的求解算法6/26/2025最速下降法（梯度法）

TheSteepestdescentmethod（TheGradientMethod））基本思想：以負(fù)梯度方向作為尋優(yōu)方向特點(diǎn)：迭代過程簡單，存儲量少，計(jì)算量小；即使是正定二次函數(shù)也不能有限步收斂；相鄰兩次尋優(yōu)方向是垂直的;尋優(yōu)路線呈鋸齒狀（Zig-Zag)，在極小點(diǎn)附近收斂緩慢;5.6.1梯度法356/26/20255.6.1梯度法

36X0P0P1X1X2P2P3X3X*X46/26/20255.6.1梯度法376/26/20255.6.2牛頓法牛頓法（Newton’smethod)

在搜索方向上比梯度法有所改進(jìn)。利用了目標(biāo)函數(shù)在搜索點(diǎn)的梯度（一階導(dǎo)數(shù)）利用了目標(biāo)函數(shù)的二階導(dǎo)數(shù)不但考慮了函數(shù)的梯度，還考慮了梯度的變化趨勢，收斂速度快。缺點(diǎn)：計(jì)算復(fù)雜，每步迭代都需要計(jì)算目標(biāo)函數(shù)的二階偏導(dǎo)數(shù)（Hessian矩陣）和矩陣的逆。386/26/20255.6.2牛頓法

396/26/20255.6.3擬牛頓法擬牛頓法（Quasi-Newtonmethod）（變尺度法（VariableMetricMethod)）

406/26/20255.6.3擬牛頓法41算法5.3（擬牛頓法）Step1.給定初始點(diǎn)

，初始矩陣

Step2.計(jì)算梯度

，檢驗(yàn)是否滿足收斂性準(zhǔn)則：

若滿足則停止迭代，得到

；否則，進(jìn)入Step3。

Step3.解

得擬牛頓方向

(或計(jì)算

)。

Step4.進(jìn)行一維搜索，即求解單變量極值問題，

得到步長

，并令Step5.校正

產(chǎn)生

(或校正

產(chǎn)生

)，使得擬牛頓條件成立。Step6.令

，轉(zhuǎn)到Step2。

6/26/20255.6.2共軛梯度法共軛梯度法共軛方向的概念是在研究求解目標(biāo)函數(shù)為二次函數(shù)的問題時而提出的?；诠曹椃较虻囊环N算法

最多進(jìn)行n次一維搜索便可求得極小點(diǎn)也能用于求解可微的非二次函數(shù)的無約束極值問題426/26/20255.6.2共軛方向436/26/20255.6.2共軛方向446/26/20255.6.3共軛梯度法45算法5.4（共軛梯度法）6/26/20255.6.3共軛梯度法466/26/20255.6.3非線性共軛梯度法476/26/20255.6.3非線性共軛梯度法486/26/20255.6.3非線性共軛梯度法495.7約束極值問題的最優(yōu)性條件6/26/20255.7.1起作用約束

516/26/20255.7.2可行方向和可行下降方向

526/26/20255.7.2可行方向和可行下降方向

536/26/20255.7.3庫恩-塔克條件庫恩-塔克（Kuhn-Tucker）條件，簡稱K-T條件，是非線性規(guī)劃領(lǐng)域中最重要的理論成果之一，是由H.W.Kuhn和A.W.Tucker在1951年發(fā)表的關(guān)于最優(yōu)性條件的論文中提出的。K-T條件是確定某點(diǎn)為局部最優(yōu)解的一階必要條件，只要是最優(yōu)點(diǎn)（同時是正則點(diǎn)）就必須滿足這個條件。但一般來說，它不是充分條件，即滿足這個條件的點(diǎn)不一定是最優(yōu)點(diǎn)。不過對于凸規(guī)劃來說，庫恩-塔克條件既是必要條件，也是充分條件。545.7約束極值問題的求解6/26/20255.7.1外點(diǎn)法和內(nèi)點(diǎn)法

外點(diǎn)法（罰函數(shù)法）

外點(diǎn)法和內(nèi)點(diǎn)法都是通過構(gòu)造某種罰函數(shù)，將有約束的優(yōu)化問題轉(zhuǎn)換為一系列無約束的優(yōu)化問題來進(jìn)行求解，因此稱之為序列無約束極小化技術(shù)（SequentialUnconstrainedMinimizationTechnique,SUMT）。極限意義下，無約束優(yōu)化問題的解將最終收斂到有約束優(yōu)化問題的解。566/26/20255.7.1外點(diǎn)法和內(nèi)點(diǎn)法

內(nèi)點(diǎn)法（障礙函數(shù)法）

和外點(diǎn)法從可行域外部逐漸靠近最優(yōu)解不同，內(nèi)點(diǎn)法的主要思想是：在可行域的邊界上筑起一道很高的“圍墻”，當(dāng)?shù)c(diǎn)從可行域內(nèi)部靠近邊界時，目標(biāo)函數(shù)陡然增大，以示懲罰，阻止迭代點(diǎn)穿越邊界，因此搜索過程始終在可行域內(nèi)，每一個迭代點(diǎn)都是嚴(yán)格可行的。顯然，內(nèi)點(diǎn)法要求優(yōu)化問題的可行域內(nèi)部非空，因而其不適用于等式約束的優(yōu)化問題。576/26/20255.7.2增廣拉格朗日乘子法為克服這個缺點(diǎn)，Hestenes和Powell于1969年首先提出了針對等式約束優(yōu)化問題的乘子法。Rockafellar于1973年將其推廣到不等式約束的優(yōu)化問題。本節(jié)將介紹在罰函數(shù)基礎(chǔ)上提出的增廣拉格朗日乘子法（又稱“乘子罰函數(shù)法”）。

585.8應(yīng)用舉例6/26/20255.8.1投資組合問題

由于存在各種風(fēng)險和不確定性因素，人們投資時的收益往往是不確定的，因此收益率是一個隨機(jī)變量。當(dāng)進(jìn)行投資決策時，除了要考慮收益的期望值外，還應(yīng)當(dāng)考慮風(fēng)險控制。馬科維茲（Markowitz）投資組合模型是現(xiàn)代投資組合理論的基礎(chǔ)之一，其核心思想就是通過將不同資產(chǎn)的預(yù)期回報(bào)率、風(fēng)險以及它們之間的相關(guān)性納入考慮，構(gòu)建出一系列優(yōu)化的投資組合。下面給出投資組合問題的具體描述，我們將把投資各資產(chǎn)的比例看作決策變量并引入收益率、風(fēng)險等約束，以及考慮不同資產(chǎn)之間的非線性因素來建立數(shù)學(xué)模型。606/26/20255.8.1投資組合問題61

6/26/20255.8.1投資組合問題62

6/26/20255.8.1投資組合問題63

6/26/20255.8.2報(bào)童問題

報(bào)童問題（NewsvendorProblem）是一個經(jīng)典的庫存管理模型，用于分析庫存管理決策對經(jīng)濟(jì)利益的影響，于1956年首次被提出。在該問題中，報(bào)童每天需要決定從報(bào)社訂購多少份報(bào)紙。如果訂購的報(bào)紙過多，那么在一天結(jié)束時他將剩下許多沒有價值的報(bào)紙，造成過量損失；如果訂購過少，報(bào)童則將失去潛在的客戶需求，導(dǎo)致短缺損失。由于需求難以提前準(zhǔn)確預(yù)測，因此報(bào)童必須綜合權(quán)衡這兩種損失，訂購適量的報(bào)紙數(shù)。報(bào)童問題的目標(biāo)是通過尋找產(chǎn)品最佳訂貨量，來使期望利潤最大或期望損失最小。646/26/20255.8.2報(bào)童問題

656/26/20255.8.3矩陣補(bǔ)全問題推薦系統(tǒng)是一種利用大數(shù)據(jù)和機(jī)器學(xué)習(xí)技術(shù)來預(yù)測用戶可能感興趣的商品或內(nèi)容，并將其自動推薦給用戶的系統(tǒng)。它通過采集和分析用戶的歷史行為、偏好、特征等數(shù)據(jù)，為用戶提供個性化的推薦服務(wù)，常見的應(yīng)用領(lǐng)域包括電商、流媒體、社交、新聞、旅游、在線教育等各類平臺。在推薦系統(tǒng)中，用戶評分可以提供有關(guān)用戶對物品偏好的有用信息，但由于用戶可能只對部分物品進(jìn)行了評分，而其他物品的評分是缺失的，因此在很多情況下，推薦系統(tǒng)無法獲得完整的用戶——物品評分矩陣。在數(shù)學(xué)上，推薦系統(tǒng)的核心問題之一就是矩陣補(bǔ)全（MatrixCompletion）問題，也就是要基于部分評分，來預(yù)測未評分物品的評分，從而進(jìn)行個性化推薦。666/26/20255.8.3矩陣補(bǔ)全問題67例如，這里可以構(gòu)建一個矩陣，矩陣的每行代表一個用戶，每列代表一部電影，如表5.2所示。其中填上數(shù)字的地方就是有用戶評分?jǐn)?shù)據(jù)的，