BZPEERReading, trust and collaboration for research
Menu

Discover

GraphFollow connections around a paper, topic or saved view.

Workspaces

HomePick up where your research flow left off.InboxHandle requests, replies and notifications from one place.CollectionsCurate reading lists, evidence sets and shareable dossiers.ResearchSee your private provenance graph, trail and imports.CollaborationMove from discovery into focused discussion rooms.PublishDraft, preview and publish full-text research articles.

Network

ExpertsFind specialists worth following or asking for help.CommunitiesJoin research circles organized around shared work.PartnersSee external organizations active around the same topics.

Opportunities

ListingsBrowse roles, calls and collaborations with clearer fit signals.

Account

Log inReturn to your reading and collaboration workspace.Create accountStart saving work, following people and joining teams.
Log inCreate account

Researcher profile

Antonis Papachristodoulou

Antonis Papachristodoulou contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
math.OCSystems and Controleess.SYMultiagent Systems

Trust snapshot

Quick read

Trust 21 - EmergingVerification L1Unclaimed author
20works
0followers
4topics
4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Identity and collaboration

How to connect with this researcher

Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.

Log in to claim

Direct collaboration

Open a focused conversation when the fit is right

Claim this author entity first to unlock direct invitations.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

20 published item(s)

preprint2022arXiv

A Time-Triggered Dimension Reduction Algorithm for the Task Assignment Problem

The task assignment problem is fundamental in combinatorial optimisation, aiming at allocating one or more tasks to a number of agents while minimizing the total cost or maximizing the overall assignment benefit. This problem is known to be computationally hard since it is usually formulated as a mixed-integer programming problem. In this paper, we consider a novel time-triggered dimension reduction algorithm (TTDRA). We propose convexification approaches to convexify both the constraints and the cost function for the general non-convex assignment problem. The computational speed is accelerated via our time-triggered dimension reduction scheme, where the triggering condition is designed based on the optimality tolerance and the convexity of the cost function. Optimality and computational efficiency are verified via numerical simulations on benchmark examples.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Block Factor-width-two Matrices and Their Applications to Semidefinite and Sum-of-squares Optimization

Semidefinite and sum-of-squares (SOS) optimization are fundamental computational tools in many areas, including linear and nonlinear systems theory. However, the scale of problems that can be addressed reliably and efficiently is still limited. In this paper, we introduce a new notion of block factor-width-two matrices and build a new hierarchy of inner and outer approximations of the cone of positive semidefinite (PSD) matrices. This notion is a block extension of the standard factor-width-two matrices, and allows for an improved inner-approximation of the PSD cone. In the context of SOS optimization, this leads to a block extension of the scaled diagonally dominant sum-of-squares (SDSOS) polynomials. By varying a matrix partition, the notion of block factor-width-two matrices can balance a trade-off between the computation scalability and solution quality for solving semidefinite and SOS optimization problems. Numerical experiments on a range of large-scale instances confirm our theoretical findings.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Explicit Solutions for Safety Problems Using Control Barrier Functions

The control Barrier function approach has been widely used for safe controller synthesis. By solving an online convex quadratic programming problem, an optimal safe controller can be synthesized implicitly in state-space. Since the solution is unique, the mapping from state-space to control inputs is injective, thus enabling us to evaluate the underlying relationship. In this paper we aim at explicitly synthesizing a safe control law as a function of the state for nonlinear control-affine systems with limited control ability. We propose to transform the online quadratic programming problem into an offline parameterized optimisation problem which considers states as parameters. The obtained explicit safe controller is shown to be a piece-wise Lipschitz continuous function over the partitioned state space if the program is feasible. We address the infeasible cases by solving a parameterized adaptive control Barrier function-based quadratic programming problem. Extensive simulation results show the state-space partition and the controller properties.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

On the exact feasibility of convex scenario programs with discarded constraints

