楊東,芮文娟

(1.中國(guó)電信徐州分公司,江蘇徐州221000;2.中國(guó)礦業(yè)大學(xué)理學(xué)院,江蘇徐州221000)

無(wú)界域二次規(guī)劃問(wèn)題的區(qū)間算法

楊東1,芮文娟2

(1.中國(guó)電信徐州分公司,江蘇徐州221000;2.中國(guó)礦業(yè)大學(xué)理學(xué)院,江蘇徐州221000)

利用罰函數(shù)將無(wú)界域二次規(guī)劃問(wèn)題轉(zhuǎn)化為無(wú)約束優(yōu)化問(wèn)題,討論了罰函數(shù)的區(qū)間擴(kuò)張,利用Moore二分法與無(wú)解區(qū)域的刪除原則,給出了求解無(wú)界域二次規(guī)劃問(wèn)題的區(qū)間算法。理論分析和實(shí)例計(jì)算均表明算法是可靠和有效的。

二次規(guī)劃;區(qū)間算法;罰函數(shù)

0 引言

二次規(guī)劃問(wèn)題是一類重要的非線性規(guī)劃問(wèn)題。一方面來(lái)自于實(shí)際問(wèn)題,出現(xiàn)在很多應(yīng)用領(lǐng)域內(nèi),如最優(yōu)控制、工程設(shè)計(jì)、證券投資決策及最小二乘問(wèn)題等;另一方面,它具有重要的理論價(jià)值,例如,它常常作為子問(wèn)題,出現(xiàn)在一般非線性規(guī)劃問(wèn)題的求解中。近來(lái),對(duì)于凸二次規(guī)劃,人們進(jìn)行了比較深入的研究,給出的方法也非常有效。這些算法大都采用“有效集”策略,通過(guò)逐次求解等式約束二次規(guī)劃問(wèn)題來(lái)逼近最優(yōu)解。1984年Karmarkar[1]首次提出了多項(xiàng)式時(shí)間算法,隨著線性規(guī)劃、駐點(diǎn)問(wèn)題和線性互補(bǔ)問(wèn)題的進(jìn)一步深入研究,對(duì)二次規(guī)劃的研究也進(jìn)入了一個(gè)新的階段。這些新的研究結(jié)果與同倫延拓算法、內(nèi)點(diǎn)法有著密切的關(guān)系[2-3]。

區(qū)間算法是研究數(shù)值問(wèn)題的一類重要的方法[4-11]。本文以區(qū)間數(shù)學(xué)為工具,研究和建立求解二次規(guī)劃問(wèn)題的區(qū)間算法。

本文主要考慮如下無(wú)界區(qū)域上的二次規(guī)劃問(wèn)題

式中:H∈Rn×n是對(duì)稱矩陣;A∈Rm×n為行滿秩矩陣;b∈Rm;d∈Rn。

記X(0)=Rn,則式(1)可記作

對(duì)本文所討論的任意區(qū)間X,X的中點(diǎn)、寬度、半徑和絕對(duì)值分別以m(X)、W(X)、R(X)和|X|表示。如果函數(shù)f(x)和區(qū)間函數(shù)F(X)滿足f(x)∈F(X)(?x∈X),則稱F(X)是f(x)的區(qū)間擴(kuò)張。

1 罰函數(shù)的區(qū)間擴(kuò)張

其中:t(x,β)=f(x)+βg(x)為罰函數(shù);β＞0是罰因子。

以Sx表示問(wèn)題(1)的最優(yōu)點(diǎn)集。若x(β)是式(3)的一個(gè)解,并且x(β)→x?(β→+∞),則x?∈Sx。

定義t0:

t0(x,β)=

則式(3)可轉(zhuǎn)化為

下面建立t0(x,β)的區(qū)間擴(kuò)張。對(duì)任意X∈I(X(0)),取F1(X)為f(x)的自然區(qū)間擴(kuò)張

取F2(X)為f(x)的中值型區(qū)間擴(kuò)張

取Gj(X)為gj(x)的自然區(qū)間擴(kuò)張

定義

對(duì)任意X∈I∞(X(0)),定義

定理1T1(X,β),T2(X,β)分別是t(x,β)的區(qū)間擴(kuò)張。

證明先證明T1(X,β)是t(x,β)的區(qū)間擴(kuò)張。

對(duì)任意x∈X∈I(X(0)),因?yàn)镕1(X),Gj(X)分別是f(x),gj(x)區(qū)間擴(kuò)張,所以有

所以

故T1(X,β)是t(x,β)的區(qū)間擴(kuò)張。

