Archive for the ‘Geometry’ Category

« Older Entries

Deciding 2-colorability via quantifier elimination

September 1, 2011

A vertex coloring of a graph G = (V,E) is a map \kappa : V \to C that assigns a color to each vertex of G. The coloring is proper if adjacent vertices are assigned distinct colors. The graph is 2-colorable if there exists a proper coloring whose color set C has two elements.

For instance, consider a graph G = (V,E) whose vertex set is V := \{1, 2, 3\} and whose edge set is E := \{\{1,2\}, \{1,3\}, \{2,3\}\}. A pictorial representation of this graph is depicted below

Note that this graph is complete. We can assign two distinct colors to any two vertices, but we cannot assign a color to the third vertex that will yield a proper coloring. Therefore, the graph is not 2-colorable. To illustrate, we use the color set C := \{\text{pink}, \text{blue}\} and generate all 2^3 = 8 possible vertex 2-colorings, as depicted below

Notice that none of these 2-colorings is proper, as expected.

As discussed by De Loera et alia [1], the graph vertex-coloring problem can be modeled using polynomial equations. We introduce variables x_1, x_2, x_3, where x_i = -1 if vertex i is assigned the color \text{pink}, and x_i = 1 if vertex i is assigned the color \text{blue}. Given an edge \{i,j\} \in E, we have that:

  • if both vertices are pink, we get x_i + x_j = -2.
  • if both vertices are blue, we get x_i + x_j = 2.
  • if the vertices have distinct colors, we get x_i + x_j = 0.

Thus, stating that adjacent vertices must be assigned distinct colors is equivalent to imposing the constraints x_i + x_j = 0 for all \{i,j\} \in E. We thus obtain a system of three equations

\begin{array}{rl} x_1 + x_2 &= 0\\ x_1 + x_3 &= 0\\ x_2 + x_3 &= 0\end{array}

where x_1, x_2, x_3 \in \{-1,1\}. This is still a combinatorial problem, though. We can transform it into an algebraic-geometric problem. Here is a truly beautiful trick [1]: the constraint x_i \in \{-1,1\} can be encoded as x_i^2 = 1 with x_i \in \mathbb{R}. How quaint!! We then obtain a system of six equations with polynomials in \mathbb{R}[x_1, x_2, x_3]

\begin{array}{rl} x_1 + x_2 &= 0\\ x_1 + x_3 &= 0\\ x_2 + x_3 &= 0\\ x_1^2 - 1 &= 0\\ x_2^2 - 1 &= 0\\ x_3^2 -1 &= 0\end{array}

whose solution set, which we denote by S, is algebraic [2]. The given graph is 2-colorable if and only if the system of polynomial equations above is feasible, i.e., if set S is nonempty [1]. The following REDUCE + REDLOG script uses quantifier elimination to decide if S is nonempty:

% feasibility via quantifier elimination

load_package redlog;
rlset ofsf;

% define polynomial functions
f1 := x1+x2;
f2 := x1+x3;
f3 := x2+x3;
f4 := x1^2-1;
f5 := x2^2-1;
f6 := x3^2-1;

% define existential formula
phi := ex({x1,x2,x3}, f1=0 and f2=0 and f3=0 and
                      f4=0 and f5=0 and f6=0);

% perform quantifier elimination
rlqe phi;

end;

This script produces the truth value false. Thus, the solution set S is empty, which means that the system of polynomial equations is infeasible. We conclude that the given graph is not 2-colorable.

__________

References

[1] Jesús De Loera, Jon Lee, Susan Margulies, Shmuel Onn, Expressing Combinatorial Optimization Problems by Systems of Polynomial Equations and the Nullstellensatz, 2007.

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

Tags:, , , , , , , , , ,
Posted in Algebraic Geometry, Graph Theory | 1 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:, , , , , ,
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:, , , , , ,
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:, , , , ,
Posted in Algebraic Geometry | Leave a Comment »

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.

Tags:, , , ,
Posted in Algebraic Geometry | Leave a Comment »

« Older Entries
Follow

Get every new post delivered to your Inbox.

Join 47 other followers