Fast ADMM for semidefinite programs with chordal sparsity by Zheng, Y, Fantuzzi, G, Papachristodoulou, A, Goulart, P, Wynn, A

“…For large-scale SDPs, it is important to exploit the inherent sparsity to improve scalability. This paper develops efficient first-order methods to solve SDPs with chordal sparsity based on the alternating direction method of multipliers (ADMM). …”

Chordal sparsity in control and optimization of large-scale systems by Zheng, Y

“…</p> <p>The first part of this thesis proposes a new conversion framework for large-scale SDPs characterized by chordal sparsity. This framework is analogous to standard conversion techniques for interior-point methods, but is more suitable for the application of first-order methods. …”

Exploiting sparsity in the coefficient matching conditions in sum-of-squares programming using ADMM by Zheng, Y, Fantuzzi, G, Papachristodoulou, A

“…This letter introduces an efficient first-order method based on the alternating direction method of multipliers (ADMM) to solve semidefinite programs arising from sum-of-squares (SOS) programming. We exploit the sparsity of the coefficient matching conditions when SOS programs are formulated in the usual monomial basis to reduce the computational cost of the ADMM algorithm. …”

Improving efficiency and scalability of sum of squares optimization: Recent advances and limitations by Ahmadi, AA, Hall, G, Papachristodoulou, A, Saunderson, J, Zheng, Y

“…The first method leverages the sparsity of the underlying SDP to obtain computational speed-ups. …”

Scalable design of structured controllers using chordal decomposition by Zheng, Y, Mason, R, Papachristodoulou, A

“…We first extend the chordal decomposition theorem for positive semidefinite matrices to the case of matrices with block-chordal sparsity. Then, a block-diagonal Lyapunov matrix assumption is used to convert the design of structured feedback gains into a convex problem, which inherits the sparsity pattern of the original problem. …”

Decomposition and completion of sum-of-squares matrices by Zheng, Y, Fantuzzi, G, Papachristodoulou, A

“…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. …”

Distributed design for decentralized control using chordal decomposition and ADMM by Zheng, Y, Kamgarpour, M, Sootla, A, Papachristodoulou, A

“…We propose a distributed design method for decentralized control by exploiting the underlying sparsity properties of the problem. Our method is based on the chordal decomposition of sparse block matrices and the alternating direction method of multipliers (ADMM). …”

Chordal decomposition in rank minimized semidefinite programs with applications to subspace clustering by Miller, J, Zheng, Y, Roig-Solvas, B, Sznaier, M, Papachristodoulou, A

“…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. …”

Fast ADMM for homogeneous self-dual embeddings of sparse SDPs by Zheng, Y, Fantuzzi, G, Papachristodoulou, A, Goulart, P, Wynn, A

“…In contrast to previous first-order methods that exploit chordal sparsity, our algorithm returns both primal and dual solutions when available, and it provides a certificate of infeasibility otherwise. …”

A chordal decomposition approach to scalable design of structured feedback gains over directed graphs by Zheng, Y, Mason, R, Papachristodoulou, A

“…This paper considers the problem of designing static feedback gains subject to a priori structural constraints, which is in general a non-convex problem. By exploiting the sparsity properties of the problem, and using chordal decomposition, a scalable algorithm is proposed to compute structured stabilizing feedback gains for large-scale systems over directed graphs. …”

Decomposed structured subsets for semidefinite and sum-of-squares optimization by Miller, J, Zheng, Y, Sznaier, M, Papachristodoulou, A

“…Meanwhile, any underlying sparsity or symmetry structure may be leveraged to form an equivalent SDP with smaller positive semidefinite constraints. …”

Chordal and factor-width decompositions for scalable semidefinite and polynomial optimization by Zheng, Y, Fantuzzi, G, Papachristodoulou, A

“…Chordal decomposition exploits the sparsity of semidefinite matrices in a semidefinite program (SDP), in order to formulate an equivalent SDP with smaller semidefinite constraints that can be solved more efficiently. …”