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

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

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

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

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

（1）每個倉庫向各市場提供的貨物量之和不能超過它的存儲容量。

（2）每個市場從各倉庫得到的貨物量之和應(yīng)等于它的需要量。（3）運輸量不能為負數(shù)第4頁,共78頁，星期六，2024年，5月例2.木梁設(shè)計問題把圓形木材加工成矩形橫截面的木梁，要求木梁高度不超過，橫截面的慣性矩（高度的平方寬度）不小于，而且高度介于寬度與4倍寬度之間。問如何確定木梁尺寸可使木梁成本最小.設(shè)矩形橫截面的高度為，寬度為，則圓形木材的半徑而木梁長度無法改變，因此成本只與圓形木材的橫截面積有關(guān)。第5頁,共78頁，星期六，2024年，5月目標函數(shù)為約束條件為

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

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

若至少一個為非線性,

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

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

無約束非線性規(guī)劃或無約束最優(yōu)化問題；否則稱為約束非線性規(guī)劃或約束最優(yōu)化問題。第9頁,共78頁，星期六，2024年，5月（4）可行域和可行解：稱為MP問題的約束集或可行域。若x在X內(nèi)，稱x為MP的可行解或者可行點。第10頁,共78頁，星期六，2024年，5月（5）最優(yōu)解和極小點對于非線性規(guī)劃（MP），若，并且有如果有定義:第11頁,共78頁，星期六，2024年，5月如果有定義則稱x*是(MP)的局部最優(yōu)解或局部極小解,第12頁,共78頁，星期六，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)級解即為最小圓的半徑：f(x)=(x1－2)2+(x2－2)2=23非線性規(guī)劃問題的圖解法

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

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

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

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

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

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

性質(zhì)二梯度方向是函數(shù)具有最大變化率的方向（負梯度方向也叫最速下降方向）。第17頁,共78頁，星期六，2024年，5月解：由于例：試求目標函數(shù)在點x=[0,1]T

處的最速下降方向，并求沿這個方向移動一個單位長度后新點的目標函數(shù)值。

則函數(shù)在x=[0,1]T

處的最速下降方向是這個方向上的單位向量是：第18頁,共78頁，星期六，2024年，5月解：由于例：試求目標函數(shù)在點x=[0,1]T

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

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

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

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

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

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

k的梯度第37頁,共78頁，星期六，2024年，5月（4）終止條件②④①③第38頁,共78頁，星期六，2024年，5月（5）常用的收斂性判別準則:（１）點收斂準則:(可取Rn中任一種模)。e￡--)1()(kkxx·（２）目標函數(shù)值準則：（絕對差）。e￡--)()()1()(kkffxx（３）目標函數(shù)值準則：（相對差）。e￡--)()()()()1()(kkkfffxxx取其中之一,也可同時取(1)與(2);(1)與(3);或(1),(2)和(3)等。第39頁,共78頁，星期六，2024年，5月（6）算法的收斂速度則稱的收斂階為。設(shè)算法所得的點列為，如果1.線性收斂（當k充分大時）：2.超線性收斂：3.二階收斂：（*）式中

=2時成立。（*）第40頁,共78頁，星期六，2024年，5月

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

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

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

迭代縮短[a,b]的長度。

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

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

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

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

定義稱滿足條件（i）F0=F1=1；（ii）的數(shù)列{Fn}為Fibonacci數(shù)列。第59頁,共78頁，星期六，2024年，5月由定義推知Fibonacci數(shù)列的前10項為1,1,2,3,5,8,13,21,34,55,89。通過求解遞推關(guān)系可求得該數(shù)列的通項為úú?ùêê?é????è?--????è?+=++1125125151nnnF（2.3）由（2.3）式可求得。利用Fibonacci數(shù)的這一特點，用法中的0.618，再梢加改進，便是Fibonacci法。618.01?-nnFF618.01代替nnFF-在Fibonacci法中，第n次迭代的搜索區(qū)間的長度（記為）是上一次區(qū)間長度的倍第60頁,共78頁，星期六，2024年，5月所以要使在第n次迭代時搜索區(qū)間的長度不超過ε，只需￡01LFnε

（2.4）

即可。因

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

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

（6）

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