  


Exploiting Sparsity in Linear and Nonlinear Matrix Inequalities via Positive Semidefinite Matrix Completion
Sunyoung Kim(skimewha.ac.kr) 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 matrixinequality constraint of the problem. We classify the sparsity in two types, the domainspace sparsity (dspace 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 rangespace sparsity (rspace sparsity) for a linear or nonlinear matrixinequality constraint of the problem. Four conversion methods are proposed in this framework: two for exploiting the dspace sparsity and the other two for exploiting the rspace sparsity. When applied to a polynomial semidefinite program (SDP), these conversion methods 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. Preliminary numerical results on the conversion methods for quadratic semidefinite programs indicate their potential for improving the efficiency of solving various problems. Keywords: Semidefinite Program, Matrix Inequalities, Polynomial Optimization, Positive Semidefinite Matrix Completion, Category 1: Linear, Cone and Semidefinite Programming (Semidefinite Programming ) Citation: Research Report B452, Department of Mathematical and Computing Sciences, Tokyo Institute of Technology, OhOkayama, Meguro, Tokyo 1528552, Japan Download: [Postscript][PDF] Entry Submitted: 01/12/2009 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  