同理可證明T2(X,β)是t(x,β)的區(qū)間擴(kuò)張。證畢。

定理3對(duì)任意Z∈I(X(0)),設(shè)X∈I(Z),則當(dāng)W(X)→0時(shí)W(T2(X,β))→0。

從而

W(((X-m(X))T(HX+d))i)→0(i=1,2,···,n)

由式(7)知

W(F2(X))=W((X-m(X))T(HX+d))→0

由式(9)知

W(T2(X,β))=W(F2(X))+βW(G(X))

所以只要證W(G(X))→0即可。

事實(shí)上,當(dāng)W(X)→0時(shí),

記

則

所以

所以當(dāng)W(X)→0時(shí)W(T2(X,β))→0。證畢。

2 無(wú)界區(qū)域上的區(qū)間運(yùn)算

2.1 無(wú)界區(qū)間的寬度和二分

在建立求解無(wú)界區(qū)域二次規(guī)劃問(wèn)題的區(qū)間算法之前,必須先定義無(wú)界區(qū)域的寬度和中點(diǎn)計(jì)算公式。設(shè)0＜λ＜∞為常數(shù),λ通?？梢赃@樣選取:如果懷疑最優(yōu)解存在于[-λ0,λ0]n中,則取λ=λ0。這樣就能將[-λ0,λ0]n外的區(qū)域盡快地刪除掉。

2.2 無(wú)界區(qū)間上的運(yùn)算

設(shè)A,B∈I∞,以?表示+、-、×運(yùn)算,定義

定義A/B為包含{a/b:a∈A,b∈B,b/=0}的最小區(qū)間。

3 刪除原則

無(wú)解區(qū)域刪除原則在問(wèn)題的研究中可以大量排斥無(wú)解子區(qū)域,降低存儲(chǔ)量,減少計(jì)算成本,算法的收斂速度也可以加快。

這就是中點(diǎn)檢驗(yàn)。

當(dāng)KX/=?時(shí),令當(dāng)KX=?時(shí),令

4 算法

算法的步驟如下:

(2)如果列表為空,轉(zhuǎn)步驟(10)。

(3)從列表中取出第一項(xiàng)元素(X,TI,tM,KX),把它從列表L中刪除,令β=β0,B=min{B0,TI}。

(4)如果tM-B＜ε,轉(zhuǎn)步驟(9)。

(5)計(jì)算Gj(X)(j=1,2,···,m)。若有j滿足Gj(X)＞0,轉(zhuǎn)步驟(2);否則,令β=0。

(6)按照X最大寬度分量方向二分X得X(1), X(2)。

(7)

①l=1。

②i=1。

④i=i+1;若i≤n,轉(zhuǎn)③。

⑤令X=X(l),計(jì)算TI,tM,KX,將(X,TI,tM,KX)按TI從小到大的順序放到列表L中,令t0=min{t0,tM}。

⑥若l=2,轉(zhuǎn)步驟(8);否則令l=2,轉(zhuǎn)②。

(8)從列表L中刪除所有滿足TI＞t0的項(xiàng),轉(zhuǎn)步驟(2)。

(9)輸出[TI,tM],X,令B0=B,轉(zhuǎn)步驟(2)。

(10)結(jié)束。

設(shè)式(5)的最優(yōu)值為t+,最優(yōu)解集為X+,由定理3和文獻(xiàn)[1]中的定理2,可知有如下結(jié)論。

定理4如果上述算法經(jīng)過(guò)n次循環(huán)后,列表L中只包含有界區(qū)域,則當(dāng)n→∞時(shí),TI→t+, tM→t+,X→X+。

對(duì)于式(3),由文獻(xiàn)[1]知有如下結(jié)論。

定理5若式(5)的最優(yōu)值t+=-∞,則式(3)無(wú)最優(yōu)解,且無(wú)下界。

若式(5)的最優(yōu)值t+∈R,X?=X+∩Rn非空,則式(3)有最優(yōu)值t?=t+和最優(yōu)解X?。若X?=?,則式(3)沒(méi)有最優(yōu)解,但式(3)有下界。

5 算法的計(jì)算機(jī)實(shí)現(xiàn)

在編程進(jìn)行算法實(shí)現(xiàn)的時(shí)候,采用下面的方法來(lái)處理無(wú)界區(qū)間。

設(shè)M是計(jì)算機(jī)所能表示的最大實(shí)數(shù),以RM表示所有的機(jī)器數(shù)。

記

稱IM為有限機(jī)器區(qū)間,ˉIMIM為無(wú)限機(jī)器區(qū)間。

