اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدFast Algorithms for Packing Proportional Fairness and its Dual
50
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
The proportional fair resource allocation problem is a major problem studied in flow control of networks, operations research, and economic theory, where $mathcal{P}$ it has found numerous applications. This problem, defined as the constrained maximization of $sum_ilog x_i$ , is known as the packing proportional fairness problem when the feasible set is defined by positive linear constraints and $x in mathbb{R} geq 0$ . In this work, we present a distributed accelerated first-order method for this problem which improves upon previous approaches. We also design an algorithm for the optimization of its dual problem. Both algorithms are width-independent.
قيم البحث
اقرأ أيضاً
In this paper, we develop efficient randomized algorithms for estimating probabilistic robustness margin and constructing robustness degradation curve for uncertain dynamic systems. One remarkable feature of these algorithms is their universal applic
ability to robustness analysis problems with arbitrary robustness requirements and uncertainty bounding set. In contrast to existing probabilistic methods, our approach does not depend on the feasibility of computing deterministic robustness margin. We have developed efficient methods such as probabilistic comparison, probabilistic bisection and backward iteration to facilitate the computation. In particular, confidence interval for binomial random variables has been frequently used in the estimation of probabilistic robustness margin and in the accuracy evaluation of estimating robustness degradation function. Motivated by the importance of fast computing of binomial confidence interval in the context of probabilistic robustness analysis, we have derived an explicit formula for constructing the confidence interval of binomial parameter with guaranteed coverage probability. The formula overcomes the limitation of normal approximation which is asymptotic in nature and thus inevitably introduce unknown errors in applications. Moreover, the formula is extremely simple and very tight in comparison with classic Clopper-Pearsons approach.
We describe convergence acceleration schemes for multistep optimization algorithms. The extrapolated solution is written as a nonlinear average of the iterates produced by the original optimization method. Our analysis does not need the underlying fi
xed-point operator to be symmetric, hence handles e.g. algorithms with momentum terms such as Nesterovs accelerated method, or primal-dual methods. The weights are computed via a simple linear system and we analyze performance in both online and offline modes. We use Crouzeixs conjecture to show that acceleration performance is controlled by the solution of a Chebyshev problem on the numerical range of a non-symmetric operator modeling the behavior of iterates near the optimum. Numerical experiments are detailed on logistic regression problems.
We consider a generic empirical composition optimization problem, where there are empirical averages present both outside and inside nonlinear loss functions. Such a problem is of interest in various machine learning applications, and cannot be direc
tly solved by standard methods such as stochastic gradient descent. We take a novel approach to solving this problem by reformulating the original minimization objective into an equivalent min-max objective, which brings out all the empirical averages that are originally inside the nonlinear loss functions. We exploit the rich structures of the reformulated problem and develop a stochastic primal-dual algorithm, SVRPDA-I, to solve the problem efficiently. We carry out extensive theoretical analysis of the proposed algorithm, obtaining the convergence rate, the computation complexity and the storage complexity. In particular, the algorithm is shown to converge at a linear rate when the problem is strongly convex. Moreover, we also develop an approximate version of the algorithm, named SVRPDA-II, which further reduces the memory requirement. Finally, we evaluate our proposed algorithms on several real-world benchmarks, and experimental results show that the proposed algorithms significantly outperform existing techniques.
We study the canonical quantity-based network revenue management (NRM) problem where the decision-maker must irrevocably accept or reject each arriving customer request with the goal of maximizing the total revenue given limited resources. The exact
solution to the problem by dynamic programming is computationally intractable due to the well-known curse of dimensionality. Existing works in the literature make use of the solution to the deterministic linear program (DLP) to design asymptotically optimal algorithms. Those algorithms rely on repeatedly solving DLPs to achieve near-optimal regret bounds. It is, however, time-consuming to repeatedly compute the DLP solutions in real time, especially in large-scale problems that may involve hundreds of millions of demand units. In this paper, we propose innovative algorithms for the NRM problem that are easy to implement and do not require solving any DLPs. Our algorithm achieves a regret bound of $O(log k)$, where $k$ is the system size. To the best of our knowledge, this is the first NRM algorithm that (i) has an $o(sqrt{k})$ asymptotic regret bound, and (ii) does not require solving any DLPs.
This paper considers the robust ${cal D}$-stability margin problem under polynomic structured real parametric uncertainty. Based on the work of De Gaston and Safonov (1988), we have developed techniques such as, a parallel frequency sweeping strategy
, different domain splitting schemes, which significantly reduce the computational complexity and guarantee the convergence.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
