Operating distributed Scrubbing Centers (SCs) to mitigate massive Distributed Denial of Service (DDoS) traffic in large-scale networks faces critical challenges. The operator needs to determine the diversion rule installation and elimination in the networks, as well as the scrubbing resource activation and revocation in the SCs, while minimizing the long-term cost and the cumulative decision-switching penalty without knowing the exact amount of the malicious traffic. We model and formulate this problem as an online nonlinear integer program. In contrast to many other online problems where future inputs are unknown but at least current inputs are known, a key new challenge here is that even part of the current inputs are unknown when decisions are made. To learn the best decisions online, we transform our problem via a gap-preserving approximation into an online optimization problem with only the known inputs, which is further relaxed and decoupled into a series of one-shot convex programs solvable in individual time slots. To overcome the intractability, we design a progressive rounding algorithm to convert fractional decisions into integral ones without violating the constraints. We characterize the competitive ratio of our approach as a function of the key parameters of our problem. We conduct evaluations using real-world data and confirm our algorithms’ superiority over de facto practices and state-of-the-art methods
more »
« less
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
- NSF-PAR ID:
- 10197996
- Date Published:
- Journal Name:
- ArXivorg
- ISSN:
- 2331-8422
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
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
-
Distributed optimization algorithms are proposed to, potentially, reduce the computational time of large-scale optimization problems, such as security-constrained economic dispatch (SCED). While various geographical decomposition strategies have been presented in the literature, we proposed a temporal decomposition strategy to divide the SCED problem over the considered scheduling horizon. The proposed algorithm breaks SCED over the scheduling time and takes advantage of parallel computing using multi-core machines. In this paper, we investigate how to partition the overall time horizon. We study the effect of the number of partitions (i.e., SCED subproblems) on the overall performance of the distributed coordination algorithm and the effect of partitioning time interval on the optimal solution. In addition, the impact of system loading condition and ramp limits of the generating units on the number of iterations and solution time are analyzed. The results show that by increasing the number of subproblems, the computational burden of each subproblem is reduced, but more shared variables and constraints need to be modeled between the subproblems. This can result in increasing the total number of iterations and consequently the solution time. Moreover, since the load behavior affects the active ramping between the subproblems, the breaking hour determines the difference between shared variables. Hence, the optimal number of subproblems is problem dependent. A 3-bus and the IEEE 118-bus system are selected to analyze the effect of the number of partitions.more » « less
-
more » « less
Abstract This paper aims to develop distributed algorithms for nonconvex optimization problems with complicated constraints associated with a network. The network can be a physical one, such as an electric power network, where the constraints are nonlinear power flow equations, or an abstract one that represents constraint couplings between decision variables of different agents. Despite the recent development of distributed algorithms for nonconvex programs, highly complicated constraints still pose a significant challenge in theory and practice. We first identify some difficulties with the existing algorithms based on the alternating direction method of multipliers (ADMM) for dealing with such problems. We then propose a reformulation that enables us to design a two-level algorithm, which embeds a specially structured three-block ADMM at the inner level in an augmented Lagrangian method framework. Furthermore, we prove the global and local convergence as well as iteration complexity of this new scheme for general nonconvex constrained programs, and show that our analysis can be extended to handle more complicated multi-block inner-level problems. Finally, we demonstrate with computation that the new scheme provides convergent and parallelizable algorithms for various nonconvex applications, and is able to complement the performance of the state-of-the-art distributed algorithms in practice by achieving either faster convergence in optimality gap or in feasibility or both.
-
Feedback control design using model predictive control formulation and Carleman approximation methodmore » « less
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.
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- The DOI is not currently available.
