اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدNetwork Utility Maximization Revisited: Three Issues and Their Resolution
145
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
Distributed and iterative network utility maximization algorithms, such as the primal-dual algorithms or the network-user decomposition algorithms, often involve trajectories where the iterates may be infeasible, convergence to the optimal points of relaxed problems different from the original, or convergence to local maxima. In this paper, we highlight the three issues with iterative algorithms. We then propose a distributed and iterative algorithm that does not suffer from the three issues. In particular, we assert the feasibility of the algorithms iterates at all times, convergence to the global maximum of the given problem (rather than to global maximum of a relaxed problem), and avoidance of any associated spurious rest points of the dynamics. A benchmark algorithm due to Kelly, Maulloo and Tan (1998) [Rate control for communication networks: shadow prices, proportional fairness and stability, Journal of the Operational Research Society, 49(3), 237-252] involves fast user updates coupled with slow network updates in the form of additive-increase multiplicative-decrease of suggested user flows. The proposed algorithm may be viewed as one with fast user updates and fast network updates that keeps the iterates feasible at all times. Simulations suggest that the convergence rate of the ordinary differential equation (ODE) tracked by our proposed algorithms iterates is comparable to that of the ODE for the aforementioned benchmark algorithm.
قيم البحث
اقرأ أيضاً
We consider the Network Utility Maximization (NUM) problem for wireless networks in the presence of arbitrary types of flows, including unicast, broadcast, multicast, and anycast traffic. Building upon the recent framework of a universal control poli
cy (UMW), we design a utility optimal cross-layer admission control, routing and scheduling policy, called UMW+. The UMW+ policy takes packet level actions based on a precedence-relaxed virtual network. Using Lyapunov optimization techniques, we show that UMW+ maximizes network utility, while simultaneously keeping the physical queues in the network stable. Extensive simulation results validate the performance of UMW+; demonstrating both optimal utility performance and bounded average queue occupancy. Moreover, we establish a precise one-to-one correspondence between the dynamics of the virtual queues under the UMW+ policy, and the dynamics of the dual variables of an associated offline NUM program, under a subgradient algorithm. This correspondence sheds further insight into our understanding of UMW+.
Most existing work uses dual decomposition and subgradient methods to solve Network Utility Maximization (NUM) problems in a distributed manner, which suffer from slow rate of convergence properties. This work develops an alternative distributed Newt
on-type fast converging algorithm for solving network utility maximization problems with self-concordant utility functions. By using novel matrix splitting techniques, both primal and dual updates for the Newton step can be computed using iterative schemes in a decentralized manner with limited information exchange. Similarly, the stepsize can be obtained via an iterative consensus-based averaging scheme. We show that even when the Newton direction and the stepsize in our method are computed within some error (due to finite truncation of the iterative schemes), the resulting objective function value still converges superlinearly to an explicitly characterized error neighborhood. Simulation results demonstrate significant convergence rate improvement of our algorithm relative to the existing subgradient methods based on dual decomposition.
In this paper, we present two completely uncoupled algorithms for utility maximization. In the first part, we present an algorithm that can be applied for general non-concave utilities. We show that this algorithm induces a perturbed (by $epsilon$) M
arkov chain, whose stochastically stable states are the set of actions that maximize the sum utility. In the second part, we present an approximate sub-gradient algorithm for concave utilities which is considerably faster and requires lesser memory. We study the performance of the sub-gradient algorithm for decreasing and fixed step sizes. We show that, for decreasing step sizes, the Cesaro averages of the utilities converges to a neighbourhood of the optimal sum utility. For constant step size, we show that the time average utility converges to a neighbourhood of the optimal sum utility. Our main contribution is the expansion of the achievable rate region, which has been not considered in the prior literature on completely uncoupled algorithms for utility maximization. This expansion aids in allocating a fair share of resources to the nodes which is important in applications like channel selection, user association and power control.
This paper addresses the problem of utility maximization under uncertain parameters. In contrast with the classical approach, where the parameters of the model evolve freely within a given range, we constrain them via a penalty function. We show that
this robust optimization process can be interpreted as a two-player zero-sum stochastic differential game. We prove that the value function satisfies the Dynamic Programming Principle and that it is the unique viscosity solution of an associated Hamilton-Jacobi-Bellman-Isaacs equation. We test this robust algorithm on real market data. The results show that robust portfolios generally have higher expected utilities and are more stable under strong market downturns. To solve for the value function, we derive an analytical solution in the logarithmic utility case and obtain accurate numerical approximations in the general case by three methods: finite difference method, Monte Carlo simulation, and Generative Adversarial Networks.
We consider the problem of maximizing aggregate user utilities over a multi-hop network, subject to link capacity constraints, maximum end-to-end delay constraints, and user throughput requirements. A users utility is a concave function of the achiev
ed throughput or the experienced maximum delay. The problem is important for supporting real-time multimedia traffic, and is uniquely challenging due to the need of simultaneously considering maximum delay constraints and throughput requirements. We first show that it is NP-complete either (i) to construct a feasible solution strictly meeting all constraints, or (ii) to obtain an optimal solution after we relax maximum delay constraints or throughput requirements up to constant ratios. We then develop a polynomial-time approximation algorithm named PASS. The design of PASS leverages a novel understanding between non-convex maximum-delay-aware problems and their convex average-delay-aware counterparts, which can be of independent interest and suggest a new avenue for solving maximum-delay-aware network optimization problems. Under realistic conditions, PASS achieves constant or problem-dependent approximation ratios, at the cost of violating maximum delay constraints or throughput requirements by up to constant or problem-dependent ratios. PASS is practically useful since the conditions for PASS are satisfied in many popular application scenarios. We empirically evaluate PASS using extensive simulations of supporting video-conferencing traffic across Amazon EC2 datacenters. Compared to existing algorithms and a conceivable baseline, PASS obtains up to $100%$ improvement of utilities, by meeting the throughput requirements but relaxing the maximum delay constraints that are acceptable for practical video conferencing applications.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
