Semi-algebraic description of the closure of the image of a semi-algebraic set under a polynomial

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

paper · doi:10.48550/arxiv.2210.13933

Abstract

Given a polynomial f and a semi-algebraic set S, we provide a symbolic algorithm to find the equations and inequalities defining a semi-algebraic set Q which is identical to the closure of the image of S under f, i.e., Q=f(S) . Consequently, every polynomial optimization problem whose optimum value is finite has an equivalent form with attained optimum value, i.e., min _{t∈ Q} t =inf_{x∈ S} f(x) whenever the right-hand side is finite. Given d as the upper bound on the degrees of f and polynomials defining S, we prove that our method requires O(d^O(n)) arithmetic operations to produce polynomials of degrees at most d^O(n) defining f(S).

Related

• Bounds on the infimum of polynomials over a generic semi-algebraic set using asymptotic critical values
• On the exactness for polynomial optimization strengthened with Fritz John conditions
• Representing elementary semi-algebraic sets by a few polynomial inequalities: A constructive approach
• Minimizing Polynomials Over Semialgebraic Sets
• An algorithm for semi-infinite polynomial optimization