第五講非線性規(guī)劃的基本概念非線性規(guī)劃問(wèn)題非線性規(guī)劃數(shù)學(xué)模型非線性規(guī)劃的圖解法梯度、Hesse矩陣、Jacobi陣凸函數(shù)和凸規(guī)劃解非線性規(guī)劃方法概述一維最優(yōu)化

在科學(xué)管理和其他領(lǐng)域中，大量應(yīng)用問(wèn)題可以歸結(jié)為線性規(guī)劃問(wèn)題，但是，也有另外許多問(wèn)題，其目標(biāo)函數(shù)和（或）約束條件很難用線性函數(shù)表達(dá)。如果目標(biāo)函數(shù)和（或）約束條件中包含有自變量的非線性函數(shù)，則這樣的規(guī)劃問(wèn)題就屬于非線性規(guī)劃。

非線性規(guī)劃是運(yùn)籌學(xué)的重要分支之一。最近30多年來(lái)發(fā)展很快，不斷提出各種算法，而其應(yīng)用范圍也越來(lái)越廣泛。比如在各種預(yù)報(bào)、管理科學(xué)、最優(yōu)設(shè)計(jì)、質(zhì)量控制、系統(tǒng)控制等領(lǐng)域得到廣泛且不短深入的應(yīng)用。

一般來(lái)說(shuō)，求解非線性規(guī)劃問(wèn)題比線性規(guī)劃問(wèn)題困難得多。而且，也不象線性規(guī)劃那樣有單純形法這一通用的方法。非線性規(guī)劃的各種算法大都有自己特定的使用范圍，都有一定的局限性。到目前為止還沒有適合于各種問(wèn)題的一般算法，這是需要深入研究的一個(gè)領(lǐng)域。我們只是對(duì)一些模型及應(yīng)用作簡(jiǎn)單介紹。非線性規(guī)劃問(wèn)題舉例例一：選址問(wèn)題設(shè)有個(gè)市場(chǎng)，第個(gè)市場(chǎng)位置為，它對(duì)某種貨物的需要量為?，F(xiàn)計(jì)劃建立個(gè)倉(cāng)庫(kù)，第個(gè)倉(cāng)庫(kù)的存儲(chǔ)容量為試確定倉(cāng)庫(kù)的位置，使各倉(cāng)庫(kù)對(duì)各市場(chǎng)的運(yùn)輸量與路程乘積之和為最小。設(shè)第個(gè)倉(cāng)庫(kù)的位置為第個(gè)倉(cāng)庫(kù)到第個(gè)市場(chǎng)的貨物供應(yīng)量為則第個(gè)倉(cāng)庫(kù)到第個(gè)市場(chǎng)的距離為目標(biāo)函數(shù)為約束條件為

（1）每個(gè)倉(cāng)庫(kù)向各市場(chǎng)提供的貨物量之和不能超過(guò)它的存儲(chǔ)容量。（2）每個(gè)市場(chǎng)從各倉(cāng)庫(kù)得到的貨物量之和應(yīng)等于它的需要量。（3）運(yùn)輸量不能為負(fù)數(shù)例2.木梁設(shè)計(jì)問(wèn)題把圓形木材加工成矩形橫截面的木梁，要求木梁高度不超過(guò)，橫截面的慣性矩（高度的平方寬度）不小于，而且高度介于寬度與4倍寬度之間。問(wèn)如何確定木梁尺寸可使木梁成本最小.設(shè)矩形橫截面的高度為，寬度為，則圓形木材的半徑而木梁長(zhǎng)度無(wú)法改變，因此成本只與圓形木材的橫截面積有關(guān)。目標(biāo)函數(shù)為約束條件為

（1）數(shù)學(xué)規(guī)劃模型的一般形式：其中,簡(jiǎn)記為MP(MathematicalProgramming)2非線性規(guī)劃問(wèn)題的數(shù)學(xué)模型（2）簡(jiǎn)記形式：引入向量函數(shù)符號(hào)：（3）數(shù)學(xué)規(guī)劃問(wèn)題的分類：若為線性函數(shù)，即為線性規(guī)劃(LP)；若至少一個(gè)為非線性,即為非線性規(guī)劃(NLP)；對(duì)于非線性規(guī)劃，若沒有,即X=Rn,稱為

