Efficient Algorithm for Large-and-Sparse LMI Feasibility Problems

Richard Y. Zhang, Javad Lavaei

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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.

Original languageEnglish (US)
Title of host publication2018 IEEE Conference on Decision and Control, CDC 2018
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages6868-6875
Number of pages8
ISBN (Electronic)9781538613955
DOIs
StatePublished - Jan 18 2019
Externally publishedYes
Event57th IEEE Conference on Decision and Control, CDC 2018 - Miami, United States
Duration: Dec 17 2018Dec 19 2018

Publication series

NameProceedings of the IEEE Conference on Decision and Control
Volume2018-December
ISSN (Print)0743-1546

Conference

Conference57th IEEE Conference on Decision and Control, CDC 2018
CountryUnited States
CityMiami
Period12/17/1812/19/18

ASJC Scopus subject areas

  • Control and Systems Engineering
  • Modeling and Simulation
  • Control and Optimization

Fingerprint Dive into the research topics of 'Efficient Algorithm for Large-and-Sparse LMI Feasibility Problems'. Together they form a unique fingerprint.

  • Cite this

    Zhang, R. Y., & Lavaei, J. (2019). Efficient Algorithm for Large-and-Sparse LMI Feasibility Problems. In 2018 IEEE Conference on Decision and Control, CDC 2018 (pp. 6868-6875). [8619019] (Proceedings of the IEEE Conference on Decision and Control; Vol. 2018-December). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/CDC.2018.8619019