## Posts Tagged ‘Convex Algebraic Geometry’

### 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

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…

### 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

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

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.

### 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.

### LMI representation of convex polygons

August 5, 2011

Consider the following non-strict linear matrix inequality (LMI) [1]

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

where $A: \mathbb{R}^2 \to S_3$ is a matrix-valued function, $S_3$ is the set of real symmetric $3 \times 3$ matrices, and $A (x) \succeq 0$ means that $A (x)$ is positive semidefinite. We can write $A (x) = A_0 + x_1 A_1 + x_2 A_2$, where diagonal matrices $A_0$, $A_1$, and $A_2$ are given by

$A_0 := \left[\begin{array}{ccc} 0 & 0 & 0\\ 0 & 0 & 0\\ 0 & 0 & 1\end{array}\right]$,   $A_1 := \left[\begin{array}{ccc} 1 & 0 & 0\\ 0 & 0 & 0\\ 0 & 0 & -1\end{array}\right]$,   $A_2 := \left[\begin{array}{ccc} 0 & 0 & 0\\ 0 & 1 & 0\\ 0 & 0 & -1\end{array}\right]$

We know that $P := \{ x \in \mathbb{R}^2 \mid A (x) \succeq 0 \}$ is a convex set [1]. What else can we say about $P$? Since $A (x)$ is diagonal for all $x \in \mathbb{R}^2$, then stating that $A (x) \succeq 0$ is equivalent to stating that the diagonal entries of $A (x)$ are nonnegative. Hence, set $P$ can be defined by the conjunction of three linear inequalities, as follows

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

which allows us to conclude that $P$ is a semialgebraic set [2]. In my humble opinion, this is interesting because $P$ is one of the simplest convex semialgebraic sets that are LMI-representable. What other convex semialgebraic sets are LMI-representable?

If we depict $P$, we obtain a convex polygon. To be more precise, we obtain a right triangle

The point I am trying to make is that any convex polygon is LMI-representable. Is this of any use? Or is it a mere academic curiosity? Well, if you want to obfuscate your work, write your linear programs as semidefinite programs ;-)

__________

References

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

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