ncku-talk2010-11-26

NCTS(South) Semidefinite Programming and Its Application to Polynomial Optimization Problems

DATE 2010-11-26　10:00-11:00

PLACE R203, 2F, NCTS, NCKU

SPEAKER Prof. Masakazu Kojima（Dept. of Mathematical and Computing Sciences, Tokyo Institute of Technology, Japan）

TITLE Recent Topics(I) - Exploiting Sparsity in Linear and Nonlinear Matrix Inequalities via Positive Semidefinite Matrix Completion

ABSTRACT A basic framework for exploiting sparsity via positive semidefinite matrix completion is presented for an optimization problem with linear and nonlinear matrix inequalities. The sparsity, characterized with a chordal graph structure, can be detected in the variable matrix or in a linear or nonlinear matrix-inequality constraint of the problem. We classify the sparsity in two types, the domain-space sparsity (d-space sparsity) for the symmetric matrix variable in the objective and/or constraint functions of the problem, which is required to be positive semidefinite, and the range-space sparsity (r-space sparsity) for a linear or nonlinear matrix-inequality constraint of the problem. Conversion methods are proposed in this framework: one for exploiting the d-space sparsity and the other for exploiting the r-space sparsity. When applied to a polynomial semidefinite program (SDP), these conversion methods also enhance the structured sparsity of the problem called the correlative sparsity. As a result, the resulting polynomial SDP can be solved more effectively by applying the sparse SDP relaxation. Numerical results on the conversion methods indicate their potential for improving the efficiency of solving various problems.

NCTS(South) Semidefinite Programming and Its Application to Polynomial Optimization Problems

DATE	2010-11-26　10:00-11:00

PLACE	R203, 2F, NCTS, NCKU

SPEAKER	Prof. Masakazu Kojima（Dept. of Mathematical and Computing Sciences, Tokyo Institute of Technology, Japan）

TITLE	Recent Topics(I) - Exploiting Sparsity in Linear and Nonlinear Matrix Inequalities via Positive Semidefinite Matrix Completion

ABSTRACT	A basic framework for exploiting sparsity via positive semidefinite matrix completion is presented for an optimization problem with linear and nonlinear matrix inequalities. The sparsity, characterized with a chordal graph structure, can be detected in the variable matrix or in a linear or nonlinear matrix-inequality constraint of the problem. We classify the sparsity in two types, the domain-space sparsity (d-space sparsity) for the symmetric matrix variable in the objective and/or constraint functions of the problem, which is required to be positive semidefinite, and the range-space sparsity (r-space sparsity) for a linear or nonlinear matrix-inequality constraint of the problem. Conversion methods are proposed in this framework: one for exploiting the d-space sparsity and the other for exploiting the r-space sparsity. When applied to a polynomial semidefinite program (SDP), these conversion methods also enhance the structured sparsity of the problem called the correlative sparsity. As a result, the resulting polynomial SDP can be solved more effectively by applying the sparse SDP relaxation. Numerical results on the conversion methods indicate their potential for improving the efficiency of solving various problems.