A Facial Reduction Algorithm for Finding Sparse SOS Representations

Hayato Waki (wakics.uec.ac.jp)
Masakazu Muramatsu (muramatucs.uec.ac.jp)

Abstract: Facial reduction algorithm reduces the size of the positive semidefinite cone in SDP. The elimination method for a sparse SOS polynomial ([3]) removes unnecessary monomials for an SOS representation. In this paper, we establish a relationship between a facial reduction algorithm and the elimination method for a sparse SOS polynomial.

Keywords: Semidefinite Programming, Polynomial Optimization Problems, Facial Reduction Algorithms, Sum of Squares.

Category 1: Linear, Cone and Semidefinite Programming (Semi-definite Programming )

Category 2: Global Optimization (Theory )

Category 3: Convex and Nonsmooth Optimization (Convex Optimization )

Citation: Technical Report CS-09-02, Department of Computer Science, The University of Electro-Communications.

Download: [PDF]

Entry Submitted: 11/04/2009
Entry Accepted: 11/04/2009
Entry Last Modified: 11/05/2009

Modify/Update this entry