# 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.) –  Will Sawin Jun 15 '12 at 18:01

## 1 Answer

In this paper by Ahmadi et al 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.

-
Thanks. I am, indeed, acquainted with Ahmadi's work on deciding the convexity of polynomials. Just like some nonnegative polynomials accept sum of squares decompositions (which can be found "efficiently" using semidefinite programming), my hope was that maybe one could decide the convexity of a certain class of semialgebraic sets using some sort of "trick". An algebraic certificate of non-convexity, akin to the Positivstellensatz, would be interesting, too. But, alas, I have never heard of a Konvexitätsatz! –  Rod Carvalho Jun 17 '12 at 5:20