Composite optimization for the resource allocation problem

DOI10.1080/10556788.2020.1712599zbMATH Open1489.90116arXiv1810.00595OpenAlexW3006420746MaRDI QIDQ5085260FDOQ5085260

Authors: Anastasiya Ivanova, Pavel Dvurechensky, Dmitry Kamzolov, Alexander V. Gasnikov 

Publication date: 27 June 2022

Published in: Optimization Methods \& Software (Search for Journal in Brave)

Abstract: In this paper we consider resource allocation problem stated as a convex minimization problem with linear constraints. To solve this problem, we use gradient and accelerated gradient descent applied to the dual problem and prove the convergence rate both for the primal iterates and the dual iterates. We obtain faster convergence rates than the ones known in the literature. We also provide economic interpretation for these two methods. This means that iterations of the algorithms naturally correspond to the process of price and production adjustment in order to obtain the desired production volume in the economy. Overall, we show how these actions of the economic agents lead the whole system to the equilibrium.

Full work available at URL: https://arxiv.org/abs/1810.00595

Recommendations

• Dual subgradient method with averaging for optimal resource allocation
• Optimal scaling of a gradient method for distributed resource allocation
• Numerical methods for the resource allocation problem in a computer network
• Distributed stochastic mirror descent algorithm for resource allocation problem
• scientific article; zbMATH DE number 37746

zbMATH Keywords

gradient methodprimal-dual methodcomposite optimizationaccelerated gradient methoddecentralized pricing

Mathematics Subject Classification ID

Convex programming (90C25) Analysis of algorithms and problem complexity (68Q25) Resource and cost allocation (including fair division, apportionment, etc.) (91B32)

Cites Work

• Distributed optimization and statistical learning via the alternating direction method of multipliers
• Smooth minimization of non-smooth functions
• Title not available (Why is that?)
• Dual Averaging for Distributed Optimization: Convergence Analysis and Network Scaling
• Title not available (Why is that?)
• Distributed Subgradient Methods for Multi-Agent Optimization
• Fast Distributed Gradient Methods
• Title not available (Why is that?)
• The complexity of resource allocation and price mechanisms under bounded rationality
• Dual subgradient method with averaging for optimal resource allocation
• Fast primal-dual gradient method for strongly convex minimization problems with linear constraints
• Dual approaches to the minimization of strongly convex functionals with a simple structure under affine constraints
• Optimal convergence rates for convex distributed optimization in networks
• Mirror descent and convex optimization problems with non-smooth inequality constraints
• Parallel algorithms and probability of large deviation for stochastic convex optimization problems
• Accelerated primal-dual gradient descent with linesearch for convex, nonconvex, and nonsmooth optimization problems
• Universal method of searching for equilibria and stochastic equilibria in transportation networks
• Numerical methods for the resource allocation problem in a computer network

Cited In (8)

• Selective bi-coordinate variations for resource allocation type problems
• Dual subgradient method with averaging for optimal resource allocation
• Numerical methods for the resource allocation problem in a computer network
• Title not available (Why is that?)
• Advances in Information Retrieval
• Alternating minimization methods for strongly convex optimization
• An accelerated decentralized stochastic optimization algorithm with inexact model
• A distributed primal-dual hybrid gradient algorithm for fair resource allocation

This page was built for publication: Composite optimization for the resource allocation problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5085260)