-

 

 

 




Optimization Online





 

An extension of the elimination method for a sparse SOS polynomial

Hayato Waki (waki***at***cs.uec.ac.jp)
Masakazu Muramatsu (muramatu***at***cs.uec.ac.jp)

Abstract: We propose a method to reduce the sizes of SDP relaxation problems for a given polynomial optimization problem (POP). This method is an extension of the elimination method for a sparse SOS polynomial in [Kojima et al., Mathematical Programming] and exploits sparsity of polynomials involved in a given POP. In addition, we show that this method is a partial application of a facial reduction algorithm, which generates a smaller SDP problem with an interior feasible solution. In general, SDP relaxation problems for POPs often become highly degenerate because of a lack of interior feasible solutions. As a result, the resulting SDP relaxation problems obtained by this method may have an interior feasible solution, and one may be able to solve the SDP relaxation problems effectively. Numerical results in this paper show that the resulting SDP relaxation problems obtained by this method can be solved fast and accurately.

Keywords: Semidefinite programming, semidefinite programming relaxation, polynomial optimization, facial reduction algorithm

Category 1: Linear, Cone and Semidefinite Programming

Category 2: Convex and Nonsmooth Optimization

Category 3: Global Optimization

Citation: This paper will be published in Journal of the Operations Research Society of Japan, Vol. 54, No. 5.

Download: [PDF]

Entry Submitted: 11/01/2011
Entry Accepted: 11/01/2011
Entry Last Modified: 11/01/2011

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
Mathematical Optimization Society