Optimization by QE and SDP

By Sylvester's criterion semidefinite constraints are reduced to a conjunction of inequalities and the SDP problems are reduced to the ordinary nonlinear programming problems.

In [21] Weispfenning showed that the optimization problem, in particular linear programming problems, can be solved successfully by using his highly improved QE algorithm. We utilize his algorithm for a nonlinear programming problem derived from the SDP problem as above. This explains how we solve the SDP problems by using QE.

Here we show the brief sketch of his method to solve optimization problems given by a Boolean system $\psi(X,U)$ consisting of equations and inequalities and an objective function h(X,U); First introduce a new indeterminate z assigned to the object function h. Consider the new Boolean system $\psi' = \psi \ \land ( z - h \geq 0 ).$Then the problem minimizing h subject to $\psi(X,U)$ is formulated as first-order formula $\varphi = \ ^\exists x_1 \cdots \ ^\exists x_n ( \psi' )$. Next eliminate all quantified variables $x_1,\cdots,x_n$to have the resulting qf formula $\varphi'$ in z and U. After that we specialize parameters U of $\varphi'$ by an appropriate real values, then $\varphi'$ gives a finite union M of intervals for z, which shows a possible range of z. If M is empty, $\psi$ is unsolvable (i.e. infeasible); if M is unbounded from below, h has no minimum w.r.t. $\psi$; if $m \in M$ is a lowest endpoint of M, then m is the minimum value of z w.r.t. $\psi$ (for details [21]). As for the coordinates of a minimum point for z can be obtained by back-substitution from the test terms used during the elimination if we use test term approach (see [21]).