Decomposition-based Method for Sparse Semidefinite Relaxations of Polynomial Optimization Problems |
| |
Authors: | P M Kleniati P Parpas B Rustem |
| |
Institution: | 1.Department of Computing,Imperial College London,London,UK |
| |
Abstract: | We consider polynomial optimization problems pervaded by a sparsity pattern. It has been shown in Lasserre (SIAM J. Optim.
17(3):822–843, 2006) and Waki et al. (SIAM J. Optim. 17(1):218–248, 2006) 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 decomposition-based
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 (Benders, Comput. Manag. Sci.
2(1):3–19, 2005). |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|