Wireless networks routing: ApproachesOptimization-based approachSolving optimization problemA primer on solving convex optimization through dualityConvex optimization problem in standard formThe LagrangianThe Lagrange dual functionThe Lagrange dual problemWeak & strict dualityA variant of convex optimization problemThe Lagrangian for the variantThe Lagrange dual function for the variantThe Lagrange dual problem for the variant1Wireless networks routing: Approachesreactive & proactive approachesbeing standardizedoptimization approachprovably optimal propertiesrouting for delay/disruption tolerant networksA different paradigmother approachescross-layer design, network coding, …2Optimization-based approachOptimization metricsEnergy consideration•Minimum energy routing•Maximum lifetime routing(function of) throughputJoint considerations•Routing & resource allocation•Routing & sensing3Solving optimization problemProblem specificA very common approachDual decomposition: naturally renders distributed algorithmsOnly describe one representative paperL. Xiao, M. Johansson, and S. Boyd, Simultaneous Routing and Resource Allocation via Dual Decomposition, IEEE Transactions on Communications, 52(7):1136-1144, July 2004. Goals: how to formulate optimization problem; solve convex optimization through duality4A primer on solving convex optimization through duality5Convex optimization problem in standard formpibxamixftsxfiTiix,...,1,,...,1,0)(..)(:min0mfff ,...,,10are convex functions.0,0,1,,)()()(βαβαRyxforyfβxfαyβxαfniii6The LagrangianmultiplierLagrangianμλbxaxhxhμxfλxfμλxLiTiiipiimiii:,)()()()(),,(1107The Lagrange dual function))()()((inf),,(inf),(110xhμxfλxfμλxLμλgipiimiiixxp*: optimal value of the original problem.*),(,,0 pμλgμλfor Important property:8The Lagrange dual problemWhat is the best lower bound that can be obtained from the Lagrange dual function?miλtsμλgiμλ,...,1,0..),(:max,This is the dual problem. The original problem is called primal problem.9Weak & strict dualityWeak duality**pd d*: optimal value of the dual problem.p*: optimal value of the primary problem.Optimal duality gap: Strong duality0** dp**pd 10A variant of convex optimization problempibxamixftsxfiTiix,...,1,,...,1,0)(..)(:max0f0: concave function.:,...,1mffconvex functions.11The Lagrangian for the variantmultiplierLagrangianμλbxaxhxhμxfλxfμλxLiTiiipiimiii:,)()()()(),,(11012The Lagrange dual function for the variant))()()((sup),,(sup),(110xhμxfλxfμλxLμλgipiimiiixxp*: optimal value of the original problem.*),(,,0 pμλgμλfor Important property:13The Lagrange dual problem for the variantWhat is the best upper bound that can be obtained from the Lagrange dual