JournalonComputing第6章

非線性規(guī)劃CONTENTS01非線性規(guī)劃問題的基本概念03凸函數(shù)與凸規(guī)劃局部極值與全局極值0204無約束非線性規(guī)劃問題05約束非線性規(guī)劃問題PART01非線性規(guī)劃問題的基本概念引例1：某證券公司投資組合預(yù)期收益與風險決策問題小趙是某證券公司的職業(yè)經(jīng)理人，負責證券投資的管理工作，在他進行投資決策時不僅會關(guān)注該項目所能帶來的預(yù)期回報，還會兼顧投資風險，通過給不同的項目分配不同比例的資金來盡可能達到收益與風險的最佳平衡?，F(xiàn)公司準備投入一筆資金來購買市場上的三支股票A，B，C，投資部門對股票歷史收益數(shù)據(jù)進行了調(diào)研與評估獲得了這三支股票的預(yù)期收益投資風險（標準差）以及每兩支股票投資組合的交叉風險（協(xié)方差）。非線性規(guī)劃問題的基本概念已知股票A的預(yù)期收益為21%，投資風險為25%，股票B的預(yù)期收益為30%，投資風險為45%，股票C的預(yù)期收益為8%，投資風險為5%，當投資組合為A與C時，交叉風險為-0.005；當投資組合為A與B時，其交叉風險為0.040；當投資組合為B與C時，交叉風險為0.010。非線性規(guī)劃問題的基本概念

非線性規(guī)劃問題的基本概念

非線性函數(shù)

非線性非線性規(guī)劃問題的基本概念

解：設(shè)投資決策變量為非線性規(guī)劃問題的基本概念

非線性規(guī)劃問題的基本概念另外，最佳的投資方案應(yīng)滿足投資額最小而總收益最大的方案，所以最佳投資決策問題可以歸結(jié)于在總資金以及決策變量（取0或1）的限制條件下，最大化總收益與總投資之比。因此該問題的數(shù)學模型可以表示為：

非線性函數(shù)

非線性規(guī)劃問題的基本概念工地位置123456812610812非線性規(guī)劃問題的基本概念

非線性規(guī)劃問題的基本概念因此該數(shù)學模型可以表達為以下形式：

非線性函數(shù)非線性規(guī)劃問題的基本概念目標函數(shù)或約束條件不同：線性規(guī)劃的目標函數(shù)和約束條件都是其決策變量的線性函數(shù)（一次式）；非線性規(guī)劃的目標函數(shù)或約束條件是其決策變量的非線性函數(shù)（含有非線性成分）。最優(yōu)解范圍不同：如果最優(yōu)解存在，線性規(guī)劃只能存在可行域的邊界上找到；非線性規(guī)劃的最優(yōu)解可能存在于可行域的任意一點。非線性規(guī)劃與線性規(guī)劃問題相比，區(qū)別主要在以下兩個方面：非線性規(guī)劃問題的基本概念非線性規(guī)劃數(shù)學模型一般形式

所以我們也經(jīng)常將非線性規(guī)劃的數(shù)學模型寫做無等式形式（即約束條件中不出現(xiàn)等式）：

非線性規(guī)劃問題的基本概念當非線性規(guī)劃問題只有一個或者兩個自變量時，可以利用圖解法進行求解。非線性規(guī)劃的圖解法就是用幾何作圖的方法分析并求出最優(yōu)解的過程，其大致思路如線性規(guī)劃圖解法相類似，下面用一個例子來討論圖解法的求解過程。

如左圖所示，該非線性規(guī)劃的可行域為一條垂直于水平軸的直線，圓形弧線為目標函數(shù)等值線，當目標函數(shù)等值線與直線相切時，可以得到相切點非線性規(guī)劃問題的基本概念

PART02局部極值與全局極值局部極值與全局極值

局部極小值與嚴格局部極小值：

局部極值與全局極值

全局極小值與嚴格全局極小值：

局部極值與全局極值

局部極小點全局極小點局部極值與全局極值PART03凸函數(shù)與凸規(guī)劃凸函數(shù)與凸規(guī)劃在對學習凸函數(shù)之前，需要了解以下基礎(chǔ)知識

凸函數(shù)與凸規(guī)劃

凸函數(shù)與凸規(guī)劃凸函數(shù)的定義

