Solving BMI by QE

Algorithm 1 (Feasible problems)   ``Find X which satisfies $M(X) >_d (or \geq_d) 0$''

1.

Transform $M(X) >_d (or \geq_d) 0$ to an equivalent formula $\varphi(X)$ by using Sylvester's theorem.

2.

Construct the first-order formula $\psi = \exists X (\varphi(X))$.

3.

Perform QE for $\psi$.

QE outputs true or false. In the case of true QE returns one feasible solution. false means there are no feasible solutions.

Example 1   ``Does BMI B(x₁,x₂) <_d 0 have any feasible solutions in $(x_1,x_2) \in [-\frac{1}{2},2]\times [-3,7]$? [9]'' where

B(x₁,x₂)= $\left [ \begin{array}{ccc} -10 & -\frac{1}{2} & -2 \\ -\frac{1}{2} & \frac{9}... ...-\frac{1}{10} & \frac{6}{5} & -1 \\ -\frac{2}{5} & -1 & 0 \end{array}\right ]$

$+x_2 \left [ \begin{array}{ccc} 9 & \frac{1}{2} & 0 \\ \frac{1}{2} & 0 & -3 \\... ...y}{ccc} 0 & 0 & 2 \\ 0 & -\frac{11}{2} & 3 \\ 2 & 3 & 0 \end{array}\right ].$

This problem is equivalent to the following QE problem:

$$\exists x_1 \exists x_2 (A_1 \land A_2 \land A_3 \land -\frac{1}{2} \leq x_1 \leq 2 \land -3 \leq x_2 \leq 7)$$

where

A₁ = -45x₁+9x₂+50 > 0 ,

A₂ = (-4950x₂-25)x₁²+(990x₂²+6590x₂+4100)x₁-217x₂²

-2020x₂-4525 > 0,

A₃ = (-11000x₂³+37500x₂²-102750x₂+40375)x₁³+ (-700x₂³

-15850x₂²+141250x₂-27500)x₁²+ (3680x₂³+12935x₂²

-71900x₂-19625)x₁-764x₂³-3280x₂²+7000x₂+9000 > 0.

After performing QE for this, we have ``true''. In the case of $(x_1,x_2) \in {\bf R}^2$, after performing QE for $\exists x_1 \exists x_2 (A_1 \land A_2 \land A_3)$we also have true.

Algorithm 2 (linear objective minimization problems)   ``minimize 'c^T X subject to $M(X) >_d (or \geq_d) 0$.

1.

Transform $M(X) >_d (or \geq_d) 0$ to an equivalent formula $\varphi(X)$ by using Sylvester's theorem.

2.

Assign the new variable z to the objective function; $z-c^T X \geq 0$.

3.

Construct the first-order formula $\psi = \exists X \ (\varphi(X) \ \land \ z-c^T X \geq 0 )$.

4.

Perform QE for $\psi$.

We consider some examples (which are modified one taken from [20]), and apply the above mentioned method to them in order to demonstrate the potential of QE approach to SDP problems.

$\bullet$Non-Parametric: Minimize x₁+x₂ subject to

$$\left [ \begin{array}{ccc} 1 & x_1 & 0 \\ x_1 & x_2 & 0 \\ 0 & 0 & x_1+1 \end{array}\right] \geq_d 0.$$ (8)

The semidefinite constraint (8) is reduced to a Boolean system of inequalities constraints by using Sylvester's criterion;

$\psi= (1 \geq 0) \land (x_2 \geq 0) \land (x_1+1 \geq 0) \land (x_2-x_1^2 \ge... ..._2x_1+x_2) \geq 0) \land (x_1+1 \geq 0) \land (-x_1^3-x_1^2+x_2x_1+x_2 \geq 0).$

Assign new slack variable z to objective function x₁+x₂ and let $\psi' = \psi \land (z-x_1-x_2 \geq 0).$Then the problem is formulated as a first-order formula $\varphi = \ ^\exists x_1 \ ^\exists x_2 \ ( \psi' ).$After QE we have an equivalent qf formula describing the range of objective function;

$$4z + 1 \geq 0$$ (9)

$\bullet$Parametric(1): Minimize ax₁+x₂ subject to (8) with a parameter a.

