skip to main content

Attention:

The NSF Public Access Repository (PAR) system and access will be unavailable from 11:00 PM ET on Thursday, February 13 until 2:00 AM ET on Friday, February 14 due to maintenance. We apologize for the inconvenience.


Title: Fast and Stable Nonconvex Constrained Distributed Optimization: The ELLADA Algorithm
Distributed optimization, where the computations are performed in a localized and coordinated manner using multiple agents, is a promising approach for solving large-scale optimization problems, e.g., those arising in model predictive control (MPC) of large-scale plants. However, a distributed optimization algorithm that is computationally efficient, globally convergent, amenable to nonconvex constraints and general inter-subsystem interactions remains an open problem. In this paper, we combine three important modifications to the classical alternating direction method of multipliers (ADMM) for distributed optimization. Specifically, (i) an extra-layer architecture is adopted to accommodate nonconvexity and handle inequality constraints, (ii) equality-constrained nonlinear programming (NLP) problems are allowed to be solved approximately, and (iii) a modified Anderson acceleration is employed for reducing the number of iterations. Theoretical convergence towards stationary solutions and computational complexity of the proposed algorithm, named ELLADA, is established. Its application to distributed nonlinear MPC is also described and illustrated through a benchmark process system.  more » « less
Award ID(s):
1926303
PAR ID:
10197996
Author(s) / Creator(s):
;
Date Published:
Journal Name:
ArXivorg
ISSN:
2331-8422
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. Abstract

    Model predictive control (MPC) for nonlinear systems involves a nonlinear dynamic optimization (NDO) step, which is required to be solved repeatedly. This step is computationally demanding, specially in dealing with constrained and/or nonlinear large‐scale systems. This paper presents a method for accelerating the NDO in state‐feedback regulation problems. Exploiting Carleman approximation, this method represents the nonlinear dynamics in a bilinear form and discretizes the resulting system in the time domain. The gradient and Hessian of the cost function with respect to the feedback gains are also analytically derived. The Carleman approximation of the nonlinear system may introduce errors in the prediction and sensitivity analysis. The manuscript derives a criterion under which the input‐to‐state stability of the new design is guaranteed. The proposed MPC is implemented in a chemical reactor example. Simulation results show that replacing conventional MPC schemes by the presented method reduces the computation time by an order of magnitude.

     
    more » « less
  2. Over the past decade, there has been increasing interest in distributed/parallel algorithms for processing large-scale graphs. By now, we have quite fast algorithms---usually sublogarithmic-time and often poly(łogłog n)-time, or even faster---for a number of fundamental graph problems in the massively parallel computation (MPC) model. This model is a widely-adopted theoretical abstraction of MapReduce style settings, where a number of machines communicate in an all-to-all manner to process large-scale data. Contributing to this line of work on MPC graph algorithms, we present poly(łog k) ε poly(łogłog n) round MPC algorithms for computing O(k^1+o(1) )-spanners in the strongly sublinear regime of local memory. To the best of our knowledge, these are the first sublogarithmic-time MPC algorithms for spanner construction. As primary applications of our spanners, we get two important implications, as follows: -For the MPC setting, we get an O(łog^2łog n)-round algorithm for O(łog^1+o(1) n) approximation of all pairs shortest paths (APSP) in the near-linear regime of local memory. To the best of our knowledge, this is the first sublogarithmic-time MPC algorithm for distance approximations. -Our result above also extends to the Congested Clique model of distributed computing, with the same round complexity and approximation guarantee. This gives the first sub-logarithmic algorithm for approximating APSP in weighted graphs in the Congested Clique model. 
    more » « less
  3. We consider a class of multi-agent cooperative consensus optimization problems with local nonlinear convex constraints where only those agents connected by an edge can directly communicate, hence, the optimal consensus decision lies in the intersection of these private sets. We develop an asynchronous distributed accelerated primal-dual algorithm to solve the considered problem. The proposed scheme is the first asynchronous method with an optimal convergence guarantee for this class of problems, to the best of our knowledge. In particular, we provide an optimal convergence rate of $\mathcal O(1/K)$ for suboptimality, infeasibility, and consensus violation. 
    more » « less
  4. This paper develops a closed-loop approach for ink-jet 3D printing. The control design is based on a distributed model predictive control scheme, which can handle constraints (such as droplet volume) as well as the large-scale nature of the problem. The high resolution of ink-jet 3D printing make centralized methods extremely time-consuming, thus a distributed implementation of the controller is developed. First a graph-based height evolution model that can capture the liquid flow dynamics is proposed. Then, a scalable closed-loop control algorithm is designed based on the model using Distributed MPC, that reduces computation time significantly. The performance and efficiency of the algorithm are shown to outperform open-loop printing and closed-loop printing with existing Centralized MPC methods through simulation results. 
    more » « less
  5. Nonlinear optimization problems arise in all industries. Accelerating optimization solvers is desirable. Efforts have been made to accelerate interior point methods for large scale problems. However, since the interior point algorithm used requires many function evaluations, the acceleration of the algorithm becomes less beneficial. We introduce a way to accelerate the sequential quadratic programming method, which is characterized by minimizing function evaluations, on graphical processing units. 
    more » « less