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

關(guān)于非線性規(guī)劃的基本概念

在科學(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ī)劃的各種算法大都有自己特定的使用范圍，都有一定的局限性。到目前為止還沒(méi)有適合于各種問(wèn)題的一般算法，這是需要深入研究的一個(gè)領(lǐng)域。我們只是對(duì)一些模型及應(yīng)用作簡(jiǎn)單介紹。第2頁(yè),共78頁(yè)，星期六，2024年，5月非線性規(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)的距離為第3頁(yè),共78頁(yè)，星期六，2024年，5月目標(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ù)第4頁(yè),共78頁(yè)，星期六，2024年，5月例2.木梁設(shè)計(jì)問(wèn)題把圓形木材加工成矩形橫截面的木梁，要求木梁高度不超過(guò)，橫截面的慣性矩（高度的平方寬度）不小于，而且高度介于寬度與4倍寬度之間。問(wèn)如何確定木梁尺寸可使木梁成本最小.設(shè)矩形橫截面的高度為，寬度為，則圓形木材的半徑而木梁長(zhǎng)度無(wú)法改變，因此成本只與圓形木材的橫截面積有關(guān)。第5頁(yè),共78頁(yè)，星期六，2024年，5月目標(biāo)函數(shù)為約束條件為

第6頁(yè),共78頁(yè)，星期六，2024年，5月（1）數(shù)學(xué)規(guī)劃模型的一般形式：其中,簡(jiǎn)記為MP(MathematicalProgramming)2非線性規(guī)劃問(wèn)題的數(shù)學(xué)模型第7頁(yè),共78頁(yè)，星期六，2024年，5月（2）簡(jiǎn)記形式：引入向量函數(shù)符號(hào)：第8頁(yè),共78頁(yè)，星期六，2024年，5月（3）數(shù)學(xué)規(guī)劃問(wèn)題的分類：

若為線性函數(shù)，即為線性規(guī)劃(LP)；

若至少一個(gè)為非線性,

即為非線性規(guī)劃(NLP)；

對(duì)于非線性規(guī)劃，若沒(méi)有,即X=Rn,稱為

無(wú)約束非線性規(guī)劃或無(wú)約束最優(yōu)化問(wèn)題；否則稱為約束非線性規(guī)劃或約束最優(yōu)化問(wèn)題。第9頁(yè),共78頁(yè)，星期六，2024年，5月（4）可行域和可行解：稱為MP問(wèn)題的約束集或可行域。若x在X內(nèi)，稱x為MP的可行解或者可行點(diǎn)。第10頁(yè),共78頁(yè)，星期六，2024年，5月（5）最優(yōu)解和極小點(diǎn)對(duì)于非線性規(guī)劃（MP），若，并且有如果有定義:第11頁(yè),共78頁(yè)，星期六，2024年，5月如果有定義則稱x*是(MP)的局部最優(yōu)解或局部極小解,第12頁(yè),共78頁(yè)，星期六，2024年，5月

例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)化問(wèn)題，總可以用圖解法求解，而對(duì)三維或高維問(wèn)題，已不便在平面上作圖，此法失效。第13頁(yè),共78頁(yè)，星期六，2024年，5月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)題的圖解法最優(yōu)級(jí)解即為最小圓的半徑：f(x)=(x1-2)2+(x2-2)2=0第14頁(yè),共78頁(yè)，星期六，2024年，5月解：①先畫出等式約束曲線的圖形——拋物線，例3：用圖解法求解②再畫出不等式約束區(qū)域，

③最后畫出目標(biāo)函數(shù)等值線，

所以最優(yōu)解x*=(4,1),最優(yōu)值minf(x)=4.第15頁(yè),共78頁(yè)，星期六，2024年，5月4梯度、Hesse矩陣、Jacobi陣(1)二次函數(shù)一般形式:矩陣形式:二次型:矩陣A的正定性:正定、半正定、負(fù)定、不定。其中A＝AT。二次型的正定性:正定、半正定、負(fù)定、不定。第16頁(yè),共78頁(yè)，星期六，2024年，5月（2）梯度

定義：f(x)是定義在En上的可微函數(shù)。f(x)的n個(gè)偏導(dǎo)數(shù)為分量的向量稱為f(x)的梯度.

性質(zhì)：設(shè)f(x)在定義域內(nèi)有連續(xù)偏導(dǎo)數(shù)，即有連續(xù)梯度，則梯度有以下兩個(gè)重要性質(zhì)：

性質(zhì)一函數(shù)在某點(diǎn)的梯度不為零，則該梯度方向必與過(guò)該點(diǎn)的等值面垂直;

