Real ideal and the duality of semidefinite programming for polynomial optimization

DOI10.1007/S13160-013-0104-6MaRDI QIDQ351462zbMATH OpenOpenAlexFDO

Authors Yoshiyuki Sekiguchi, T. Takenawa, Hayato Waki

Publication date 11 July 2013

Published in Japan Journal of Industrial and Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0901.2998

zbMATH Keywords

polynomial optimizationreal idealsemidefinite programming relaxation

Mathematics Subject Classification ID

Fields related with sums of squares (formally real fields, Pythagorean fields, etc.) (12D15) Real algebraic sets (14P05) Semialgebraic sets and related spaces (14P10) Semidefinite programming (90C22)

Abstract: We study the ideal generated by polynomials vanishing on a semialgebraic set and propose an algorithm to calculate the generators, which is based on some techniques of the cylindrical algebraic decomposition. By applying these, polynomial optimization problems with polynomial equality constraints can be modified equivalently so that the associated semidefinite programming relaxation problems have no duality gap. Elementary proofs for some criteria on reality of ideals are also given.

Recommendations

• Real radicals and finite convergence of polynomial optimization problems
• Positive polynomials and semidefinite programming
• Strong duality in lasserre's hierarchy for polynomial optimization
• Moments and sums of squares for polynomial optimization and related problems
• Semidefinite program duals for separable polynomial programs involving box constraints

Cites work

• A zero-dimensional approach to compute real radicals
• Algorithms in real algebraic geometry
• EQUALITY BASED CONTRACTION OF SEMIDEFINITE PROGRAMMING RELAXATIONS IN POLYNOMIAL OPTIMIZATION
• Global optimization with polynomials and the problem of moments
• scientific article; zbMATH DE number 421675 (Why is no real title available?)
• scientific article; zbMATH DE number 43569 (Why is no real title available?)
• scientific article; zbMATH DE number 1201576 (Why is no real title available?)
• scientific article; zbMATH DE number 517393 (Why is no real title available?)
• scientific article; zbMATH DE number 3269628 (Why is no real title available?)
• Local reality on algebraic varieties
• Optimization of Polynomial Functions
• Optimization of Polynomials on Compact Semialgebraic Sets
• Positive polynomials and sums of squares
• Semidefinite characterization and computation of zero-dimensional real radical ideals
• Semidefinite programming relaxations for semialgebraic problems
• Sums of squares, moment matrices and optimization over polynomials

Cited in

(3)

• Computing real radicals and S-radicals of polynomial systems
• Real radicals and finite convergence of polynomial optimization problems
• Computing real radicals by moment optimization

This page was built for publication: Real ideal and the duality of semidefinite programming for polynomial optimization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q351462)