拉格朗日松弛算法(LR)

1、Outline Deep into SG algorithm。Solve parallel machine scheduling using L-G methodSimulationanalysisDeep into SG methodWidely used in non-differentiable optimization; Min f(x)dual0max( )LDLRzz1.尋找到下界2.得到一個(gè)初始的解illustration for dual problems原問題：尋找使得目標(biāo)值最小的x對(duì)偶問題：尋找使得目標(biāo)函數(shù)最大的Steps of SGStep1:選一個(gè)初始拉格朗日乘子如 0

2、,t=1;Step2：對(duì)于 從中任選一個(gè)次梯度 ；若 0則達(dá)到了最優(yōu)解而停止計(jì)算；否則， t=t+1,重復(fù)STEP2；tstts1m ax, 0tttts202ttu p e rlo w e rw ithsIllustration of SGupper1上升很慢Gama vLemma1：whenvLemma2： and for all k, thenvHalve the dual gapwf *fw k)2/()*(*)(minlimwffxfkikiIllustration for gama050010001500200025003000350000.511.5迭 代 次 數(shù) 步 長coun

3、ter與 lmd的 曲 線 步 長 的 曲 線 upper05001000150020002500300035000510152025303540countervalue藍(lán) 線 的 期 望 值 高 于 紫 線 期 望 值 不 同 對(duì) 迭 代 造 成 的 影 響期 望 值 接 近 最 優(yōu) 解 ， 造 成 迭 代 次 數(shù) 增 加 好 處 ？lower010020030040050060070080090010000510152025303540不 同 的 下 界 開 始 的 時(shí) 間countervalue 36從 下 界 36， 上 屆 40開 始 搜 索從 下 界 0， 上 屆 40開 始 搜

4、索 descriptionBasic parallel machine schedulingjob4job3job2job1M2M1Pro_time, weight, duedate, start_time1.目 標(biāo)2.能力約束3.自身約束Formulation vproblem formulation 1,2,K111,2,ii iBiikkiiiiMinJ withJTMkC Bti ，（） ， N(2)Steps of LG methodstep1 .relaxation of the hard constrainstep2 .solve the L-G dual problem usi

5、ng S-G methodstep3. get feasible solution using heuristic alg0rithmWhy using LG methodvGood primal sequencevGood bound.First step relaxation()iiikikkBikiMinJwithJTM1,2,K1ikkiMk，（ ）11,2,iiiCBti，N(2)0kDual problem() iiiikikkBikikkiikikBkikMaxLwithLMinTMMMinT 11,2,iiiCBti ，N(2)0kMax min problem (LSS)Co

6、ordinatorMax f( )Optimize subproblem1For given to obtainB1Optimize subproblem2For given to obtainB2Optimize subproblemNFor given to obtainBn1max,0ttttsDual problem11,2, iiiCBti，N(2)0k () iii ikikkBikikki ikikBkikMaxL withLMinTMMMinT decompositionM i nT+iiki k Biki給定 將上述問題分解成N個(gè)子問題iiiiiiMinLwithL T +

7、i ik ik1 Bk-t +1kis.tCB1ti 1,2, ，NSolve dual problem原問題sub1sub2分解成N個(gè)子問題求解N個(gè)子問題得到一組給定一個(gè) Bi將帶回原問題得到關(guān)于的函數(shù)用次梯度法得到一個(gè)新的BiheuristicGet feasible solution LG-solution is a good primal solutionThe sequence is good but violate the capacity constrain.The one who cost much goes first,so it goes on.Flow chart of

8、heuristicList 按照（LG start）K=1,i=1Mk=0?no有任務(wù)在k完成嗎yesMk+;(k+1 N)yesSetK=k+1Reform the listi+;調(diào)度下一個(gè)jobi=job_num?re-freshstartRefresh startnoendyesSimulation resultseg1: 12 jobs and 2 identical machines ;Eg2:25 jobs and 4 identical machines ;Result:Eg1 bound=31.82 with best heuristic result 34;Eg2 bound

9、=37.74 with best heuristic result 38;analysisDeep into paithe LG multipliervWhat is the meaning of pai in physical sense?vHow it acts and changes during the itaration?The LG solution is a good primal solution though non-feasible.v Why the LG solution is a good primal solution?Pai (what)It tells usvH

10、ow important is the time K vHow important is the machine of time kConclusionvThe cost of using the resource of time kMathematical sense (pai)* ikkiikikBkikkkM a x Lw ithLMM inTd Jd MPai stands for the cost of resource at time kIllustration for pai0100200300400500600700800900100000.511.522.533.54前 端

11、中 后 端 后 端 不同時(shí)刻的pai在整個(gè)迭代過程中的趨向K在Illustration for pai0510152025303540455001234567k個(gè) 時(shí) 刻pai的值1 2 3 4 5 pai向 量 在 迭 代 過 程 中 的 趨 向1.2.3.4.5分別代表不同的迭代時(shí)間經(jīng)過迭代pai46最終的值Illustration for pai05101520253035404550012345671 2 3 4 5 Pai !=0vPai !=0;vHow can the solution of a completely different problem gives you a good primal solution?原問題一定跟對(duì)偶問題很不一樣Formulation vproblem formulation 1,2,K111,2,ii iBiikkiiiiMinJ withJTMkC Bti ，（） ，