# Deciding the convexity of semialgebraic sets

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?

• This problem is no easier than deciding whether a given convex basic closed semialgebraic set is contained in a given arbitrary basic closed semialgebraic set, which seems like it would require quantifier elimination to solve. (If $f_i(x)\geq 0$ are the equations that define the first set and $g_j(x)\geq 0$ are the equations that define the second, then $f_i(x)\geq0\wedge g_j(x)+y^2\geq 0$ define a set that is convex if and only if the first is contained in the second.) Jun 15 '12 at 18:01