于亞茹,姚奕榮

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

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

于亞茹,姚奕榮

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

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

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

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

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

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

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

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

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

1 積分總極值理論

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

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

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

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

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

性質1[21]設A?Rn,B?Zm,X=Rn×Zm是乘積拓撲空間,則有

反之,設(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中的開集,故反之,設(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),因此

證畢.

由上述性質可以得到以下結論.

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

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

由上述定理和性質可知,f(x,y)在拓撲空間X上滿足(A),(M),(R)條件:

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

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

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

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

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

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

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

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

2 指數變差積分途徑

2.1 指數變差積分函數及數學性質

(4)假設Δc＞0(Δc＜0的證明方法類似),當c＞c?時,有

2.2 最優(yōu)性條件

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

矛盾.故定理得證.

2.3 指數變差積分算法

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

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

3 數值算例

以下算例運用Monte-Carlo模擬方法結合指數變差積分算法進行計算,其中指數變差積分函數為

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

表1 例1的數值計算結果Table 1 Numerical results of Case 1

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

表2 例2的數值計算結果Table 2 Numerical results of Case 2

根據以上兩個算例可以看出,當維數分別是10,20,30,40,50時,計算結果精度均滿足條件λ＜1.0×e?10,這表明本算法是可行的.

4 結束語

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

[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]鄭權,蔣百川,莊松林.一個求總極值的方法[J].應用數學學報,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—),男,副教授,博士,研究方向為運籌學與控制論.E-mail:yryao@staff.shu.edu.cn