Leverage sparse structure in order to render large-scale semidefinite programs tractable
Interior-point methods for Semidefinite Programming (SDP) scale in a polynomial manner with the size of the largest Positive Semidefinite (PSD) block and the number of affine constraints (when solving up to epsilon-optimality). This complexity may be reduced if the problem instance contains structure, such as symmetry or sparsity. The cost and all constraints of an SDP with symmetry are invariant under group actions. An SDP has sparse structure if there exist elements which are not active in the cost nor any constraint matrix: their only function is to ensure that the matrix is PSD.
Decomposed Structured Subsets
Structured subset approximations are cones that inner/outer approximate the PSD cone to generate upper/lower bounds on the SDP optimum. An example of a structured subset for a minimization objective is the cone of diagonally dominant (DD) matrices (inner/upper bound) or its dual (outer/lower bound). Our observation in (Miller et al., 2022) is twofold: imposition of a structured subset destroys sparse structure in an SDP, and requiring clique-submatrices are in a structured subset yields a broader set of solutions (more accurate bounds) as compared to requiring the original matrix is in the subset.
The below figures visualize an affine slice of a spectahedron involving a PSD-completable matrix constraint of size 4x4, with cliques of size 2x2 and 3x3. The black region is the slice of the PSD set. Imposing that the 4x4 PSD-completable matrix is in a structured subset (resp. DD or scaled DD) is stricter than forcing its cliques to be in the same structured subset.
Left: The red feasible set has the 4x4 block DD. The blue superset forces the 2x2 and 3x3 cliques to be DD. Right: The yellow set is 4x4 scaled DD, and the brown superset has its cliques scaled DD.
This scheme allows for mixing cones: intractably large blocks can be approximated while small PSD blocks remain PSD.
Left: The green set has the 2x2 clique PSD while the 3x3 clique is DD. Right: The orange set has the 2x2 clique DD while the 3x3 clique is PSD.
Multiple kinds of structure can be combined together. For a system with simultaneous symmetry and sparsity properties, applying the symmetric then sparse decomposition before approximating yields the tightest bounds to the SDP.
Rank Minimization
Our work in (Miller et al., 2019) aimed to solve SDP that contained rank-constraints. Rank-constraints and rank-minimization problems are NP-hard, but there exist convex heuristics that attempt to approximate the optimal solution. On their own, rank-constrained SDPs scale in an exponential manner with the size of the largest rank-constrained PSD block. After utilizing a minimum-rank completion, the complexity now scales in an exponential manner with the size of the largest rank-constrained clique. This phenomenon may be used to construct regularizers (reweighted trace heuristic) based on the sum of clique matrices. An application of this method is in Subspace Clustering, which is a highly sparse polynomial optimization problem that classifies noisy points into subspaces. We developed a more efficient chordal extension to reduce the complexity of subspace clustering, and applied it to solve clustering and system identification problems.
Left: An instance of Subspace Clustering. Right: Chordal extensions associated with the Subspace Clustering problem. Our scheme scales exponentially with dimension and jointly linearly with the number of points and clusters.
All rank-relevant submatrices must be rank-1 in order to have a valid subspace clustering (rank-1-ness = ratio of largest eigenvalue to sum of eigenvalues).
Relevant Publications:
Journal Articles
AUT
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∞ norm estimation and constrained polynomial optimization. An existing basis pursuit method is adapted into this framework to iteratively refine bounds.
Conference Articles
IFAC
Decomposed Structured Subsets for Semidefinite Optimization
Semidefinite programs (SDPs) are important computational tools in controls, optimization, and operations research. Standard interior-point methods scale poorly for solving large-scale SDPs. With certain compromise of solution quality, one method for scalability is to use the notion of structured subsets (e.g. diagonally-dominant (DD) and scaled-diagonally dominant (SDD) matrices), to derive inner/outer approximations for SDPs. For sparse SDPs, chordal decomposition techniques have been widely used to derive equivalent SDP reformations with smaller PSD constraints. In this paper, we investigate a notion of decomposed structured subsets by combining chordal decomposition with DD/SDD approximations. This notion takes advantage of any underlying sparsity via chordal decomposition, while embracing the scalability of DD/SDD approximations. We discuss the applications of decomposed structured subsets to semidefinite optimization. Basis pursuit for refining DD/SDD approximations are also incorporated into the decomposed structured subset framework, and numerical performance is improved as compared to standard DD/SDD approximations. These results are demonstrated on H∞ norm estimation problems for networked systems.
@inproceedings{miller2020decomposed,author={Miller, Jared and Zheng, Yang and Sznaier, Mario and Papachristodoulou, Antonis},booktitle={21st IFAC World Congress},title={{Decomposed Structured Subsets for Semidefinite Optimization}},year={2020},bibtex_show={true},volume={},number={},tag={sparsity},abbr={IFAC},url={https://www.sciencedirect.com/science/article/pii/S2405896320316645},html={https://www.sciencedirect.com/science/article/pii/S2405896320316645},slides={IFAC_decomposed.pdf},poster={IPAM_decomposed_poster.pdf}}
CCTA
Domain Adaptation Based Fault Detection in Label Imbalanced Cyberphysical Systems
In this paper we propose a data-driven fault detection framework for semi-supervised scenarios where labeled training data from the system under consideration (the “target”) is imbalanced (e.g. only relatively few labels are available from one of the classes), but data from a related system (the “source”) is readily available. An example of this situation is when a generic simulator is available, but needs to be tuned on a case-by-case basis to match the parameters of the actual system. The goal of this paper is to work with the statistical distribution of the data without necessitating system identification. Our main result shows that if the source and target domain are related by a linear transformation (a common assumption in domain adaptation), the problem of designing a classifier that minimizes a miss-classification loss over the joint source and target domains reduces to a convex optimization subject to a single (non-convex) equality constraint. This second-order equality constraint can be recast as a rank-1 optimization problem, where the rank constraint can be efficiently handled through a reweighted nuclear norm surrogate. These results are illustrated with a practical application: fault detection in additive manufacturing (industrial 3D printing). The proposed method is able to exploit simulation data (source domain) to substantially outperform classifiers tuned using only data from a single domain.
@inproceedings{taskazan2019domain,author={Taskazan, Beg\"{u}m and Miller, Jared and Inyang-Udoh, Uduak and Camps, Octavia and Sznaier, Mario},booktitle={IEEE Conference on Control Technology and Applications (CCTA)},title={{Domain Adaptation Based Fault Detection in Label Imbalanced Cyberphysical Systems}},year={2019},volume={},number={},tag={sparsity},pages={142-147},doi={10.1109/CCTA.2019.8920608},abbr={CCTA},bibtex_show={true},url={https://ieeexplore.ieee.org/abstract/document/8920608},html={https://ieeexplore.ieee.org/abstract/document/8920608}}
CDC
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.
@inproceedings{miller2019rank,author={Miller, Jared and Zheng, Yang and Roig-Solvas, Biel and Sznaier, Mario and Papachristodoulou, Antonis},booktitle={IEEE 58th Conference on Decision and Control (CDC)},title={{Chordal Decomposition in Rank Minimized Semidefinite Programs with Applications to Subspace Clustering}},year={2019},volume={},number={},tag={sparsity},pages={4916-4921},doi={10.1109/CDC40024.2019.9029620},url={https://ieeexplore.ieee.org/document/9029620},html={https://ieeexplore.ieee.org/document/9029620},abbr={CDC},bibtex_show={true},poster={l4dc_poster_rank.pdf}}
