逐次極值法及其應(yīng)用

陳 剛

(南通職業(yè)大學(xué)基礎(chǔ)部，江蘇南通226007)

尋求三元函數(shù)F(x,y,t)在有界閉區(qū)域Ω上的最小值，經(jīng)典的微分法已解決理論定位[1]：找出區(qū)域Ω內(nèi)部的駐點(diǎn)和邊界上的疑似極值點(diǎn)，比較它們的函數(shù)值，即可確定全區(qū)域的最小值.

但理論定位還遠(yuǎn)未完全解決現(xiàn)實(shí)的最小值認(rèn)定.在實(shí)際問(wèn)題中，一方面內(nèi)部駐點(diǎn)和邊界極值點(diǎn)通常沒(méi)有解析表達(dá)，難以比較函數(shù)值；另一方面雖然計(jì)算機(jī)程序可提供足夠精度的數(shù)值計(jì)算，但函數(shù)F(x,y,t)中往往含有大量的參數(shù)，這些參數(shù)未給定具體數(shù)值前或處于變動(dòng)時(shí)無(wú)法實(shí)施數(shù)值搜索.此外，經(jīng)典微分法著眼于整體處置，缺少個(gè)性特點(diǎn)，運(yùn)算量比較大.

為了解決上述困難，本文考慮運(yùn)用逐次極值法，并結(jié)合典型案例，說(shuō)明逐次極值法的實(shí)際分析操作.

1 逐次極值法原理與算法

1.1 逐次極值法的原理

定理1設(shè)F(x,y,t)的可行域?yàn)棣福瑢?duì)于每一個(gè)固定的t∈{t|(x,y,t)∈Ω}，二元函數(shù)F(x,y,t)取得最小值φ(t).若函數(shù)φ(t)在t=t*時(shí)取得最小值φ(t*)，則φ(t*)必為三元函數(shù)F(x,y,t)在區(qū)域Ω中的最小值.

證根據(jù)最小值的可達(dá)性知，存在(x*,y*,t*)∈Ω使φ(t*)=F(x*,y*,t*).再根據(jù)φ(t)的定義知，對(duì)于任意(x,y,t)∈Ω，

F(x,y,t)≥φ(t)≥φ(t*)=F(x*,y*,t*).

定理1給出了求最優(yōu)解的逐次遞推方法：對(duì)于固定的t，可得到低維區(qū)域Dt?Ω，求出Dt中的最小值點(diǎn)x=x(t)，y=y(t)，則φ(t)=F(x(t),y(t),t)，然后設(shè)法求出φ(t)的最小值.

這里的x=x(t)，y=y(t)是區(qū)域Ω中的曲線，稱之為優(yōu)勢(shì)曲線，φ(t)稱為優(yōu)勢(shì)函數(shù)，最小值點(diǎn)(x(t*),y(t*),t*)也叫最優(yōu)點(diǎn).最優(yōu)點(diǎn)的位置往往隨函數(shù)中的參數(shù)而變，分析優(yōu)勢(shì)曲線和優(yōu)勢(shì)函數(shù)，可以獲得各個(gè)可能極值點(diǎn)成為最優(yōu)點(diǎn)的充分必要條件，進(jìn)而完成最優(yōu)性的理論定位.

1.2 逐次極值法的算法

對(duì)于固定的t，尋求二元函數(shù)F(x,y,t)的最小值，也可用逐次極值法，比如固定y，求出關(guān)于x的最小值，得到區(qū)域Dt中的優(yōu)勢(shì)曲線，分析該優(yōu)勢(shì)曲線即可確定優(yōu)勢(shì)函數(shù)φ(t).

在尋求優(yōu)勢(shì)曲線時(shí)，可以用微分法.例如對(duì)于二維問(wèn)題

minf(x,y)，

s.t.a≤x≤b，c(x)≤y≤d(x)，

先固定x，令f′y(x,y)=0，求出駐點(diǎn)y=y0(x)(可能不止一個(gè)解)，比較函數(shù)值

f(x,y0(x))，f(x,c(x))，f(x,d(x))，

