求解混合整數(shù)規(guī)劃問題的指數(shù)變差積分算法

于亞茹,姚奕榮

(上海大學(xué)理學(xué)院,上海 200444)

求解混合整數(shù)規(guī)劃問題的指數(shù)變差積分算法

于亞茹,姚奕榮

(上海大學(xué)理學(xué)院,上海 200444)

研究了一種求解混合整數(shù)規(guī)劃問題的指數(shù)變差積分算法.利用積分型總極小值理論及指數(shù)變差積分對混合整數(shù)規(guī)劃問題進(jìn)行研究,通過變差積分函數(shù)的分析性質(zhì)及混合整數(shù)規(guī)劃的最優(yōu)性條件,結(jié)合牛頓法設(shè)計(jì)了一種求解混合整數(shù)規(guī)劃的指數(shù)變差積分新算法.運(yùn)用Monte-Carlo模擬方法實(shí)現(xiàn)整個(gè)算法,數(shù)值結(jié)果表明該算法是有效的.

混合整數(shù)規(guī)劃;最優(yōu)性條件;指數(shù)變差積分;Monte-Carlo模擬

混合整數(shù)規(guī)劃問題已廣泛應(yīng)用于國際金融、通信、環(huán)境工程、工業(yè)和醫(yī)療等重要領(lǐng)域,特別是隨著科學(xué)信息技術(shù)的飛速發(fā)展,研究人員對混合整數(shù)規(guī)劃問題的發(fā)展越來越重視,同時(shí)也提出了很多不同于傳統(tǒng)求解混合整數(shù)規(guī)劃問題的方法[1-4].

Zheng[5-8]以豐滿分析理論為基礎(chǔ)提出了尋求優(yōu)化問題全局最優(yōu)解的積分水平集方法[9-12],該算法不需求解方向梯度,也不受初始點(diǎn)的影響,其優(yōu)勢恰能較好地處理不連續(xù)優(yōu)化問題[6-7].之后Yao等[13]和Han等[14]又給出擬豐滿函數(shù)和變差積分函數(shù)方法,并結(jié)合牛頓法實(shí)現(xiàn)了積分水平集算法的收斂性,其中變差積分函數(shù)針對總極值問題具有更好的性質(zhì),如凸性、單調(diào)性和可導(dǎo)性.此外,積分水平集方法在光學(xué)薄膜自動設(shè)計(jì)[15]、最優(yōu)控制中的無變分迭代方法[16]、非線性對策[17]、偏微分方程的隱含解[18]、標(biāo)準(zhǔn)透鏡的自動生成[19]和經(jīng)濟(jì)平衡點(diǎn)計(jì)算[20]等問題中都已得到了有效的應(yīng)用.

2013年,Zheng等[21]提出了適合混合整數(shù)規(guī)劃問題的積分水平集算法.該算法首先構(gòu)造了一個(gè)Q-測度空間,使得混合整數(shù)規(guī)劃問題在該空間中滿足豐滿分析理論;然后,證明混合整數(shù)規(guī)劃問題滿足(A),(M),(R)條件[6,22],并根據(jù)空間上的測度定義確定目標(biāo)函數(shù)在水平集上的測度積分,證明最優(yōu)性條件及算法的收斂性;最后,通過計(jì)算積分均值和方差來求解目標(biāo)問題的全局最優(yōu)解.

本工作在積分水平集算法基礎(chǔ)上通過引入指數(shù)變差積分函數(shù)來討論混合整數(shù)規(guī)劃問題的求解問題.針對混合整數(shù)規(guī)劃問題,運(yùn)用不同的變差積分函數(shù)方法有更有效的結(jié)果.

考慮如下混合整數(shù)規(guī)劃問題:

一定條件下序列{ck+1}收斂于最優(yōu)值,{Hck+1}收斂于總極值點(diǎn).在算法的實(shí)現(xiàn)上,選擇用Monte-Carlo模擬方法進(jìn)行數(shù)值逼近,這樣使得算法和程序設(shè)計(jì)比較簡單,然后通過數(shù)值算例說明本算法的可行性.

