Complexity for exact polynomial optimization strengthened with Fritz John conditions

2022/05/24 by Mai, Ngoc Hoang Anh
#Algebraic Geometry (math.AG) #FOS: Mathematics #Optimization and Control (math.OC)

paper · doi:10.48550/arxiv.2205.11797

Abstract

Let f,g₁,…,g_m be polynomials of degree at most d with real coefficients in a vector of variables x=(x₁,…,x_n). Assume that f is non-negative on a basic semi-algebraic set S defined by polynomial inequalities g_j(x)≥ 0, for j=1,…,m. Our previous work [arXiv:2205.04254 (2022)] has stated several representations of f based on the Fritz John conditions. This paper provides some explicit degree bounds depending on n, m, and d for these representations. In application to polynomial optimization, we obtain explicit rates of finite convergence of the hierarchies of semidefinite relaxations based on these representations.

Related

• On the exactness for polynomial optimization strengthened with Fritz John conditions
• Exact polynomial optimization strengthened with Fritz John conditions
• A bounded degree SOS hierarchy for polynomial optimization
• Bounds on the infimum of polynomials over a generic semi-algebraic set using asymptotic critical values
• Convergence rates of S.O.S hierarchies for polynomial semidefinite programs