### 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 language | English (US) |
---|---|

Title of host publication | 2018 IEEE Conference on Decision and Control, CDC 2018 |

Publisher | Institute of Electrical and Electronics Engineers Inc. |

Pages | 6868-6875 |

Number of pages | 8 |

ISBN (Electronic) | 9781538613955 |

DOIs | |

State | Published - Jan 18 2019 |

Externally published | Yes |

Event | 57th IEEE Conference on Decision and Control, CDC 2018 - Miami, United States Duration: Dec 17 2018 → Dec 19 2018 |

### Publication series

Name | Proceedings of the IEEE Conference on Decision and Control |
---|---|

Volume | 2018-December |

ISSN (Print) | 0743-1546 |

### Conference

Conference | 57th IEEE Conference on Decision and Control, CDC 2018 |
---|---|

Country | United States |

City | Miami |

Period | 12/17/18 → 12/19/18 |

### Fingerprint

### ASJC Scopus subject areas

- Control and Systems Engineering
- Modeling and Simulation
- Control and Optimization

### Cite this

*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

**Efficient Algorithm for Large-and-Sparse LMI Feasibility Problems.** / Zhang, Richard Y.; Lavaei, Javad.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

*2018 IEEE Conference on Decision and Control, CDC 2018.*, 8619019, Proceedings of the IEEE Conference on Decision and Control, vol. 2018-December, Institute of Electrical and Electronics Engineers Inc., pp. 6868-6875, 57th IEEE Conference on Decision and Control, CDC 2018, Miami, United States, 12/17/18. https://doi.org/10.1109/CDC.2018.8619019

}

TY - GEN

T1 - Efficient Algorithm for Large-and-Sparse LMI Feasibility Problems

AU - Zhang, Richard Y.

AU - Lavaei, Javad

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.

ER -