1 積分總極值理論

首先介紹有關(guān)混合整數(shù)規(guī)劃問題的豐滿分析理論,包括Q-測度空間的構(gòu)造和豐滿性證明.

設(shè)f為Rn上的下半連續(xù)且上豐滿的函數(shù).?1是Rn的集族,?2是Zm的冪集.由拓?fù)淇臻g的定義可知,(Zm,?2)是離散拓?fù)淇臻g.構(gòu)造乘積拓?fù)淇臻g及Borel域:

定理1[21](X,?,μ)是Q-測度空間.

證明由(Zm,?2)是離散的拓?fù)淇臻g可知,Zm中的每個(gè)集合既是開集又是閉集,?2中的每個(gè)集合都是開的,并且每個(gè)非空開集的測度是正且有限的.因此(Zm,?2,μ2)是一個(gè)Q-測度空間.由于(Rn,?1,μ1)也是Q-測度空間,則對于Rn×Zm中任意的非空開集D=A×B,存在鄰域O=O1×O2使得O?D,因此μ(D)≥μ(O)＞0.由上述分析得到(X,?,μ)也是Q-測度空間.

下面介紹乘積空間X=Rn×Zm中的性質(zhì).

性質(zhì)1[21]設(shè)A?Rn,B?Zm,X=Rn×Zm是乘積拓?fù)淇臻g,則有

反之,設(shè)(x,y)∈clA×clB,并且W?X是含(x,y)的任意開集,于是存在含x的開集U(x)?Rn,含y的開集V(y)?Zm,使得(x,y)∈U(x)×V(y)?W.由于x∈clA,y∈clB, 故

因此,(x,y)∈cl(A×B),即clA×clB?cl(A×B).故cl(A×B)=clA×clB. (2)顯然intA×intB?A×B.由于intA×intB是X中的開集,故反之,設(shè)(x,y)∈int(A×B),于是存在含x的開集U(x)及含y的開集V(y)使得

因此,x∈intA,y∈intB,即(x,y)∈intA×intB且int(A×B)?intA×intB. (3)由于?(A×B)=cl(A×B)int(A×B),因此

證畢.

由上述性質(zhì)可以得到以下結(jié)論.

性質(zhì)2[21]若對任意的A×B?X,A?Rn,B?Zm,A是Rn中的豐滿集,則A×B 是X上的豐滿集.

證明由(Zm,?2)是離散的拓?fù)淇臻g可知B?Zm是開集且是上豐滿的,故有也是豐滿集.故f(x,y)在X上是上豐滿的.

由上述定理和性質(zhì)可知,f(x,y)在拓?fù)淇臻gX上滿足(A),(M),(R)條件:

(A)A×B是可測的豐滿集且f(x,y)是下半連續(xù)函數(shù);

(M)(X,?,μ)是Q-測度空間;

(R)f(x,y)是上豐滿函數(shù).

n-維Lebesgue測度空間(Rn,?,μ)是Q-測度空間.一個(gè)特定的總極值問題應(yīng)考慮與之相適應(yīng)的一個(gè)特定的Q-測度空間,一旦測度空間給定就可以用傳統(tǒng)方式定義積分.

需要注意的是,特定的最優(yōu)化問題需考慮與之相適應(yīng)的特定的Q-測度空間.若一旦測度空間被確定,則測度易求.由于一個(gè)非空開集的內(nèi)部是非空的,則包含非空豐滿集的可測集的Q-測度總是正的,這是在最小化的積分途徑中所必須的性質(zhì).因此通常作以下假設(shè):

(A＇)D是可測的豐滿集,f是D上的下半連續(xù)函數(shù);

(M＇)(X,?,μ)是Q-測度空間;

(R＇)f是上豐滿函數(shù).

2 指數(shù)變差積分途徑