其中最小者對(duì)應(yīng)的y值y=u(x)(u(x)等于y0(x)或c(x)或d(x))，便給出了優(yōu)勢(shì)曲線.然后代入目標(biāo)函數(shù)，得到優(yōu)勢(shì)函數(shù)φ(x)=f(x,u(x))，化簡(jiǎn)后令φ′(x)=0，解得駐點(diǎn)x=x0. 再比較函數(shù)值φ(x0)，φ(a)和φ(b)，就可得到目標(biāo)函數(shù)f(x,y)的最小值.

顯然，這個(gè)算法對(duì)于開(kāi)放的無(wú)界區(qū)域也適用，比如約束區(qū)域?yàn)镈：a≤x<+∞，c(x)≤y≤d(x)，這時(shí)優(yōu)勢(shì)函數(shù)φ(x)的最優(yōu)值可以通過(guò)比較φ(x0)，φ(a)和φ(+∞)φ(x)加以認(rèn)定.目標(biāo)函數(shù)f(x,y)在無(wú)界區(qū)域未必有最優(yōu)值，判斷最優(yōu)性的難度增大，而逐次極值法在低維度下進(jìn)行最優(yōu)性判斷相對(duì)比較容易.

如果目標(biāo)函數(shù)f(x,y)的約束區(qū)域?yàn)镈：a(y)≤x≤b(y)，c≤y≤d，則先固定y，令f′x(x,y)=0，求出x的駐點(diǎn). 經(jīng)比較函數(shù)值可得優(yōu)勢(shì)曲線x=v(y)，優(yōu)勢(shì)函數(shù)為φ(y)=f(v(y),y)，化簡(jiǎn)后令φ′(y)=0，解得駐點(diǎn)y=y0.再與端點(diǎn)y=c，y=d比較，即可得到目標(biāo)函數(shù)f(x,y)的最小值.

如果目標(biāo)函數(shù)f(x,y)的可微性較好，沒(méi)有病態(tài)特征，那么上述判別最優(yōu)性的函數(shù)值比較過(guò)程可以省略，利用唯一駐點(diǎn)或唯一極值點(diǎn)就是最優(yōu)點(diǎn)的原理，直接認(rèn)定優(yōu)勢(shì)曲線.

對(duì)于比較簡(jiǎn)單的目標(biāo)函數(shù)，尋求優(yōu)勢(shì)曲線還可以用初等方法.常見(jiàn)的初等方法是利用算術(shù)平均與幾何平均的關(guān)系.初等方法的好處是省卻了最優(yōu)性判斷，在獲得駐點(diǎn)的同時(shí)便已完成最優(yōu)性的證明.

逐次極值法是對(duì)各個(gè)變量逐次尋優(yōu)，顯然可推廣到更多元的函數(shù)，當(dāng)然也適用于求函數(shù)的最大值.定理1并未限定Ω為有界閉區(qū)域，其應(yīng)用性相當(dāng)廣泛.

逐次極值法的基本算法為：針對(duì)多元函數(shù)，選定其中一個(gè)變量選優(yōu)，其余變量固定為常數(shù)；完成單元函數(shù)選優(yōu)后，將目標(biāo)函數(shù)化為低一維的函數(shù)；重復(fù)這一選優(yōu)過(guò)程，直至降維到一元優(yōu)勢(shì)函數(shù)；對(duì)此一元優(yōu)勢(shì)函數(shù)尋優(yōu)，便得到原目標(biāo)函數(shù)的最優(yōu)值.

2 逐次極值法的應(yīng)用案例

2.1 用初等方法求優(yōu)勢(shì)曲線

初等方法除了前面提到的算術(shù)平均不小于幾何平均外，還有二次函數(shù)極值法和幾何直線最短法等.

圖1 管線鋪設(shè)示意圖

例1[2]油管鋪設(shè)問(wèn)題.如圖1所示，鐵路線(x軸)同側(cè)有兩個(gè)煉油廠A(0,a)和B(c,b)，a≤b，長(zhǎng)度單位為km.現(xiàn)欲在鐵路線上增建一個(gè)車站P(x,0)，用來(lái)運(yùn)送成品油，希望管線建設(shè)費(fèi)用最少.管線鋪設(shè)費(fèi)用為r萬(wàn)元/km；若安排共用管線，則其費(fèi)用為p萬(wàn)元/km (r≤p<2r).

