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