Deciding the convexity of semialgebraic sets - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-19T14:35:21Z http://mathoverflow.net/feeds/question/99720 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/99720/deciding-the-convexity-of-semialgebraic-sets Deciding the convexity of semialgebraic sets Rod Carvalho 2012-06-15T16:14:51Z 2012-06-15T20:54:10Z <p>Given a basic closed <a href="http://en.wikipedia.org/wiki/Semialgebraic_set" rel="nofollow">semialgebraic set</a>, $S \subset \mathbb{R}^n$, defined by</p> <p>$S = \{ x \in \mathbb{R}^n \mid g_1 (x) \geq 0 \land \dots \land g_m (x) \geq 0\}$</p> <p>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 <a href="http://www.math.uni-konstanz.de/~schweigh/" rel="nofollow">Schweighofer</a>'s slides on <a href="http://www.math.uni-konstanz.de/~schweigh/presentations/dcssblmi.pdf" rel="nofollow">LMI representations of convex semialgebraic sets</a> [pdf].</p> <p>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 <a href="http://www.stanford.edu/~boyd/cvxbook/" rel="nofollow">Boyd &amp; Vandenberghe</a>, we have the following definition:</p> <blockquote> <p>A set $C$ is <em>convex</em> if the line segment between any two points in $C$ lies in $C$, <em>i.e.</em>, 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$.</p> </blockquote> <p>Hence, $S$ is convex if and only if the following universally quantified formula</p> <p>$\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]$</p> <p>where $x_1, x_2$ range over $\mathbb{R}^n$ and $\theta$ ranges over $\mathbb{R}$, evaluates to <em>true</em>. The formula above can be decided using a quantifier elimination package like <a href="http://www.usna.edu/cs/~qepcad/B/QEPCAD.html" rel="nofollow">QEPCAD</a> or <a href="http://redlog.dolzmann.de/" rel="nofollow">REDLOG</a>. </p> <p><strong>Question:</strong> other than quantifier elimination, is there any procedure that would allow one to decide the convexity of a given basic closed <a href="http://en.wikipedia.org/wiki/Semialgebraic_set" rel="nofollow">semialgebraic set</a>?</p> http://mathoverflow.net/questions/99720/deciding-the-convexity-of-semialgebraic-sets/99746#99746 Answer by Igor Rivin for Deciding the convexity of semialgebraic sets Igor Rivin 2012-06-15T20:54:10Z 2012-06-15T20:54:10Z <p>In <a href="http://www.optimization-online.org/DB_FILE/2010/12/2846.pdf" rel="nofollow">this paper by Ahmadi et al</a> 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.</p>