并行計(jì)算的前后動(dòng)態(tài)混合規(guī)劃方法(原版譯文)

1、技術(shù)札記平行計(jì)算的前后動(dòng)態(tài)混合規(guī)劃方法J. B. LASSERRE 2與 S. E. Dreyfus合議摘要：我們考慮使用前后動(dòng)態(tài)混合規(guī)劃解決最優(yōu)化問(wèn)題，并提出一種通過(guò)兩個(gè)處理器執(zhí)行平行計(jì)算來(lái)減少計(jì)算時(shí)間的方法。關(guān)鍵詞：動(dòng)力學(xué)設(shè)計(jì)，平行線(xiàn)計(jì)算1.介紹我們關(guān)注一種分散時(shí)間最理想的控制難題，而在這個(gè)難題中， 動(dòng)態(tài)可能采用常規(guī)方式描述 xt=ft(xt-1,ut)或者用動(dòng)態(tài)規(guī)劃的向后處理法xt-1= ft(xt,ut)例如，在生產(chǎn)計(jì)劃或庫(kù)存計(jì)劃中，庫(kù)存水平方程式就屬于這種形式：xt=AtXt-1+Btut所以，如果At是一個(gè)可逆矩陣（從參考文獻(xiàn)1查看這些模型）也可以寫(xiě)做：xt-1=At-1xt+At

2、-1Btut因此，這個(gè)問(wèn)題能使用標(biāo)準(zhǔn)的向后或向前動(dòng)態(tài)規(guī)劃處理法解決。1. 此項(xiàng)研究由國(guó)家科學(xué)基金會(huì)贊助（項(xiàng)目號(hào)INT-78-09263），時(shí)值作者在加利福尼亞州伯克利的加利福尼亞大學(xué)訪(fǎng)學(xué)期間。2. 高級(jí)研究員，就職于Laboratoire dAutomatique et dAnalyse des Sustmes du CNRS，法國(guó)圖盧茲。 165假設(shè)兩個(gè)處理器能平行計(jì)算，我們提出一種前后動(dòng)態(tài)混合規(guī)劃方法。一個(gè)處理器使用向前動(dòng)態(tài)規(guī)劃運(yùn)算法則來(lái)解決T/2周期問(wèn)題（假設(shè)原始問(wèn)題有T周期）。同時(shí)，第二個(gè)處理器則使用向后動(dòng)態(tài)規(guī)劃運(yùn)算法則來(lái)解決另T/2周期問(wèn)題。一旦成功，小小額外工作就是尋找一種原始問(wèn)題

3、的最佳解決方案。計(jì)算的整個(gè)數(shù)量與標(biāo)準(zhǔn)向后動(dòng)態(tài)規(guī)劃運(yùn)算法則相同（如果我們假設(shè)向前或向后動(dòng)態(tài)規(guī)劃運(yùn)算需要同樣的計(jì)算）。這樣，計(jì)算時(shí)間基本上可分成兩部分，就一個(gè)龐大的運(yùn)算周期來(lái)說(shuō)，這個(gè)小小的額外工作可以忽略不計(jì)（在兩個(gè)處理器都解決了各自的問(wèn)題之后）2. 注釋與定義讓我們思考以下問(wèn)題問(wèn)題（P）：取最大值 T ft(xt)+gt(ut), t=1s.t. xt=ht(xt-1,ut), xtXt,utUt,已知x0，這里的xt是一個(gè)維矢量，ut是一個(gè)多元向量。假設(shè) 存在一個(gè)明確的函數(shù)h，就有：xt=ht(xt-1,ut) xt-1=ht(xt,ut).讓我們把Vt(xt)叫做從X0開(kāi)始、Xt結(jié)束的最優(yōu)策

