Optimization Online


A Facial Reduction Algorithm for Finding Sparse SOS Representations

Hayato Waki (waki***at***cs.uec.ac.jp)
Masakazu Muramatsu (muramatu***at***cs.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

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society