TY - GEN
T1 - Efficient Algorithm for Large-and-Sparse LMI Feasibility Problems
AU - Zhang, Richard Y.
AU - Lavaei, Javad
N1 - Funding Information:
This work was supported by NSF Award 1808859, DARPA Award D16AP00002, AFOSR Award FA9550-17-1-0163, and ONR YIP.
Publisher Copyright:
© 2018 IEEE.
PY - 2019/1/18
Y1 - 2019/1/18
N2 - Linear matrix inequalities (LMIs) play a fundamental role in robust and optimal control theory. However, their practical use remains limited, in part because their solution complexities of O(n-{6.5}) time and O(n-{4}) memory limit their applicability to systems containing no more than a few hundred state variables. This paper describes a Newton-PCG algorithm to efficiently solve large-and-sparse LMI feasibility problems, based on efficient log-det barriers for sparse matrices. Assuming that the data matrices share a sparsity pattern that admits a sparse Cholesky factorization, we prove that the algorithm converges in linear O(n) time and memory. The algorithm is highly efficient in practice: we solve LMI feasibility problems over power system models with as many as n=5738 state variables in 2 minutes on a standard workstation running MATLAB.
AB - Linear matrix inequalities (LMIs) play a fundamental role in robust and optimal control theory. However, their practical use remains limited, in part because their solution complexities of O(n-{6.5}) time and O(n-{4}) memory limit their applicability to systems containing no more than a few hundred state variables. This paper describes a Newton-PCG algorithm to efficiently solve large-and-sparse LMI feasibility problems, based on efficient log-det barriers for sparse matrices. Assuming that the data matrices share a sparsity pattern that admits a sparse Cholesky factorization, we prove that the algorithm converges in linear O(n) time and memory. The algorithm is highly efficient in practice: we solve LMI feasibility problems over power system models with as many as n=5738 state variables in 2 minutes on a standard workstation running MATLAB.
UR - http://www.scopus.com/inward/record.url?scp=85062182397&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85062182397&partnerID=8YFLogxK
U2 - 10.1109/CDC.2018.8619019
DO - 10.1109/CDC.2018.8619019
M3 - Conference contribution
AN - SCOPUS:85062182397
T3 - Proceedings of the IEEE Conference on Decision and Control
SP - 6868
EP - 6875
BT - 2018 IEEE Conference on Decision and Control, CDC 2018
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 57th IEEE Conference on Decision and Control, CDC 2018
Y2 - 17 December 2018 through 19 December 2018
ER -