清華大學(xué)《運籌學(xué)》第四章

第四章非線性數(shù)規(guī)劃

Nonlinear

Programming§1問題的提出

[eg.1]某單位擬建一排廠房，廠房建筑平面如圖所示。由于資金及材料的限制，圍墻及隔墻的總長度不能超過80米。為使建筑面積最大，應(yīng)如何選擇長寬尺寸？分析：設(shè)長為米，寬為米，則有

f(x)為非線性函數(shù)1清華大學(xué)《運籌學(xué)》第四章共49頁，您現(xiàn)在瀏覽的是第1頁!例2設(shè)某物理過程具有如下規(guī)律用試驗法?，F(xiàn)要確定參數(shù)使所得試驗點構(gòu)成的曲線與理論曲線誤差平方和為最小，且滿足2清華大學(xué)《運籌學(xué)》第四章共49頁，您現(xiàn)在瀏覽的是第2頁!非線性規(guī)劃：目標(biāo)函數(shù)或（和）約束條件為非線性函數(shù)的規(guī)劃。分析：

f(x)為非線性函數(shù)，求最小。3清華大學(xué)《運籌學(xué)》第四章共49頁，您現(xiàn)在瀏覽的是第3頁!§2基本概念2.1非線性規(guī)劃的數(shù)學(xué)模型數(shù)學(xué)模型的一般描述4清華大學(xué)《運籌學(xué)》第四章共49頁，您現(xiàn)在瀏覽的是第4頁!2.2非線性規(guī)劃的圖示例1求解如下非線性規(guī)劃問題o22665清華大學(xué)《運籌學(xué)》第四章共49頁，您現(xiàn)在瀏覽的是第5頁!2.3極值問題極值存在的條件6清華大學(xué)《運籌學(xué)》第四章共49頁，您現(xiàn)在瀏覽的是第6頁!7清華大學(xué)《運籌學(xué)》第四章共49頁，您現(xiàn)在瀏覽的是第7頁!8清華大學(xué)《運籌學(xué)》第四章共49頁，您現(xiàn)在瀏覽的是第8頁!2.4凸函熟與凸規(guī)劃1、凸函熟與凹函熟9清華大學(xué)《運籌學(xué)》第四章共49頁，您現(xiàn)在瀏覽的是第9頁!2、凸性的判別10清華大學(xué)《運籌學(xué)》第四章共49頁，您現(xiàn)在瀏覽的是第10頁!3.凸函數(shù)的極值對于定義在凸集上的凸函數(shù)，其極小點就是最小點，極小值就是最小值。4.凸規(guī)劃下述問題為凸規(guī)劃.11清華大學(xué)《運籌學(xué)》第四章共49頁，您現(xiàn)在瀏覽的是第11頁!例如下非線性規(guī)劃是否為凸規(guī)劃：12清華大學(xué)《運籌學(xué)》第四章共49頁，您現(xiàn)在瀏覽的是第12頁!如圖所示，該問題最優(yōu)解（最小點）在C點取得。13清華大學(xué)《運籌學(xué)》第四章共49頁，您現(xiàn)在瀏覽的是第13頁!幾種終止迭代的準(zhǔn)則：14清華大學(xué)《運籌學(xué)》第四章共49頁，您現(xiàn)在瀏覽的是第14頁!梯度法1.基本原理15清華大學(xué)《運籌學(xué)》第四章共49頁，您現(xiàn)在瀏覽的是第15頁!2、求解步驟(1)16清華大學(xué)《運籌學(xué)》第四章共49頁，您現(xiàn)在瀏覽的是第16頁!例17清華大學(xué)《運籌學(xué)》第四章共49頁，您現(xiàn)在瀏覽的是第17頁!

于是18清華大學(xué)《運籌學(xué)》第四章共49頁，您現(xiàn)在瀏覽的是第18頁!§4有約束的非線性規(guī)劃有約束非線性規(guī)劃數(shù)學(xué)描述19清華大學(xué)《運籌學(xué)》第四章共49頁，您現(xiàn)在瀏覽的是第19頁!對于20清華大學(xué)《運籌學(xué)》第四章共49頁，您現(xiàn)在瀏覽的是第20頁!式中21清華大學(xué)《運籌學(xué)》第四章共49頁，您現(xiàn)在瀏覽的是第21頁!引入乘子22清華大學(xué)《運籌學(xué)》第四章共49頁，您現(xiàn)在瀏覽的是第22頁!4.2二次規(guī)劃二次規(guī)劃的數(shù)學(xué)描述23清華大學(xué)《運籌學(xué)》第四章共49頁，您現(xiàn)在瀏覽的是第23頁!引拉格朗日乘子24清華大學(xué)《運籌學(xué)》第四章共49頁，您現(xiàn)在瀏覽的是第24頁!取25清華大學(xué)《運籌學(xué)》第四章共49頁，您現(xiàn)在瀏覽的是第25頁!以26清華大學(xué)《運籌學(xué)》第四章共49頁，您現(xiàn)在瀏覽的是第26頁!或27清華大學(xué)《運籌學(xué)》第四章共49頁，您現(xiàn)在瀏覽的是第27頁!分析：

