Given a basic closed semialgebraic set, $S \subset \mathbb{R}^n$, defined by
$S = \{ x \in \mathbb{R}^n \mid g_1 (x) \geq 0 \land \dots \land g_m (x) \geq 0\}$
where $m \in \mathbb{N}$ and $g_1, \dots, g_m \in \mathbb{R}[x]$, how can one decide if $S$ is convex? Some context: this question arose while reading Schweighofer's slides on LMI representations of convex semialgebraic sets [pdf].
Let us introduce the predicate $p (x) = \bigwedge_{i=1}^m g_i (x) \geq 0$, so that we can write $S$ in the more parsimonious form $S = \{ x \in \mathbb{R}^n \mid p (x)\}$. From Boyd & Vandenberghe, we have the following definition:
A set $C$ is convex if the line segment between any two points in $C$ lies in $C$, i.e., if for any $x_1, > x_2 \in C$ and any $\theta$ with $0 \leq \theta \leq > 1$, we have $\theta x_1 + (1-\theta) > x_2 \in C$.
Hence, $S$ is convex if and only if the following universally quantified formula
$\forall x_1 \, \forall x_2 \, \forall \theta \, \left[\, p(x_1) \land p(x_2) \land (\theta \geq 0 \land \theta \leq 1) \implies p (\theta x_1 + (1-\theta) x_2) \, \right]$
where $x_1, x_2$ range over $\mathbb{R}^n$ and $\theta$ ranges over $\mathbb{R}$, evaluates to true. The formula above can be decided using a quantifier elimination package like QEPCAD or REDLOG.
Question: other than quantifier elimination, is there any procedure that would allow one to decide the convexity of a given basic closed semialgebraic set?