Let $\psi'_{P_1} = \psi \land (z-ax_1-x_2 \geq 0).$The problem is formulated as $\varphi_{P_1} = \ ^\exists x_1 \ ^\exists x_2 \ ( \psi'_{P_1} ).$After QE we have an equivalent qf formula describing the range of objective function z with a parameter a;

$(a + z - 1 \geq 0) \lor (z \geq 0) \lor ((a^3 - 2a^2z + a^2 + az^2 - az \leq ... ... + 2z \geq 0) \land (a - 2 \leq 0)) \lor ((a^2 + 4z \geq 0) \land (a - 2 < 0)).$

If we substitute a parameter a with 1 and simplify the result, we have same result as (9).

$\bullet$Restricted region: Minimize x₁+x₂ subject to (8) in restricted domains D₁,D₂ respectively, where (i) $D_1= \{ x_1,x_2 \in {\bf R} \ \vert \ 0 \leq x_1 \leq 3, 0 \leq x_2 \leq 5 \}$and (ii) $D_2= \{ x_1,x_2 \in {\bf R} \ \vert \ 0 \leq x_1 \leq 10, 5 \leq x_2 \leq 10 \}$.

(i) In this case the problem is formulated as

$$\varphi_{D_1} = \ ^\exists x_1 \ ^\exists x_2 (\psi' \land (0 \leq x_1 \leq 3 \land 0 \leq x_2 \leq 5) )$$

After QE we have $4z + 1 \geq 0$.

(ii) In this case the problem is formulated as

$$\varphi_{D_2} = \ ^\exists x_1 \ ^\exists x_2 (\psi' \land (0 \leq x_1 \leq 10 \land 5 \leq x_2 \leq 10) )$$

After QE we have

$(z - 4 \geq 0) \lor ((z^2 - 10z + 20 \leq 0) \land (z^2 - 20z + 90 \geq 0) \la... ... 20 \leq 0) \land (z^2 - 20z + 90 \geq 0) \land (4z + 1 \geq 0) \land (z < 0)).$

$\bullet$Parametric(2): Minimize x₁+x₂ subject to

$$\left [ \begin{array}{ccc} s & x_1 & 0 \\ x_1 & x_2 & 0 \\ 0 & 0 & x_1+1 \end{array}\right] \geq_d 0.$$ (10)

where s is a parameter.

The semidefinite constraint (10) is reduced to

$\psi_P= (s \geq 0) \land (x_2 \geq 0) \land (x_1+1 \geq 0) \land (sx_2-x_1^2 \... ...+x_2) \geq 0) \land (s(x_1+1) \geq 0) \land ((x_2x_1+x_2)s-x_1^3-x_1^2 \geq 0).$

Let $\psi'_{P_2} = \psi_P \land (z-x_1-x_2 \geq 0).$Then the problem is formulated as a first-order formula $\varphi_{P_2} = \ ^\exists x_1 \ ^\exists x_2 \ ( \psi'_{P_2} ).$After QE we obtain

$(sz + s - 1 \geq 0 \land s > 0 \land z + 1 \geq 0) \lor (sz + s - 1 \geq 0 \la... ...(s > 0 \land (s^2 z + s^2 - s > 0 \lor (s^2 - 2s < 0 \land sz + s - 1 = 0))).$

If we substitute the parameter s with 1 and simplify the result, we have same result as (9).

$\bullet$ Parameter uncertainty: Minimize x₁+x₂ subject to (10) within the regions of a parameter s (i) $-5 \leq s \leq -1$, (ii) $-10 \leq s \leq 0$, respectively.

For (i),(ii), the problem is formulated as a first-order formula; $\varphi_{(i)} = \ ^\exists x_1 \ ^\exists x_2 (\psi'_{P_2} \land (-5 \leq s \leq -1))$, $\varphi_{(ii)} = \ ^\exists x_1 \ ^\exists x_2 (\psi'_{P_2} \land ( -10 \leq s \leq 0))$, respectively. After QE we obtain ``false'' for (i) and for (ii)

$(sz + s - 1 \geq 0 \land s = 0 \land z + 1 \geq 0) \lor (sz + s \geq 0 \land s... ... \geq 0 \land (sz + s - 1 \geq 0 \lor z = 0)))))) \lor (s = 0 \land z \geq 0).$