Algorithm development Sample Clauses

Algorithm development. ‌ To develop an online network resource allocation algorithm that minimizes the end-to-end delay, we rewrite the problem (3.16) as per time-slot problem, as follows min xt∈X ,∀t ψt(xt) s. t. gt(xt) ⪯ 0. (3.19) δα λ 2 The problem (3.19) is convex, because the cost function is a maximum function of the linear functions, and the constraint function is affine with respect to xt [21]. The solution to problem (3.19) can be found by solving its max-min problem, expressed as xxx xxx Lt(x, λ) = max min ψt(x) + λ⊤gt(x) − 2 , + + λ∈RM +N x∈X λ∈RM +N x∈X + where λ ∈ RM+N stacks the Lagrange multipliers associated with the time-varying constraints, δ is the constant scaling factor, α is the step size which will be used in (3.20) to update the primal variable xt and in (3.22) for calculating the gradient δα λ 2 of the Lagrange function with respect to λ, is the regularizing term inserted to avoid getting large values for λ per time-slot and ensuring numerical stability of the solutions [76, 21]. The convex cost and constraint functions in (3.19) are only revealed at the end of each time-slot and, hence, ψt(xt) and gt(xt) are unknown at the beginning of each time-slot t, which could be completely different from the previous ones, ψt−1(xt−1) and gt−1(xt−1). Therefore, to solve the problem in (3.20), we use projection gradient descent to choose the primal variable xt followed by a projection gradient ascent to determine the corresponding dual variable λt+1 as functions of the decisions made in time-slot t, as follows xt = PX {xt−1 − α∇x⊤Lt−1(xt−1, λt−1)}, (3.20) where ∇x⊤Lt−1(xt−1, λt−1) = ∇⊤ψt−1(xt−1) + ∇⊤gt−1(xt−1)λt−1, or xt = PX {xt−1 − α∇x⊤Lt−1(xt−1, λt)}, (3.21) where ∇x⊤Lt−1(xt−1, λt) = ∇⊤ψt−1(xt−1) + ∇⊤gt−1(xt−1)λt, and + λt+1 = PRM +N λt + µ∇λLt(xt, λt)}, (3.22) where µ is a positive stepsize, ∇λLt(xt, λt) = gt(xt) − δαλt = bt + Xxx − δαλt. The proposed algorithm is summarized in Algorithm 3.1. Apart from the gradients of the objective function and the constraint function at last time slot t − 1, i.e., ∇⊤ψt−1(xt−1) and ∇⊤gt−1(xt−1), the update of primal variable xt also depends on the dual variable λt−1 which represents the queue status at time slot t− 2 or the dual variable λt which represents the queue status at time slot t− 1. Due to the time-varying and possibly the adversarial environment, we explore Algorithm 3.1 Online Computing Resource Allocation