We revisit the so-called sampling and discarding approach used to quantify the probability of constraint violation of a solution to convex scenario programs when some of the original samples are allowed to be discarded. Motivated by two scenario programs that possess analytic solutions and the fact that the existing bound for scenario programs with discarded constraints is not tight, we analyze a removal scheme that consists of a cascade of optimization problems, where at each step we remove a superset of the active constraints. By relying on results from compression learning theory, we show that such a removal scheme leads to less conservative bounds for the probability of constraint violation than the existing ones. We also show that the proposed bound is tight by characterizing a class of optimization problems that achieves the given upper bound. The performance improvement of the proposed methodology is illustrated by an example that involves a resource sharing linear program.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Safety Verification and Controller Synthesis for Systems with Input Constraints

In this paper we consider the safety verification and safe controller synthesis problems for nonlinear control systems. The Control Barrier Certificates (CBC) approach is proposed as an extension to the Barrier certificates approach. Our approach can be used to characterize the control invariance of a given set in terms of safety of a general nonlinear control system subject to input constraints. From the point of view of controller design, the proposed method provides an approach to synthesize a safe control law that guarantees that the trajectories of the system starting from a given initial set do not enter an unsafe set. Unlike the related control Barrier functions approach, our formulation only considers the vector field within the tangent cone of the zero level set defined by the certificates, and is shown to be less conservative by means of numerical evidence. For polynomial systems with semi-algebraic initial and safe sets, CBCs and safe control laws can be synthesized using sum-of-squares decomposition and semi-definite programming. Examples demonstrate our method.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Sparse Polynomial Optimisation for Neural Network Verification

The prevalence of neural networks in society is expanding at an increasing rate. It is becoming clear that providing robust guarantees on systems that use neural networks is very important, especially in safety-critical applications. A trained neural network's sensitivity to adversarial attacks is one of its greatest shortcomings. To provide robust guarantees, one popular method that has seen success is to bound the activation functions using equality and inequality constraints. However, there are numerous ways to form these bounds, providing a trade-off between conservativeness and complexity. Depending on the complexity of these bounds, the computational time of the optimisation problem varies, with longer solve times often leading to tighter bounds. We approach the problem from a different perspective, using sparse polynomial optimisation theory and the Positivstellensatz, which derives from the field of real algebraic geometry. The former exploits the natural cascading structure of the neural network using ideas from chordal sparsity while the later asserts the emptiness of a semi-algebraic set with a nested family of tests of non-decreasing accuracy to provide tight bounds. We show that bounds can be tightened significantly, whilst the computational time remains reasonable. We compare the solve times of different solvers and show how the accuracy can be improved at the expense of increased computation time. We show that by using this sparse polynomial framework the solve time and accuracy can be improved over other methods for neural network verification with ReLU, sigmoid and tanh activation functions.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Stability of Non-linear Neural Feedback Loops using Sum of Squares

Neural network controllers have the potential to improve the performance of feedback systems compared to traditional controllers, due to their ability to act as general function approximators. However, quantifying their safety and robustness properties has proven challenging due to the non-linearities of the activation functions inside the neural network. A key robustness indicator is certifying the stability properties of the feedback system and providing a region of attraction, which has been addressed in previous literature. However, these works only address linear systems or require one to abstract the plant non-linearities and bound them using slope and sector constraints. In this paper we use a Sum of Squares programming framework to compute the stability of non-linear systems with neural network controllers directly. Within this framework, we can propose higher order candidate Lyapunov functions with richer structures that are able to better capture the dynamics of the non-linear system and the nonlinearities in the neural network. We are also able to analyse these systems in continuous time, whereas other methods rely on discretising the system. These higher order Lyapunov functions are used in conjunction with higher order multipliers on the inequality and equality constraints that bound the neural network input-output properties. The volume of the region of attraction computed is increased compared to other methods, allowing for better safety guarantees on the stability of the system. We are also able to easily analyse non-linear polynomial systems, which is not possible to do with other methods. We are also able to conduct robustness analysis on the parameter uncertainty. We show the benefits of our method using numerical examples.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Control Reconfiguration of Dynamical Systems for Improved Performance via Reverse- and Forward-engineering

