JournalonComputing第6章

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

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

非線性函數(shù)

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

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

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

非線性函數(shù)

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

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

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

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

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

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

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

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

局部極值與全局極值

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

局部極值與全局極值

局部極小點全局極小點局部極值與全局極值PART03凸函數(shù)與凸規(guī)劃凸函數(shù)與凸規(guī)劃在對學(xué)習(xí)凸函數(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ù)學(xué)分析，判定過程較為繁瑣。如果某一函數(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ī)劃的目標(biāo)函數(shù)為凸函數(shù)，可行域為凸集，則稱該非線性規(guī)劃為凸規(guī)劃，即

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

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