ADMM优化算法讲解
alternating direction method of multipliers优化算法讲解OutlineDual decompositionMethod of multipliersAlternating direction method of multipliersCommon patternsExamplConsensus and exchangeConclusionsDual decompositionDual problemp convex equality constrained optimization problemminimizesubject to Ax= 6e Lagrangian: L(a, g)=f(a)+y(Ac-bdual function: g(y)=infx L(, g)e dual problem: maximize g(g)recover x*=argminL(, y*)Dual decompositionDual ascentgradient method for dual problem: y+l=yk +aVg(yky ")=A c-b, where a= argmin L(a, y")b dual ascent method isk+1gminz L(a, yk/-minimization(Axk+I-b)// dual updateworks, with lots of strong assumptionsDual decompositionDual decompositione suppose f is separablef(x)=f1(x1)+…+fN(xN),x=(x1Nthen L is separable in x: L(a, y)=L1(a1, 3)+...+Ln(N, 3)-y bLi(ai, y)=fi(ai)+y Aiaie -minimization in dual ascent splits into N separate minimizationsk+1argmin Li(li, y)Which can be carried out in parallelDual decompositionDual decompositiondual decomposition(Everett, Dantzig, Wolfe, Benders 1960-65k+1argLi(ei, y)N A: k+scatterupdate i in parallel, gather Ai k+solve a large problemby iteratively solving subproblems(in parallel)dual variable update provides coordinationworks, with lots of assumptions; often slowDual decompositionOutlineDual decompositionMethod of multipliersAlternating direction method of multipliersCommon patternsExamplConsensus and exchangeConclusionsMethod of multipliersMethod of multipliersa method to robustify dual ascentb use augmented Lagrangian(Hestenes, Powell 1969),p>0(, y)=f(c)+y(Ax-b)+(p/2)Acmethod of multipliers( Hestenes, Powell; analysis in Bertsekas 1982)k+1argmin Lp(a, yD(A.(note specific dual update step length pMethod of multipliersMethod of multipliers dual update stepoptimality conditions( for differentiableAcx-b=0, Vf(a*)+A(primal and dual feasibility)Since ah+1minimizes Lp(a, y)k+1 kf(x4+1)+A7(y+p(AVxf(at)+adual update yti=y+p(k+1k+1dual feasibleprimal feasibility achieved in limit: A k+I-b>0Method of multipliers
- 2021-05-06下载
- 积分：1
基于粒子群遗传算法的云计算任务调度研究
对云计算任务调度进行了研究，针对用户满意度和云提供商利益需求，提出一种融合粒子群和遗传算法的PSOGA改进算法。首先根据云环境特点对虚拟机资源进行分类，同时引入任务‐资源满意度距离、资源综合性能概念；然后对粒子群初始粒子操作进行优化，来提高粒子质量；最后为克服粒子易陷入局部最优解问题，加入遗传算法（GA）的交叉、变异操作，扩展粒子的搜索空间。仿真结果表明，该调度策略提高了用户满意度的同时减少了任务的完成时间，是云平台下一种有效的任务调度策略。Computer engineering and applications[0,1]Ka By+M=85,7,4,7,41 aya+B+rBr0.10.20.7(9,1,25,7)(9,25,5,7)=(1,0,0,1,1)3 a oB∑01(1,0,1,1)④0.9(1,1,0,1)=(1xx,1)010.109(3,2,1,5,4)∞(1,0,1,1,1)=(3x,15,4)GA3.2Computer engineering and applications0.36Cloudsim 3.0CloudsimDatacenter Brokerbind cloudlettovm=0.82bind CloudlettovmMyclipse100PSOGAPSOGAK=844%Cloud[1000040000rand([150,200rand()]预处理任务及資、「5001000rand(]源,并更新虚拟机计算任务-资谅满总度距离[60100rand()ndo初始负载从可用资源随机生|根据得致的任务最PSOGA成S3/4个子佳虚拟机类型生成S/4个粒子PSOPSOGAGA初始化S个粒了的还200度,并设置最大迭代次数L和 fitness=tPSOGA很据車新定义的粒了探作,计算 fitness值,并更新pb利gb根据规则选择粒了进亻[15交叉变异探作,并计算fitness值,更新忡群(12)达到最大次效LL=L+1fitness阈值结太,得到最优解(13)M=200300200200LPSOs Lo n PsoGAPSOGAPSOGAGAComputer engineering and applications80070600s■PSO400AGA300■ PSOGA200PSOGAPSO GA100PSO GA0第一批第二批第三批PSOGAPSO GAPAOGAPSOGA2.5PSOPSOGAA0.5PSOGA第一北第二批第批PSOGAPSO GA5400190r170015001301100西GAn□1sGAGA了0050o笫一批第二批第二批43.532.5NGA□05第一枇第二批第三批Computer engineering and applications基于粒子群遗传算法的云计算任务调度研究万F据WANFANG DATA文献链接作者王菠,张晓磊作者单位:重庆人学计算机学院,重庆400044刊名:计算机工程与应用英文刊名:Com uter Engineering ar d Appl ications年,卷(期)2013Axfe:http://d.wanfangdata.concn/periodiCalpre8fb5c222-8042-4959-ba95-2a3a31f59b2e.aspx
- 2020-12-08下载
- 积分：1
|
联系客服（QQ：3324461878）