This paper presents a control reconfiguration approach to improve the performance of two classes of dynamical systems. Motivated by recent research on re-engineering cyber-physical systems, we propose a three-step control retrofit procedure. First, we reverse-engineer a dynamical system to dig out an optimization problem it actually solves. Second, we forward-engineer the system by applying a corresponding faster algorithm to solve this optimization problem. Finally, by comparing the original and accelerated dynamics, we obtain the implementation of the redesigned part (the extra dynamics). As a result, the convergence rate/speed or transient behavior of the given system can be improved while the system control structure is maintained. Internet congestion control and distributed proportional-integral (PI) control, as applications in the two different classes of target systems, are used to show the effectiveness of the proposed approach.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Decomposed Structured Subsets for Semidefinite and Sum-of-Squares Optimization

Semidefinite programs (SDPs) are standard convex problems that are frequently found in control and optimization applications. Interior-point methods can solve SDPs in polynomial time up to arbitrary accuracy, but scale poorly as the size of matrix variables and the number of constraints increases. To improve scalability, SDPs can be approximated with lower and upper bounds through the use of structured subsets (e.g., diagonally-dominant and scaled-diagonally dominant matrices). Meanwhile, any underlying sparsity or symmetry structure may be leveraged to form an equivalent SDP with smaller positive semidefinite constraints. In this paper, we present a notion of decomposed structured subsets}to approximate an SDP with structured subsets after an equivalent conversion. The lower/upper bounds found by approximation after conversion become tighter than the bounds obtained by approximating the original SDP directly. We apply decomposed structured subsets to semidefinite and sum-of-squares optimization problems with examples of H-infinity norm estimation and constrained polynomial optimization. An existing basis pursuit method is adapted into this framework to iteratively refine bounds.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

An Input-Output Parametrization of Stabilizing Controllers: amidst Youla and System Level Synthesis

This paper proposes a novel input-output parametrization of the set of internally stabilizing output-feedback controllers for linear time-invariant (LTI) systems. Our underlying idea is to directly treat the closed-loop transfer matrices from disturbances to input and output signals as design parameters and exploit their affine relationships. This input-output perspective is particularly effective when a doubly-coprime factorization is difficult to compute, or an initial stabilizing controller is challenging to find; most previous work requires one of these pre-computation steps. Instead, our approach can bypass such pre-computations, in the sense that a stabilizing controller is computed by directly solving a linear program (LP). Furthermore, we show that the proposed input-output parametrization allows for computing norm-optimal controllers subject to quadratically invariant (QI) constraints using convex programming.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Sparsity Invariance for Convex Design of Distributed Controllers

We address the problem of designing optimal linear time-invariant (LTI) sparse controllers for LTI systems, which corresponds to minimizing a norm of the closed-loop system subject to sparsity constraints on the controller structure. This problem is NP-hard in general and motivates the development of tractable approximations. We characterize a class of convex restrictions based on a new notion of Sparsity Invariance (SI). The underlying idea of SI is to design sparsity patterns for transfer matrices Y(s) and X(s) such that any corresponding controller K(s)=Y(s)X(s)^-1 exhibits the desired sparsity pattern. For sparsity constraints, the approach of SI goes beyond the notion of Quadratic Invariance (QI): 1) the SI approach always yields a convex restriction; 2) the solution via the SI approach is guaranteed to be globally optimal when QI holds and performs at least as well as considering a nearest QI subset. Moreover, the notion of SI naturally applies to designing structured static controllers, while QI is not utilizable. Numerical examples show that even for non-QI cases, SI can recover solutions that are 1) globally optimal and 2) strictly more performing than previous methods.

0 citations0 reviewsNo code linkedOpen access
preprint2019arXiv

Chordal decomposition in operator-splitting methods for sparse semidefinite programs

