Deciding the convexity of semialgebraic sets

Given a basic closed semialgebraic set [1], $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 set $S$ is convex? Can one use quantifier elimination?

__________

Convexity

Let us recall the definition of convexity [2]:

Definition: A set $S$ is convex if the line segment between any two points in $S$ lies in $S$ , i.e., if for any $x, y \in S$ and any $\theta$ with $0 \leq \theta \leq 1$ , we have $\theta x + (1-\theta) y \in S$ .

Let us introduce a predicate $p : \mathbb{R}^n \to \{\text{True}, \text{False}\}$ , defined by

$\displaystyle 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) \}$ .

Hence, writing $x \in S$ is equivalent to asserting that $p (x) = \text{True}$ . From the definition above, it follows that set $S$ is convex if and only if the following universally quantified formula

$\forall x \, \forall y \, \forall \theta \, \left[ \, p(x) \land p(y) \land (\theta \geq 0 \land \theta \leq 1) \implies p (\theta x + (1-\theta) y) \, \right]$

where $x, y$ range over $\mathbb{R}^n$ and $\theta$ ranges over $\mathbb{R}$ , evaluates to $\text{True}$ . Since $g_1, \dots, g_m$ are polynomials, the formula above can be decided using quantifier elimination software like QEPCAD or REDLOG. Unfortunately, decidability does not imply that real quantifier elimination will decide the formula in an expedite manner. Let us now consider two instances of the decision problem under study.

__________

Example #1

Consider the following semialgebraic set

$S_1 := \{ x \in \mathbb{R}^2 \mid x_1 - x_2^2 + 3 \geq 0 \land -x_1 - x_2^2 + 3 \geq 0\}$

which we depict below

Visual inspection of the plot above allows us to conclude that set $S_1$ is convex. However, relying on the human visual system is extremely limiting. Therefore, we would like to automate the decision. We decide the convexity of $S_1$ via quantifier elimination using the following REDUCE + REDLOG script:

% decide the convexity of a semialgebraic set

load_package redlog;
rlset ofsf;

% define predicates in antecedent
p1 := (x1-x2^2+3>=0) and (-x1-x2^2+3>=0);
p2 := (y1-y2^2+3>=0) and (-y1-y2^2+3>=0);
p3 := (theta>=0) and (theta<=1);

% define predicate in the consequent
z1 := theta*x1+(1-theta)*y1;
z2 := theta*x2+(1-theta)*y2;
q  := (z1-z2^2+3>=0) and (-z1-z2^2+3>=0); 

% define universal formula
phi := all({x1,x2,y1,y2,theta}, (p1 and p2 and p3) impl q);

% perform quantifier elimination
rlqe phi;

end;

This script returns the truth value $\text{True}$ and, hence, $S_1$ is, indeed, convex. However, it took REDLOG approximately 60 seconds to decide the convexity of $S_1$ , which is considerably longer than any of my previous experiments with REDLOG. Since we are performing quantifier elimination on a formula with five universal quantifiers, I am not incredibly surprised that it takes a while to obtain an answer.

__________

Example #2

Consider now the following semialgebraic set

$S_2 := \{ x \in \mathbb{R}^2 \mid x_1 - x_2^2 + 3 \geq 0 \land x_1 - x_2^2 + 1 \leq 0\}$

part of which we depict below

Visual inspection of the plot above allows us to conclude that set $S_2$ is not convex. We decide the convexity of $S_2$ using the following REDUCE + REDLOG script:

% decide the convexity of a semialgebraic set

load_package redlog;
rlset ofsf;

% define predicates in antecedent
p1 := (x1-x2^2+3>=0) and (x1-x2^2+1<=0);
p2 := (y1-y2^2+3>=0) and (y1-y2^2+1<=0);
p3 := (theta>=0) and (theta<=1);

% define predicate in the consequent
z1 := theta*x1+(1-theta)*y1;
z2 := theta*x2+(1-theta)*y2;
q  := (z1-z2^2+3>=0) and (z1-z2^2+1<=0); 

% define universal formula
phi := all({x1,x2,y1,y2,theta}, (p1 and p2 and p3) impl q);

% perform quantifier elimination
rlqe phi;

end;

This script returns the truth value $\text{False}$ and, hence, $S_2$ is, indeed, not convex. Interestingly, it took REDLOG less than one second to decide the formula. That is over two orders of magnitude faster than in example #1.

__________

References

[1] Markus Schweighofer, Describing convex semialgebraic sets by linear matrix inequalities, International Symposium on Symbolic and Algebraic Computation, Korea Institute for Advanced Study, Seoul, July 2009.

[2] Stephen Boyd, Lieven Vandenberghe, Convex Optimization.

About these ads

Tags: Convex Algebraic Geometry, Convexity, Decision Problems, Quantifier Elimination, Real Algebraic Geometry, REDLOG, REDUCE, Semialgebraic Geometry, Semialgebraic Sets

This entry was posted on June 16, 2012 at 21:01 and is filed under Algebraic Geometry. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

Rod Carvalho

Deciding the convexity of semialgebraic sets

Like this:

Leave a Reply Cancel reply

Follow “Rod Carvalho”