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

From MaRDI portal
scientific article
Language Label Description Also known as
English
Exploiting sparsity in linear and nonlinear matrix inequalities via positive semidefinite matrix completion
scientific article

    Statements

    Exploiting sparsity in linear and nonlinear matrix inequalities via positive semidefinite matrix completion (English)
    0 references
    0 references
    0 references
    0 references
    0 references
    27 September 2011
    0 references
    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.
    0 references
    semidefinite program
    0 references
    matrix inequalities
    0 references
    polynomial optimization
    0 references
    positive semidefinite matrix completion
    0 references
    sparsity
    0 references
    chordal graph
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references