無(wú)約束非線性規(guī)劃或無(wú)約束最優(yōu)化問(wèn)題；否則稱為約束非線性規(guī)劃或約束最優(yōu)化問(wèn)題。（4）可行域和可行解：稱為MP問(wèn)題的約束集或可行域。若x在X內(nèi)，稱x為MP的可行解或者可行點(diǎn)。（5））最優(yōu)優(yōu)解和和極小小點(diǎn)對(duì)于非線性規(guī)劃（MP），若，并且有如果有有定義:如果有有定義則稱x*是(MP)的局部最優(yōu)解解或局部極小解解,例1：用圖解解法求解minf(x)=(x1－2)2+(x2－2)2s.t.h(x)=x1+x2-6=0x1x20662233最優(yōu)解x*=(3，3)T可行解x=(1.5，4.5)T最優(yōu)級(jí)解即即為最小圓圓的半徑：：f(x)=(x1－2)2+(x2－2)2=23非線性性規(guī)劃問(wèn)題題的圖解法法對(duì)二維最優(yōu)優(yōu)化問(wèn)題，，總可以用用圖解法求求解，而對(duì)對(duì)三維或高高維問(wèn)題，，已不便在在平面上作作圖，此法法失效。x1x206622D可行域最優(yōu)解x*=(2，2)T例2：用圖解法求求解minf(x)=(x1-2)2+(x2-2)2s.t.h(x)=x1+x2-6≤03非線線性規(guī)劃問(wèn)問(wèn)題的圖解解法最優(yōu)級(jí)解即即為最小圓圓的半徑：：f(x)=(x1-2)2+(x2-2)2=0解：①先畫出出等式約束束曲線的的圖圖形——拋拋物線，例3：用圖解法法求解②再畫出不不等式約束束區(qū)域，③最后畫出出目標(biāo)函數(shù)數(shù)等值線，，所以最優(yōu)解x*=(4,1),最最優(yōu)值minf(x)=4.4梯度、、Hesse矩陣、、Jacobi陣(1)二二次次函數(shù)一般形式式:矩陣形式式:二次型:矩陣A的正定性:正定定、半正正定、負(fù)負(fù)定、不不定。其中A＝AT。二次型的的正定性:正定定、半正正定、負(fù)負(fù)定、不不定。（2）梯梯度定義：f(x)是定定義在En上的可微微函數(shù)。。f(x)的n個(gè)偏導(dǎo)數(shù)數(shù)為分量量的向量量稱為f(x)的梯度.性質(zhì)：設(shè)f(x)在定定義域內(nèi)內(nèi)有連續(xù)續(xù)偏導(dǎo)數(shù)數(shù)，即有有連續(xù)梯梯度，則則梯度有有以下兩兩個(gè)重要要性質(zhì)：：性質(zhì)一函數(shù)在某某點(diǎn)的梯梯度不為為零，則則該梯度度方向必必與過(guò)該該點(diǎn)的等等值面垂垂直;性質(zhì)二梯度方向向是函數(shù)數(shù)具有最最大變化化率的方方向（負(fù)負(fù)梯度方方向也叫叫最速下降降方向）。解：由于例：試求目標(biāo)標(biāo)函數(shù)在在點(diǎn)x=[0,1]T處的最速速下降方方向，并并求沿這這個(gè)方向向移動(dòng)一一個(gè)單位位長(zhǎng)度后后新點(diǎn)的的目標(biāo)函函數(shù)值。。則函數(shù)在在x=[0,1]T處的最速速下降方方向是這個(gè)方向向上的單單位向量量是：解：由于例：試求目標(biāo)標(biāo)函數(shù)在在點(diǎn)點(diǎn)x=[0,1]T處的最速速下降方方向，并并求沿這這個(gè)方向向移動(dòng)一一個(gè)單位位長(zhǎng)度后后新點(diǎn)的的目標(biāo)函函數(shù)值。。新點(diǎn)是：：函數(shù)值：：幾個(gè)常用用的梯度度公式：（3）Hesse矩陣多元函數(shù)數(shù)f(x)關(guān)于于x的二階導(dǎo)導(dǎo)數(shù)，稱稱為f(x)的Hesse矩陣.當(dāng)f(x)的所有有二階偏偏導(dǎo)數(shù)連連續(xù)時(shí),即Hesse矩陣陣是對(duì)稱稱的.時(shí)，幾個(gè)常用用Hessian公式式：（4）Jacobi矩陣向量變量量值函數(shù)數(shù)：向量值函函數(shù)g(x)在點(diǎn)x0處的Jacobi矩陣陣向量變量量值函數(shù)數(shù)的導(dǎo)數(shù)數(shù)：(1)凸凸函數(shù)：：定義5凸函函數(shù)和凸凸規(guī)劃例：正定定二次函函數(shù)其中A是是正定矩矩陣，f(x)是凸函函數(shù)。參見P104例例。性質(zhì)1:（2）凸凸函數(shù)的的性質(zhì)性質(zhì)2:是凸集。。證明:略略.定理1：：（一階階條件））n=1時(shí)時(shí)幾何意意義：可可微函數(shù)數(shù)是凸的的等價(jià)于于切線不不在函數(shù)數(shù)圖像上上方。（3）凸凸函函數(shù)的判判定定理2：：（二階階條件））（4）凸凸規(guī)劃的的定義及及其性質(zhì)質(zhì)：凸規(guī)劃定定義：凸規(guī)劃性性質(zhì)：凸規(guī)劃的任一一局部最優(yōu)解解都是它的整整體最優(yōu)解。。凸規(guī)劃是以后后重點(diǎn)討論的的一類非線性性規(guī)劃凸函數(shù)線性函數(shù)（1）微分學(xué)學(xué)方法的局限限性：實(shí)際的問(wèn)題中中，函數(shù)可能能是不連續(xù)或或者不可微的的。需要解復(fù)雜的的方程組，而而方程組到目目前仍沒有有有效的算法。。實(shí)際的問(wèn)題可可能含有不等等式約束，微微分學(xué)方法不不易處理。6非線性性規(guī)劃方法概概述（2）數(shù)值方方法的基本思思路：迭代給定初始點(diǎn)x0根據(jù)x0,依次迭代產(chǎn)產(chǎn)生點(diǎn)列{xk}{xk}的最后一點(diǎn)點(diǎn)為最優(yōu)解{xk}有限{xk}無(wú)限{xk}收斂于最優(yōu)優(yōu)解迭代格式xkxk+1pk稱pk為第k輪搜索方向，tk為第k輪沿pk方向的步長(zhǎng)。產(chǎn)生tk和pk的不同方法，，形成了不同同的算法。定義：特殊搜索方方向——下降方向向定義：特殊搜索方向向——可行下降方向解非線性規(guī)劃劃問(wèn)題，關(guān)鍵鍵在于找到某某個(gè)方向，使使得在此方向向上，目標(biāo)函函數(shù)得到下降降，同時(shí)還是是可行方向。。這樣的方向稱稱為可行下降方向向。定義：算法收收斂、下降迭迭代算法集合S上的迭迭代算法：（1）初始點(diǎn)點(diǎn)；（2）按照某某種搜索方向向pk產(chǎn)生下一個(gè)迭迭代點(diǎn)（i）如果點(diǎn)點(diǎn)列收斂于最優(yōu)解解，則稱此算法收斂。（ii）如果果，則稱此算法法為下降迭代算法法。...（3）下降迭迭代算法步驟驟（1）給出初初始點(diǎn)，令；（2）按照某某種規(guī)則確定定下降搜索方方向；（3）按照某某種規(guī)則確定定搜索步長(zhǎng)，使得；（4）令，；（5）判斷是否滿足停止條件。是則停止，，否則轉(zhuǎn)第2步。搜索步長(zhǎng)確定定方法：稱為最優(yōu)步長(zhǎng)，且有對(duì)k的梯度（4）終終止條件②④①③（5）常用的的收斂性判別別準(zhǔn)則:（１）點(diǎn)收斂準(zhǔn)則:(可取Rn中任一種模)。e￡--)1()(kkxx·（２）目標(biāo)函數(shù)值準(zhǔn)則：（絕對(duì)差）。e￡--)()()1()(kkffxx（３）目標(biāo)函數(shù)值準(zhǔn)則：（相對(duì)差）。e￡--)()()()()1()(kkkfffxxx取其中之一,也可同時(shí)取取(1)與(2);(1)與(3);或(1),(2)和和(3)等。。（6）算法的的收斂速度則稱的的收斂階為為。。設(shè)算法所得的的點(diǎn)列為，如果1.線性收斂斂（當(dāng)k充分大時(shí)）：：2.超線性收收斂：3.二階收斂斂：（*））式中=2時(shí)成立。。（*）單變量(一維維)最優(yōu)化一維最優(yōu)化問(wèn)問(wèn)題進(jìn)退法黃金分割法拋物線搜索法法三次插值法下降迭代算法法中最優(yōu)步長(zhǎng)的的確定..一維最優(yōu)化問(wèn)問(wèn)題：解析的方法（極值點(diǎn)的必要要條件）一、一維最優(yōu)優(yōu)化問(wèn)題1.單峰峰函數(shù)定義：設(shè)是區(qū)間上的一元函數(shù)數(shù)，是在上的極小點(diǎn)，，且對(duì)任意的的有（a）當(dāng)時(shí)，（b）當(dāng).....則稱是是單峰峰函數(shù)數(shù)。..性質(zhì)：通過(guò)過(guò)計(jì)算算區(qū)間間[a,b]內(nèi)內(nèi)兩個(gè)個(gè)不同同點(diǎn)的的函數(shù)數(shù)值，，就可可以確確定一一個(gè)包包含極極小點(diǎn)點(diǎn)的子子區(qū)間間。定理

設(shè)是區(qū)間上的一元函數(shù)，是在上的極小點(diǎn)。任取點(diǎn)則有（1）如果，則（2）如果則.....2搜搜索法法求解解：或基本過(guò)過(guò)程：：給出[a,b],使使得x*在[a,b]中中。[a,b]稱為為搜索區(qū)區(qū)間。迭代縮縮短[a,b]的長(zhǎng)長(zhǎng)度。。當(dāng)[a,b]的的長(zhǎng)度度小于于某個(gè)個(gè)預(yù)設(shè)設(shè)的值值，或或者導(dǎo)導(dǎo)數(shù)的的絕對(duì)對(duì)值小小于某某個(gè)預(yù)預(yù)設(shè)的的正數(shù)數(shù)，則則迭代代終止止。二．進(jìn)進(jìn)退法法思想從一點(diǎn)點(diǎn)出發(fā)發(fā),按按一定定的步步長(zhǎng),試試圖確確定出出函數(shù)數(shù)值呈呈現(xiàn)““高-低低-高高””的三點(diǎn)點(diǎn)。一一個(gè)方方向不不成功功，就就退回回來(lái)，，再沿沿相反反方向向?qū)ふ艺?。進(jìn)退法法的計(jì)計(jì)算步步驟如何確確定包包含極極小點(diǎn)點(diǎn)的一一個(gè)區(qū)區(qū)間？？例：假定：：已經(jīng)經(jīng)確定定了單單峰區(qū)區(qū)間[a,b]x1x2ababx12新搜索索區(qū)間間為[a,x2]新搜索索區(qū)間間為[x1,b]三.黃黃金分分割法法（0.618法））區(qū)間縮縮小比比例的的確定定：區(qū)間縮縮短比比例為為(x2-a)/(b-a)縮短比比例為為(b-x1)/(b-a)縮短比比例滿滿足足：每次插插入搜搜索點(diǎn)點(diǎn)使得得兩個(gè)個(gè)區(qū)間間[a,x2]和[x1,b]相等等；每次迭迭代都都以相相等的的比例例縮小小區(qū)間間。0.618法x1x2ababx1x2黃金金分分割割法法的的計(jì)計(jì)算算公公式式的的推推導(dǎo)導(dǎo)：：通過(guò)過(guò)確確定定的的取取值值，，使使上上一一次次迭迭代代剩剩余余的的迭迭代代點(diǎn)點(diǎn)恰恰與與下下一一次次迭迭代代的的一一個(gè)個(gè)迭迭代代點(diǎn)點(diǎn)重重合合，，從從而而減減少少算算法法的的計(jì)計(jì)算算量量。。同理理可可得得。。3.0.618法法的的算算法法步步驟驟：：確定定[a,b],計(jì)計(jì)算算探探索索點(diǎn)點(diǎn)x1=a+0.382(b-a)x2=a+0.618(b-a)是否是停止止，，輸輸出出x1否以[a,x2]為為新新的的搜搜索索區(qū)區(qū)間間是停止止，，輸輸出出x2否以[x1,b]為為新新的的搜搜索索區(qū)區(qū)間間3.0.618法法的的算算法法框框圖圖：：黃金金分分割割法法的的迭迭代代效效果果：：第k次后迭代代后所得得區(qū)間長(zhǎng)長(zhǎng)度為初初始區(qū)間間長(zhǎng)度的的其它的試試探點(diǎn)算算法：Fibonacci算算法。例：解：t1t230t1、第一一輪：t1=1.146,t2=1.854t2－0>0.52、第二二輪：t2=1.146,t1=0.708t2－0=1.146>0.53、第三三輪：t1=0.438,t2=0.708b-t1=1.146-0.438>0.51.8540tt2t11.1460tt2t14、第四四輪：t2=0.876=(1.146-0.438),t1=0.708b-t1=1.146-0.708<0.5輸出：t*=t2=0.876為為最優(yōu)解解，最優(yōu)優(yōu)值為-0.079801.146tt1t2四．Fibonacci法法此法類似似于0.618法，也也是用于于單峰函函數(shù)。其其計(jì)算過(guò)過(guò)程也與與0.618類類似，第第1次迭迭代計(jì)算算兩個(gè)試試探點(diǎn)，，以后每每次迭代代只需新新加一點(diǎn)點(diǎn)，另一一試探點(diǎn)點(diǎn)取自上上次的迭迭代點(diǎn)。。此法與與0.618法法的主要要差別為為：區(qū)間間長(zhǎng)度的的縮短比比率不是是常數(shù)，，而是由由Fibonacci數(shù)確確定；給給出精度度后，迭迭代次數(shù)數(shù)可預(yù)先先確定；；適合于于參數(shù)只只能取整整數(shù)值的的情況。。定義稱滿足條條件（i）F0=F1=1；；（ii））的數(shù)列{Fn}為Fibonacci數(shù)列列。由定義推推知Fibonacci數(shù)列列的前10項(xiàng)為為1,1,2,3,5,8,13,21,34,55,89。。通過(guò)求求解遞推推關(guān)系可可求得該該數(shù)列的的通項(xiàng)為為úú?ùêê?é????è?--????è?+=++1125125151nnnF（2.3）由（2.3）式可求得。利用Fibonacci數(shù)的這一特點(diǎn)，用法中的0.618，再梢加改進(jìn)，便是Fibonacci法。618.01?-nnFF618.01代替nnFF-在Fibonacci法中，，第n次迭代的的搜索區(qū)區(qū)間的長(zhǎng)長(zhǎng)度（記記為）是上一一次區(qū)間間長(zhǎng)度的的倍倍所以要使使在第n次迭代時(shí)時(shí)搜索區(qū)區(qū)間的長(zhǎng)長(zhǎng)度不超超過(guò)ε，，只需￡01LFnε