解方案設(shè)計(jì)的關(guān)鍵決策點(diǎn)是交匯點(diǎn)Q(x,y).點(diǎn)到直線的距離垂線最短，故共用管線PQ垂直于x軸；又兩點(diǎn)間直線最短，所以鋪設(shè)的管線由直線段AQ,BQ,PQ構(gòu)成.于是需要最小化的總費(fèi)用w可用二元函數(shù)表示為

可行域?yàn)橛薪玳]區(qū)域D：0≤x≤c，0≤y≤a.

先固定y，用幾何方法求|AQ|+|BQ|的最小值：作平行于x軸、高度為y的直線，如圖1中虛線所示，在y軸上作點(diǎn)A關(guān)于該直線的對(duì)稱點(diǎn)A1(0,2y-a)，則直線A1B給出|AQ|+|BQ|的最小值.利用圖中兩個(gè)直角三角形的比例關(guān)系，容易求得點(diǎn)Q的橫坐標(biāo)為

此方程給出優(yōu)勢(shì)曲線，因?yàn)閮牲c(diǎn)間直線最短，所以其最優(yōu)性不必另行判定.將優(yōu)勢(shì)曲線方程代入目標(biāo)函數(shù)f(x,y)，或者直接求出直線A1B的長(zhǎng)度，可得優(yōu)勢(shì)函數(shù)

將y*的表達(dá)式回代到優(yōu)勢(shì)曲線方程，可得最優(yōu)點(diǎn)Q的橫坐標(biāo)為

若需對(duì)最優(yōu)性作嚴(yán)格認(rèn)定，則可將導(dǎo)數(shù)作通分、有理化變形為

再討論φ′(y)的符號(hào).

2.2 優(yōu)勢(shì)曲線有尖點(diǎn)的情形

優(yōu)勢(shì)曲線y=u(x)通過(guò)比較函數(shù)值獲得，u(x)可能等于駐點(diǎn)y0(x)，也可能等于端點(diǎn)c(x)或d(x). 如果對(duì)于不同的x，u(x)的取值對(duì)象不同，那么優(yōu)勢(shì)曲線就會(huì)分段給出，形成尖點(diǎn).在這種情況下，要關(guān)注適當(dāng)?shù)挠懻?

例2求解二維問(wèn)題

maxf(x,y)=x3-10x2+4xy-2y2+13x+6，

s.t. 0≤x≤7，0≤y≤3.

解先固定x，則f(x,y)是y的二次函數(shù).當(dāng)0≤x≤3時(shí)，在駐點(diǎn)y=x處取得最大值；當(dāng)3

將此y代入f(x,y)，得到優(yōu)勢(shì)函數(shù)

對(duì)于0≤x≤3，令φ′(x)=3x2-16x+13=0，得[0,3]內(nèi)的駐點(diǎn)x=1；對(duì)于3

φ(0)=6，φ(1)=12，φ(3)=0，φ(5)=-12，φ(7)=16.

其中φ(7)=16最大，對(duì)應(yīng)的最優(yōu)點(diǎn)為x*=7，y*=3，最大值為maxf(x,y)=f(7,3)=16.

若按經(jīng)典的二元函數(shù)極值法，令f′x(x,y)=f′y(x,y)=0，得到可行域內(nèi)的唯一駐點(diǎn)x=y=1，但f(1,1)=12并非最大值，還需在4條邊界x=0，x=7，y=0，y=3處，分別求函數(shù)

f(0,y)=-2y2+6，

f(7,y)=-50+28y-2y2，

f(x,0)=x3-10x2+13x+6,

f(x,3)=x3-10x2+25x-12

的最大值再作比較，求后兩個(gè)函數(shù)最大值的計(jì)算量較大，最后也得到maxf(x,y)=f(7,3)=16.

2.3 逐次選優(yōu)過(guò)程中的靈活應(yīng)變

當(dāng)變量個(gè)數(shù)較多時(shí)，逐次極值法面對(duì)多個(gè)選優(yōu)過(guò)程，這些過(guò)程相對(duì)獨(dú)立，從而可針對(duì)個(gè)性化特征，采用不同的方法靈活處置.

圖2 場(chǎng)地圍墻示意圖