非線性規(guī)劃的最優(yōu)解可能在可行域的任一點達(dá)到。28清華大學(xué)《運籌學(xué)》第四章共49頁，您現(xiàn)在瀏覽的是第28頁!29清華大學(xué)《運籌學(xué)》第四章共49頁，您現(xiàn)在瀏覽的是第29頁!30清華大學(xué)《運籌學(xué)》第四章共49頁，您現(xiàn)在瀏覽的是第30頁!31清華大學(xué)《運籌學(xué)》第四章共49頁，您現(xiàn)在瀏覽的是第31頁!

函數(shù)f(x)圖示32清華大學(xué)《運籌學(xué)》第四章共49頁，您現(xiàn)在瀏覽的是第32頁!例333清華大學(xué)《運籌學(xué)》第四章共49頁，您現(xiàn)在瀏覽的是第33頁!凸規(guī)劃的局部最優(yōu)解為全局最優(yōu)解，當(dāng)凸規(guī)劃的目標(biāo)函數(shù)為嚴(yán)格凸函數(shù)時，若存在最優(yōu)解，則最優(yōu)解必定唯一。凸規(guī)劃是一類比較簡單而又具有重要理論意義的非線性規(guī)劃。34清華大學(xué)《運籌學(xué)》第四章共49頁，您現(xiàn)在瀏覽的是第34頁!

的海賽矩陣：所以，該問題為凸規(guī)劃。35清華大學(xué)《運籌學(xué)》第四章共49頁，您現(xiàn)在瀏覽的是第35頁!5.下降迭代算法下降迭代算法36清華大學(xué)《運籌學(xué)》第四章共49頁，您現(xiàn)在瀏覽的是第36頁!§3無約束非線性規(guī)劃的解法無約束非線性規(guī)劃的數(shù)學(xué)描述解法分類：解析法：用函數(shù)的解析性（一階、二階導(dǎo)數(shù)）。梯度法、共扼梯度法、變尺度法等。直接法：用問題的函數(shù)值。步長加速法。37清華大學(xué)《運籌學(xué)》第四章共49頁，您現(xiàn)在瀏覽的是第37頁!對于充分小的38清華大學(xué)《運籌學(xué)》第四章共49頁，您現(xiàn)在瀏覽的是第38頁!其中重復(fù)迭代，直至滿足精度為止。39清華大學(xué)《運籌學(xué)》第四章共49頁，您現(xiàn)在瀏覽的是第39頁!找下一點40清華大學(xué)《運籌學(xué)》第四章共49頁，您現(xiàn)在瀏覽的是第40頁!幾何分析D(1,1)

對于等值線為圓的無約束極小化問題，不管初始點選在哪里，只要一次迭代即可求得最優(yōu)解。41清華大學(xué)《運籌學(xué)》第四章共49頁，您現(xiàn)在瀏覽的是第41頁!4.1庫恩-塔克(Kuha-Tucker)條件1.幾何說明42清華大學(xué)《運籌學(xué)》第四章共49頁，您現(xiàn)在瀏覽的是第42頁!2.庫恩-塔克(Kuha-Tucker)條件設(shè)43清華大學(xué)《運籌學(xué)》第四章共49頁，您現(xiàn)在瀏覽的是第43頁!例用K-T條件求解如下非線性規(guī)劃。44清華大學(xué)《運籌學(xué)》第四章共49頁，您現(xiàn)在瀏覽的是第44頁!討論：45清華大學(xué)《運籌學(xué)》第四章共49頁，您現(xiàn)在瀏覽的是第45頁!1.二次規(guī)劃的K-T條件求相應(yīng)問題梯度46清華大學(xué)《運籌學(xué)》第四章共49頁，您現(xiàn)在