性質(zhì)二梯度方向是函數(shù)具有最大變化率的方向（負(fù)梯度方向也叫最速下降方向）。第17頁(yè),共78頁(yè)，星期六，2024年，5月解：由于例：試求目標(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è)方向上的單位向量是：第18頁(yè),共78頁(yè)，星期六，2024年，5月解：由于例：試求目標(biāo)函數(shù)在點(diǎn)x=[0,1]T

處的最速下降方向，并求沿這個(gè)方向移動(dòng)一個(gè)單位長(zhǎng)度后新點(diǎn)的目標(biāo)函數(shù)值。新點(diǎn)是：函數(shù)值：第19頁(yè),共78頁(yè)，星期六，2024年，5月幾個(gè)常用的梯度公式：第20頁(yè),共78頁(yè)，星期六，2024年，5月（3）Hesse矩陣多元函數(shù)f(x)關(guān)于x的二階導(dǎo)數(shù)，稱為f(x)的Hesse矩陣.當(dāng)f(x)的所有二階偏導(dǎo)數(shù)連續(xù)時(shí),即Hesse矩陣是對(duì)稱的.時(shí)，第21頁(yè),共78頁(yè)，星期六，2024年，5月幾個(gè)常用Hessian公式：第22頁(yè),共78頁(yè)，星期六，2024年，5月（4）Jacobi矩陣向量變量值函數(shù)：向量值函數(shù)g(x)在點(diǎn)x0處的Jacobi矩陣向量變量值函數(shù)的導(dǎo)數(shù)：第23頁(yè),共78頁(yè)，星期六，2024年，5月(1)凸函數(shù)：定義5凸函數(shù)和凸規(guī)劃第24頁(yè),共78頁(yè)，星期六，2024年，5月例：正定二次函數(shù)其中A是正定矩陣，f(x)是凸函數(shù)。參見(jiàn)P104例。第25頁(yè),共78頁(yè)，星期六，2024年，5月性質(zhì)1:（2）凸函數(shù)的性質(zhì)性質(zhì)2:是凸集。證明:略.第26頁(yè),共78頁(yè)，星期六，2024年，5月定理1：（一階條件）n=1時(shí)幾何意義：可微函數(shù)是凸的等價(jià)于切線不在函數(shù)圖像上方。

（3）凸函數(shù)的判定第27頁(yè),共78頁(yè)，星期六，2024年，5月定理2：（二階條件）第28頁(yè),共78頁(yè)，星期六，2024年，5月（4）凸規(guī)劃的定義及其性質(zhì)：凸規(guī)劃定義：第29頁(yè),共78頁(yè)，星期六，2024年，5月凸規(guī)劃性質(zhì)：凸規(guī)劃的任一局部最優(yōu)解都是它的整體最優(yōu)解。

凸規(guī)劃是以后重點(diǎn)討論的一類非線性規(guī)劃凸函數(shù)線性函數(shù)第30頁(yè),共78頁(yè)，星期六，2024年，5月（1）微分學(xué)方法的局限性：

實(shí)際的問(wèn)題中，函數(shù)可能是不連續(xù)或者不可微的。

需要解復(fù)雜的方程組，而方程組到目前仍沒(méi)有有效的算法。

實(shí)際的問(wèn)題可能含有不等式約束，微分學(xué)方法不易處理。6非線性規(guī)劃方法概述第31頁(yè),共78頁(yè)，星期六，2024年，5月（2）數(shù)值方法的基本思路：迭代給定初始點(diǎn)x0根據(jù)x0,依次迭代產(chǎn)生點(diǎn)列{xk}{xk}的最后一點(diǎn)為最優(yōu)解{xk}有限{xk}無(wú)限{xk}收斂于最優(yōu)解第32頁(yè),共78頁(yè)，星期六，2024年，5月迭代格式xkxk+1pk稱pk為第k輪搜索方向，tk為第k輪沿pk方向的步長(zhǎng)。產(chǎn)生tk和pk的不同方法，形成了不同的算法。第33頁(yè),共78頁(yè)，星期六，2024年，5月定義：特殊搜索方向——下降方向第34頁(yè),共78頁(yè)，星期六，2024年，5月定義：特殊搜索方向——可行下降方向解非線性規(guī)劃問(wèn)題，關(guān)鍵在于找到某個(gè)方向，使得在此方向上，目標(biāo)函數(shù)得到下降，同時(shí)還是可行方向。這樣的方向稱為可行下降方向。第35頁(yè),共78頁(yè)，星期六，2024年，5月定義：算法收斂、下降迭代算法集合S上的迭代算法：（1）初始點(diǎn)；（2）按照某種搜索方向pk產(chǎn)生下一個(gè)迭代點(diǎn)（i）如果點(diǎn)列收斂于最優(yōu)解，則稱此算法收斂。（ii）如果，則稱此算法為下降迭代算法。...第36頁(yè),共78頁(yè)，星期六，2024年，5月（3）下降迭代算法步驟（1）給出初始點(diǎn)，令；（2）按照某種規(guī)則確定下降搜索方向；（3）按照某種規(guī)則確定搜索步長(zhǎng)，使得；（4）令，；（5）判斷是否滿足停止條件。是則停止，否則轉(zhuǎn)第2步。搜索步長(zhǎng)確定方法：稱為最優(yōu)步長(zhǎng)，且有對(duì)