凸函數(shù)與凸規(guī)劃

幾何意義：凸函數(shù)圖形上的任意兩點的連線都在這個圖形的上方，就是向下凸的。凹函數(shù)則相反。凸函數(shù)與凸規(guī)劃例6.4

請判定以下函數(shù)是否為凸函數(shù)。

根據(jù)凸函數(shù)的定義需要判斷以下表達式的正負：

整理上式可得

凸函數(shù)與凸規(guī)劃凸函數(shù)的性質(zhì)

凸函數(shù)與凸規(guī)劃現(xiàn)對定理6.2進行證明：

將以上兩式相加得：

凸函數(shù)與凸規(guī)劃

凸函數(shù)與凸規(guī)劃凸函數(shù)的判定在判定一個函數(shù)是否為凸函數(shù)時，可以根據(jù)其定義進行判斷，這種方法較為直觀且適用于各種類型的函數(shù)，但對于較為復(fù)雜的函數(shù)使用這種方法往往需要深入的數(shù)學分析，判定過程較為繁瑣。如果某一函數(shù)是可導(dǎo)函數(shù)時，則可以利用函數(shù)的導(dǎo)數(shù)信息進行判斷。凸函數(shù)與凸規(guī)劃泰勒公式（TaylorFormula）

其中

凸函數(shù)與凸規(guī)劃(1)一階條件

凸函數(shù)與凸規(guī)劃證明：首先證明其必要性：

將上式變形為

由泰勒公式可知：

將其代入上式得：

凸函數(shù)與凸規(guī)劃其次證明其充分性：

凸函數(shù)與凸規(guī)劃

凸函數(shù)的定義式實質(zhì)上是說明凸函數(shù)上兩點之間的線性插值不低于兩點之間函數(shù)的值，而該定理說明函數(shù)上某點導(dǎo)數(shù)的線性近似不高于這個點的函數(shù)值。凸函數(shù)與凸規(guī)劃凸函數(shù)的判定二階條件

凸函數(shù)與凸規(guī)劃

凸函數(shù)與凸規(guī)劃

凸函數(shù)的根本重要性就在于定理6.6的這個基本性質(zhì)。凸函數(shù)與凸規(guī)劃例6.5：請判斷以下二次函數(shù)的凹凸性解：本題可利用凸函數(shù)的二階條件進行判定。首先求得該函數(shù)的海賽矩陣如下：

凸函數(shù)與凸規(guī)劃凸規(guī)劃對于非線性規(guī)劃式：定義6.7若某一非線性規(guī)劃的目標函數(shù)為凸函數(shù)，可行域為凸集，則稱該非線性規(guī)劃為凸規(guī)劃，即

凸函數(shù)與凸規(guī)劃

凸函數(shù)與凸規(guī)劃凸規(guī)劃的性質(zhì)可行解集為凸集。最優(yōu)解集為凸集（假定最優(yōu)解存在）。任何局部最優(yōu)解也是其全局最優(yōu)解。若目標函數(shù)為嚴格凸函數(shù)，且最優(yōu)解存在，則其最優(yōu)解必唯一。凸規(guī)劃是一類比較簡單且具有重要意義的非線性規(guī)劃，如果某個問題是凸規(guī)劃問題或能將其描述為凸規(guī)劃問題將會大有裨益。凸函數(shù)與凸規(guī)劃例6.6：請判定以下非線性規(guī)劃問題是否是凸規(guī)劃問題。

凸函數(shù)與凸規(guī)劃例6.7：請判定以下非線性規(guī)劃問題是否是凸規(guī)劃問題

凸函數(shù)與凸規(guī)劃

例6.8請判定以下非線性規(guī)劃問題是否是凸規(guī)劃問題凸函數(shù)與凸規(guī)劃

可判定該問題的可行域為凸集，該問題是凸規(guī)劃問題。PART04無約束非線性規(guī)劃問題無約束非線性規(guī)劃問題本節(jié)共分為以下幾個部分1.無約束問題極值點存在的條件2.下降迭代算法一維搜索與0.618法最速下降法牛頓法PART4.1無約束問題極值點存在的條件無約束非線性規(guī)劃問題

本節(jié)考慮如下無約束非線性規(guī)劃問題：無約束問題極值點存在的條件無約束非線性規(guī)劃問題

