# Optimization problem defined by polynomials only always leads to algebraic solutions?

Let $\Omega$ be a non-empty set in ${\mathbb R}^n$ defined by a set of polynomial inequalities with rational coefficients $P_i(x_1, \ldots ,x_n) \gt 0 (1 \leq i\leq m)$ and $Q_j(x_1, \ldots ,x_n) \geq 0 (1 \leq j\leq m')$. Let $F(x_1, \ldots ,x_n)$ be a polynomial with rational coefficients such that $F$ attains its minimum on $\Omega$ at a unique point $(z_1, \ldots ,z_n)$. Does it follow that all the $z_k$ are algebraic over $\mathbb Q$ ?

UPDATE (15 mins later) :since an answer by André Nicolas pointed out that this is a standard fact in model theory, I guess I should rephrase my question as, "Where may I learn more about this" (preferably on the internet ?)

-

It does follow. I think of it as a theorem of Model Theory: the field of real numbers is an elementary extension of the field of real algebraic numbers.

-
Thanks for your quick answer even though I don't understand one word of it. I updated my original question accordingly. – Ewan Delanoy May 1 '12 at 6:16
I recalled, perhaps incorrectly, that you had asked some questions connected with Mathematical Logic. The result can be proved using Tarski's result on quantifier elimination. – André Nicolas May 1 '12 at 6:24
I know some mathematical logic indeed, but not much about model theory. I'll google "quantifier elimination". – Ewan Delanoy May 1 '12 at 6:41
The assertion that $F$, subject to the a specific (finite) set of constraints, attains a minimum at the unique point $(z_1,\dots,z_n)$, is a sentence of the first-order theory of real-closed fields. So true in all real-closed fields or in none. And if true in real algebraics, then because the reals are an elementary extension, it is true at the same place if quantifiers range over the reals. – André Nicolas May 1 '12 at 6:51
By the way, nice intuition! There is an informal similar fact in algebraic geometry called the Lefschetz Principle, which basically says true over the algebraic numbers iff true over the complex numbers. A precise version of that is a theorem of Model Theory, very accessible. Real and real algebraics is quite a bit harder. – André Nicolas May 1 '12 at 7:10

Under the assumption that the minimum satisfies standard assumptions of mathematical optimization, it is the solution of a KKT system with some constraint qualification. The minimizer is then uniquely charakterized by the equality and active inequality constraints, and the equations for the Lagrange multipliers of these constraints. All equations of this system are polynomials with rational coefficients and the minimizer is one of its solutions, so it is an algebraic point.

If the KKT system is not 'nice' in the above sense, higher derivatives than the first enter the system of equations, but in the end, there results a system of polynomials with rational coefficients.

-