非線性規(guī)劃-無約束問題課件

第三章最優(yōu)化方法運籌學當要求容器的容積一定，求表面積最小，以使用料最省。第三節(jié)非線性規(guī)劃x1x2s.tx1≥0，x2≥0一連續(xù)反應器如圖所示，進行如下反應根據(jù)預測，市場只能提供物料A600單位/h，產(chǎn)品B的市場需求量FB不超過50單位/h，產(chǎn)品B的價格為C3=2000元/單位。試確定物料A的進料速度FA0、初始濃度CA0、反應器體積V和轉(zhuǎn)化率各取多大，才能使得該反應器在單位時間內(nèi)的經(jīng)濟效益是最好的？目標函數(shù)或約束條件中有非線性函數(shù)的規(guī)劃問題非線性規(guī)劃非線性規(guī)劃的最優(yōu)解可能在其可行域中的任意一點達到不一定是全局最優(yōu)解求解思路：迭代從一個選定的初始點x0出發(fā)，按照某種特定的迭代規(guī)則產(chǎn)生一個點列{xk}xk有窮點列：最后一個點為最優(yōu)解xk無窮點列：其中一個點為最優(yōu)解對于存在ε>0，使則稱x*為R上的局部極小點，f(x*)稱為局部極小值→嚴格局部極小點、嚴格局部極小值基本概念若對于任意x，有則x*為R上的全局極小點，f(x*)為全局極小值→嚴格全局極小點、嚴格全局極小值基本概念Hessian矩陣凸性和凹性的判定（二階條件）H為對稱矩陣多元函數(shù)，如何判斷H是否正定？特征值f(x)H特征值嚴格凸函數(shù)正定>0凸函數(shù)半正定≥0凹函數(shù)半負定≤0嚴格凹函數(shù)負定<0既凸又凹（線性函數(shù)）=0非凸非凹>0,<0H正定，f(x)為嚴格凸函數(shù)對n維函數(shù)必要條件：f(x)在x*處一階可導充分條件H(x*)正定，則x*為極小值，反之為極大值例求函數(shù)的所有穩(wěn)定點解試判斷所得的穩(wěn)定點是否為最優(yōu)解求得各點的H特征值和穩(wěn)定點類型如下：穩(wěn)定點f(x)特征值1.941，3.8540.985537.030.97局部極小點-1.053，1.028-0.513410.503.50（全局）極小點0.6117，1.49292.83007.0-2.56鞍點一維搜索法步長tk的選定是由使目標函數(shù)值沿搜索方向下降最多為依據(jù)的，因此這一工作變成了求解以tk為變量的一元函數(shù)，故得名一維搜索法。無約束問題適用于某些不能求得一階導數(shù)解析解的問題如求最小回流比其中ij：組分i對組分j的相對揮發(fā)度

xDi：塔頂產(chǎn)品中i組分的組成

：由Underwood公式確定用經(jīng)典的微分方法很難求解斐波那契（Fibonacci）法（分數(shù)法）0.618法無需求導，根據(jù)函數(shù)值判斷搜索方向適用于求解已知極值區(qū)間的單峰函數(shù)一維搜索法（消去法）f(x2)＜f(x1)，去掉[x1,b0]，此時x*[a0,x1]一維搜索法（消去法）f(x)xoa0b0x*x1,x2在x*的右側(cè)x1x2f(x2)＞f(x1)，去掉[a0,x2]，此時x*[x2,b0]一維搜索法（消去法）f(x)xoa0b0x*x1,x2在x*的左側(cè)x1x2f(x2)＝f(x1)：

a.去掉[x1,b0]，此時x*[a0,x1]b.去掉[a0,x2]，此時x*[x2,b0]f(x)xoa0b0x*x1,x2在x*的兩側(cè)x1x2斐波那契數(shù)列數(shù)列{Fn}為斐波那契數(shù)列

斐波那契分數(shù)斐波那契（Fibonacci）法n012345Fn112358n67891011Fn1321345589144計算步驟選取初始數(shù)據(jù)，確定單峰區(qū)間[a0,b0]根據(jù)縮短率計算Fn，再確定最小n值計算初值t1和t2，計算f(t1)、f(t2)當區(qū)間變?yōu)閇a0,t2]反之區(qū)間變?yōu)閇t1,b0]確定n個搜索點以后，每次的區(qū)間縮短率為n次計算能得到的區(qū)間長度比為要使精度夠大，即δ：區(qū)間縮短的相對精度如果至某一步則可令可以證明對于斐波那契數(shù)列，其奇數(shù)項和偶數(shù)項都各自收斂于同一極限，該極限值等于0.618法以0.618作為固定的區(qū)間縮短率代替斐波那契法不同的縮短率，就得到了0.618法實施更為容易計算步驟選取初始區(qū)間[a0,b0]

f(t1)<f(t2)，取[a1=a0,b1=t2]

