Semialgebraic Sets | Rod Carvalho

Posts Tagged ‘Semialgebraic Sets’

Deciding the convexity of semialgebraic sets II

June 23, 2012

Let $S_3 \subset \mathbb{R}^{3 \times 3}$ denote the set of real symmetric $3 \times 3$ matrices. We introduce a matrix-valued function $A: \mathbb{R}^3 \to S_3$ defined by

$A (x) = \left[\begin{array}{ccc} 1 & x_1 & x_2\\ x_1 & 1 & x_3\\ x_2 & x_3 & 1\end{array}\right]$

The elliptope $E_3 \subset \mathbb{R}^3$ is defined by

$E_3 = \left\{ x \in \mathbb{R}^3 \mid A (x) \succeq 0 \right\}$

where $A (x) \succeq 0$ means that matrix $A (x)$ is positive semidefinite. Since the elliptope $E_3$ is defined by the linear matrix inequality (LMI) $A (x) \succeq 0$ , we can conclude that $E_3$ is a spectrahedron and, therefore, we have that $E_3$ is convex.

The $E_3$ elliptope (also known as “inflated tetrahedron”) is the yellow part (surface and interior) of the Cayley’s cubic surface plotted below

[ source ]

__________

$E_3$ is a semialgebraic set

Saying that $A (x)$ is positive semidefinite is equivalent to saying that the $2^3 - 1 = 7$ principal minors of $A (x)$ are nonnegative. If $A (x) \succeq 0$ , then the three 1st order principal minors (which are the diagonal entries of $A (x)$ ) lead to the following three (admittedly uninteresting) inequalities

$1 \geq 0$ , $1 \geq 0$ , $1 \geq 0$

which we can discard. The three 2nd order principal minors (determinants of $2 \times 2$ submatrices of $A (x)$ ) and the 3rd order principal minor (the determinant of $A (x)$ ) can be computed using the following Python 2.5 + SymPy script:

from sympy import *

# symbolic variables
x1 = Symbol('x1')
x2 = Symbol('x2')
x3 = Symbol('x3')

# build matrix A(x)
A = Matrix([[1,x1,x2],
            [x1,1,x3],
            [x2,x3,1]])

print "\nMatrix A(x):"
print A

print "\n2nd order principal minors:"
print A.extract([0,1],[0,1]).det()
print A.extract([0,2],[0,2]).det()
print A.extract([1,2],[1,2]).det()

print "\n3rd order principal minor:"
print A.det()

which produces the following output:

Matrix A(x):
[ 1, x1, x2]
[x1,  1, x3]
[x2, x3,  1]

2nd order principal minors:
-x1**2 + 1
-x2**2 + 1
-x3**2 + 1

3rd order principal minor:
-x1**2 + 2*x1*x2*x3 - x2**2 - x3**2 + 1

Hence, the 2nd order principal minors yield the following inequalities

$1 - x_1^2 \geq 0$ , $1 - x_2^2 \geq 0$ , $1 - x_3^2 \geq 0$

which define the $3$ -dimensional cube $[-1,1]^3 \subset \mathbb{R}^3$ . The 3rd order principal minor (i.e., the determinant) yields the inequality

$1 + 2 x_1 x_2 x_3 - (x_1^2 + x_2^2 + x_3^3) \geq 0$ .

We can thus conclude that $E_3$ is a basic closed semialgebraic set.

__________

Deciding the convexity of $E_3$

In my last post, I used quantifier elimination to decide the convexity of two semialgebraic sets in $\mathbb{R}^2$ . Let us now decide the convexity of $E_3$ , which is of higher “complexity” than the sets I considered last time. What is the goal? The goal is to find out whether REDLOG can decide the convexity of $E_3$ in less than 10 minutes.

Based on the scripts in my previous post, we write the following REDUCE + REDLOG script to decide the convexity of $E_3$ :

% decide the convexity of the elliptope E3

load_package redlog;
rlset ofsf;

% define predicates in antecedent
p1 := (1-x1^2>=0) and (1-x2^2>=0) and (1-x3^2>=0) and 
      (1-x1^2-x2^2-x3^2+2*x1*x2*x3>=0);
