scientific article; zbMATH DE number 1985306
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].
- Semidefinite Programming vs. LP Relaxations for Polynomial Programming
- Polynomial Programming: LP-Relaxations Also Converge
- Semidefinite programming relaxations for linear semi-infinite polynomial programming
- Semidefinite programming relaxations for semialgebraic problems
- New SDP relaxations for unconstrained 0-1 polynomial programming problems
- On linear programming relaxations for solving polynomial programming problems
- Affine reductions for LPs and SDPs
- Alternative SDP and SOCP approximations for polynomial optimization
- A Lagrangian relaxation view of linear and semidefinite hierarchies
- New SDP relaxations for unconstrained 0-1 polynomial programming problems
- SDP vs. LP Relaxations for the Moment Approach in Some Performance Evaluation Problems
- Exploiting Symmetries in SDP-Relaxations for Polynomial Optimization
- Polynomial Programming: LP-Relaxations Also Converge
- Semidefinite Programming vs. LP Relaxations for Polynomial Programming
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4429170)