1,720,988 research outputs found
Randomized dual proximal gradient for large-scale distributed optimization
Full text linkIn this paper we consider distributed optimization problems in which the cost
function is separable (i.e., a sum of possibly non-smooth functions all
sharing a common variable) and can be split into a strongly convex term and a
convex one. The second term is typically used to encode constraints or to
regularize the solution. We propose an asynchronous, distributed optimization
algorithm over an undirected topology, based on a proximal gradient update on
the dual problem. We show that by means of a proper choice of primal
variables, the dual problem is separable and the dual variables can be stacked
into separate blocks. This allows us to show that a distributed
gossip update can be obtained by means of a randomized block-coordinate
proximal gradient on the dual function
A randomized primal distributed algorithm for partitioned and big-data non-convex optimization
Full text linkIn this paper we consider a distributed opti- mization scenario in which the aggregate objective function to minimize is partitioned, big-data and possibly non-convex. Specifically, we focus on a set-up in which the dimension of the decision variable depends on the network size as well as the number of local functions, but each local function handled by a node depends only on a (small) portion of the entire optimiza- tion variable. This problem set-up has been shown to appear in many interesting network application scenarios. As main paper contribution, we develop a simple, primal distributed algorithm to solve the optimization problem, based on a randomized descent approach, which works under asynchronous gossip communication. We prove that the proposed asynchronous algorithm is a proper, ad-hoc version of a coordinate descent method and thus converges to a stationary point. To show the effectiveness of the proposed algorithm, we also present numerical simulations on a non-convex quadratic program, which confirm the theoretical results
Asynchronous Distributed Optimization Via Randomized Dual Proximal Gradient
Full text linkIn this paper we consider distributed optimization problems in which the cost function is separable, i.e., a sum of possibly non-smooth functions all sharing a common variable, and can be split into a strongly convex term and a convex one. The second term is typically used to encode constraints or to regularize the solution. We propose a class of distributed optimization algorithms based on proximal gradient methods applied to the dual problem. We show that, by choosing suitable primal variable copies, the dual problem is itself separable when written in terms of conjugate functions, and the dual variables can be stacked into non-overlapping blocks associated to the computing nodes. We first show that a weighted proximal gradient on the dual function leads to a synchronous distributed algorithm with local dual proximal gradient updates at each node. Then, as main paper contribution, we develop asynchronous versions of the algorithm in which the node updates are triggered by local timers without any global iteration counter. The algorithms are shown to be proper randomized block-coordinate proximal gradient updates on the dual function
Nonconvex Big-Data Optimization via System Theory: a Block-wise Incremental Gradient Method
Full text linkIn this paper, we propose and analyze Block-wise Incremental Gradient with Averaging (BIG-A), i.e., a novel optimization algorithm tailored for large-scale and bigdata nonconvex optimization problems with a composite cost function. At each iteration, the algorithm uses a block of a single function gradient to properly update auxiliary variables providing a proxy of a descent direction. We interpret BIG-A as a dynamical system arising from the interconnection between a fast, time-varying scheme and a slow, time-invariant one. This interpretation allows us to prove the convergence properties by using system theory results relying on the LaSalle-Yoshizawa invariance principle and singular perturbations. The solution estimate sequence generated by BIG-A is shown to converge toward the set of stationary points of the problem, which is not assumed to be convex nor satisfying the Polyak-Łojasiewicz condition. If strong convexity is also assumed, linear convergence toward the unique optimal solution is established. Finally, numerical simulations confirm the theoretical findings
A duality-based approach for distributed min-max optimization with application to demand side management
Full text linkIn this paper we consider a distributed optimiza- tion scenario in which a set of processors aims at minimizing the maximum of a collection of “separable convex functions” subject to local constraints. This set-up is motivated by peak- demand minimization problems in smart grids. Here, the goal is to minimize the peak value over a finite horizon with: (i) the demand at each time instant being the sum of contributions from different devices, and (ii) the local states at different time instants being coupled through local dynamics. The min-max structure and the double coupling (through the devices and over the time horizon) makes this problem challenging in a distributed set-up (e.g., well-known distributed dual decompo- sition approaches cannot be applied). We propose a distributed algorithm based on the combination of duality methods and properties from min-max optimization. Specifically, we derive a series of equivalent problems by introducing ad-hoc slack variables and by going back and forth from primal and dual formulations. On the resulting problem we apply a dual sub- gradient method, which turns out to be a distributed algorithm. We prove the correctness of the proposed algorithm and show its effectiveness via numerical computation
Distributed Optimization for Smart Cyber-Physical Networks
Full text linkThe presence of embedded electronics and communication capabilities as well as sensing and control in smart devices has given rise to the novel concept of cyber-physical networks, in which agents aim at cooperatively solving complex tasks by local computation and communication. Numerous estimation, learning, decision and control tasks in smart networks involve the solution of large-scale, structured optimization problems in which network agents have only a partial knowledge of the whole problem. Distributed optimization aims at designing local computation and communication rules for the network processors allowing them to cooperatively solve the global optimization problem without relying on any central unit. The purpose of this survey is to provide an introduction to distributed optimization methodologies. Principal approaches, namely (primal) consensus-based, duality-based and constraint exchange methods, are formalized. An analysis of the basic schemes is supplied, and state-of-the-art extensions are reviewed
Distributed Stochastic Dual Subgradient for Constraint-Coupled Optimization
Full text linkIn this paper we consider a distributed stochastic optimization framework in which agents in a network aim to cooperatively learn an optimal network-wide policy. The goal is to compute local functions to minimize the expected value of a given cost, subject to individual constraints and average coupling constraints. In order to handle the challenges of the distributed stochastic context, we resort to a Lagrangian duality approach that allows us to derive an associated stochastic dual problem with a separable structure. Thus, we propose a distributed algorithm, without a central coordinator, that exploits consensus iterations and stochastic approximation to find an optimal solution to the problem, with attractive scalability properties. We demonstrate convergence of the proposed scheme and validate its behavior through simulations
A randomized primal distributed algorithm for partitioned and big-data non-convex optimization
No full text- …