無約束問題極值點存在的條件無約束非線性規(guī)劃問題

無約束問題極值點存在的條件無約束非線性規(guī)劃問題無約束問題極值點存在的條件無約束非線性規(guī)劃問題

無約束問題極值點存在的條件無約束非線性規(guī)劃問題

解：該問題的求解通?？梢苑譃閮刹剑紫仁乔蟪瞿繕撕瘮?shù)的所有駐點，然后再分別判定其是否為極值點。先求得該目標函數(shù)的梯度為：

用定理6.8來判斷兩個駐點是否為極值點，首先求得該目標函數(shù)的海賽矩陣如下：

無約束問題極值點存在的條件無約束非線性規(guī)劃問題

將這兩個駐點代入海賽矩陣中，得：

無約束問題極值點存在的條件無約束非線性規(guī)劃問題

無約束問題極值點存在的條件無約束非線性規(guī)劃問題

解：先求得該目標函數(shù)的梯度為：

用定理6.8來判斷兩個駐點是否為極值點，首先求得該目標函數(shù)的海賽矩陣如下：

無約束問題極值點存在的條件無約束非線性規(guī)劃問題

將這兩個駐點代入海賽矩陣中，得：

無約束問題極值點存在的條件無約束非線性規(guī)劃問題例6.10請求解以下無約束問題。

無約束問題極值點存在的條件PART4.2下降迭代算法無約束非線性規(guī)劃問題

迭代法可大致分成兩類：一類是解析法，在迭代過程中需要用到函數(shù)的一階導(dǎo)數(shù)或二階導(dǎo)數(shù)等解析性質(zhì)；另一類是直接法，在迭代過程中僅需用到函數(shù)值，而不要求函數(shù)的解析性質(zhì)。無約束非線性規(guī)劃問題

無約束非線性規(guī)劃問題常用終止準則判斷類型常用終止準則說明根據(jù)兩次連續(xù)迭代結(jié)果的絕對誤差進行判斷根據(jù)兩次連續(xù)迭代結(jié)果的相對誤差進行判斷根據(jù)目標函數(shù)梯度的模進行判斷

無約束非線性規(guī)劃問題

無約束非線性規(guī)劃問題由此可歸納下降迭代算法的基本步驟如下：

無約束非線性規(guī)劃問題

(1)如何確定某點處的搜索方向？(2)如何基于搜索方向確定搜索步長？PART4.2.1一維搜索與0.618法無約束非線性規(guī)劃問題

一維搜索無約束非線性規(guī)劃問題

一維搜索無約束非線性規(guī)劃問題要說明的是，當函數(shù)比較復(fù)雜時基本不可能在有限步內(nèi)求得以下方程的精確解，只能得到滿足一定精度的近似解。所以下面介紹一種直接搜索方法—0.618法，用于確定函數(shù)的極小點。該方法沒有利用函數(shù)的導(dǎo)數(shù)信息，所以對于一些非光滑函數(shù)或?qū)?shù)表達式復(fù)雜的函數(shù)也同樣適用。

一維搜索無約束非線性規(guī)劃問題在介紹該方法之前，需要先了解搜索區(qū)間和單峰函數(shù)的相關(guān)概念。

1.搜索區(qū)間與單峰函數(shù)一維搜索無約束非線性規(guī)劃問題

一維搜索無約束非線性規(guī)劃問題

一維搜索無約束非線性規(guī)劃問題

一維搜索無約束非線性規(guī)劃問題下面介紹一種直接搜索方法—0.618法，用于確定函數(shù)的極小點。

0.618法無約束非線性規(guī)劃問題該方法的主要步驟如下：

0.618法無約束非線性規(guī)劃問題

所以在每次計算左右試探點的函數(shù)值時，實際上只需計算一個試探點處的函數(shù)值即可。0.618法無約束非線性規(guī)劃問題

0.618法無約束非線性規(guī)劃問題例6.11某公司在年初需要制定對生產(chǎn)部門這一年度的投資計劃，已知根據(jù)財務(wù)部門對于歷史生產(chǎn)數(shù)據(jù)的分析與測算，發(fā)現(xiàn)如果在上一年度經(jīng)費的基礎(chǔ)上削減經(jīng)費節(jié)約開支，或者增加經(jīng)費以提升效率都有可能會降低該部門的生產(chǎn)成本，并給出了總生產(chǎn)成本變化量（單位：10萬元）與經(jīng)費調(diào)整量（單位：1萬元）之間的關(guān)系表達式如下：

