楊東,芮文娟

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

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

楊東1,芮文娟2

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

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

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

0 引言

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

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

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

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

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

對本文所討論的任意區(qū)間X,X的中點、寬度、半徑和絕對值分別以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ū)間擴張。

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

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

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

定義t0:

t0(x,β)=

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

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

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

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

定義

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

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

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

對任意x∈X∈I(X(0)),因為F1(X),Gj(X)分別是f(x),gj(x)區(qū)間擴張,所以有

所以

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

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

定理3對任意Z∈I(X(0)),設(shè)X∈I(Z),則當(dāng)W(X)→0時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即可。

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

記

則

所以

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

2 無界區(qū)域上的區(qū)間運算

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

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

2.2 無界區(qū)間上的運算

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

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

3 刪除原則

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

這就是中點檢驗。

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

4 算法

算法的步驟如下:

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

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

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

(5)計算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),計算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的項,轉(zhuǎn)步驟(2)。

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

(10)結(jié)束。

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

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

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

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

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

5 算法的計算機實現(xiàn)

在編程進行算法實現(xiàn)的時候,采用下面的方法來處理無界區(qū)間。

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

記

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

在無界區(qū)間進行計算時或構(gòu)造區(qū)間擴張時,按如下方法處理:

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

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

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

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

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

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

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

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

用上述區(qū)間算法計算輸出的第一個結(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)化問題的區(qū)間算法[J].高等學(xué)校計算數(shù)學(xué)學(xué)報,1998,20(1):23-33.

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

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

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

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

[11]王海軍,曹德欣,李蘇北,等.非線性等式約束全局優(yōu)化問題的區(qū)間算法[J].中國礦業(yè)大學(xué)學(xué)報,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ōu)化和非光滑優(yōu)化問題的區(qū)間算法。

電子郵箱xzhzgya@126.com。

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