在無(wú)界區(qū)間進(jìn)行計(jì)算時(shí)或構(gòu)造區(qū)間擴(kuò)張時(shí),按如下方法處理:

假定程序n次迭代后終止,則這時(shí)可得到t+=-∞或是輸出[TI,tM],X。對(duì)于輸出結(jié)果,根據(jù)定理5和式(11),可以做出這樣的結(jié)論:

(1)若t+=-∞,則t(x,β)無(wú)下界,式(3)無(wú)最優(yōu)解。

(2)若X,[TI,tM]均是有限機(jī)器區(qū)間,則式(3)有最優(yōu)解和最優(yōu)值。

(3)若[TI,tM]或X為無(wú)限機(jī)器區(qū)間,則不能判別式(3)是否有解。

6 數(shù)值結(jié)果

依據(jù)上述算法,利用Matlab6.0編程進(jìn)行數(shù)值實(shí)驗(yàn),可得如下數(shù)值結(jié)果,其中X(0)表示初始區(qū)域,ε表示計(jì)算精度,β表示罰因子。

X(0)=R2,其最優(yōu)解為:最優(yōu)值為f?=-7.2。

用上述區(qū)間算法計(jì)算輸出的第一個(gè)結(jié)果是(ε=10-5,β=103):

用上述區(qū)間算法計(jì)算輸出的第一個(gè)結(jié)果是(ε=10-4,β=102):

[1]KARMARKAR N.A new polynomial-time algorithm for linear programming[J].Combinalorica,1984,4(4):373-395.

[2]HAN C G,PARADOS E,YE Y.On the solution of indefinite quadratic program using an interior point algorithm [J].Informatica,1991(3):474-496.

[3]HUANG Z Y.An intrval entropy penalty method for nonlinear global opitimization[J].Reliable Computing,1998, 4(1):15-25.

[4]RATSCHEK H,ROKNE J.New computer methods for global optimization[M].Chichester:EuisHorwood Limited,1988.

[5]MOORE R E.Methods and applications of interval analysis[M].Philadelphia:SIAM,1979.

[6]曹德欣,沈祖和.一類非光滑優(yōu)化問(wèn)題的區(qū)間算法[J].高等學(xué)校計(jì)算數(shù)學(xué)學(xué)報(bào),1998,20(1):23-33.

[7]曹德欣,葉帥民,王海軍.An interval maximum-entropy method for a class of constrained nondifferentiable optimization problems[J].運(yùn)籌學(xué)學(xué)報(bào),1999,3(4):55-64.

[8]高岳林,徐成賢.邊界約束非凸二次規(guī)劃問(wèn)題的分枝定界方法[J].運(yùn)籌學(xué)學(xué)報(bào),2001,5(4):81-89.

[9]曹德欣,李蘇北,吳彥強(qiáng),等.求連續(xù)minimax問(wèn)題整體解的區(qū)間算法[J].高等學(xué)校計(jì)算數(shù)學(xué)學(xué)報(bào),2002,24(4): 359-365.

[10]沈祖和.區(qū)間分析方法及其應(yīng)用[J].應(yīng)用數(shù)學(xué)與計(jì)算數(shù)學(xué)學(xué)報(bào),1983(2):1-29.

[11]王海軍,曹德欣,李蘇北,等.非線性等式約束全局優(yōu)化問(wèn)題的區(qū)間算法[J].中國(guó)礦業(yè)大學(xué)學(xué)報(bào),2003,32(2): 204-208.

An Interval Algorithm for Quadratic Programming in Unbounded Domains

YANG Dong1,RUI Wen-juan2
(1.China Telecom Xuzhou Branch,Xuzhou 221000,Jiangsu,P.R.China;2.School of Science,China University of Mining and Technology,Xuzhou 221000,Jiangsu,P.R.China)

By using the penalty function,the quadratic programming problems in unbounded domain are transferred to unconstrained optimization problems.The interval extension of penalty function is discussed.With no deletion of principle based on Moore dichotomy, the interval algorithm for solving quadratic programming problems in unbounded domain is established.Theory analysis and example calculation show that the algorithm is reliable and effcient.

quadratic programming;interval algorithm;penalty function

O221.7

A

1001-4543(2014)03-0239-06

2014-04-10

芮文娟(1979–),女,安徽亳州人,講師,碩士,主要研究方向?yàn)榉蔷€性優(yōu)化和非光滑優(yōu)化問(wèn)題的區(qū)間算法。

電子郵箱xzhzgya@126.com。

中央高?；究蒲袠I(yè)務(wù)費(fèi)專項(xiàng)資金(No.2013QNA33)資助