k的梯度第37頁(yè),共78頁(yè)，星期六，2024年，5月（4）終止條件②④①③第38頁(yè),共78頁(yè)，星期六，2024年，5月（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)等。第39頁(yè),共78頁(yè)，星期六，2024年，5月（6）算法的收斂速度則稱的收斂階為。設(shè)算法所得的點(diǎn)列為，如果1.線性收斂（當(dāng)k充分大時(shí)）：2.超線性收斂：3.二階收斂：（*）式中

=2時(shí)成立。（*）第40頁(yè),共78頁(yè)，星期六，2024年，5月

單變量(一維)最優(yōu)化一維最優(yōu)化問(wèn)題進(jìn)退法黃金分割法拋物線搜索法三次插值法第41頁(yè),共78頁(yè)，星期六，2024年，5月下降迭代算法中最優(yōu)步長(zhǎng)的確定..一維最優(yōu)化問(wèn)題：解析的方法（極值點(diǎn)的必要條件）一、一維最優(yōu)化問(wèn)題第42頁(yè),共78頁(yè)，星期六，2024年，5月1.單峰函數(shù)定義：設(shè)是區(qū)間上的一元函數(shù)，是在上的極小點(diǎn)，且對(duì)任意的有（a）當(dāng)時(shí)，（b）當(dāng).....則稱是單峰函數(shù)。..第43頁(yè),共78頁(yè)，星期六，2024年，5月性質(zhì)：通過(guò)計(jì)算區(qū)間[a,b]內(nèi)兩個(gè)不同點(diǎn)的函數(shù)值，就可以確定一個(gè)包含極小點(diǎn)的子區(qū)間。定理

設(shè)是區(qū)間上的一元函數(shù)，是在上的極小點(diǎn)。任取點(diǎn)則有（1）如果，則（2）如果則.....第44頁(yè),共78頁(yè)，星期六，2024年，5月2搜索法求解：或基本過(guò)程：

給出[a,b],使得x*在[a,b]中。[a,b]稱為搜索區(qū)間。

迭代縮短[a,b]的長(zhǎng)度。

當(dāng)[a,b]的長(zhǎng)度小于某個(gè)預(yù)設(shè)的值，或者導(dǎo)數(shù)的絕對(duì)值小于某個(gè)預(yù)設(shè)的正數(shù)，則迭代終止。第45頁(yè),共78頁(yè)，星期六，2024年，5月二．進(jìn)退法思想從一點(diǎn)出發(fā),按一定的步長(zhǎng),試圖確定出函數(shù)值呈現(xiàn)“高-低-高”的三點(diǎn)。一個(gè)方向不成功，就退回來(lái)，再沿相反方向?qū)ふ?。進(jìn)退法的計(jì)算步驟如何確定包含極小點(diǎn)的一個(gè)區(qū)間？第46頁(yè),共78頁(yè)，星期六，2024年，5月例：第47頁(yè),共78頁(yè)，星期六，2024年，5月假定：已經(jīng)確定了單峰區(qū)間[a,b]x1x2ababx12新搜索區(qū)間為[a,x2]新搜索區(qū)間為[x1,b]三.黃金分割法（0.618法）第48頁(yè),共78頁(yè)，星期六，2024年，5月區(qū)間縮小比例的確定：區(qū)間縮短比例為(x2-a)/(b-a)縮短比例為(b-x1)/(b-a)縮短比例滿足：

每次插入搜索點(diǎn)使得兩個(gè)區(qū)間[a,x2]和[x1,b]相等；

