Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userDistributed and Asynchronous Algorithms for N-block Convex Optimization with Coupling Constraints
118
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
This paper first proposes an N-block PCPM algorithm to solve N-block convex optimization problems with both linear and nonlinear constraints, with global convergence established. A linear convergence rate under the strong second-order conditions for optimality is observed in the numerical experiments. Next, for a starting point, an asynchronous N-block PCPM algorithm is proposed to solve linearly constrained N-block convex optimization problems. The numerical results demonstrate the sub-linear convergence rate under the bounded delay assumption, as well as the faster convergence with more short-time iterations than a synchronous iterative scheme.
rate research
Read More
This paper considers a distributed convex optimization problem over a time-varying multi-agent network, where each agent has its own decision variables that should be set so as to minimize its individual objective subject to local constraints and global coupling equality constraints. Over directed graphs, a distributed algorithm is proposed that incorporates the push-sum protocol into dual subgradient methods. Under the convexity assumption, the optimality of primal and dual variables, and constraint violations is first established. Then the explicit convergence rates of the proposed algorithm are obtained. Finally, some numerical experiments on the economic dispatch problem are provided to demonstrate the efficacy of the proposed algorithm.
Large scale, non-convex optimization problems arising in many complex networks such as the power system call for efficient and scalable distributed optimization algorithms. Existing distributed methods are usually iterative and require synchronization of all workers at each iteration, which is hard to scale and could result in the under-utilization of computation resources due to the heterogeneity of the subproblems. To address those limitations of synchronous schemes, this paper proposes an asynchronous distributed optimization method based on the Alternating Direction Method of Multipliers (ADMM) for non-convex optimization. The proposed method only requires local communications and allows each worker to perform local updates with information from a subset of but not all neighbors. We provide sufficient conditions on the problem formulation, the choice of algorithm parameter and network delay, and show that under those mild conditions, the proposed asynchronous ADMM method asymptotically converges to the KKT point of the non-convex problem. We validate the effectiveness of asynchronous ADMM by applying it to the Optimal Power Flow problem in multiple power systems and show that the convergence of the proposed asynchronous scheme could be faster than its synchronous counterpart in large-scale applications.
The paper considers the minimization of a separable convex function subject to linear ascending constraints. The problem arises as the core optimization in several resource allocation scenarios, and is a special case of an optimization of a separable convex function over the bases of a polymatroid with a certain structure. The paper presents a survey of state-of-the-art algorithms that solve this optimization problem. The algorithms are applicable to the class of separable convex objective functions that need not be smooth or strictly convex. When the objective function is a so-called $d$-separable function, a simpler linear time algorithm solves the problem.
Optimization models with non-convex constraints arise in many tasks in machine learning, e.g., learning with fairness constraints or Neyman-Pearson classification with non-convex loss. Although many efficient methods have been developed with theoretical convergence guarantees for non-convex unconstrained problems, it remains a challenge to design provably efficient algorithms for problems with non-convex functional constraints. This paper proposes a class of subgradient methods for constrained optimization where the objective function and the constraint functions are are weakly convex. Our methods solve a sequence of strongly convex subproblems, where a proximal term is added to both the objective function and each constraint function. Each subproblem can be solved by various algorithms for strongly convex optimization. Under a uniform Slaters condition, we establish the computation complexities of our methods for finding a nearly stationary point.
Distributed coordination algorithms (DCA) carry out information processing processes among a group of networked agents without centralized information fusion. Though it is well known that DCA characterized by an SIA (stochastic, indecomposable, aperiodic) matrix generate consensus asymptotically via synchronous iterations, the dynamics of DCA with asynchronous iterations have not been studied extensively, especially when viewed as stochastic processes. This paper aims to show that for any given irreducible stochastic matrix, even non-SIA, the corresponding DCA lead to consensus successfully via random asynchronous iterations under a wide range of conditions on the transition probability. Particularly, the transition probability is neither required to be independent and identically distributed, nor characterized by a Markov chain.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
