1,720,980 research outputs found
Passivity-based Analysis of the ADMM Algorithm for Constraint-Coupled Optimization
Full text linkWe propose a novel, system theoretic analysis of the Alternating Direction Method of Multipliers (ADMM) applied to a convex constraint-coupled optimization problem. The resulting algorithm can be interpreted as a linear, discrete-time dynamical system (modeling the multiplier ascent update) in closed loop with a static nonlinearity (representing the minimization of the augmented Lagrangian). When expressed in suitable coordinates, we prove that the discrete-time linear dynamical system has a discrete positive-real transfer function and is interconnected in closed loop with a static, passive nonlinearity. This readily shows that the origin is a stable equilibrium for the feedback interconnection. Finally, we also show global asymptotic stability of the origin for the closed-loop system and, thus, global asymptotic convergence of ADMM to the optimal solution of the optimization problem
A Distributed Dual Proximal Minimization Algorithm for Constraint-Coupled Optimization Problems
Full text linkWe address constraint-coupled optimization for a system composed of multiple cooperative agents communicating over a time-varying network. We propose a distributed proximal minimization algorithm that is guaranteed to converge to an optimal solution of the optimization problem, under suitable convexity and connectivity assumptions. The performance of the introduced algorithm is shown on a numerical example of a charging scheduling problem for a fleet of plug-in electric vehicles
Distributed decision-coupled constrained optimization via Proximal-Tracking
Full text linkIn this paper we deal with decision-coupled problems involving multiple agents over a network. Each agent has its own local objective function and local constraints, and all agents aim at finding the value of a common decision vector that minimizes the sum of all agents’ cost functions and satisfies all local constraints. To this purpose, we introduce a Proximal-Tracking distributed optimization algorithm that integrates dynamic average consensus within the proximal minimization method. Convergence to an optimal consensus solution is guaranteed for any value of a constant penalty parameter, under a convexity assumption only, without requiring differentiability, Lipschitz continuity, or smoothness of the local objective functions. Numerical simulations show the effectiveness of the proposed scheme
Lane Change in Automated Driving: An Explicit Coordination Strategy
Full text linkWe address a multi-vehicle automated driving scenario, where a vehicle has to change lane and merge in a platoon in a one-way roadway with two lanes. We focus on the coordination phase of the lane change, where vehicles in the platoon need to create a gap for the merging vehicle to enter safely following a pre-computed optimal trajectory. The goal is pre-computing also the multi-vehicle coordination strategy, so as to limit the computational and communication effort involved in its online implementation. This is achieved by considering the platoon as if it was composed of an infinite number of vehicles and solving a multi-parametric optimization program providing the coordination strategy as an explicit function of position and velocity of the ego vehicle, integrating a multi-class classifier to identify the best merging position. Numerical simulations show that the resulting performance degradation when implementing the strategy on a finite platoon is limited to boundary effects at its head and tail
A decentralized approach to multi-agent MILPs: Finite-time feasibility and performance guarantees
Full text linkWe address the optimization of a large scale multi-agent system where each agent has discrete and/or continuous decision variables that need to be set so as to optimize the sum of linear local cost functions, in presence of linear local and global constraints. The problem reduces to a Mixed Integer Linear Program (MILP) that is here addressed according to a decentralized iterative scheme based on dual decomposition, where each agent determines its decision vector by solving a smaller MILP involving its local cost function and constraint given some dual variable, whereas a central unit enforces the global coupling constraint by updating the dual variable based on the tentative primal solutions of all agents. An appropriate tightening of the coupling constraint through iterations allows to obtain a solution that is feasible for the original MILP. The proposed approach is inspired by a recent paper to the MILP approximate solution via dual decomposition and constraint tightening, but shows finite-time convergence to a feasible solution and provides sharper performance guarantees by means of an adaptive tightening. The two approaches are compared on a plug-in electric vehicles optimal charging problem. (C) 2019 Elsevier Ltd. All rights reserved
Augmented Lagrangian Tracking for distributed optimization with equality and inequality coupling constraints
Full text linkIn this paper we propose a novel Augmented Lagrangian Tracking distributed optimization algorithm for solving multi-agent optimization problems where each agent has its own decision variables, cost function and constraint set, and the goal is to minimize the sum of the agents' cost functions subject to local constraints plus some additional coupling constraint involving the decision variables of all the agents. In contrast to alternative approaches available in the literature, the proposed algorithm jointly features a constant penalty parameter, the ability to cope with unbounded local constraint sets, and the ability to handle both affine equality and nonlinear inequality coupling constraints, while requiring convexity only. The effectiveness of the approach is shown first on an artificial example with complexity features that make other state-of-the-art algorithms not applicable and then on a realistic example involving the optimization of the charging schedule of a fleet of electric vehicles
Hyper-Graph Partitioning for a Multi-Agent Reformulation of Large-Scale MILPs
Full text linkThis letter addresses the challenge of solving large-scale Mixed Integer Linear Programs (MILPs). A resolution scheme is proposed for the class of MILPs with a hidden constraint-coupled multi-agent structure. In particular, we focus on the problem of disclosing such a structure to then apply a computationally efficient decentralized optimization algorithm recently proposed in the literature. The multi-agent reformulation problem consists in manipulating the matrix defining the linear constraints of the MILP so as to put it in a singly-bordered block-angular form, where the blocks define local constraints and decision variables of the agents, whereas the border defines the coupling constraints. We translate the matrix reformulation problem into a hyper-graph partitioning problem and introduce a novel algorithm which accounts for the specific requirements on the singly-bordered block-angular form to best take advantage of the decentralized optimization approach. Numerical results show the effectiveness of the proposed hyper-graph partitioning algorithm
A constrained clustering approach to bounded-error identification of switched and piecewise affine systems
Full text linkThis paper proposes a novel clustering-based approach to the bounded-error identification of switched and piecewise affine autoregressive exogenous systems. We address the problem of determining a minimal collection of linear-in-the-parameters models (called modes) fitting with a given accuracy \eps a set of input-output data while complying with the switched or piecewise affine nature of the system. The problem is tackled by suitably clustering the data according to their preferences with respect to a pool of candidate models identified on subsets of the available data. The preference of a data point for a model is assessed based on the extent to which that model fits that data point and is set to zero if the fit is worse than \eps. A two-level clustering with outliers isolation is employed, first grouping data based on their preferences subject to suitable time/space adjacency conditions depending on the nature of the switching mechanism, and then collecting together non-adjacent clusters that can be described by the same mode. The performance of the proposed method is demonstrated via comparative numerical examples and on experimental data from an electronic component placement process in a pick-and-place machine
Optimal steady-state disturbance compensation for constrained linear systems: the Gaussian noise case
Full text linkWe consider the problem of designing a disturbance compensator for a discrete time linear system, so as to optimize a performance index while satisfying probabilistic state and input constraints in steady-state conditions. The problem is formulated as a chance-constrained program that depends on the compensator parameters through the state and input stationary distributions. In this paper, we focus on the Gaussian noise case and provide an analytic expression of the stationary state distribution as a function of the compensator parameters. This expression can be used in the chance-constrained program, which can then be tackled via the scenario approach. Some useful extensions of the set-up are also discussed to further broaden the applicability of the approach. Performance of the proposed design methodology is shown on a building energy management problem where cyclostationary disturbances are compensated, thus providing a stochastic periodic control solution
Towards a comprehensive framework for V2G optimal operation in presence of uncertainty
Full text linkAs the global fleet of Electric Vehicles keeps increasing in number, the Vehicle To Grid (V2G) paradigm is gaining more and more attention. From the grid point of view an aggregate of electric vehicles can act as a flexible load, thus able to provide balancing services. The problem of computing the optimal day-ahead charging schedule for all vehicles in the fleet is a challenging one, especially because it is affected by many sources of uncertainty. In this paper we consider the uncertainty deriving from arrival and departure times, arrival energy and services market outcomes. We propose a general optimization framework to deal with the day ahead planning that encompasses different kind of use-cases. We adopt a robust paradigm to enforce the constraints and an expectation paradigm for the cost function. For all constraints and cost terms we propose an exact formulation or a very tight approximation, even in the case of piece-wise linear battery dynamics. Numerical results corroborates the theoretical findings
- …