每次迭代都以相等的比例縮小區(qū)間。0.618法x1x2ababx1x2第49頁(yè),共78頁(yè)，星期六，2024年，5月黃金分割法的計(jì)算公式的推導(dǎo)：第50頁(yè),共78頁(yè)，星期六，2024年，5月第51頁(yè),共78頁(yè)，星期六，2024年，5月通過(guò)確定的取值，使上一次迭代剩余的迭代點(diǎn)恰與下一次迭代的一個(gè)迭代點(diǎn)重合，從而減少算法的計(jì)算量。同理可得。第52頁(yè),共78頁(yè)，星期六，2024年，5月3.0.618法的算法步驟：第53頁(yè),共78頁(yè)，星期六，2024年，5月確定[a,b],計(jì)算探索點(diǎn)x1=a+0.382(b-a)x2=a+0.618(b-a)是否是停止，輸出x1否以[a,x2]為新的搜索區(qū)間是停止，輸出x2否以[x1,b]為新的搜索區(qū)間3.0.618法的算法框圖：第54頁(yè),共78頁(yè)，星期六，2024年，5月黃金分割法的迭代效果：第k次后迭代后所得區(qū)間長(zhǎng)度為初始區(qū)間長(zhǎng)度的其它的試探點(diǎn)算法：Fibonacci算法。第55頁(yè),共78頁(yè)，星期六，2024年，5月例：解：t1t230t1、第一輪：t1=1.146,t2=1.854t2－0>0.5第56頁(yè),共78頁(yè)，星期六，2024年，5月2、第二輪：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.1460tt2t1第57頁(yè),共78頁(yè)，星期六，2024年，5月4、第四輪：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)值為-0.079801.146tt1t2第58頁(yè),共78頁(yè)，星期六，2024年，5月四．Fibonacci法

此法類似于0.618法，也是用于單峰函數(shù)。其計(jì)算過(guò)程也與0.618類似，第1次迭代計(jì)算兩個(gè)試探點(diǎn)，以后每次迭代只需新加一點(diǎn)，另一試探點(diǎn)取自上次的迭代點(diǎn)。此法與0.618法的主要差別為：區(qū)間長(zhǎng)度的縮短比率不是常數(shù)，而是由Fibonacci數(shù)確定；給出精度后，迭代次數(shù)可預(yù)先確定；適合于參數(shù)只能取整數(shù)值的情況。

定義稱滿足條件（i）F0=F1=1；（ii）的數(shù)列{Fn}為Fibonacci數(shù)列。第59頁(yè),共78頁(yè)，星期六，2024年，5月由定義推知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ū)間的長(zhǎng)度（記為）是上一次區(qū)間長(zhǎng)度的倍第60頁(yè),共78頁(yè)，星期六，2024年，5月所以要使在第n次迭代時(shí)搜索區(qū)間的長(zhǎng)度不超過(guò)ε，只需￡01LFnε

（2.4）

即可。因

是已知值，所以給出精度ε后利用（2.4）式可求得迭代次數(shù)。Fibonacc法在迭代中計(jì)算試探點(diǎn)的公式為即有第61頁(yè),共78頁(yè)，星期六，2024年，5月Fibonacci法(1)對(duì)初始區(qū)間和精度ε>0，求目標(biāo)函數(shù)值的計(jì)算次數(shù)n，使置辨別常數(shù)δ>0。計(jì)算試探點(diǎn)計(jì)算函數(shù)值和。置k=1。（2）若，則轉(zhuǎn)（3）；若，則轉(zhuǎn)（4）。第62頁(yè),共78頁(yè)，星期六，2024年，5月（3）

（5）置k﹕=k+1，轉(zhuǎn)（2）。（4）

（6）

第63頁(yè),共78頁(yè)，星期六，2024年，5月思想在極小點(diǎn)附近，用二次三項(xiàng)式四.拋物線（二次）插值即“兩頭大中間小”第64頁(yè),共78頁(yè)，星期六，2024年，5月如何計(jì)算函數(shù)令x=33221123322221111111121fxfxfxxfxfxf-第65頁(yè),共78頁(yè)，星期六，2024年，5月拋物線插值算法步驟：解出第66頁(yè),共78頁(yè)，星期六，2024年，5月思路：五.三次插值法第67頁(yè),共78頁(yè)，星期六，2024年，5月設(shè)令則有第68頁(yè),共78頁(yè)，星期六，2024年，5月求解滿足的極小點(diǎn)令而解方程（3），有兩種情況：由（2）可知第69頁(yè),共78頁(yè)，星期六，2024年，5月第70頁(yè),共78頁(yè)，星期六，2024年，5月極小點(diǎn)的計(jì)算公式：令第71頁(yè),共78頁(yè)，星期六，2024年，5月算法步驟：第72頁(yè),共78頁(yè)，星期六，2024年，5月第73頁(yè),共78