t’2=t1

t’1=a1+0.382(b1-a1)

f(t1)＞f(t2)，取[a1=t1,b1=b0]

t’2=a1+

0.618(b1-a1)

t’1=t2

Lt2t1a0b0La1b1t’2t’1a1b1t’2t’1搜索n個點后的區(qū)間長度縮短為或者說，迭代k次以后的區(qū)間長度變?yōu)榧匆阎阉鞯南鄬龋螖?shù)滿足例用0.618法求設(shè)初始區(qū)間為a0=-1.0，b0=3.0，要求剩余區(qū)間長度不大于0.1解本例可以通過解析法求得精確解第一次搜索選取兩個初始試算點比較得，可以得到下一次搜索區(qū)間第二次搜索計算試算點確定下一輪搜索區(qū)間迭代次數(shù)kak-1bk-1x(k,1)x(k,2)φ(x(k,1))φ(x(k,2))剩余區(qū)間長度1-130.5281.4721.750782.694782.4722-11.472-0.0556960.5282.058791.750781.5276963-0.0556961.4720.5280.888421.750781.900870.9441164-0.0556960.888420.3049560.5281.788041.750780.58346450.3049560.888420.5280.6655361.750781.777400.3605860.3049560.6655360.44270.5281.75321.750780.228……101.750021.750060.0325不斷用低次（不超過三次）多項式來近似目標函數(shù)，并逐步用插值多項式的極小點來逼近最優(yōu)解多項式近似（插值法、拋物線法）使用導數(shù)的方法對于迭代格式使目標函數(shù)f下降最快的方向是點xk的負梯度方向稱為f在xk的最速下降方向每一輪都從點xk出發(fā)沿最速下降方向進行搜索的方法，稱為最速下降法最速下降法具體步驟選取初始點x0，給定終止誤差求梯度向量。計算

，若

，停止迭代，輸出xk構(gòu)造負梯度方向進行搜索。求tk，使得令

，重新求梯度向量最速下降法例求解令x(0)=(μ1,μ2)T,μ1，μ2為任意實數(shù)假設(shè)x(0)不是最優(yōu)點則令代入目標函數(shù)，求最優(yōu)步長t0有令因故x(1)為最優(yōu)解，最優(yōu)值f(x*)=0對于目標函數(shù)的等值線為圓的問題，最速下降法總能一步得到最優(yōu)解例用最速下降法求解

取x(0)=(2,2)T令代入目標函數(shù)，得t(0)=2.005繼續(xù)迭代，得kt(k)x1x202.0052.0002100.0810411.8501.920-0.0033.8433.68720.0710.0710.0713.5470.13130.0650.0680.0000.1360.463×10-240.0030.0030.0030.1260.164×10-2可能在任何類型的穩(wěn)定點終止。通過分析Hessian矩陣來檢驗是否是極小點。對f(x)的尺度太靈敏，收斂緩慢，容易產(chǎn)生大量擺動（局部最速下降，相鄰搜索方向彼此正交）。最速下降法f(x)為二階可導函數(shù)，且在每個搜索方向上能準確最小化，則較少次迭代即可收斂計算量略大，收斂速度大幅提高搜索方向結(jié)合當前梯度方向和前一次梯度方向，搜索方向共軛解大型線性或非線性方程組最有效的方法之一存儲空間小，穩(wěn)定性高共軛梯度法牛頓法（Newton’smethod）

（Newton-Raphsonmethod）若H正定，則Q(x)的穩(wěn)定點xk+1為最小點，該點可表示為解得對照可得由此，可反復利用方程直到滿足收斂條件牛頓法例用牛頓法求解該函數(shù)的一階、二階導數(shù)分別為一維函數(shù)的牛頓法若取初始點x(0)=3，則故迭代次數(shù)kx(k)φ’(x(k))φ’’(x(k))|φ’(x(k))|03-52245215.167153.352184.33153.35224.33532.302109.44632.30234.0403.38386.8703.38344.0010.005584.0470.0055|φ’(x(k))|<0.01例求解解，取x(0)=(0,0)T有得為檢驗x(1)是否為最優(yōu)點，即x(1)為最優(yōu)點幾何意義牛頓法收斂速度很快，對于嚴格凸函數(shù)，只需一步即可得到極小值對純牛頓法模型，如果初始值與局部極小值不是足夠接近，通常不收斂需要計算一階、二階導數(shù)，計算量大，存儲空間大對于一階導數(shù)非單調(diào)變化的函數(shù)，往往會失敗牛頓法為避免計算二階導數(shù)矩陣H及其逆陣，我們設(shè)法構(gòu)造另一個矩陣，用它來逼近二階導數(shù)矩陣的逆陣

，稱擬牛頓法擬牛頓法（Quasi-NewtonMethod）構(gòu)造近似矩陣當f(x)為二階函數(shù)，H