例3建筑材料問(wèn)題.一塊場(chǎng)地由矩形和等腰梯形拼接而成，如圖2所示，場(chǎng)地的面積為S=4280m2；四周的圍墻寬度有額定要求：CP和DQ段為δ=0.2m，PQ段為aδ，AB段為bδ，AC和BD段為cδ. 這里的a,b,c是圍墻的寬度比，其中c≥1.為了節(jié)省墻體材料，需要確定各段墻的長(zhǎng)度，使得用料最少，前提是保持場(chǎng)地面積不變，各段墻的寬度不變.

場(chǎng)地面積的計(jì)算公式為S=2HR+y(1+x)R2.在面積公式中解出H代入目標(biāo)函數(shù)，并去掉與最小化無(wú)關(guān)的公因子δ，得到三元優(yōu)化問(wèn)題

運(yùn)用逐次極值法，先將x,y看作常數(shù)，記

則

當(dāng)且僅當(dāng)左端兩項(xiàng)相等，即

繼續(xù)運(yùn)用逐次極值法，將x看作常數(shù)，求f(x,y)的最小值即可.令

得到駐點(diǎn)

求出二階導(dǎo)數(shù)，不難發(fā)現(xiàn)f″yy(x,y)>0，因而f′y(x,y)在駐點(diǎn)兩側(cè)左負(fù)右正，所以f(x,y)在該駐點(diǎn)處取得最小值，即上述方程給出優(yōu)勢(shì)曲線.回代到f(x,y)即得優(yōu)勢(shì)函數(shù)

求優(yōu)勢(shì)函數(shù)φ(x)的最小值難以用微分法，因?yàn)榉匠苔铡?x)=0整理后是一個(gè)關(guān)于x的4次方程.于是轉(zhuǎn)而用數(shù)值搜索的方法，取定一組墻寬的比值a=0.8,b=0.9,c=1.1.對(duì)x∈[0,1]，計(jì)算φ(x)的值，從中找出最小值，這是一維搜索，可在Excel表中完成.數(shù)值搜索的結(jié)果是：當(dāng)x=0.6794時(shí)，優(yōu)勢(shì)函數(shù)取得最小值minφ(x)=3.27853486.回代到前面的優(yōu)勢(shì)曲線(曲面)方程可得y=0.3789，R=36.1312. 代入面積約束公式可算得H的值，進(jìn)而計(jì)算圍墻各段的長(zhǎng)度

2R*=72.26 m， 2r*=49.10 m，h*=13.69 m，H*=47.73 m.

3 逐次極值法的優(yōu)點(diǎn)

從以上案例可以看出，逐次極值法相對(duì)于經(jīng)典方法有以下優(yōu)點(diǎn)：

(i)逐次極值法每次選優(yōu)都針對(duì)一元函數(shù)，原理簡(jiǎn)單，方法多樣，微分方法、初等方法可以靈活處置，對(duì)已知參數(shù)的討論也比較方便(參看例1)；

(ii)一元函數(shù)的最優(yōu)性認(rèn)定方法豐富、成熟、有效，如導(dǎo)數(shù)的符號(hào)，不等式的現(xiàn)成結(jié)論等，所以逐次極值法對(duì)于最優(yōu)性的論證可以做得很充分；

(iii)逐次極值法的每一步都可利用優(yōu)勢(shì)曲線(曲面)將目標(biāo)函數(shù)降維并化簡(jiǎn)，為后繼尋優(yōu)帶來(lái)很大便利，還能像例2那樣，省去許多不必要的計(jì)算；

(iv)有許多極值問(wèn)題沒(méi)有解析解，如例3，令三個(gè)偏導(dǎo)數(shù)等于零，難以整體推演，需要作多維數(shù)值搜索，而逐次極值法能夠?qū)㈦y點(diǎn)后移，只需作一維搜索，并且求解的脈絡(luò)清晰.

[參 考 文 獻(xiàn)]

[1] 菲赫金戈?duì)柶?ГМ.微積分學(xué)教程(一卷二分冊(cè))[M].葉彥謙譯.北京：高等教育出版社，1959：376-431.

[2] 全國(guó)大學(xué)生數(shù)學(xué)建模競(jìng)賽組委會(huì).2010高教社杯全國(guó)大學(xué)生數(shù)學(xué)建模競(jìng)賽(CUMCM)題目C題[EB/OL].[2010-09-09] http:∥www.mcm.edu.cn/