AN EXTENSION OF THE ELIMINATION METHOD FOR A SPARSE SOS POLYNOMIAL(<Special Issue>SCOPE (Seminar on Computation and OPtimization for new Extensions))

スポンサーリンク

概要

• 論文の詳細を見る

• 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 [8] 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.

著者

• Muramatsu Masakazu

  The University of Electro-Communications

• Waki Hayato

  The University Of Electro-communications

関連論文

• EQUALITY BASED CONTRACTION OF SEMIDEFINITE PROGRAMMING RELAXATIONS IN POLYNOMIAL OPTIMIZATION
• AN EXTENSION OF THE ELIMINATION METHOD FOR A SPARSE SOS POLYNOMIAL(SCOPE (Seminar on Computation and OPtimization for new Extensions))
• A NEW SECOND-ORDER CONE PROGRAMMING RELAXATION FOR MAX-CUT PROBLEMS

スポンサーリンク