No label defined (Q4429170)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 1985306
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | No label defined |
scientific article; zbMATH DE number 1985306 |
Statements
24 September 2003
0 references
linear programming
0 references
semidefinite programming
0 references
convex relaxations
0 references
non-convex programming
0 references
0.8967257738113403
0 references
0.8269683122634888
0 references
0.815718412399292
0 references
0.8144230246543884
0 references
0.8071927428245544
0 references
The author investigates relationships between linear programming (LP) and semi-definite programming (SDP) convex relaxations to non-convex polynomial optimization problems, trying to balance respective pros and cons. LP relaxations, originally proposed by Shor in the mid 1980s and then revisited by Sherali and Adams, consist in multiplying the original constraints by themselves, linearizing (or lifting) the constraints by introducing additional variables, and then solving the resulting LP problem. Hierarchies of SDP relaxations, originally proposed by the author in 2001, are derived by interpreting the polynomial optimization problem as an optimization problem over moments of a probability measure. It is shown that LP relaxations can also be given an interpreation in terms of moments, and dually, as a representation of a polynomial positive on a compact semi-algebraic set. Contrary to Lasserre's SDP relaxations, for the hierarchies of LP relaxations proposed in the literature there is in general no guarantee of convergence to the global optimum of the original non-convex problem. Moreover, in the LP relaxations the linear constraints feature binomial coefficients so it is suspected that the resulting LP problems can be difficult to solve numerically. On the other hand, available LP solvers are far more powerful than existing SDP solvers, in terms of number of variables and constraints. So in practice LP relaxations can still prove a useful alternative when building up convex relaxations of non-convex polynomial optimization problems. For the entire collection see [Zbl 1013.00014].
0 references