We employ chordal decomposition to reformulate a large and sparse semidefinite program (SDP), either in primal or dual standard form, into an equivalent SDP with smaller positive semidefinite (PSD) constraints. In contrast to previous approaches, the decomposed SDP is suitable for the application of first-order operator-splitting methods, enabling the development of efficient and scalable algorithms. In particular, we apply the alternating direction method of multipliers (ADMM) to solve decomposed primal- and dual-standard-form SDPs. Each iteration of such ADMM algorithms requires a projection onto an affine subspace, and a set of projections onto small PSD cones that can be computed in parallel. We also formulate the homogeneous self-dual embedding (HSDE) of a primal-dual pair of decomposed SDPs, and extend a recent ADMM-based algorithm to exploit the structure of our HSDE. The resulting HSDE algorithm has the same leading-order computational cost as those for the primal or dual problems only, with the advantage of being able to identify infeasible problems and produce an infeasibility certificate. All algorithms are implemented in the open-source MATLAB solver CDCS. Numerical experiments on a range of large-scale SDPs demonstrate the computational advantages of the proposed methods compared to common state-of-the-art solvers.

0 citations0 reviewsNo code linkedOpen access
preprint2019arXiv

Chordal Decomposition in Rank Minimized Semidefinite Programs with Applications to Subspace Clustering

Semidefinite programs (SDPs) often arise in relaxations of some NP-hard problems, and if the solution of the SDP obeys certain rank constraints, the relaxation will be tight. Decomposition methods based on chordal sparsity have already been applied to speed up the solution of sparse SDPs, but methods for dealing with rank constraints are underdeveloped. This paper leverages a minimum rank completion result to decompose the rank constraint on a single large matrix into multiple rank constraints on a set of smaller matrices. The re-weighted heuristic is used as a proxy for rank, and the specific form of the heuristic preserves the sparsity pattern between iterations. Implementations of rank-minimized SDPs through interior-point and first-order algorithms are discussed. The problem of subspace clustering is used to demonstrate the computational improvement of the proposed method.

0 citations0 reviewsNo code linkedOpen access
preprint2019arXiv

Distributed Design for Decentralized Control using Chordal Decomposition and ADMM

We propose a distributed design method for decentralized control by exploiting the underlying sparsity properties of the problem. Our method is based on chordal decomposition of sparse block matrices and the alternating direction method of multipliers (ADMM). We first apply a classical parameterization technique to restrict the optimal decentralized control into a convex problem that inherits the sparsity pattern of the original problem. The parameterization relies on a notion of strongly decentralized stabilization, and sufficient conditions are discussed to guarantee this notion. Then, chordal decomposition allows us to decompose the convex restriction into a problem with partially coupled constraints, and the framework of ADMM enables us to solve the decomposed problem in a distributed fashion. Consequently, the subsystems only need to share their model data with their direct neighbours, not needing a central computation. Numerical experiments demonstrate the effectiveness of the proposed method.

0 citations0 reviewsNo code linkedOpen access
preprint2019arXiv

On the Equivalence of Youla, System-level and Input-output Parameterizations

A convex parameterization of internally stabilizing controllers is fundamental for many controller synthesis procedures. The celebrated Youla parameterization relies on a doubly-coprime factorization of the system, while the recent system-level and input-output characterizations require no doubly-coprime factorization but a set of equality constraints for achievable closed-loop responses. In this paper, we present explicit affine mappings among Youla, system-level and input-output parameterizations. Two direct implications of the affine mappings are 1) any convex problem in Youla, system level, or input-output parameters can be equivalently and convexly formulated in any other one of these frameworks, including the convex system-level synthesis (SLS); 2) the condition of quadratic invariance (QI) is sufficient and necessary for the classical distributed control problem to admit an equivalent convex reformulation in terms of Youla, system-level, or input-output parameters.

0 citations0 reviewsNo code linkedOpen access
preprint2019arXiv

On the Existence of Block-Diagonal Solutions to Lyapunov and $\mathcal{H}_{\infty}$ Riccati Inequalities

In this paper, we describe sufficient conditions when block-diagonal solutions to Lyapunov and $\mathcal{H}_{\infty}$ Riccati inequalities exist. In order to derive our results, we define a new type of comparison systems, which are positive and are computed using the state-space matrices of the original (possibly nonpositive) systems. Computing the comparison system involves only the calculation of $\mathcal{H}_{\infty}$ norms of its subsystems. We show that the stability of this comparison system implies the existence of block-diagonal solutions to Lyapunov and Riccati inequalities. Furthermore, our proof is constructive and the overall framework allows the computation of block-diagonal solutions to these matrix inequalities with linear algebra and linear programming. Numerical examples illustrate our theoretical results.