（2.4）

即可。。因是已知知值，，所以以給出出精度度ε后后利用用（2.4）式式可求求得迭迭代次次數(shù)。。Fibonacc法法在迭迭代中中計(jì)算算試探探點(diǎn)的的公式式為即有Fibonacci法(1)對(duì)對(duì)初初始區(qū)區(qū)間和和精度度ε>0，，求目目標(biāo)函函數(shù)值值的計(jì)計(jì)算次次數(shù)n，使置辨別別常數(shù)數(shù)δ>0。。計(jì)算算試探探點(diǎn)計(jì)算函函數(shù)值值和。。置置k=1。。（2））若若，，則轉(zhuǎn)轉(zhuǎn)（3）；；若，，則轉(zhuǎn)轉(zhuǎn)（4）。。（3））（5））置置k﹕=k+1，，轉(zhuǎn)（（2））。（4））（6））思想在極小小點(diǎn)附附近，，用二二次三三項(xiàng)式式四.拋拋物物線（（二次次）插插值即“兩兩頭大大中間間小””如何計(jì)計(jì)算函函數(shù)令x=33221123322221111111121fxfxfxxfxfxf-拋物線線插值值算法法步驟驟：解出思路：：五.三三次次插值值法設(shè)令則有求解滿滿足的極小小點(diǎn)令而解方程程（3），，有兩兩種情情況：：由（2）可可知極小點(diǎn)點(diǎn)的計(jì)計(jì)算公公式：：令算法步步驟：：其它插插值算算法：：有理插插值。。收斂速速度：：三次次插值值算法法的收收斂階階為2。六、MATLAB單變量量函數(shù)數(shù)求最最小值值的標(biāo)標(biāo)準(zhǔn)形形式為為s.t函數(shù)fminbnd格式x=fminbnd(fun,x1,x2)%返回自自變量量x在區(qū)間間上函數(shù)數(shù)fun取取最小小值時(shí)時(shí)x值值，fun為目目標(biāo)函函數(shù)的的表達(dá)達(dá)式字字符串串或MATLAB自自定義義函數(shù)數(shù)的函函數(shù)柄柄。函數(shù)fminbnd的算算法基基于黃黃金分分割法法和二