Name
Title | ||
|---|---|---|
Generalized Lagrangian Duals and Sums of Squares Relaxations of Sparse Polynomial Optimization Problems |
Abstract | ||
|---|---|---|
Sequences of generalized Lagrangian duals and their sums of squares (SOS) of polynomials relaxations for a polynomial optimization problem (POP) are introduced. The sparsity of polynomials in the POP is used to reduce the sizes of the Lagrangian duals and their SOS relaxations. It is proved that the optimal values of the Lagrangian duals in the sequence converge to the optimal value of the POP using a method from the penalty function approach. The sequence of SOS relaxations is transformed into a sequence of semidefinite programing (SDP) relaxations of the POP, which correspond to duals of modification and generalization of SDP relaxations given by Lasserre for the POP. |
Year | DOI | Venue |
|---|---|---|
2005 | 10.1137/030601260 | SIAM Journal on Optimization |
Keywords | Field | DocType |
penalty function approach,semidefinite program relaxation,optimal value,generalized lagrangian dual,squares relaxations,semidefinite programing,lagrangian dual,sparse polynomial optimization problems,generalized lagrangian duals,lagrangian relaxation,polynomials relaxation,sums of squares optimization,polynomial optimization problem,sequence converge,semidefinite program,lagrangian re- laxation,sos relaxation,global optimization,semidefinite pro- gram relaxation,sparsity,sum of squares,penalty function | Discrete mathematics,Polynomial optimization,Mathematical optimization,Global optimization,Polynomial,Lagrangian,Dual polyhedron,Lagrangian relaxation,Optimization problem,Mathematics,Penalty method | Journal |
Volume | Issue | ISSN |
15 | 3 | 1052-6234 |
Citations | PageRank | References |
24 | 2.45 | 12 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Sunyoung Kim | 1 | 461 | 38.82 |
| Masakazu Kojima | 2 | 1603 | 222.51 |
| Hayato Waki | 3 | 376 | 28.82 |