2.1 指數(shù)變差積分函數(shù)及數(shù)學(xué)性質(zhì)

(4)假設(shè)Δc＞0(Δc＜0的證明方法類似),當(dāng)c＞c?時(shí),有

2.2 最優(yōu)性條件

下面給出混合整數(shù)規(guī)劃問題的最優(yōu)性條件.設(shè)

矛盾.故定理得證.

2.3 指數(shù)變差積分算法

因此,由最優(yōu)性條件可知c?=c?是總極小值.

令x∈H?,對k(k＞k0)有f(x,y)≤ck.設(shè)k→∞,可以得到f(x,y)≤c?.但是對區(qū)間X上的所有(x,y),有f(x,y)≥c?,因此H?={(x,y):f(x,y)=c?,(x,y)∈X},即H?是總極小值點(diǎn)集.

3 數(shù)值算例

以下算例運(yùn)用Monte-Carlo模擬方法結(jié)合指數(shù)變差積分算法進(jìn)行計(jì)算,其中指數(shù)變差積分函數(shù)為

最優(yōu)解為x?=(1,1,···,1),f?=0,λ＜1.0×e?10.運(yùn)用指數(shù)變差積分算法進(jìn)行計(jì)算,數(shù)值結(jié)果如表1所示.

表1 例1的數(shù)值計(jì)算結(jié)果Table 1 Numerical results of Case 1

最優(yōu)解為x?=(1,1,···,1),f?=0,λ＜1.0×e?10.運(yùn)用指數(shù)變差積分算法進(jìn)行計(jì)算,數(shù)值結(jié)果如表2所示.

表2 例2的數(shù)值計(jì)算結(jié)果Table 2 Numerical results of Case 2

根據(jù)以上兩個(gè)算例可以看出,當(dāng)維數(shù)分別是10,20,30,40,50時(shí),計(jì)算結(jié)果精度均滿足條件λ＜1.0×e?10,這表明本算法是可行的.

4 結(jié)束語

本工作基于積分型總極小值理論,運(yùn)用指數(shù)變差積分算法對混合整數(shù)規(guī)劃問題進(jìn)行了研究.不僅驗(yàn)證了變差積分函數(shù)的分析性質(zhì)和混合整數(shù)規(guī)劃的最優(yōu)性條件,而且進(jìn)一步結(jié)合牛頓法,設(shè)計(jì)了一種求解混合整數(shù)規(guī)劃問題的指數(shù)變差積分算法.在算法實(shí)現(xiàn)過程中運(yùn)用了Monte-Carlo模擬方法,但是偶爾會出現(xiàn)由于選取了特殊的初始值而導(dǎo)致算法結(jié)果異常,因此在計(jì)算水平集的具體實(shí)現(xiàn)上會有較大的研究空間.積分總極值方法具有堅(jiān)實(shí)的分析理論基礎(chǔ),且具有較廣的應(yīng)用范圍,對于一般的凸規(guī)劃問題和不連續(xù)問題的求解都有較強(qiáng)的可行性.因此如何把積分總值方法應(yīng)用于實(shí)際問題,例如投資組合、通信工程等現(xiàn)代領(lǐng)域,這將是值得深入研究的課題.

[1]BONAMI P,GONC?ALVES J P M.Heuristics for convex mixed integer nonlinear programs[J]. Computational Optimization and Applications,2012,51(2):729-747.

[2]BERTHOLD T.Primal heuristics for mixed integer programs[D].Berlin:Technischen Universit¨at, 2006.

[3]ELHEDHLI S,GOFFIN J L.The integration of an interior-point cutting plane method within a branch-and-price algorithm[J].Mathematical Programming,2004,100(2):267-294.

[4]JOE N S.Interior point cutting plane methods in integer programming[J].Computers and Operations Research,2011,38(9):1335-1341.

[5]ZHENG Q.Robust analysis and global optimization[J].Annals of Operations Research,1990, 24(1):273-286.

