\documentstyle[12pt]{article}
\begin{document}
\newcommand{\elabel}[1]{\renewcommand{\theequation}{#1}}
\baselineskip=20pt
\title{On Lower Bounds for Nonconvex Quadratic Programming }
\author{Baoyan Ding}
\begin{center}
{\bf \large\large On Lower Bound for Nonconvex Quadratic Programming Problems }\\
$ \ $ \\
{\bf Baoyan Ding}\\ 
{\bf ID\#: 92800147}
\end{center}

\section{Introduction}

\quad In this project, we consider the following nonconvex quadratic programming 
problem 

\noindent
$(QP1)$\quad\quad $\rho_{1}=$ min $f_{0}(x)$,

\quad\quad\quad\quad\quad\quad subject to

\quad\quad\quad\quad\quad\quad $f_{i}(x)\leq 0,\ i=1,\cdots,m$,

\noindent
where $f_{i}(x)=x^{t}A_{i}x+2b_{i}^{t}x+c_{i}$, $A_{i}\in S^{n},
b_{i}\in R^{n}$ and $c_{i}\in R^{1},\ i=0,\cdots,m$. The matrices  
$A_{i}$ $(i=0,\cdots,m)$ can be indefinite. Ref. 2 and 
Ref. 3  
have proposed to compute a lower bound by solving the following semidefinite 
programming

\noindent
$(SDP1)$\quad $\mu_{1}=$ max $t$

\quad\quad\quad\quad\quad\ \ subject to
\[\quad\quad\quad
t \left[ \begin{array}{c}
0\ \ \ \  0\\
\ 0\ -1
\end{array} \right]+\tau_{1}
\left[ \begin{array}{c}
A_{1}\ b_{1}\\
b_{1}^{t}\ c_{1}
\end{array} \right]+\cdots +
\tau_{m}\left[ \begin{array}{c}
A_{m}\ b_{m}\\
b_{m}^{t}\ c_{m}
\end{array} \right]
\]
\[
\succeq 
\left[ \begin{array}{c}
-A_{0}\ -b_{0}\\
-b_{0}^{t}\ -c_{0}
\end{array} \right],\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad
\] 

\quad\quad\quad\quad\quad\quad $\tau_{i}\geq 0,\ i=1,\cdots,m$.

  It is easy to check that $\mu_{1}$ is a lower bound of $(QP1)$, i.e., 
$\mu_{1}\leq \rho_{1}$. 

{\bf Remark 1.1}. If both $(QP1)$ and $(SDP1)$ are feasible, then both of 
them have optimal solutions.

  The above remark is trivial result, but it does tell us that for some class of 
nonconvex quadratic programming problems, semidefinite programming method can 
also tell whether $(QP1)$ has optimal solutions. 

   Our purpose is to use $(SDP1)$ to compute a lower bound for $(QP1)$. But 
$(SDP1)$ may be infeasible, such examples can be given easily. Even $(SDP1)$ 
is feasible, there is still a question on how to find an interior feasible 
solution. In the following section, we will consider how to find interior 
feasible solutions for $(SDP1)$ and its dual.

\section{Interior Feasible Points for the Primal and the Dual}

\quad In order to apply the primal and dual interior point method to 
solve $(SDP1)$, we need 
to provide starting points, i.e., interior feasible points for the primal and 
the dual. In th subsequent arguments, we need two assumptions as follows.

{\bf Assumption 2.1}. $(QP1)$ has an optimal solution.

{\bf Assumption 2.2}. (Slater condition) There exists a point $x^{0}\in R^{n}$ 
such that
\[
f_{i}(x^{0})<0,\ i=1,\cdots,m.
\]

{\bf Proposition 2.1}. There exists a sufficiently large $r>0$ such that 
any optimal solution of $(QP2)$ is also an optimal solution of $(QP1)$, where 
$(QP2)$ is defined as

\noindent
$(QP2)$\quad\quad $\rho_{2}=$ min $f_{0}(x)$,

\quad\quad\quad\quad\quad\quad subject to

\quad\quad\quad\quad\quad\quad $f_{i}(x)\leq 0,\ i=1,\cdots,m$,

\quad\quad\quad\quad\quad\quad $ x_{1}^{2}+\cdots +x_{n}^{2}\leq r.$

   The reason we use $(QP2)$ to replace $(QP1)$ is that the corresponding 
semidefinite programming to $(QP2)$ always has interior feasible points. 
Let us write down the corresponding semidefinite programming to $(QP2)$.

\noindent
$(SDP2)$\quad $\mu_{2}=$ max $t$

\quad\quad\quad\quad\quad\ \ subject to
\[\quad\quad\quad
t \left[ \begin{array}{c}
0\ \ \ \  0\\
\ 0\ -1
\end{array} \right]+
\tau_{0}
\left[ \begin{array}{c}
I\ \ \ 0\\
\ 0\ -r
\end{array} \right]
+\tau_{1}
\left[ \begin{array}{c}
A_{1}\ b_{1}\\
b_{1}^{t}\ c_{1}
\end{array} \right]+\cdots +
\]
\[
\tau_{m}\left[ \begin{array}{c}
A_{m}\ b_{m}\\
b_{m}^{t}\ c_{m}
\end{array} \right]
\succeq
\left[ \begin{array}{c}
-A_{0}\ -b_{0}\\
-b_{0}^{t}\ -c_{0}
\end{array} \right],\quad\quad\quad\quad\ \ 
\]

\quad\quad\quad\quad\quad\quad $\tau_{i}\geq 0,\ i=0,\cdots,m$.

{\bf Remark 2.1}. From Proposition 2.1, we know $\rho_{1}=\rho_{2}$, but 
$\mu_{1}\leq \mu_{2}$. Sometime we may have $\mu_{1}< \mu_{2}$.

    From the special structure of $(SDP2)$, we can get an interior feasible 
point easily by taking $\tau_{i}=1$ for $i=1,\cdots,m$ and sufficiently 
large $-t$ and $\tau_{0}$.

    Since we also need to find an interior feasible point for the dual of 
$(SDP2)$, let us write down the dual of $(SDP2)$ 

\[
(DSDP2)\quad\quad\quad \mbox{max}\ tr\left[ 
\begin{array}{c}
-A_{0}\ -b_{0}\\
-b_{0}^{t}\ -c_{0}
\end{array} \right] X, \quad\quad\quad\quad\quad\quad
\quad\quad\quad\quad\quad\quad\quad\quad\quad
\]

\quad\quad\quad\quad\quad\quad subject to

\quad\quad\quad\quad\quad\quad $X(n+1,n+1)=1$,

\quad\quad\quad\quad\quad\quad $\sum_{j=1}^{n}X(j,j)-r\leq 0,$

\[
tr\left[ \begin{array}{c}
A_{i}\ b_{i}\\ 
b_{i}^{t}\ c_{i}
\end{array}
\right] X \leq 0,\ i=1,\cdots,m,\quad\quad\quad\quad
\]

\quad\quad\quad\quad\quad\quad $X\succeq 0$.

   Now let us explain how to find an interior feasible point for $(DSDP2)$. In 
doing so, we need Assumption 2.2 and the following process:

{\bf Step 2.1}. From $f_{i}(x)=f_{i}(x^{0})+\nabla f_{i}(x^{0})(x-x^{0})+
(x-x^{0})^{t}A_{i}(x-x^{0})$, we can get an equivalent quadratic programming 
to $QP2)$ by setting $y=x-x^{0}$. For the new $(QP2)$, Assumption 2.2 implies 
new $c_{i}=f_{i}(x^{0})<0$, $i=1,\cdots,m$.

{\bf Step 2.2}. Set up the corresponding $(SDP2)$ for new $(QP2)$ established 
in Step 2.1.

{\bf Step 2.3}. Take $X$ to be a positive diagnal matrix such that
\[
\sum_{j=1}^{n}X(j,j)<r\ \mbox{and}\ 
\sum_{j=1}^{n}A_{i}(j,j)X(j,j)<-c_{i},\ i=1,\cdots,m.
\]

   Since $r>0$ and $-c_{i}>0$ for $i=1,\cdots,m$, the inequalities in Step 2.3 
can be satisfied by setting $X(j,j)$ $(j=1,\cdots,n)$ small enough. So this 
gives an interior feasible points for $(DSDP2)$.

   So far we already know how to find interior points for the primal and the 
dual. Therefore we can compute a lower bound for a given nonconvex 
quadratic programming problems. But there are still some questions which we 
need to do further consideration. For example, (i) 
is it the best way to add a ball 
constraint in $(QP1)$?  (ii) If some $A_{i}=0$ $(i=1,\cdots,m)$, i.e., if we 
have some purely linear constraints in $(QP1)$, how to deal with these linear 
constraints? We will consider these problems in next section.

\section{Nonconvex Quadratic Programming with Linear Constraints}

\quad In this section we consider the following quadratic programming problem

\noindent
$(QP3)$\quad\quad $\rho_{3}=$ min $x^{t}A_{0}x+2b_{0}^{t}x+c_{0}$,

\quad\quad\quad\quad\quad\quad subject to

\quad\quad\quad\quad\quad\quad $a_{i}^{t}x-b_{i}\leq 0,\ i=1,\cdots,m$, 

\noindent
where $A_{0}\in S^{n},\ b_{0},a_{i}\in R^{n},\ c_{0},b_{i}\in R^{1},\ 
i=1,\cdots,m$. 
If we use $(SDP2)$ to form the semidefinite programming for $(QP3)$, we have 

\noindent
$(SDP3)$\quad $\mu_{3}=$ max $t$

\quad\quad\quad\quad\quad\ \ subject to
\[\quad\quad\quad
t \left[ \begin{array}{c}
0\ \ \ \  0\\
\ 0\ -1
\end{array} \right]+
\tau_{0}
\left[ \begin{array}{c}
I\ \ \ 0\\
\ 0\ -r
\end{array} \right]
+\tau_{1}
\left[ \begin{array}{c}
0\ \ \quad\ 0.5a_{1}\\
0.5a_{1}^{t}\ \quad -b_{1}
\end{array} \right]+\cdots +
\]
\[
\tau_{m}\left[ \begin{array}{c}
0\ \ \quad\ 0.5a_{m}\\
0.5a_{m}^{t}\ \quad -b_{m}
\end{array} \right]
\succeq
\left[ \begin{array}{c}
-A_{0}\ -b_{0}\\
-b_{0}^{t}\ -c_{0}
\end{array} \right],\ \ \quad\quad\quad\quad
\]

\quad\quad\quad\quad\quad\quad $\tau_{i}\geq 0,\ i=0,\cdots,m$.

  In the most cases, a semidefinite approximation from a linear constraint does not give much improvement on lower bounds. That is, if $(t^{*},\tau_{0}^{*}$,
$\tau_{1},\cdots,\tau_{m})$ is an optimal solution for $(SDP3)$, then 
$\tau_{i}^{*}=0$ for most $i$ $(i=1,\cdots,m)$. Even some $\tau_{i}^{*}>0$, 
it is always a quite small number. So we need to use the quadratic constraints 
derived from the linear constraints to replace the linear constraints. Shor 
(Ref. 2) has suggested the following process: 

   For any $i,j$ with $i\neq j$, form a quadratic constraint

   $-(a_{i}^{t}x-b_{i})(a_{j}^{t}x-b_{j})\leq 0$.

\noindent
Note that the Hessian of $-(a_{i}^{t}x-b_{i})(a_{j}^{t}x-b_{j})$ is 
$0.5(a_{i}a_{j}^{t}+a_{j}a_{i}^{t})$, so if $a_{i}\approx -a_{j}$, a semidefinite 
approximation from $-(a_{i}^{t}x-b_{i})(a_{j}^{t}x-b_{j})\leq 0$ will do a better 
job on improving the lower bounds. For the above process, Shor (Ref. 2) proved 
the following theorem.

{\bf Theorem 3.1}. If the convex hull of the vectors $a_{i}$ $(i=1,\cdots,m)$ has 
zero as an interior points, there exists a nonnegative vector of Lagrange 
multipliers $\{\lambda_{ij}\}_{i,j=1}^{m}$ such that 
\[
-\sum_{i,j=1,i\neq j}^{m}\lambda_{ij}(a_{i}a_{j}^{t}+a_{j}a_{i}^{t})
\succ -A_{0}.
\]

 Shor (Ref. 2) also established the following corollary from Theorem 3.1.

{\bf Corollary 3.1}. If polyhedron $\{x\in R^{n}\mid a_{i}^{t}x-b_{i}\leq 0$, 
$i=1\cdots,m\}$ is nonempty and bounded, there exists a nonnegative vector of 
Lagrange multipliers $\{\lambda_{ij}\}_{i,j=1}^{m}$ such that 
\[
-\sum_{i,j=1,i\neq j}^{m}\lambda_{ij}(a_{i}a_{j}^{t}+a_{j}a_{i}^{t})
\succ -A_{0}.
\]

In fact, the conditions of Theorem 3.1 and Corollary 3.1 are equivalent in 
some sense.

{\bf Proposition 3.1}. If polyhedron $\{x\in R^{n}\mid a_{i}^{t}x-b_{i}\leq 0$, 
$i=1\cdots,m\}$ is nonempty, then it is bounded iff the convex hull of 
the vectors $a_{i}$ $(i=1,\cdots,m)$ has
zero as an interior points.

{\bf Remark 3.1}. By Proposition 3.1, the coodition of Theorem 3.1 implies that 
$\{x\in R^{n}\mid a_{i}^{t}x-b_{i}\leq 0$,$i=1\cdots,m\}$ is empty or bounded.

{\bf Remark 3.2}. From the above, we can see that what Shor considered is exactly 
a bounded case. 

   Now let us consider how to get rid of the ball constraint added to $(QP1)$ 
in $(QP2)$ if 
we know that the feasible region of $(QP1)$ is bounded, i.e., we have 
$l_{i}\leq x_{i}\leq u_{i}$, where $l_{i}<0$ and $u_{i}>0$, $i=1,\cdots,n$. 
There are two ways to deal with this problem.

(i) Use $x_{i}^{2}\leq (max\{-l_{i},u_{i}\})^{2}$ to replace 
$l_{i}\leq x_{i}\leq u_{i}$ for $i=1,\cdots,n$. In this way, the ball 
constraint in $(QP2)$ is not needed.

(ii) As Shor suggested in the above, use $(x_{i}-l_{i})(x_{i}-u_{i})\leq 0$ to 
replace $l_{i}\leq x_{i}\leq u_{i}$ for $i=1,\cdots,n$. In this way, the ball
constraint in $(QP2)$ is not needed either.

From the examples we dealt with, (ii) seems better than (i). Obviously, (i) and 
(ii) are same if $u_{i}=-l_{i}$ for $i=1,\cdots,n$.

   Before the end of this section, we like to consider an application of main 
idea of this section. 

{\bf Example 3.1}. For a given symmetric matrix $C\in R^{n\times n}$ and vectors 
$a_{i}\in R^{n}$, $i=1,\cdots,m$, we like to know if the following condition 
holds
\[
x^{t}Cx\geq 0\ \mbox{for any}\ x\in \{y\in R^{n}\mid a_{i}^{t}y\leq 0,\ 
i=1,\cdots,m\}.
\]

   This is a copositivity problem. The following 
is a sufficient condition for $C$ to be copositive on the cone 
$\{y\in R^{n}\mid a_{i}^{t}y\leq 0,\ i=1,\cdots,m\}$: 
there exists a nonnegative vector of Lagrange
multipliers $\{\lambda_{ij}\}_{i,j=1}^{m}$ such that
\[
-\sum_{i,j=1,i\neq j}^{m}\lambda_{ij}(a_{i}a_{j}^{t}+a_{j}a_{i}^{t})
\succeq -C.
\]
\noindent
So a semidefinite programming can be formed to check the above 
sufficient condition as follows

\noindent
$(SDP4)$\quad $\mu_{4}=$ min $t$,

\quad\quad\quad\quad\quad\ \ subject to 

\[tI-\sum_{i,j=1,i\neq j}^{m}\lambda_{ij}(a_{i}a_{j}^{t}+a_{j}a_{i}^{t})
\succeq -C. \quad\quad\quad\  
\]

\quad\quad\quad\quad\quad\ \ $t\geq 0,\lambda_{ij}\geq 0,\ i,j=1,\cdots,m$.
\noindent

\noindent
That is, the above sufficient condition holds iff $\mu_{4}=0$. 



\section{Some Computational Examples}

\quad {\bf Example 4.1}. (A testing problem from Ref. 1)

$\ $

\quad\quad Min $37.293239x_{1}+0.8356891x_{1}x_{5}+5.357854x_{3}^{2}-
40729.141,$

\quad\quad Subject to 

\quad\quad $-0.0022053x_{3}x_{5}+0.0056858x_{2}x_{5}+0.0006262x_{1}x_{4}-
6.665593 \leq 0,$

\quad\quad $0.0022053x_{3}x_{5}-0.0056858x_{2}x_{5}-0.0006262x_{1}x_{4}-
85.334407 \leq 0,$

\quad\quad $0.0071317x_{2}x_{5}+0.0021813x_{3}^{2}+0.0029955x_{1}x_{2}
-29.48751 \leq 0,$

\quad\quad $-0.0071317x_{2}x_{5}-0.0021813x_{3}^{2}-0.0029955x_{1}x_{2}
+9.48751 \leq 0,$

\quad\quad $0.0047026x_{3}x_{5}+0.0019085x_{3}x_{4}+0.0012547x_{1}x_{3}
-15.699039\leq 0,$

\quad\quad $-0.0047026x_{3}x_{5}-0.0019085x_{3}x_{4}-0.0012547x_{1}x_{3}
+10.699039\leq 0,$

\quad\quad $78\leq x_{1}\leq 102,$

\quad\quad $33\leq x_{2}\leq 45,$

\quad\quad $27\leq x_{3}\leq 45,$

\quad\quad $27\leq x_{4}\leq 45,$

\quad\quad $27\leq x_{5}\leq 45.$


Best known solution:

\quad\quad $x^{*}=(78,33,29.9953,45,36.7758)$

\quad\quad $f(x^{*})=-30665.5387$


In order to find interior points for the primal and the dual of 
corresponding SDP much easily, we have 
done the following transformation for the above problem:

\quad\quad $x_{1}=100+y_{1},$

\quad\quad $x_{2}=35+y_{2},$

\quad\quad $x_{3}=40+y_{3},$

\quad\quad $x_{4}=30+y_{4},$

\quad\quad $x_{5}=30+y_{5},$

i.e., $x^{0}=(100,35,40,30,30)^{t}$.

\noindent
So, the above problem is equivalent to:

\quad\quad Min $62.363912y_{1}+
428.62838y_{3}+83.56891y_{5}+
0.8356891y_{1}y_{5}+5.357854y_{3}^{2}
$

\quad\quad\quad\quad\quad $-25983.182,$

\quad\quad Subject to

\quad\quad$-0.0022053y_{3}y_{5}+0.0056858y_{2}y_{5}
+0.0006262y_{1}y_{4}
+0.018786y_{1}+$

\quad\quad$0.170574y_{2}-0.066159y_{3}+0.06262y_{4}+0.110791y_{5}-
1.463263 \leq 0,$

\quad\quad $0.0022053y_{3}y_{5}-0.0056858y_{2}y_{5}
-0.0006262y_{1}y_{4}
-0.018786y_{1}-$

\quad\quad $0.170574y_{2}+0.066159y_{3}-0.06262y_{4}+0.110791y_{5}-
90.536737 \leq 0,$

\quad\quad $0.0071317y_{2}y_{5}+0.0021813y_{3}^{2}+0.0029955y_{1}y_{2}
+0.1048425y_{1}+$

\quad\quad $0.513501y_{2}+0.174504y_{3}+0.2496095y_{5}
-8.0249 \leq 0,$

\quad\quad $-0.0071317y_{2}y_{5}-0.0021813y_{3}^{2}-0.0029955y_{1}y_{2}
-0.1048425y_{1}-$

\quad\quad $0.513501y_{2}-0.174504y_{3}-0.2496095y_{5}
-11.975105 \leq 0,$

\quad\quad $0.0047026y_{3}y_{5}+0.0019085y_{3}y_{4}+0.0012547y_{1}y_{3}
+0.050188 y_{1}+$

\quad\quad $0.3238y_{3}+0.07634y_{4}+0.188104y_{5}
-2.746919\leq 0,$

\quad\quad $-0.0047026y_{3}y_{5}-0.0019085y_{3}y_{4}-0.0012547y_{1}y_{3}
-0.050188 y_{1}-$

\quad\quad $0.3238y_{3}-0.07634y_{4}-0.188104y_{5}
-2.253081\leq 0,$

\quad\quad $-22\leq y_{1}\leq 2,$

\quad\quad $-2\leq y_{2}\leq 10,$

\quad\quad $-13\leq y_{3}\leq 5,$

\quad\quad $-3\leq y_{4}\leq 15,$

\quad\quad $-3\leq y_{5}\leq 15.$


If we use the following quadratic constraints $y_{1}^{2}\leq 484$, 
$y_{2}^{2}\leq 100$, $y_{3}^{2}\leq 169$, $y_{4}^{2}\leq 225$ and 
$y_{5}^{2}\leq 225$ to replace the above linear constraints, SDP provides 
a lower bound $-30962$. 

If we replace the above linear constraints by the following quadratic 
constraints

\quad\quad $y_{1}^{2}+20y_{1}-44\leq 0,$

\quad\quad $y_{2}^{2}-8y_{2}-20\leq 0,$

\quad\quad $y_{3}^{2}+8y_{3}-65\leq 0,$

\quad\quad $y_{4}^{2}-12y_{4}-45\leq 0,$

\quad\quad $y_{5}^{2}-12 y_{5}-45\leq 0,$

\noindent
then SDP provides a lower bound $-30765$. 

   From this example, we can see at least two facts: (i) A proper 
quadratic representation for linear constraint can really improve 
a lower bound and (ii) Since $-30765$ is quite closed to $-30665.5387$, 
$-30765$ and $-30665.5387$ are a nice lower bound and a acceptable 
`optimal' value, respectively.


{\bf Example 4.2}. Cosider 

\quad\quad\quad\quad min $x_{1}^{2}+x^{2}_{2}-x_{3}^{2}-x_{4}^{2}+x_{1}-2x_{2}
-3x_{3}+x_{4}$

\quad\quad\quad\quad subject to

\quad\quad\quad\quad $-x_{1}^{2}+3x_{3}^{2}-x_{4}\leq 10$,

\quad\quad\quad\quad $x_{1}x_{3}-x_{2}x_{4}-3x_{1}+2x_{4}\leq 4$,

\quad\quad\quad\quad $-x_{2}^{2} +2x_{4}^{2}+x_{3}\leq 9,$

\quad\quad\quad\quad $x_{1}x_{4}-x_{3}^{2}-x_{2}^{2}+2x_{2}\leq 2.$

     This is a nonconvex problem and the feasible region is unbounded. We like 
to know whether the problem has optimal solutions or not. If it has optimal 
solutions, find a lower bound for the problem. 

   In order to answer the above question, we add a ball constraint just like 
model $(QP2)$, say $r=400$. Then we use $(SDP2)$ to compute $\mu_{2}$. We get 
$\mu_{2}=-16.0196$ and $(t^{*},\tau_{0}^{*},\tau_{1}^{*},\tau_{2}^{*}$
$,\tau_{3}^{*},\tau_{4}^{*})$
$=(-16.0195,0,0.571,0,0.5436,0)$. Since $\tau_{0}^{*}=0$, the problem has an 
optimal solution and $\mu_{2}=-16.0196$ is indeed a lower bound. 
It is easy to check that $x=(0,1,2,2)$ is a feasible solution with the objective 
value $-13$. So $\mu_{2}=-16.0196$ is a nice lower bound.   

   This is a simple example. But from it, we can see that for some class of 
nonconvex quadratic programming problems, SDP method can tell us if problem has 
optimal solution, if it has, a lower bound can be computed. In fact, if 
$(QP1)$ is feasible and we only want to know  
whether $(QP1)$ has optimal solution or not, the following SDP will provide 
a sufficient condition

\noindent
$(SDP5)$\quad $\mu_{5}=$ min $\tau_{0}$

\quad\quad\quad\quad\quad\ \ subject to
\[\quad\quad\quad
t \left[ \begin{array}{c}
0\ \ \ \  0\\
\ 0\ -1
\end{array} \right]+
\tau_{0}
\left[ \begin{array}{c}
I\ \ \ 0\\
\ 0\ -r
\end{array} \right]
+\tau_{1}
\left[ \begin{array}{c}
A_{1}\ b_{1}\\
b_{1}^{t}\ c_{1}
\end{array} \right]+\cdots +
\]
\[
\tau_{m}\left[ \begin{array}{c}
A_{m}\ b_{m}\\
b_{m}^{t}\ c_{m}
\end{array} \right]
\succeq
\left[ \begin{array}{c}
-A_{0}\ -b_{0}\\
-b_{0}^{t}\ -c_{0}
\end{array} \right],\quad\quad\quad\quad\ \
\]

\quad\quad\quad\quad\quad\quad $\tau_{i}\geq 0,\ i=0,\cdots,m$,

\noindent
i.e., $\mu_{5}=0$ implies that $(QP1)$ has an optimal solution.

{\bf Example 4.3}. Consider 

\quad\quad\quad min $2x_{1}^{2}+2x_{1}x_{2}+x_{2}^{2}+4x_{3}^{2}-x_{4}^{2}+
x_{3}x_{5}+x_{5}^{2}-2x_{6}^{2}$

\quad\quad\quad\quad\quad\  $+0.7x_{1}-0.8x_{2}-1.8x_{3}-3x_{4}+0.2x_{5}+2.2x_{6}$

\quad\quad\quad subject to

\quad\quad\quad $-2\leq x_{1}+x_{2}\leq 3,$

\quad\quad\quad $-2\leq x_{2}+x_{3}\leq 3,$

\quad\quad\quad $-2\leq x_{3}+x_{4}\leq 3,$

\quad\quad\quad $-2\leq x_{4}+x_{5}\leq 3,$

\quad\quad\quad $-2\leq x_{5}+x_{6}\leq 3,$

\quad\quad\quad $-2\leq x_{1}+x_{4}+x_{6}\leq 3.$

   For this problem, it is easy to check $-33\leq$ the optimal value 
$\leq -30$. When we use quadratic constraints derived by the linear constraints 
to replace the linear constraints, SDP gives a lower bound $-48.4394$. 
So we can see 
that this lower bound is too far away from the optimal value relatively. 
In fact, the feasible region of this problem is bounded and the quadratic 
constraints derived from the linear constraints are convex. So it seems 
that SDP does not provide a nice lower bound for nonconvex quadratic 
programming problems with purely linear constraints. However, 
for some class of nonconvex quadratic programming problems with purely linear 
constraints we 
can also use SDP method to check whether the problem has optimal solutions or 
not just like what we did in Example 4.2. Of course, here we need to use 
the quadratic constraints derived from the linear constraints to 
replace the linear constraints. 


\section{Conclusion}

\quad This project has explained how to use the semidefinite programming to 
compute a lower bound for nonconvex quadratic programming problems as 
suggested by Ref. 2 and Ref. 3. A simple procedure for finding interior 
feasible points to the primal and the dual is given. Some possible 
applications are discussed. Computational results show that for some class of 
nonconvex quadratic programming problems, the semidefinite programming 
really give a nice lower bound.  
$\ $

\noindent
References

\begin{description}
\item [] [1] C.A. Floudas and P.M. Pardalos, A Collection of Test Problems for 
Constrained Global Optimization Algorithms, {\em 
Lecture Notes in Computer Science}, 
{\bf 455}, Springer-Verlag, Berlin, 1990.

\item [] [2] N.Z. Shor, Quadratic Optimization Problems, 
{\em Tekhnicheskaya Kibernetica}, No. 1, 1987, pp. 128-139.

\item [] [3] L. Vandenberghe and S. Boyd, Positive Definite Programming, 
Submitted to {\em SIAM Review}, July, 1994.

\end{description}


\end{document}
