Submission date: 25 October 2022

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 limits_{t ∈ Q} t =inf limits_{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).

Mathematics Subject Classification:

Keywords and phrases:

Full text arXiv 2210.13933: pdf,