4、略的最優(yōu)成本。通過(guò)使用向前的動(dòng)態(tài)規(guī)劃定理，我們得到：*V1(x)= f1(x)+g1(u), 對(duì)于xX1 (1a)其中，u=argmax g1(u1) (1b) s.t. h1(xo,u1)=x, (1c) u1U1 (1d)166和Vt(x)=ft(x)+maxgt(ut)+vt-1(xt-1), (2a)s.t xt-1=ht(x,ut), (2b) xt-1Xt-1, utUt (2c)讓我們把Wt(x)稱(chēng)作最優(yōu)策略的最佳成本，用x來(lái)表示起始時(shí)間t，用T來(lái)表示完成時(shí)間。通過(guò)動(dòng)態(tài)規(guī)劃方程定理，我們可以得知：WT-1(X)=maxgt(uT)+fT(Xt), (3a)s.t xT=hT(x,

5、uT), (3b) xTXT, uTUT , (3c)和Wt(x)=maxft+1(xt+1)+gt+1(ut+1)+Wt+1(xt+1), (4a) s.t. xt+1=ht+1(x,ut+1), (4b) xt+1Xt+1, ut+1Ut+1 (4b)用向后動(dòng)態(tài)規(guī)劃運(yùn)算法則計(jì)算時(shí)，可以把最佳成本設(shè)為W0(X0)。在下一部分，我們將明白向前動(dòng)態(tài)規(guī)劃和向后動(dòng)態(tài)規(guī)劃如何結(jié)合以更快地得到最優(yōu)解。3. 前后動(dòng)態(tài)混合規(guī)劃方程求解過(guò)程 把問(wèn)題(P)的最佳成本設(shè)為C*。接著，通過(guò)最優(yōu)定理，我們可知：任何t，其C*=maxVt(x)+Wt(x), (5a) s.t. xXt (5b)現(xiàn)在，假設(shè)我們可以平行使

6、用兩臺(tái)處理器計(jì)算。接著，運(yùn)用（1）和(2)， Vt(x)可以在處理器1中進(jìn)行運(yùn)算，同時(shí)將 Wt(x)輸入處理器2用（3）和（4）進(jìn)行運(yùn)算。這樣，一旦開(kāi)始計(jì)算 Vt(.)和 Wt(.)，我們只需要使用（5）來(lái)檢測(cè)x賦予C*的值。我們需要用標(biāo)準(zhǔn)的向后動(dòng)態(tài)規(guī)劃計(jì)算 W0(x0)。如果T=2p，那么選擇t = p，167Vp和Wp基本上要求等量的計(jì)算。如果T=2p+1，那么選擇t = p，Wp會(huì)比計(jì)算Vp稍多花一點(diǎn)時(shí)間，因?yàn)椋?）會(huì)有比（2）有更多的重復(fù)計(jì)算。所以，計(jì)算時(shí)間幾乎要除以2，因?yàn)橛茫?）去計(jì)算C*的工作量相對(duì)更大的T來(lái)說(shuō)是微不足道的。在下一部分，我們會(huì)舉例說(shuō)明在一個(gè)典型的資源分配問(wèn)題中應(yīng)用

7、的結(jié)果。4. 資源分配問(wèn)題中的計(jì)算量讓我們思考一個(gè)典型的資源分配問(wèn)題（看參考文獻(xiàn)2，第33頁(yè)）。需要用(T-2)(X+1)(X+2)/2加法和(p-1)X(X+1)/2對(duì)照來(lái)計(jì)算 WT-2(x),. . .,Wp(x)。W0(X0)需要X+1加法和X對(duì)照。 WT-1(x)只需要估算。讓我們現(xiàn)在來(lái)思考一下這個(gè)新方程。例題Case(i).T=2p. 一臺(tái)處理器運(yùn)算, WT-1,WT-2,Wp, 同時(shí)另一臺(tái)處理器計(jì)算 V1, V2,. . .,VP.。最后，全部的計(jì)算量是：(p-1)(x+1)(x+2)/2加法和(p-1)X(X+1)/2對(duì)照在一臺(tái)處理器上計(jì)算WT-2(x),. . . ,Wp(x)

8、同時(shí)另一臺(tái)處理器計(jì)算V1(x),Vp(x)。我們也需要 X+1和X對(duì)照去計(jì)算C*。因此，在計(jì)算過(guò)程中需要去演算(p-1)(X+I)(X+2)/2+X+I加法和(p- 1)X(X+ I)/2+X對(duì)照，而不是(p- 1)(X+ 1)(X+2)+X+ 1加法和(p - 1)X(X + 1) + X對(duì)照。對(duì)于大P，實(shí)際上計(jì)算時(shí)間將會(huì)除以2.例題Case(ii).T=2p+1.為了計(jì)算 Wp，我們需要p(X+l)(X+2)/2附加和pX(X+ 1)/2比較，然而對(duì)Vp我們需要(p-1) (X+ 1)(X +2)/2加法和(p- 1)X(X+ 1)/2對(duì)照。在此之前，用X + 1加法和X對(duì)照計(jì)算C*。同樣地，對(duì)于大P，實(shí)際計(jì)算時(shí)間要除以2。參考文獻(xiàn)：1. JOHNSON, L. A., and MONTGOMERY, P. C., Operations Research in Production Planning, Scheduling, and Inventory Control, Wiley, New York, New