[6]ZHENG Q.Robust analysis and global minimization of a class of discontinuous functions(Ⅰ)[J]. Acta Mathematical Applicatae Sinica(English Series),1990,6(3):205-223.

[7]ZHENG Q.Robust analysis and global minimization of a class of discontinuous functions(Ⅱ)[J]. Acta Mathematical Applicatae Sinica(English Series),1990,6(4):317-337.

[8]ZHENG Q.Robust analysis and global optimization[J].Computers and Mathematics with Applications,1991,21(6/7):17-24.

[9]BAZARAA M S,SHERALL H D,SHETTY C M.Nonlinear programming:theory and algorithms[M]. 3rd ed.New York:John Wiley&Sons,2006.

[10]ZHENG Q.Optimality conditions of global optimization(Ⅰ)[J].Acta Mathematicae Applicatae Sinica(English Series),1985,1(2):66-78.

[11]ZHENG Q.Optimality conditions of global optimization(Ⅱ)[J].Acta Mathematicae Applicatae Sinica(English Series),1985,1(3):118-132.

[12]鄭權(quán),蔣百川,莊松林.一個(gè)求總極值的方法[J].應(yīng)用數(shù)學(xué)學(xué)報(bào),1978,1(2):161-174.

[13]YAO Y R,CHEN L,ZHENG Q.Optimality condition and algorithm with deviation integral for global optimization[J].Journal of Mathematical Analysis and Applications,2009,357(2):371-384.

[14]HAN B S,YAO Y R.Existence and optimality of accessible and approximatable minimizers of quasi upper robust functions[J].Computers and Mathematics with Applications,2006,52: 65-80.

[15]TANG J F,ZHENG Q.Automatic design of optical thin-film system merit function and numerical optimization method[J].Journal of Optical Society of America,1982,72(11):1522-1528.

[16]GALPERIN E A,ZHENG Q.Variation-free iterative method for global optimal control[J].International Journal of Control,1989,50(5):1731-1743.

[17]GALPERIN E A,ZHENG Q.Integral global optimization method for nonlinear games[J]. Computers and Mathematics with Applications,1991,21(6/7):145-159.

[18]GALPERINA E A,PAN Z X,ZHENG Q.Application of global optimization to implicit solution of partial differential equations[J].Computers and Mathematics with Applications,1993, 25(10/11):119-124.

[19]ZHUANG S L,ZHENG Q,YU F T.Automatic generation of prototype lenses[J].Optics Letters, 1982,7(12):581-583.

[20]ZHENG Q,ZHUANG D.Equi-robust set-valued mappings and the approximation of fixed points[C]//Proceedings of the Second International Conference on Fixed Point Theory and Applications.1992:346-361.

[21]ZHENG Q,YAO Y R,ZHANG M L.An integral global optimization algorithm for mixed programming problem[C]//Proceedings of the 2013 International Conference on Advanced Mechatronic Systems.2013:25-27.

[22]SHI S Z,ZHENG Q,ZHUANG D M.Discontinuous robust mapping are approximately[J].Transactions of the American Mathematical Society,1995,347(12):4943-4957.

An exponent deviation integral algorithm for mixed integer programming

YU Yaru,YAO Yirong
(College of Sciences,Shanghai University,Shanghai 200444,China)

This paper studies an exponent deviation integral approach to the mixed integer programming problem.A deviation integral function with good properties is proposed,and the optimality condition for a mixed integer programming problem is examined.Then an exponent deviation integral algorithm is developed.Numerical calculation is performed using the Monte-Carlo technique to show effectiveness and feasibility of the algorithm.

mixed integer programming;optimality condition;exponent deviation integral;Monte-Carlo simulation

O 221.7

A

1007-2861(2017)02-0276-14

10.3969/j.issn.1007-2861.2015.05.010

2015-07-27

姚奕榮(1959—),男,副教授,博士,研究方向?yàn)檫\(yùn)籌學(xué)與控制論.E-mail:yryao@staff.shu.edu.cn