0.618法無約束非線性規(guī)劃問題

123450.6068-0.23866

0.618法PART4.2.2最速下降法無約束非線性規(guī)劃問題之前內(nèi)容已經(jīng)介紹了基于搜索方向求最優(yōu)步長的方法，而如何選擇搜索方向才是求解無約束問題的核心問題，搜索方向的不同選擇，形成不同的求解算法。接下來我們重點介紹解析法中的最速下降法與牛頓法這兩種經(jīng)典的下降迭代算法。無約束非線性規(guī)劃問題的解法最速下降法無約束非線性規(guī)劃問題最速下降法（SteepestDescentMethod），也稱作梯度下降法，是一種用于求解無約束優(yōu)化問題的迭代算法，它的迭代過程簡單，易于理解，且具有較強的啟發(fā)性，許多求解無約束問題的現(xiàn)代方法都是在這種方法基礎(chǔ)上或在其啟發(fā)下建立起來的，所以本節(jié)首先來介紹這個算法。無約束非線性規(guī)劃問題的解法—最速下降法考慮無約束規(guī)劃問題：

最速下降法無約束非線性規(guī)劃問題

最速下降法無約束非線性規(guī)劃問題

最速下降法無約束非線性規(guī)劃問題這種方法也稱為最速下降法，其計算步驟如下：

最速下降法

技術(shù)部門利用曲線擬合方法得到了運輸成本關(guān)于位置坐標的近似表達式如下，請用最速下降法求解該問題：無約束非線性規(guī)劃問題最速下降法

解：目標函數(shù)在初始點的梯度與海賽矩陣分別為：

可知該海賽矩陣為正定矩陣，所以目標函數(shù)為凸函數(shù)，該非線性規(guī)劃為凸規(guī)劃。下降迭代法的求解過程如下表：無約束非線性規(guī)劃問題最速下降法PART4.2.3牛頓法無約束非線性規(guī)劃問題牛頓法（Newton’sMethod）也是一種用于求解無約束優(yōu)化問題的迭代算法，不同于最速下降法中利用當前點的負梯度方向作為其搜索方向，牛頓法則是通過使用二階泰勒展開式來逼近（擬合）原目標函數(shù)，并利用泰勒展開式中的一階和二階導(dǎo)數(shù)信息來確定搜索方向，從而較為快速地找到原目標函數(shù)的極值點。無約束非線性規(guī)劃問題的解法-牛頓法考慮無約束規(guī)劃問題：

牛頓法無約束非線性規(guī)劃問題

牛頓法無約束非線性規(guī)劃問題

為了計算方便，可以將上式表示為：

牛頓法無約束非線性規(guī)劃問題

牛頓法將最速下降法與牛頓法這兩種方法進行對比，可知在求解以上無約束問題時，用牛頓法求解會更加簡單與高效。

無約束非線性規(guī)劃問題牛頓法利用牛頓法求解最優(yōu)化問題的優(yōu)點是收斂速度快，此外，由于利用了目標函數(shù)的二階導(dǎo)數(shù)信息，所以選擇的搜索方向會更準確，也能夠更快速地接近極小點。然而，牛頓法也存在一些問題。首先，計算二階導(dǎo)數(shù)（海賽矩陣）可能帶來較大的計算量或不可行。此外，初始點的選擇對結(jié)果影響較大，當初始點選擇不當或目標函數(shù)不具備二次可導(dǎo)性時，牛頓法可能會出現(xiàn)發(fā)散或收斂到局部最優(yōu)解的問題，所以還要有其他相關(guān)的改進算法，如擬牛頓法、共軛梯度法等，這些改進算法的穩(wěn)定性和收斂性能更高，在實際應(yīng)用中也得到了更為廣泛的應(yīng)用。

