Decomposition-Based Method for Sparse Semidefinite Relaxations of Polynomial Optimization Problems

P. M. Kleniati, Panos Parpas and Berc Rustem

No 22, Working Papers from COMISEF

Abstract: We consider polynomial optimization problems pervaded by a sparsity pattern. It has been shown in [1, 2] that the optimal solution of a polynomial programming problem with structured sparsity can be computed by solving a series of semidefinite relaxations that possess the same kind of sparsity. We aim at solving the former relaxations with a decompositionbased method, which partitions the relaxations according to their sparsity pattern. The decomposition-based method that we propose is an extension to semidefinite programming of the Benders decomposition for linear programs [3] .

Keywords: Polynomial optimization; Semidefinite programming; Sparse SDP relaxations; Benders decomposition (search for similar items in EconPapers)
Pages: 29 pages
Date: 2009-11-10
References: View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://comisef.eu/files/wps022.pdf (application/pdf)
Our link check indicates that this URL is bad, the error code is: 500 Can't connect to comisef.eu:80 (A connection attempt failed because the connected party did not properly respond after a period of time, or established connection failed because connected host has failed to respond.)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:com:wpaper:022

Access Statistics for this paper

More papers in Working Papers from COMISEF
Bibliographic data for series maintained by Anil Khuman ().