We study representation of solutions and certificates to quadratic and cubic optimization problems. Specifically, we focus on minimizing a cubic function over a polyhedron and also minimizing a linear function over quadratic constraints. We show when there exist rational feasible solutions (and if we can detect them) and when we can prove feasibility of sublevel sets. We also show that in fixed dimension, the feasibility problem over a set defined by polynomial inequalities is in NP.
Article
View Complexity, Exactness, and Rationality in Polynomial Optimization