Exploiting sparsity in linear and nonlinear matrix inequalities via positive semidefinite matrix completion (Q717129)

Optimization problems with nonlinear matrix inequalities, including quadratic and polynomial matrix inequalities, are known as hard problems. They frequently belong to large-scale optimization problems. Exploiting sparsity has been one of the essential tools for solving large-scale optimization problems. The authors present a basic framework for exploiting the sparsity characterized in terms of a chordal graph structure via positive semidefinite matrix completion. Depending on where the sparsity is observed, two types of sparsities are studied: the domain-space sparsity for a symmetric matrix that appears as a variable in the objective and/or the constraint functions of a given optimization problem and is required to be positive semidefinite, and the range-space sparsity for a matrix inequality involved in the constraint of the problem. Four conversion methods are proposed in this framework: two for exploiting the domain-space sparsity and the other two for exploiting the range-space sparsity. These conversion methods enhance the structured sparsity of the problem when they are applied to a polynomial semidefinite program.