p2 := (1-y1^2>=0) and (1-y2^2>=0) and (1-y3^2>=0) and 
      (1-y1^2-y2^2-y3^2+2*y1*y2*y3>=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  := (1-z1^2>=0) and (1-z2^2>=0) and (1-z3^2>=0) and 
      (1-z1^2-z2^2-z3^2+2*z1*z2*z3>=0);

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

% perform quantifier elimination
rlqe phi;

end;

After 30 minutes (!!!) waiting for the decision procedure to terminate, I killed the reduce.exe process (which was eating all my machine’s CPU cycles and RAM memory). This is disappointing…

Tags:Convex Algebraic Geometry, Convexity, Decision Problems, Linear Matrix Inequalities, Python, Quantifier Elimination, REDLOG, REDUCE, Semialgebraic Geometry, Semialgebraic Sets, Spectrahedra, SymPy
Posted in Algebraic Geometry, Python | Leave a Comment »

Deciding the convexity of semialgebraic sets

June 16, 2012

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.

Tags:Convex Algebraic Geometry, Convexity, Decision Problems, Quantifier Elimination, Real Algebraic Geometry, REDLOG, REDUCE, Semialgebraic Geometry, Semialgebraic Sets
Posted in Algebraic Geometry | Leave a Comment »

Feasibility via quantifier elimination II

August 29, 2011

Suppose we want to decide whether the following semialgebraic set

$S := \{(x,y) \in \mathbb{R}^2 \mid x - y^2 + 1 \geq 0 \land -x - y^2 + 1 \geq 0\}$

is nonempty. This is the same as determining whether the following system of polynomial inequalities

$\begin{array}{rrl} g_1 (x, y) :=& x - y^2 + 1 &\geq 0\\ g_2 (x, y) :=& -x - y^2 +1 &\geq 0\end{array}$

is feasible. We now define $S_1 := \{(x,y) \in \mathbb{R}^2 \mid g_1 (x, y) \geq 0\}$ , and $S_2 := \{(x,y) \in \mathbb{R}^2 \mid g_2 (x, y) \geq 0\}$ . Set $S_1$ is depicted below

and set $S_2$ is depicted below

Note that $S = S_1 \cap S_2$ . We depict this intersection below

Visual inspection of the plot of the intersection $S = S_1 \cap S_2$ allows us to conclude that $S$ in nonempty. Asserting that $S$ is nonempty is the same as stating that the proposition

$\exists{x}\exists{y} \left(g_1 (x,y) \geq 0 \land g_2 (x,y) \geq 0\right)$

is true. We can determine the truth value of this proposition via quantifier elimination using the following REDUCE + REDLOG script:

% feasibility via quantifier elimination

load_package redlog;
rlset ofsf;

% define polynomial functions
g1 :=  x-y^2+1;
g2 := -x-y^2+1;

% define existential formula
phi := ex({x,y}, g1>=0 and g2>=0);

% perform quantifier elimination
rlqe phi;

end;

which produces the truth value true. This means that there exists a $(x,y)$ that satisfies the polynomial inequalities, i.e., $S$ is nonempty.

__________

Remark: the plots in this post were generated by Wolfram Alpha.

Tags:Decision Problems, Feasibility, Quantifier Elimination, Real Algebraic Geometry, REDLOG, REDUCE, Semialgebraic Geometry, Semialgebraic Sets
Posted in Algebraic Geometry | Leave a Comment »

Feasibility via quantifier elimination

August 27, 2011

Consider the system of polynomial equations and inequalities [1]

$\begin{array}{rrl} f_1 (x_1, x_2) :=& x_1^2 + x_2^2 - 1 &= 0\\ g_1 (x_1, x_2) :=& 3 x_2 - x_1^3 - 2 &\geq 0\\ g_2 (x_1, x_2) :=& x_1 - 8 x_2^3 &\geq 0\end{array}$

whose solution set is the following semialgebraic set

$S := \{ (x_1,x_2) \in \mathbb{R}^2 \mid f_1 (x_1,x_2) = 0 \land g_1 (x_1,x_2) \geq 0 \land g_2 (x_1,x_2) \geq 0\}$

Parrilo showed in [1] that this system is infeasible, i.e., set $S$ is empty, using the Positivstellensatz [2]. Alternatively, one could use quantifier elimination to conclude infeasibility.

Consider the following proposition

$\exists{x_1}\exists{x_2} \left(f_1 (x_1,x_2) = 0 \land g_1 (x_1,x_2) \geq 0 \land g_2 (x_1,x_2) \geq 0\right)$ .

If this proposition is true, then the system is feasible and $S$ is nonempty. If the proposition is false, then the system is infeasible and $S$ is empty. We can determine the truth value of the proposition using REDUCE + REDLOG to perform quantifier elimination:

% feasibility via quantifier elimination

load_package redlog;
rlset ofsf;

% define polynomial functions
f1 := x1^2+x2^2-1;
g1 := 3*x2-x1^3-2;
g2 := x1-8*x2^3;

% define existential formula
phi := ex({x1,x2}, f1=0 and g1>=0 and g2>=0);

% perform quantifier elimination
rlqe phi;

end;

The output of this script is the following:

The proposition is false and, thus, the system is infeasible.

__________

References

[1] Pablo Parrilo, Sum of Squares Programs and Polynomial Inequalities.

[2] Jacek Bochnak, Michel Coste, Marie-Françoise Roy, Real Algebraic Geometry, Springer, 1998.

Tags:Decision Problems, Feasibility, Quantifier Elimination, Real Algebraic Geometry, REDLOG, REDUCE, Semialgebraic Geometry, Semialgebraic Sets
Posted in Algebraic Geometry | Leave a Comment »

LMI representation of convex polytopes

August 7, 2011

Suppose we are given a convex polytope $P \subset \mathbb{R}^n$ defined by the intersection of $m$ closed half-spaces

$P := \{ x \in \mathbb{R}^n \mid A x \leq b \}$

where $A \in \mathbb{R}^{m \times n}$ and $b \in \mathbb{R}^m$ . Note that set $P$ is the solution set of a system of $m$ non-strict linear inequalities in $n$ variables. Let

$p_i (x) := b_i - a_{i1} x_1 - a_{i2} x_2 - \dots - a_{in} x_n$

so that set $P$ can be described as follows

$P = \{ x \in \mathbb{R}^n \mid p_1 (x) \geq 0 \land p_2 (x) \geq 0 \land \dots \land p_m (x) \geq 0\}$

which allows us to conclude that $P$ is a semialgebraic set [1]. The conjunction of the $m$ non-strict linear inequalities $p_i (x) \geq 0$ is equivalent to the following linear matrix inequality (LMI) [2]

$F (x) := \left[\begin{array}{cccc} p_1 (x) & 0 & \ldots & 0\\ 0 & p_2 (x) & \ldots & 0\\ \vdots & \vdots & \ddots & \vdots\\ 0 & 0 & \ldots & p_m (x)\end{array}\right] \succeq 0$

which, since the $p_i$ polynomials are of degree 1, can be written as

$F (x) = F_0 + x_1 F_1 + x_2 F_2 + \dots + x_n F_n \succeq 0$

where the real diagonal $m \times m$ matrices $F_0, F_1, \dots, F_n$ are given by

$F_0 := \left[\begin{array}{cccc} b_1 & 0 & \ldots & 0\\ 0 & b_2 & \ldots & 0\\ \vdots & \vdots & \ddots & \vdots\\ 0 & 0 & \ldots & b_m\end{array}\right]$ , $F_j = \left[\begin{array}{cccc} -a_{1j} & 0 & \ldots & 0\\ 0 & -a_{2j} & \ldots & 0\\ \vdots & \vdots & \ddots & \vdots\\ 0 & 0 & \ldots & -a_{m j}\end{array}\right]$

for $j = 1, 2,\dots, n$ . Thus, convex polytope $P$ can be defined using the LMI $F (x) \succeq 0$ , as follows

$P = \{ x \in \mathbb{R}^n \mid F (x) \succeq 0 \}$

where the $F_0, F_1, \dots, F_n$ matrices are diagonal.

__________

References

[1] Jacek Bochnak, Michel Coste, Marie-Françoise Roy, Real Algebraic Geometry, Springer, 1998.

[2] Stephen Boyd, Laurent El Ghaoui, Eric Feron, and V. Balakrishnan, Linear Matrix Inequalities in System and Control Theory, SIAM, 1994.

Tags:Convex Algebraic Geometry, Convex Polytopes, Linear Matrix Inequalities, Real Algebraic Geometry, Semialgebraic Geometry, Semialgebraic Sets, Spectrahedra
Posted in Algebraic Geometry | Leave a Comment »

S	M	T	W	T	F	S
« Dec
			1	2	3	4
5	6	7	8	9	10	11
12	13	14	15	16	17	18
19	20	21	22	23	24	25
26	27	28	29	30	31

Rod Carvalho

Posts Tagged ‘Semialgebraic Sets’

Deciding the convexity of semialgebraic sets II

Deciding the convexity of semialgebraic sets

Feasibility via quantifier elimination II

Feasibility via quantifier elimination

LMI representation of convex polytopes

Pages

Categories

Top Posts

Recent Posts

Recent Comments

Tag Cloud

Archives

Blog Stats

Artists

Blogs

Haskell

Math Blogs

MATLAB

Python

Robotics

Software

Symbolic Computation

Powered by FeedBurner

Meta

Follow “Rod Carvalho”

Rod Carvalho

Posts Tagged ‘Semialgebraic Sets’

Deciding the convexity of semialgebraic sets II

Deciding the convexity of semialgebraic sets

Feasibility via quantifier elimination II

Feasibility via quantifier elimination

LMI representation of convex polytopes

Pages

Categories

Top Posts

Recent Posts

Recent Comments

Tag Cloud

Archives

Blog Stats

Artists

Blogs

Haskell

Math Blogs

MATLAB

Python

Robotics

Software

Symbolic Computation

Category Cloud

Powered by FeedBurner

Meta

Follow “Rod Carvalho”