اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدNear-Optimal Primal-Dual Algorithms for Quantity-Based Network Revenue Management
75
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
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.
قيم البحث
اقرأ أيضاً
Most recent research in network revenue management incorporates choice behavior that models the customers buying logic. These models are consequently more complex to solve, but they return a more robust policy that usually generates better expected r
evenue than an independent-demand model. Choice network revenue management has an exact dynamic programming formulation that rapidly becomes intractable. Approximations have been developed, and many of them are based on the multinomial logit demand model. However, this parametric model has the property known as the independence of irrelevant alternatives and is often replaced in practice by a nonparametric model. We propose a new approximation called the product closing program that is specifically designed for a ranking-based choice model representing a nonparametric demand. Numerical experiments show that our approach quickly returns expected revenues that are slightly better than those of other approximations, especially for large instances. Our approximation can also supply a good initial solution for other approaches.
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.
With the rapid growth in renewable energy and battery storage technologies, there exists significant opportunity to improve energy efficiency and reduce costs through optimization. However, optimization algorithms must take into account the underlyin
g dynamics and uncertainties of the various interconnected subsystems in order to fully realize this potential. To this end, we formulate and solve an energy management optimization problem as a Markov Decision Process (MDP) consisting of battery storage dynamics, a stochastic demand model, a stochastic solar generation model, and an electricity pricing scheme. The stochastic model for predicting solar generation is constructed based on weather forecast data from the National Oceanic and Atmospheric Administration. A near-optimal policy design is proposed via stochastic dynamic programming. Simulation results are presented in the context of storage and solar-integrated residential and commercial building environments. Results indicate that the near-optimal policy significantly reduces the operating costs compared to several heuristic alternatives. The proposed framework facilitates the design and evaluation of energy management policies with configurable demand-supply-storage parameters in the presence of weather-induced uncertainties.
This paper studies the distributed optimization problem where the objective functions might be nondifferentiable and subject to heterogeneous set constraints. Unlike existing subgradient methods, we focus on the case when the exact subgradients of th
e local objective functions can not be accessed by the agents. To solve this problem, we propose a projected primal-dual dynamics using only the objective functions approximate subgradients. We first prove that the formulated optimization problem can only be solved with an approximate error depending upon the accuracy of the available subgradients. Then, we show the exact solvability of this optimization problem if the accumulated approximation error is not too large. After that, we also give a novel componentwise normalized variant to improve the transient behavior of the convergent sequence. The effectiveness of our algorithms is verified by a numerical example.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