最速下降法牛頓法搜索方向計算量僅需計算一階導(dǎo)數(shù)，相對較小需要計算海賽矩陣，相對較大收斂速度較慢較快無約束非線性規(guī)劃問題牛頓法PART05約束非線性規(guī)劃問題約束非線性規(guī)劃問題上一節(jié)我們介紹了無約束非線性規(guī)劃的極值問題及其求解方法，該類問題沒有約束條件，只需要根據(jù)目標函數(shù)的自身性質(zhì)進行分析，因此可以在全局范圍內(nèi)搜索最優(yōu)解，自由度較高。而本章我們將要進一步介紹約束非線性規(guī)劃問題，因為在日常實踐與研究中大多遇到的規(guī)劃問題的變量都會受到一定條件的限制，如投資組合問題的資金約束，生產(chǎn)計劃問題的生產(chǎn)時間與物料約束等。一般來說，求解約束問題要比求解無約束問題困難得多，為了簡化優(yōu)化工作，可采用以下方法：將約束問題化為無約束問題；將非線性規(guī)劃問題化為線性規(guī)劃問題，以及能將復(fù)雜問題變換為較簡單問題的其它方法，這也是我們本章的重點。約束非線性規(guī)劃問題本節(jié)考慮以下約束非線性規(guī)劃問題

PART5.1等式約束非線性規(guī)劃問題約束非線性規(guī)劃問題根據(jù)約束條件類型，我們首先介紹只具有等式約束的非線性規(guī)劃這種特殊情形。

（6-1）等式約束非線性規(guī)劃問題約束非線性規(guī)劃問題

（6-2）等式約束非線性規(guī)劃問題約束非線性規(guī)劃問題

需要說明的是，在非線性規(guī)劃問題中，拉格朗日乘子也具有對應(yīng)的經(jīng)濟含義，我們接下來利用下面這個例子進行簡要說明。等式約束非線性規(guī)劃問題約束非線性規(guī)劃問題

解：由題意可建立該問題的數(shù)學模型如下：

（6-3）等式約束非線性規(guī)劃問題約束非線性規(guī)劃問題

（6-4）等式約束非線性規(guī)劃問題約束非線性規(guī)劃問題即：

根據(jù)復(fù)合函數(shù)鏈式求導(dǎo)法則，有：

（6-5）等式約束非線性規(guī)劃問題約束非線性規(guī)劃問題

所以式（6-5）可以表示為：

此時，拉格朗日乘子表示資源約束對于目標函數(shù)值的邊際貢獻，為產(chǎn)量的邊際生產(chǎn)成本，即在第二章所介紹的影子價格。等式約束非線性規(guī)劃問題約束非線性規(guī)劃問題解：首先建立該問題的數(shù)學模型如下：

等式約束非線性規(guī)劃問題約束非線性規(guī)劃問題令拉格朗日函數(shù)為：

可得該問題的拉格朗日條件為：

另外，拉格朗日函數(shù)的海賽矩陣為：等式約束非線性規(guī)劃問題約束非線性規(guī)劃問題課堂練習：請求解以下非線性規(guī)劃問題：

等式約束非線性規(guī)劃問題

約束非線性規(guī)劃問題令拉格朗日函數(shù)為：

可得該問題的拉格朗日條件為：

另外，拉格朗日函數(shù)的海賽矩陣為：等式約束非線性規(guī)劃問題PART5.2不等式約束非線性規(guī)劃問題約束非線性規(guī)劃問題考慮具有不等式約束的非線性規(guī)劃問題，即：

一類是嚴格不等式約束，即：

（6-6）（6-7）（6-8）不等式約束非線性規(guī)劃問題約束非線性規(guī)劃問題

不等式約束非線性規(guī)劃問題約束非線性規(guī)劃問題1.可行方向與下降方向

（1）定義6.10（下降方向）

不等式約束非線性規(guī)劃問題約束非線性規(guī)劃問題2.定義6.11（可行方向）

由泰勒公式，有：

（6-9）不等式約束非線性規(guī)劃問題約束非線性規(guī)劃問題

（6-10）不等式約束非線性規(guī)劃問題約束非線性規(guī)劃問題

不等式約束非線性規(guī)劃問題約束非線性規(guī)劃問題

不等式約束非線性規(guī)劃問題約束非線性規(guī)劃問題2.庫恩-塔克條件

不等式約束非線性規(guī)劃問題約束非線性規(guī)劃問題

不等式約束非線性規(guī)劃問題約束非線性規(guī)劃問題

不等式約