A hierarchy of spectral relaxations for polynomial optimization

2020/07/17 by Mai, Ngoc Hoang Anh, Magron, Victor, Lasserre, Jean-Bernard · 1 citation
#FOS: Mathematics #Optimization and Control (math.OC)

paper · doi:10.48550/arxiv.2007.09027

Abstract

We show that (i) any constrained polynomial optimization problem (POP) has an equivalent formulation on a variety contained in an Euclidean sphere and (ii) the resulting semidefinite relaxations in the moment-SOS hierarchy have the constant trace property (CTP) for the involved matrices. We then exploit the CTP to avoid solving the semidefinite relaxations via interior-point methods and rather use ad-hoc spectral methods that minimize the largest eigenvalue of a matrix pencil. Convergence to the optimal value of the semidefinite relaxation is guaranteed. As a result we obtain a hierarchy of nonsmooth "spectral relaxations" of the initial POP. Efficiency and robustness of this spectral hierarchy is tested against several equality constrained POPs on a sphere as well as on a sample of randomly generated quadratically constrained quadratic problems (QCQPs).

Cited by

• Certifiably Optimal Estimation and Calibration in Robotics via Trace-Constrained Semi-Definite Programming

Related

• Exploiting constant trace property in large-scale polynomial optimization
• Spectral Methods for Polynomial Optimization
• A bounded degree SOS hierarchy for polynomial optimization
• Rank conditions for exactness of semidefinite relaxations in polynomial optimization
• Convergence of SDP hierarchies for polynomial optimization on the\n hypersphere