Deciding the convexity of semialgebraic sets

2012-06-15T16:14:51Z

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?

Answer by Igor Rivin for Deciding the convexity of semialgebraic sets

2012-06-15T20:54:10Z

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.

Deciding the convexity of semialgebraic sets - MathOverflow

Deciding the convexity of semialgebraic sets

Answer by Igor Rivin for Deciding the convexity of semialgebraic sets