0 citations0 reviewsNo code linkedOpen access
preprint2018arXiv

Decomposition and Completion of Sum-of-Squares Matrices

This paper introduces a notion of decomposition and completion of sum-of-squares (SOS) matrices. We show that a subset of sparse SOS matrices with chordal sparsity patterns can be equivalently decomposed into a sum of multiple SOS matrices that are nonzero only on a principal submatrix. Also, the completion of an SOS matrix is equivalent to a set of SOS conditions on its principal submatrices and a consistency condition on the Gram representation of the principal submatrices. These results are partial extensions of chordal decomposition and completion of scalar matrices to matrices with polynomial entries. We apply the SOS decomposition result to exploit sparsity in matrix-valued SOS programs. Numerical results demonstrate the high potential of this approach for solving large-scale sparse matrix-valued SOS programs.

0 citations0 reviewsNo code linkedOpen access
preprint2018arXiv

Fast ADMM for sum-of-squares programs using partial orthogonality

When sum-of-squares (SOS) programs are recast as semidefinite programs (SDPs) using the standard monomial basis, the constraint matrices in the SDP possess a structural property that we call \emph{partial orthogonality}. In this paper, we leverage partial orthogonality to develop a fast first-order method, based on the alternating direction method of multipliers (ADMM), for the solution of the homogeneous self-dual embedding of SDPs describing SOS programs. Precisely, we show how a "diagonal plus low rank" structure implied by partial orthogonality can be exploited to project efficiently the iterates of a recent ADMM algorithm for generic conic programs onto the set defined by the affine constraints of the SDP. The resulting algorithm, implemented as a new package in the solver CDCS, is tested on a range of large-scale SOS programs arising from constrained polynomial optimization problems and from Lyapunov stability analysis of polynomial dynamical systems. These numerical experiments demonstrate the effectiveness of our approach compared to common state-of-the-art solvers.

0 citations0 reviewsNo code linkedOpen access
preprint2018arXiv

Sparse sum-of-squares (SOS) optimization: A bridge between DSOS/SDSOS and SOS optimization for sparse polynomials

Optimization over non-negative polynomials is fundamental for nonlinear systems analysis and control. We investigate the relation between three tractable relaxations for optimizing over sparse non-negative polynomials: sparse sum-of-squares (SSOS) optimization, diagonally dominant sum-of-squares (DSOS) optimization, and scaled diagonally dominant sum-of-squares (SDSOS) optimization. We prove that the set of SSOS polynomials, an inner approximation of the cone of SOS polynomials, strictly contains the spaces of sparse DSOS/SDSOS polynomials. When applicable, therefore, SSOS optimization is less conservative than its DSOS/SDSOS counterparts. Numerical results for large-scale sparse polynomial optimization problems demonstrate this fact, and also that SSOS optimization can be faster than DSOS/SDSOS methods despite requiring the solution of semidefinite programs instead of less expensive linear/second-order cone programs.

0 citations0 reviewsNo code linkedOpen access
preprint2017arXiv

Fast ADMM for Semidefinite Programs with Chordal Sparsity

Many problems in control theory can be formulated as semidefinite programs (SDPs). For large-scale SDPs, it is important to exploit the inherent sparsity to improve the scalability. This paper develops efficient first-order methods to solve SDPs with chordal sparsity based on the alternating direction method of multipliers (ADMM). We show that chordal decomposition can be applied to either the primal or the dual standard form of a sparse SDP, resulting in scaled versions of ADMM algorithms with the same computational cost. Each iteration of our algorithms consists of a projection on the product of small positive semidefinite cones, followed by a projection on an affine set, both of which can be carried out efficiently. Our techniques are implemented in CDCS, an open source add-on to MATLAB. Numerical experiments on large-scale sparse problems in SDPLIB and random SDPs with block-arrow sparse patterns show speedups compared to some common state-of-the-art software packages.

0 citations0 reviewsNo code linkedOpen access