對于0-1分?jǐn)?shù)規(guī)劃的Dinkelbach算法的分析
武鋼三中 吳豪[譯]
摘要:
0-1分?jǐn)?shù)規(guī)劃問題是指求出解集{xi|xi=0或1}使目標(biāo)(c1x1+c2x2+
+cnxn) /(d1x1+d2x2+…+dnxn)=cx/dx達(dá)到最大。對于分?jǐn)?shù)規(guī)劃問題，Dinkelbach提出了一個算法，它通過解決一個子問題Q(L)來得到原文題的解。這里Q是一個線性的最小化目標(biāo)函數(shù)cx-Ldx，且滿足x等于0或1。在本文中，我們證明了Dinkelbach算法在最壞情況下可以在O(log(nM))的時間內(nèi)解決子問題，這里M=max{max|ci|,max|di|,1}。
1．0-1分?jǐn)?shù)規(guī)劃問題
要使兩個線性函數(shù)的比值最大或最小的問題，我們稱作分?jǐn)?shù)規(guī)劃問題或雙曲線問題。分?jǐn)?shù)規(guī)劃問題在許多領(lǐng)域都可以找到[22]。它在經(jīng)濟(jì)學(xué)中的應(yīng)用有些常見的例子，如尋找最優(yōu)收入比率或者在效益約束下的最佳物資調(diào)配問題。另外，系統(tǒng)效率也常常用比率來衡量，如收益/時間、利潤/風(fēng)險和消費(fèi)/時間。有大量的文章對這類問題做了分析[3，5，12，20，24]。
有幾類分?jǐn)?shù)規(guī)劃問題已被廣泛地研究。如0-1分?jǐn)?shù)規(guī)劃問題[1],它包含最優(yōu)比率生成樹問題[4]，最優(yōu)比率環(huán)問題[8，6，19]，分?jǐn)?shù)背包問題[15]，以及分?jǐn)?shù)剪枝問題[10]。在本文中，我們研究0-1分?jǐn)?shù)規(guī)劃問題，它的描述如下：
令c=(c1,c2,…,cn)和d=(d1,d2,…,dn)為n維整數(shù)向量，那么一個0-1分?jǐn)?shù)規(guī)劃問題用公式描述如下:
FP: 最小化
(c1x1+…cnxn)/(d1x1…dnxn)=cx/dx
xi∈{0,1}
這里x表示列向量(x1,x2,…,xn)T .0-1值向量的子集Ω稱作可行域，而x則是Ω的一個元素，我們稱x為可行解。貫穿全文，我們假定對于任意可行解x,dx都是正數(shù)。這里我們記C=max{max|ci|,1},D=max{max|di|,1}。那么，顯然問題的最優(yōu)解在區(qū)間[-nC,nC]內(nèi)。
對于分?jǐn)?shù)規(guī)劃問題，有許多算法都能利用下面的線性目標(biāo)函數(shù)解決問題。
Q(L): 最小化 cx-Ldx
xi∈{0,1}
記z(L)為Q(L)的最值。令x*為分?jǐn)?shù)規(guī)劃的最優(yōu)解，并且令L*=(cx*)/(dx*)(注：分?jǐn)?shù)規(guī)劃的最值)。那么下面就容易知道了：
z(L) > 0
當(dāng)且僅當(dāng)
L<L*
z(L) = 0
當(dāng)且僅當(dāng)
L=L*
z(L) < 0
當(dāng)且僅當(dāng)
L>L*
此外，Q(L*)的最優(yōu)解也能使分?jǐn)?shù)規(guī)劃最優(yōu)化[7,16,17]。因此，解決分?jǐn)?shù)規(guī)劃問題在本質(zhì)上等同于尋找L=L*使z(L)=0。出于這個目的，關(guān)于L的函數(shù)z(L)具有很多不錯的性質(zhì)：分段線性，凹函數(shù)，嚴(yán)格遞減，z(-nC)<0，且z(nC)>0。根據(jù)上面的性質(zhì)，顯然當(dāng)我們確定參量L，我們可以檢驗最值L*是否大于小于或等于當(dāng)前的L。
有一些方法能夠產(chǎn)生一系列收斂于L*的參量。其中一種借助于二分搜索[17,21,13]。在兩個不同的可行解的目標(biāo)值不相同的情況下，他們的差距將大于等于1/(nD)^2。這暗示我們，當(dāng)我們采用二分搜索時，最優(yōu)值L*可以通過解決子問題Q(L)在最多O(log(2nC/(1/nD)^2))<=O(log(nCD))的時間內(nèi)得到。
在1979年，Megiddo[18]提出了一個巧妙的方法來系統(tǒng)地產(chǎn)生參量序列。他證明了如果子問題Q(L)能夠通過O(p(n))的比較和O(q(n))的累加被解決，那么分?jǐn)?shù)規(guī)劃問題就能用O(p(n)+q(n))的時間被解決。
另一種方法理論上類似于牛頓迭代法，他被Isbell、Marlow[14]和Dinkelbach[7]提出（也被稱作Dinkelbach算法）。這個算法在[17,21,11]中被討論（也可能是其他文獻(xiàn)）。下一節(jié)將對它進(jìn)行正式的論述。Schaible[21]證明了對于非線性分?jǐn)?shù)規(guī)劃問題，二分搜索的方法的收斂速度僅僅是線性的，而Dinkelbach的收斂速度卻是超線性的。另外，據(jù)說Dinkelbach算法在實(shí)際應(yīng)用中強(qiáng)力而有效（參見[13,23]的例子）。然而，Dinkelbach算法對于0-1分?jǐn)?shù)規(guī)劃問題的最壞時間復(fù)雜度卻沒有被證明。在本文中，我們證明了,Dinkelbach算法最多會在O(log(nCD))的時間內(nèi)解決子問題。注意它的時間復(fù)雜度與普通的二分搜索相同。我們的結(jié)論暗示了，如果對于子問題Q(L)存在多項式算法，Dinkelbach算法也能夠在多項式時間內(nèi)解決分?jǐn)?shù)規(guī)劃問題。另外，即使子問題Q(L)是NP-完全或NP-難的，對于特殊的分?jǐn)?shù)規(guī)劃我們也能夠在多項式時間內(nèi)出解。
2．Dinkelbach算法的論述
它本質(zhì)上是觀察直線
z=cx’-Ldx’
于函數(shù)z(L)在L=L’處相切，這里x’是子問題Q(L’)的最優(yōu)解。因此，-dx’是z(L)在L’處的斜率。而且很容易看出上面的直線與L軸相交與L=cx’/dx’.
現(xiàn)在我們來描述Dinkelbach對于分?jǐn)?shù)規(guī)劃的算法。Dinkelbach算法產(chǎn)生了收斂于L*的參量序列，如圖1中細(xì)線所示的方式。
Dinkelbach算法：
步驟1：設(shè)L=L1,使 L*<=L1<=nC
步驟2：解決子問題Q(L)并得到最優(yōu)解x
步驟3：如果z(L)=0，那么輸出x并終止。否則，設(shè)L=cx/dx跳到步驟2
為了初始化L1,將用到nC，因此充分挖掘拓展問題的結(jié)構(gòu)將能做出更好的選擇。
3．Dinkelbach算法的分析
在這一節(jié)中，我們假定Dinkelbach算法終止于第k次。我們可以得到一個參量序列(L1,L2…Lk)和一個0-1值的向量(x1,x2…xk).z(L)的凸度暗示了下面的不等式：
dx1>dx2>…>dxk-1>=dxk>0
cx1+nCdx1>cx2+nCdx2>>cxk-1+nCdxk-1>=cxk+nCxk>=0
由于函數(shù)z(L)是嚴(yán)格遞減的，也很容易發(fā)現(xiàn)
z(L1)<z(L2)<<z(Lk) = 0 并且 L1>L2>>Lk
引理1
如果0>=z(Lr)>-1/nD (2<=r<=k) 那么 z(Lr)=0
證明 由于Lr=cxr-1/dxr-1
z(Lr)=cxr- Lr dxr=cxr-(cxr-1dxr)/(dxr-1)=(cxrdxr-1 – cxr-1dxr)/(dxr-1)
假定z(Lr)<0，那么(cxrdxr-1 – cxr-1dxr)<=-1。
因此不等式0<dxr-1<=nD暗示了z(Lr)<=-1/nD。它是矛盾的！
上面的引理來源于權(quán)向量c和d的完整性。這個引理暗示了如果z(Lr)>=-1/nD那么z(Lr)=0，因此該算法會中止于第r次。
引理2 如果0<=cxr+nCdxr<1,那么z(cxr/dxr)=0
證明 由于cxr+nCdxr是整數(shù)，如果0<=cxr+nCdxr<1，那么cxr+nCdxr=0并且cxr/dxr=-nC。由于最值L*>=-nC, xr是分?jǐn)?shù)規(guī)劃的最優(yōu)解并且L*=cxr/dxr=-nC。那么顯然有z(cxr/dxr)=z(L*)=0
上面的引理證明了如果cxr+nCdxr < 1，那么算法就在r或者r+1次終止。
現(xiàn)在給出主要引理：
引理3
如果1<=r<=k-1那么|z(Lr+1)|<=(1/2)|z(Lr)|或cxr+1+nCdxr+1 <=(1/2)(cxr+nCdxr)將滿足。
證明 如果Lr+nC<=0 那么Lr=L*=-nC 并且它暗示著z(Lr)b=(1/2)z(Lr+1)=0
現(xiàn)在假定Lr+nC>0。就出現(xiàn)了兩種情況：
情況(i) 首先我們來考慮z(Lr+1)( Lr+nC)<=z(Lr)/2*(Lr+1+nC)。這個情形如圖２所示。在這個圖中，直線z=cxr-Ldxr被記作lr。這里我們將用到圖２的符號。令M為線段PR的中點(diǎn)。那么點(diǎn)M的坐標(biāo)為( Lr+1 , z(Lr)( Lr+1+nC)/2/ Lr+nC )。因此條件z(Lr+1)( Lr+nC)<=z(Lr)*( Lr+1+nC)/2暗示著點(diǎn)Q=( Lr+1,z(Lr+1))在線段MR上。在這個條件下，我們證明不等式cxr+1+nC dxr+1<=(1/2)( cxr+nC, dxr)成立。這意味著直線lr+1與線段MR相交，lr+1也與線段M’R’相交，這里M’是線段P’R’的中點(diǎn)。現(xiàn)在我們證明這個不等式：
(Lr-Lr+1)( cxr+1+nC dxr+1)
=( cxr+1-Lr+1 dxr+1) (Lr+nC)- ( cxr+1-Lr dxr+1) (Lr+1+nC)
=z(Lr+1) (Lr+nC) - ( cxr+1-Lr dxr+1) (Lr+1+nC)
<= z(Lr) (Lr+1+nC)/2- ( cxr-Lr dxr) (Lr+1+nC)
=-(1/2) ( cxr-Lr dxr) (Lr+1+nC)=-(1/2)( cxr/ dxr - Lr) dxr( cxr/ dxr+nC)
=-(1/2)( Lr+1-Lr) ( cxr+nC dxr)=(1/2) (Lr-Lr+1) ( cxr+nC dxr)
由于Lr>Lr+1,那么不等式cxr+1+nC dxr+1<= (1/2) ( cxr+nC dxr)已經(jīng)被證明。
情況(ii) 接著，考慮z(Lr+1)( Lr+nC)>z(Lr)/2*(Lr+1+nC)
|z(Lr+1)|=- z(Lr+1)< - z(Lr)(nC+ Lr+1)/2/(nC+ Lr)
=|z(Lr)|(1-(Lr- Lr+1)/ (nC+Lr))/2<=1/2 * |z(Lr)|
注意無論|z(L)|還是cx+nCdx在過程中都是不增長的。
在第一次，|z(L)|的值小于等于2n^2*CD。通過引理１，顯然如果存在O(log(2n^2CD/(1/nD)))<=O(log(nCD))次，他們每個都能至少將z(L)減少50%那么，然后就能得到最優(yōu)解。同樣，引理２暗示了將cx+nCdx減少50%的次數(shù)O (log(2n^2CD))<=O(log(nCD))是最壞情況。引理３證明了每次將|z(L)|或cx+nCdx減少50%。因此，重復(fù)總次數(shù)的界限是O(log(nCD))。
定理４ Dinkelbanch算法最壞情況的運(yùn)行次數(shù)是O(log(nCD))<=O(log(nM))，這里M=max{C,D}。
上面的定理證明了Dinkelbanch算法最壞運(yùn)行次數(shù)是O(log(nCD))。它暗示了，如果對于Q(L)存在強(qiáng)多項式算法，Dinkelbach算法就能在多項式時間內(nèi)解決分?jǐn)?shù)規(guī)劃問題。然而，當(dāng)我們用多項式算法解決了子問題后，我們需要估計目標(biāo)函數(shù)Q(L)的系數(shù)的輸入規(guī)模。在下一節(jié)，我們將通過分析最優(yōu)比率生成樹和分?jǐn)?shù)調(diào)配問題來討論這一點(diǎn)。
4．討論
Chandrasekaran[4]提出了最優(yōu)比率生成樹的算法，它是基于二分搜索的。Dinkelbach算法可以在O(T(v,e)log(vCD))的時間解決該問題，這里v是點(diǎn)的個數(shù)，e是邊的個數(shù)，并且用T(v,e)表示計算普通最小生成樹的強(qiáng)多項式算法。很容易將Chandrasekaran的算法延伸到一般帶有分?jǐn)?shù)目標(biāo)函數(shù)的矩陣胚規(guī)劃問題。在這種情況下，在這種情形下，函數(shù)z(L)的斷點(diǎn)數(shù)最大為n(n-1)/2（參見[4]）因此，當(dāng)可行域Ω是矩陣胚基礎(chǔ)特征向量的集合。Dinkelbach算法就會在O(min{n^2,log(nCD)})后終止。
對于調(diào)配問題，已經(jīng)研制了許多算法。大概最有名的算法就是Hungarian方法，并且它在最壞情況下的復(fù)雜度是O(v(v log v+e)) [9]。使用Hungarian方法，Dinkelbach算法可以用O(v(v log v+e)log(vCD))的時間解決分?jǐn)?shù)調(diào)配問題。在[19]中，Orlin和Ahuja提出了一個O(sqrt(v)e*log(vW))的算法來解決調(diào)配問題而且據(jù)說他們的算法因為強(qiáng)多項式算法而具有競爭性（參見[2]也可）。在他們的算法中，它假定邊權(quán)為整數(shù)，并且W代表邊權(quán)的最大絕對值。為了將這個算法與Dinkelbach算法相結(jié)合，我們需要將在運(yùn)行第r次解決的的子問題Q(L)用下面式子代替
(dxr-1) cx-( cxr-1) dx
這里xr-1表示代表運(yùn)行第i次得到的最優(yōu)解。因此，在每次運(yùn)行中，Dinkelbach算法解決邊權(quán)絕對值小于等于2v^2CD的調(diào)配問題。它暗示了Dinkelbach算法對于調(diào)配問題的最壞情況下的時間復(fù)雜度為
O(sqrt(v)e(log(2v^3CD))(log(eCD)))<=O(sqrt(v)e(log(vCD))^2)
我們說，如果一個具有線性目標(biāo)函數(shù)的0-1整數(shù)規(guī)劃問題存在多項式算法，我們可以利用上述目標(biāo)函數(shù)在多項式時間內(nèi)解決它的0-1分?jǐn)?shù)規(guī)劃問題。
posted on 2008-08-05 14:58
小果子 閱讀(1874)
評論(3) 編輯 收藏 引用