-
Efficient Robust Model Predictive Control using Chordality
Authors:
Anders Hansson,
Sina Khoshfetrat Pakazad
Abstract:
In this paper we show that chordal structure can be used to devise efficient optimization methods for robust model predictive control problems. The chordal structure is used both for computing search directions efficiently as well as for distributing all the other computations in an interior-point method for solving the problem. The framework enables efficient parallel computations.
In this paper we show that chordal structure can be used to devise efficient optimization methods for robust model predictive control problems. The chordal structure is used both for computing search directions efficiently as well as for distributing all the other computations in an interior-point method for solving the problem. The framework enables efficient parallel computations.
△ Less
Submitted 20 March, 2018;
originally announced March 2018.
-
Exploiting Chordality in Optimization Algorithms for Model Predictive Control
Authors:
Anders Hansson,
Sina Khoshfetrat Pakazad
Abstract:
In this chapter we show that chordal structure can be used to devise efficient optimization methods for many common model predictive control problems. The chordal structure is used both for computing search directions efficiently as well as for distributing all the other computations in an interior-point method for solving the problem. The chordal structure can stem both from the sequential nature…
▽ More
In this chapter we show that chordal structure can be used to devise efficient optimization methods for many common model predictive control problems. The chordal structure is used both for computing search directions efficiently as well as for distributing all the other computations in an interior-point method for solving the problem. The chordal structure can stem both from the sequential nature of the problem as well as from distributed formulations of the problem related to scenario trees or other formulations. The framework enables efficient parallel computations.
△ Less
Submitted 28 November, 2017;
originally announced November 2017.
-
Distributed, scalable and gossip-free consensus optimization with application to data analysis
Authors:
Sina Khoshfetrat Pakazad,
Christian A. Naesseth,
Fredrik Lindsten,
Anders Hansson
Abstract:
Distributed algorithms for solving additive or consensus optimization problems commonly rely on first-order or proximal splitting methods. These algorithms generally come with restrictive assumptions and at best enjoy a linear convergence rate. Hence, they can require many iterations or communications among agents to converge. In many cases, however, we do not seek a highly accurate solution for c…
▽ More
Distributed algorithms for solving additive or consensus optimization problems commonly rely on first-order or proximal splitting methods. These algorithms generally come with restrictive assumptions and at best enjoy a linear convergence rate. Hence, they can require many iterations or communications among agents to converge. In many cases, however, we do not seek a highly accurate solution for consensus problems. Based on this we propose a controlled relaxation of the coupling in the problem which allows us to compute an approximate solution, where the accuracy of the approximation can be controlled by the level of relaxation. The relaxed problem can be efficiently solved in a distributed way using a combination of primal-dual interior-point methods (PDIPMs) and message-passing. This algorithm purely relies on second-order methods and thus requires far fewer iterations and communications to converge. This is illustrated in numerical experiments, showing its superior performance compared to existing methods.
△ Less
Submitted 10 May, 2017; v1 submitted 6 May, 2017;
originally announced May 2017.
-
Distributed Localization of Tree-structured Scattered Sensor Networks
Authors:
Sina Khoshfetrat Pakazad,
Emre Özkan,
Carsten Fritsche,
Anders Hansson,
Fredrik Gustafsson
Abstract:
Many of the distributed localization algorithms are based on relaxed optimization formulations of the localization problem. These algorithms commonly rely on first-order optimization methods, and hence may require many iterations or communications among computational agents. Furthermore, some of these distributed algorithms put a considerable computational demand on the agents. In this paper, we s…
▽ More
Many of the distributed localization algorithms are based on relaxed optimization formulations of the localization problem. These algorithms commonly rely on first-order optimization methods, and hence may require many iterations or communications among computational agents. Furthermore, some of these distributed algorithms put a considerable computational demand on the agents. In this paper, we show that for tree-structured scattered sensor networks, which are networks that their inter-sensor range measurement graphs have few edges (few range measurements among sensors) and can be represented using a tree, it is possible to devise an efficient distributed localization algorithm that solely relies on second-order methods. Particularly, we apply a state-of-the-art primal-dual interior-point method to a semidefinite relaxation of the maximum-likelihood formulation of the localization problem. We then show how it is possible to exploit the tree-structure in the network and use message-passing or dynamic programming over trees, to distribute computations among different computational agents. The resulting algorithm requires far fewer iterations and communications among agents to converge to an accurate estimate. Moreover, the number of required communications among agents, seems to be less sensitive and more robust to the number of sensors in the network, the number of available measurements and the quality of the measurements. This is in stark contrast to distributed algorithms that rely on first-order methods. We illustrate the performance of our algorithm using experiments based on simulated and real data.
△ Less
Submitted 16 July, 2016;
originally announced July 2016.
-
A Scalable and Distributed Solution to the Inertial Motion Capture Problem
Authors:
Manon Kok,
Sina Khoshfetrat Pakazad,
Thomas B. Schön,
Anders Hansson,
Jeroen D. Hol
Abstract:
In inertial motion capture, a multitude of body segments are equipped with inertial sensors, consisting of 3D accelerometers and 3D gyroscopes. Using an optimization-based approach to solve the motion capture problem allows for natural inclusion of biomechanical constraints and for modeling the connection of the body segments at the joint locations. The computational complexity of solving this pro…
▽ More
In inertial motion capture, a multitude of body segments are equipped with inertial sensors, consisting of 3D accelerometers and 3D gyroscopes. Using an optimization-based approach to solve the motion capture problem allows for natural inclusion of biomechanical constraints and for modeling the connection of the body segments at the joint locations. The computational complexity of solving this problem grows both with the length of the data set and with the number of sensors and body segments considered. In this work, we present a scalable and distributed solution to this problem using tailored message passing, capable of exploiting the structure that is inherent in the problem. As a proof-of-concept we apply our algorithm to data from a lower body configuration.
△ Less
Submitted 18 August, 2016; v1 submitted 21 March, 2016;
originally announced March 2016.
-
Automated Model Generation for Analysis of Large-scale Interconnected Uncertain Systems
Authors:
Farzaneh Karami,
Sina Khoshfetrat Pakazad,
Anders Hansson,
Ahmad Afshar
Abstract:
The first challenge in robustness analysis of large-scale interconnected uncertain systems is to provide a model of such systems in a standard-form that is required within different analysis frameworks. This becomes particularly important for large-scale systems, as analysis tools that can handle such systems heavily rely on the special structure within such model descriptions. We here propose an…
▽ More
The first challenge in robustness analysis of large-scale interconnected uncertain systems is to provide a model of such systems in a standard-form that is required within different analysis frameworks. This becomes particularly important for large-scale systems, as analysis tools that can handle such systems heavily rely on the special structure within such model descriptions. We here propose an automated framework for providing such models of large-scale interconnected uncertain systems that are used in Integral Quadratic Constraint (IQC) analysis. Specifically, in this paper we put forth a methodological way to provide such models from a block-diagram and nested description of interconnected uncertain systems. We describe the details of this automated framework using an example.
△ Less
Submitted 14 December, 2015;
originally announced December 2015.
-
Distributed Semidefinite Programming with Application to Large-scale System Analysis
Authors:
Sina Khoshfetrat Pakazad,
Anders Hansson,
Martin S. Andersen,
Anders Rantzer
Abstract:
Distributed algorithms for solving coupled semidefinite programs (SDPs) commonly require many iterations to converge. They also put high computational demand on the computational agents. In this paper we show that in case the coupled problem has an inherent tree structure, it is possible to devise an efficient distributed algorithm for solving such problems. This algorithm can potentially enjoy th…
▽ More
Distributed algorithms for solving coupled semidefinite programs (SDPs) commonly require many iterations to converge. They also put high computational demand on the computational agents. In this paper we show that in case the coupled problem has an inherent tree structure, it is possible to devise an efficient distributed algorithm for solving such problems. This algorithm can potentially enjoy the same efficiency as centralized solvers that exploit sparsity. The proposed algorithm relies on predictor-corrector primal-dual interior-point methods, where we use a message-passing algorithm to compute the search directions distributedly. Message-passing here is closely related to dynamic programming over trees. This allows us to compute the exact search directions in a finite number of steps. Furthermore this number can be computed a priori and only depends on the coupling structure of the problem. We use the proposed algorithm for analyzing robustness of large-scale uncertain systems distributedly. We test the performance of this algorithm using numerical examples.
△ Less
Submitted 29 April, 2015;
originally announced April 2015.
-
Distributed Primal-dual Interior-point Methods for Solving Loosely Coupled Problems Using Message Passing
Authors:
Sina Khoshfetrat Pakazad,
Anders Hansson,
Martin S. Andersen
Abstract:
In this paper, we propose a distributed algorithm for solving loosely coupled problems with chordal sparsity which relies on primal-dual interior-point methods. We achieve this by distributing the computations at each iteration, using message-passing. In comparison to already existing distributed algorithms for solving such problems, this algorithm requires far less number of iterations to converg…
▽ More
In this paper, we propose a distributed algorithm for solving loosely coupled problems with chordal sparsity which relies on primal-dual interior-point methods. We achieve this by distributing the computations at each iteration, using message-passing. In comparison to already existing distributed algorithms for solving such problems, this algorithm requires far less number of iterations to converge to a solution with high accuracy. Furthermore, it is possible to compute an upper-bound for the number of required iterations which, unlike already existing methods, only depends on the coupling structure in the problem. We illustrate the performance of our proposed method using a set of numerical examples.
△ Less
Submitted 29 June, 2015; v1 submitted 23 February, 2015;
originally announced February 2015.
-
A distributed primal-dual interior-point method for loosely coupled problems using ADMM
Authors:
Mariette Annergren,
Sina Khoshfetrat Pakazad,
Anders Hansson,
Bo Wahlberg
Abstract:
In this paper we propose an efficient distributed algorithm for solving loosely coupled convex optimization problems. The algorithm is based on a primal-dual interior-point method in which we use the alternating direction method of multipliers (ADMM) to compute the primal-dual directions at each iteration of the method. This enables us to join the exceptional convergence properties of primal-dual…
▽ More
In this paper we propose an efficient distributed algorithm for solving loosely coupled convex optimization problems. The algorithm is based on a primal-dual interior-point method in which we use the alternating direction method of multipliers (ADMM) to compute the primal-dual directions at each iteration of the method. This enables us to join the exceptional convergence properties of primal-dual interior-point methods with the remarkable parallelizability of ADMM. The resulting algorithm has superior computational properties with respect to ADMM directly applied to our problem. The amount of computations that needs to be conducted by each computing agent is far less. In particular, the updates for all variables can be expressed in closed form, irrespective of the type of optimization problem. The most expensive computational burden of the algorithm occur in the updates of the primal variables and can be precomputed in each iteration of the interior-point method. We verify and compare our method to ADMM in numerical experiments.
△ Less
Submitted 9 February, 2015; v1 submitted 9 June, 2014;
originally announced June 2014.
-
Distributed Robustness Analysis of Interconnected Uncertain Systems Using Chordal Decomposition
Authors:
Sina Khoshfetrat Pakazad,
Anders Hansson,
Martin S. Andersen,
Anders Rantzer
Abstract:
Large-scale interconnected uncertain systems commonly have large state and uncertainty dimensions. Aside from the heavy computational cost of solving centralized robust stability analysis techniques, privacy requirements in the network can also introduce further issues. In this paper, we utilize IQC analysis for analyzing large-scale interconnected uncertain systems and we evade these issues by de…
▽ More
Large-scale interconnected uncertain systems commonly have large state and uncertainty dimensions. Aside from the heavy computational cost of solving centralized robust stability analysis techniques, privacy requirements in the network can also introduce further issues. In this paper, we utilize IQC analysis for analyzing large-scale interconnected uncertain systems and we evade these issues by describing a decomposition scheme that is based on the interconnection structure of the system. This scheme is based on the so-called chordal decomposition and does not add any conservativeness to the analysis approach. The decomposed problem can be solved using distributed computational algorithms without the need for a centralized computational unit. We further discuss the merits of the proposed analysis approach using a numerical experiment.
△ Less
Submitted 10 February, 2014;
originally announced February 2014.
-
Distributed Interior-point Method for Loosely Coupled Problems
Authors:
Sina Khoshfetrat Pakazad,
Anders Hansson,
Martin S. Andersen
Abstract:
In this paper, we put forth distributed algorithms for solving loosely coupled unconstrained and constrained optimization problems. Such problems are usually solved using algorithms that are based on a combination of decomposition and first order methods. These algorithms are commonly very slow and require many iterations to converge. In order to alleviate this issue, we propose algorithms that co…
▽ More
In this paper, we put forth distributed algorithms for solving loosely coupled unconstrained and constrained optimization problems. Such problems are usually solved using algorithms that are based on a combination of decomposition and first order methods. These algorithms are commonly very slow and require many iterations to converge. In order to alleviate this issue, we propose algorithms that combine the Newton and interior-point methods with proximal splitting methods for solving such problems. Particularly, the algorithm for solving unconstrained loosely coupled problems, is based on Newton's method and utilizes proximal splitting to distribute the computations for calculating the Newton step at each iteration. A combination of this algorithm and the interior-point method is then used to introduce a distributed algorithm for solving constrained loosely coupled problems. We also provide guidelines on how to implement the proposed methods efficiently and briefly discuss the properties of the resulting solutions.
△ Less
Submitted 19 December, 2013;
originally announced December 2013.
-
Robust Stability Analysis of Sparsely Interconnected Uncertain Systems
Authors:
Martin S. Andersen,
Sina Khoshfetrat Pakazad,
Anders Hansson,
Anders Rantzer
Abstract:
In this paper, we consider robust stability analysis of large-scale sparsely interconnected uncertain systems. By modeling the interconnections among the subsystems with integral quadratic constraints, we show that robust stability analysis of such systems can be performed by solving a set of sparse linear matrix inequalities. We also show that a sparse formulation of the analysis problem is equiv…
▽ More
In this paper, we consider robust stability analysis of large-scale sparsely interconnected uncertain systems. By modeling the interconnections among the subsystems with integral quadratic constraints, we show that robust stability analysis of such systems can be performed by solving a set of sparse linear matrix inequalities. We also show that a sparse formulation of the analysis problem is equivalent to the classical formulation of the robustness analysis problem and hence does not introduce any additional conservativeness. The sparse formulation of the analysis problem allows us to apply methods that rely on efficient sparse factorization techniques, and our numerical results illustrate the effectiveness of this approach compared to methods that are based on the standard formulation of the analysis problem.
△ Less
Submitted 11 November, 2013;
originally announced November 2013.
-
Scalable Anomaly Detection in Large Homogenous Populations
Authors:
Henrik Ohlsson,
Tianshi Chen,
Sina Khoshfetrat Pakazad,
Lennart Ljung,
S. Shankar Sastry
Abstract:
Anomaly detection in large populations is a challenging but highly relevant problem. The problem is essentially a multi-hypothesis problem, with a hypothesis for every division of the systems into normal and anomal systems. The number of hypothesis grows rapidly with the number of systems and approximate solutions become a necessity for any problems of practical interests. In the current paper we…
▽ More
Anomaly detection in large populations is a challenging but highly relevant problem. The problem is essentially a multi-hypothesis problem, with a hypothesis for every division of the systems into normal and anomal systems. The number of hypothesis grows rapidly with the number of systems and approximate solutions become a necessity for any problems of practical interests. In the current paper we take an optimization approach to this multi-hypothesis problem. We first observe that the problem is equivalent to a non-convex combinatorial optimization problem. We then relax the problem to a convex problem that can be solved distributively on the systems and that stays computationally tractable as the number of systems increase. An interesting property of the proposed method is that it can under certain conditions be shown to give exactly the same result as the combinatorial multi-hypothesis problem and the relaxation is hence tight.
△ Less
Submitted 20 September, 2013;
originally announced September 2013.
-
Distributed Solutions for Loosely Coupled Feasibility Problems Using Proximal Splitting Methods
Authors:
Sina Khoshfetrat Pakazad,
Martin S. Andersen,
Anders Hansson
Abstract:
In this paper, we consider convex feasibility problems where the underlying sets are loosely coupled, and we propose several algorithms to solve such problems in a distributed manner. These algorithms are obtained by applying proximal splitting methods to convex minimization reformulations of convex feasibility problems. We also put forth distributed convergence tests which enable us to establish…
▽ More
In this paper, we consider convex feasibility problems where the underlying sets are loosely coupled, and we propose several algorithms to solve such problems in a distributed manner. These algorithms are obtained by applying proximal splitting methods to convex minimization reformulations of convex feasibility problems. We also put forth distributed convergence tests which enable us to establish feasibility or infeasibility of the problem distributedly, and we provide convergence rate results. Under the assumption that the problem is feasible and boundedly linearly regular, these convergence results are given in terms of the distance of the iterates to the feasible set, which are similar to those of classical projection methods. In case the feasibility problem is infeasible, we provide convergence rate results that concern the convergence of certain error-bounds.
△ Less
Submitted 28 June, 2013;
originally announced June 2013.
-
Distributed Robust Stability Analysis of Interconnected Uncertain Systems
Authors:
Martin S. Andersen,
Anders Hansson,
Sina Khoshfetrat Pakazad,
Anders Rantzer
Abstract:
This paper considers robust stability analysis of a large network of interconnected uncertain systems. To avoid analyzing the entire network as a single large, lumped system, we model the network interconnections with integral quadratic constraints. This approach yields a sparse linear matrix inequality which can be decomposed into a set of smaller, coupled linear matrix inequalities. This allows…
▽ More
This paper considers robust stability analysis of a large network of interconnected uncertain systems. To avoid analyzing the entire network as a single large, lumped system, we model the network interconnections with integral quadratic constraints. This approach yields a sparse linear matrix inequality which can be decomposed into a set of smaller, coupled linear matrix inequalities. This allows us to solve the analysis problem efficiently and in a distributed manner. We also show that the decomposed problem is equivalent to the original robustness analysis problem, and hence our method does not introduce additional conservativeness.
△ Less
Submitted 6 November, 2012;
originally announced November 2012.