Given a basic closed [semialgebraic set](http://en.wikipedia.org/wiki/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](http://www.math.uni-konstanz.de/~schweigh/)'s slides on [LMI representations of convex semialgebraic sets](http://www.math.uni-konstanz.de/~schweigh/presentations/dcssblmi.pdf) [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](http://www.stanford.edu/~boyd/cvxbook/), 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](http://www.usna.edu/cs/~qepcad/B/QEPCAD.html) or [REDLOG](http://redlog.dolzmann.de/). 


**Question:** other than quantifier elimination, is there any procedure that would allow one to decide the convexity of a given basic closed [semialgebraic set](http://en.wikipedia.org/wiki/Semialgebraic_set)?



Deciding the convexity of semialgebraic sets
In [this paper by Ahmadi et al](http://www.optimization-online.org/DB_FILE/2010/12/2846.pdf) the authors show that a very special case of this question (whether a polynomial is convex, so the set is the epigraph) is NP hard in many cases, so no really easy algorithm is likely to exist.


