\documentclass{slides}
%\documentclass{article}
\pagestyle{plain}
%\setlength{\textheight}{5.3in}
%\setlength{\textwidth}{5.35in}
\setlength{\leftmargin}{0in}
\newcommand{\F}{{\cal F}}
\newcommand{\Kprod}{\otimes}
\newcommand{\Diag}{\rm Diag\,}
\newcommand{\Sn}{{\cal S}_n}
\newcommand{\tran}{^T}
\newcommand{\diag}{\rm diag\,}
\newcommand{\tr}{\rm trace\,}
\newcommand{\trace}{\rm trace\,}
\newcommand{\svec}{{\rm svec\,}}
\newcommand{\sMat}{{\rm sMat\,}}
\newcommand{\hMat}{{\rm hMat\,}}
\newcommand{\dsvec}{{\rm dsvec\,}}
\newcommand{\sdiag}{{\rm sdiag\,}}
\newcommand{\vsMat}{{\rm vsMat\,}}
\newcommand{\kvec}{{\rm vec\,}}
\newcommand{\kmat}{{\rm Mat\,}}
\newcommand{\beq}{\begin{equation}}
\newcommand{\eeq}{\end{equation}}
\newcommand{\nc}{\newcommand}
\nc{\Hcal}{{\cal H}}
%\renewcommand{\leftmargin}{-.5in}


\newcommand{\rank}{{\rm rank\,}}
\newcommand{\p}{{\cal P}}
\newcommand{\trian}{{\rm trian\,}}
\newcommand{\Trian}{{\rm Trian\,}}
\newcommand{\BoDiag}{{\rm B^0Diag\,}}
\newcommand{\OoDiag}{{\rm O^0Diag\,}}
\newcommand{\arrow}{{\rm arrow\,}}
\newcommand{\Arrow}{{\rm Arrow\,}}
\newcommand{\bodiag}{{\rm b^0diag\,}}
\newcommand{\oodiag}{{\rm o^0diag\,}}
\newcommand{\ck}{{\cal C}_k}
\newcommand{\dk}{{\cal D}_k}
\newcommand{\uu}{{\cal U}}
\newcommand{\uk}{{\cal U}_k}
\newcommand{\vk}{{\cal V}_k}
\newcommand{\wk}{{\cal W}_k}
\newcommand{\wm}{{\cal W}_m}
\newcommand{\w}{{\cal W}}
\newcommand{\wks}{{\cal W}^s_k}
\newcommand{\wms}{{\cal W}^s_m}
\newcommand{\zk}{{\cal Z}_k}
\newcommand{\zks}{{\cal Z}^s_k}
\newcommand{\z}{{\cal Z}}
\newcommand{\n}{{\cal N}}
\newcommand{\ra}{{\cal R}}
\newcommand{\q}{{\cal Q}}
\newcommand{\s}{{\cal S}_n}
\newcommand{\m}{{\cal M}_{n}}
\newcommand{\req}[1]{(\ref{#1})}
\newcommand{\adj}{{\rm adj\,}}
\newcommand{\relint}{{\rm relint\,}}




\def\QED{~\rule[-1pt] {8pt}{8pt}\par\medskip ~~}
\begin{document}
%=======================
%=======================
\begin{slide}{}
\begin{center}
{\bf
Is Lagrangian (SDP) Relaxation Best for Quadratic Optimization?
}
\end{center}


~~\\
~~\\
~~\\
~~\\
~~\\
~~\\
Henry Wolkowicz \\
University of Waterloo\\

~\\
~\\

\end{slide}
\begin{slide}{}
%\large{
\begin{center}
{\bf OUTLINE}
\end{center}
%}
\begin{enumerate}
\item[$\bullet$]
Quadratically constrained quadratic program, QQP.

\item[$\bullet$]
Special case of Max-Cut, MC, problem:\\
equivalent bounds to Lagrangian (SDP) relaxation\\
redundant constraints - strengthened SDP bound

\item[$\bullet$]
SDP equivalent to Lagrangian relaxation for QQPs.

\item[$\bullet$]
Theme (or conjecture):
{\em Lagrangian relaxation is best}

\item[$\bullet$]
zero duality gap for nonconvex problems
\end{enumerate}

\end{slide}
\begin{slide}{}


\begin{center}
We work with quadratically constrained quadratic programs\\
{\bf QQPs}
\end{center}

\[
         q_i(x) : =  x^TQ_ix+2g_i^Tx +\alpha_i, \quad Q_i=Q_i^T
\]
\[
(\mbox{QQP})
   \begin{array}{rcl}
        q^*:= &  \min  & q_0(x)\\
&{\rm subject~to} & q_k(x) \leq 0\\
  && k \in {\cal I} :=\{1, \ldots , m\}\\
&& x \in \Re^n
            \end{array}
\]
Lagrangian of QQP
\[
          L(x,\lambda):= q_0(x)
 + \sum_{k \in {\cal I} } \lambda_k q_k(x),
\]
$\lambda=(\lambda_k) \geq 0$ are nonnegative Lagrange
multipliers.

\end{slide}
\begin{slide}{}

{\bf Lagrange multipliers - two uses.}

1. Classical: if a CQ holds at optimum
$\bar{x}$, then the KKT necessary conditions for optimality
hold
\begin{eqnarray*}
    \bar{\lambda} \geq 0, \nabla L(\bar{x},\bar{\lambda})=0\\
     \bar{x} \mbox{ feasible }\\
     \bar{\lambda}_k q_k(\bar{x})=0, \forall k \in {\cal I}
\end{eqnarray*}
If the Lagrangian at $\bar{\lambda}$ is also convex
in $x$, then KKT sufficient for optimality.

2. Lagrangian Relaxation (duality):
\[
       q^* \geq d^*:=  \max\limits_{\lambda \geq 0}
          \min_x  q_0(x)  
 + \sum_{k \in {\cal I} } \lambda_k q_k(x).
\]




\end{slide}
\begin{slide}{}

Zero duality gap holds if $q^*=d^*.$ 

Strong duality holds if $q^*=d^*$ and also $d^*$ is attained. 

Moreover, $d^*$ can be efficiently evaluated using SDP.

Questions:\\
$\bullet$Can one do better than the Lagrangian relaxation?\\
$\bullet$When does a zero duality gap hold?\\
$\bullet$What redundant constraints can
be added to close (or reduce) the duality gap?








\end{slide}

\begin{slide}{}

\begin{center}
{\bf Tractable Relaxations of Max-Cut}
\end{center}
\[
(MCQ)~~~  \begin{array}{c}
   \mu^*:= \max\limits_{x \in \F} q_0(x) \quad ( : = x^TQx -2 c^Tx).
\end{array}
\]
where $\F=\left\{\pm 1\right\}^n$\\
--------------------------------

perturbing diagonal of $Q$ on $\F:$
\[
\begin{array}{rcl}
q_u(x)& : = &x^T(Q+\Diag(u))x -2 c^Tx - u^Te\\
      &~=&q_0(x),~~\forall x \in \F.
\end{array}
\]

\end{slide}
\begin{slide}{}
{\bf Bound 0:}
trivial bound from diagonal perturbations:
\[
  \mu^* \leq f_0 (u) := \max_x q_u(x).
\]
The function $f_0$ can take on the value $+\infty.$ 
Let 
\[S:=\left\{u:u^Te=0, Q+\Diag(u)\preceq 0\right\}.
\]
Then:
\[
\begin{array}{|c|}
\hline\\
  \mu^* \leq B_0 := \min\limits_u  f_0(u) \\
    \left(= \min\limits_{u^Te=0}  f_0(u),
       \mbox{ if } S \neq \emptyset   \right).  \\
~\\
\hline
\end{array}
\]
Using the hidden semidefinite constraint:
\[
  \mu^* \leq B_0 = \min\limits_{Q+\Diag(u) \preceq 0}  f_0(u).
\]

\end{slide}
\begin{slide}{}
{\bf Bound 1:}
relax the feasible set to
the sphere of radius $\sqrt{n}$ (tractable trust region subproblem, TRS):
\[
\mu^* \leq f_1(u):= \max_{|| x ||^2 =n} ~ q_u(x)
\]
and
\[
\begin{array}{|c|}
\hline\\
  \mu^* \leq B_1 :=\min\limits_u f_1(u).\\
~~\\
\hline
\end{array}
\]


The inner maximization problem is called a
trust region subproblem and is tractable.
This bound provides the central tool in the proofs of equivalence.

\end{slide}
\begin{slide}{}
{\bf Bound 2:} box constraint:
\[
\mu^* \leq f_2(u):= \max_{| x_i | \leq 1} ~ q_u(x).
\]
add the semidefinite constraint to make bound
tractable.
\[
  \mu^* \leq \min\limits_{u} f_2(u)
\]
and
\[
\begin{array}{|c|}
\hline\\
  \mu^* \leq B_2 :=\min\limits_{Q+\Diag(u) \preceq 0} f_2(u).\\
~~\\
\hline
\end{array}
\]


\end{slide}
\begin{slide}{}
{\bf Bound $B_1^c$:} lift to eigenvalue bound:

\[
 Q^c := \left[ \begin{array}{cc}
   0 &  - c^T \\
  - c &Q    \end{array}  \right]
\]
\[
 q^c_u(y) :=   y^T( Q^c+\diag(u))y-u^Te
\]
\[
  \mu^* \leq f_1^c(u) := \max_{||y||^2=n+1} q^c_u(y)
\]
where
\[
   \max_{||y||^2=n+1} q^c_u(y)
   = (n+1) \lambda_{\max} (Q^c + \diag (u) ) - u^Te
\]
\[
\begin{array}{|c|}
\hline\\
  \mu^* \leq B_1^c :=  \min\limits_{u} f_1^c(u).\\
~~\\
\hline
\end{array}
\]

Similarly, we get equivalent bounds $B_0^c$
and homogenized bounds for the other models.


\end{slide}
\begin{slide}{}
{\bf Bound $B_3$:} SDP bound:

After homogenization ( $c=0$), use
\[ x^TQx = \tr x^TQx = \tr Qxx^T\]
and, for $x \in \F,$ $y_{ij} = x_ix_j$ defines a
symmetric, rank one, positive semidefinite matrix $Y$ with diagonal elements 1.
Relax the rank one condition.
\[
\begin{array}{|ccc|}
\hline
&&\\
       B_3 :=&\max &\tr QY \\
 &  \mbox{~subject to~} &\diag(Y) = e \\
        && Y \succeq 0.\\
&&~\\
\hline
    \end{array}
\]



\end{slide}
\begin{slide}{}
Summary: ref. Polyak-Rendl-Wolkowicz (PRW) 1995.
(without restrictions e.g. $u^Te=0$)


\[
\begin{array}{|rcl|}
\hline
&&~\\
 B_0 &=&\min\limits_u \max\limits_x q_u(x)\\
 B_1 &=&\min\limits_u \max\limits_{x^Tx=n} q_u(x)\\
 B_2 &=&\min\limits_u \max\limits_{-1 \leq x_i \leq 1} q_u(x)\\
 B_3 &=&\max \{\tr Q^cY : \diag(Y) = e,~ Y \succeq 0. \}\\
 B_1^c &=&\min\limits_u \max\limits_{y^Ty=n+1} q^c_u(y)\\
&&~\\
\hline
\end{array}
\]


\end{slide}
\begin{slide}{}

Now replace $\pm 1$ constraints with $x_i^2=1, \forall i.$
\[
\begin{array}{ccc}
       (P_E)&\max & q_0(x)=x^TQx-2c^Tx \\
 &  \mbox{~subject to~} &
        x_i^2 = 1,~~i=1, \cdots, n.  \\
    \end{array}
\]
$B_L$ denotes Lagrangian relaxation bound.

Following our theme:
\begin{center}
\fbox{
{\bf Theorem } $B_L$ equals all above bounds.
}
\end{center}

 ref PRW/95.\\
(The proofs come from exploiting strong Lagrangian duality of TRS)


\end{slide}
\begin{slide}{}

{\bf A Strengthened SDP Bound for MC}
ref Anjos-Wolkowicz/99.


(second lifting - this is motivated by the strong duality results that follow
below and are from ref. Anstreicher-Wolkowicz/98 where redundant
constraints using $XX^T$ are shown to close the duality gap.)

first lifting procedure
\[ X=xx^T\]
implies second lifting procedure
\[X^2=xx^Txx^T=nX.\]
and provides an equivalent quadratic matrix model for MC

\end{slide}
\begin{slide}{}

\begin{eqnarray*}
\mu^*:=&\max& \tr QX\\
&\mbox{s.t.}&\diag(X)=e\\
&&X^2-nX=0\\
&&X \succeq 0.
\end{eqnarray*}
Note: $X^2=nX,~\trace X = n$ implies $X$ is rank one.
But, we cannot solve this nonconvex problem in general, i.e. we have to
look at the Lagrangian relaxation.
(We can also add the constraint $X \circ X = E,$ where $E$ is the matrix
of ones, and $\circ$ denotes the Hadamard matrix product.)



\end{slide}
\begin{slide}{}

notation (interesting operators and adjoints):\\
~$\bullet$ $S \in \Sn, \quad t(n)= \frac {n(n+1)}2$\\
~$\bullet$ $s=\svec(S) \in \Re^{t(n)}$ 
vector formed (columnwise) from $S$
ignoring strictly lower triang.\\
~$\bullet$ $S=\sMat(s)$ inverse of $\svec$\\
~$\bullet$ $\hMat (v)$ 
is adjoint of $\svec$,
off-diagonal terms are multiplied by a half\\
~$\bullet$ $\dsvec (S)$ is
adjoint of $\sMat$, operator 
like $\svec$ but off diagonal elements are
multiplied by 2\\
~$\bullet$ $\sdiag(s):= \diag( \sMat(s))$\\
~$\bullet$ $\vsMat(s)=\kvec(\sMat(s))$
\[\vsMat^*(s)=\dsvec \left( \left(\kmat(v)+\kmat(v)^T\right)/2 \right).
\]


\end{slide}
\begin{slide}{}

As above - use equivalent program
\[
 {\rm MC_O} \begin{array}{ccc}
    \mu^*=
    &\max &  \tr QX \\
  &\mbox{s.t.<}& \diag(X) = e\\
     &&X^2-nX=0.\\
\end{array}
\]
Replace objective with
  $\frac 1{n} QX^2$ linear constraint with $ ||\diag(X) - e||^2=0$ and
homogenize the problem. 
Use $X=\sMat(x)$.
\[
 {\rm MC_O} \begin{array}{cll}
     \mu^*=
    &\max & \frac 1{n} \tr Q\, \left(\sMat(x)\right)^2 \\
  &\mbox{s.t.}& \sdiag(x)^T \sdiag(x) \\
          && ~~~- 2 e^T \sdiag(x)y_0 + n=0\\
     &&\sMat(x)^2-n\, \sMat(x)y_0=0\\
     &&1-y_0^2=0.
\end{array}
\]

(Also include the Hadmard product constraint.)


\end{slide}
\begin{slide}{}

The dual  of this SDP  is the strengthened SDP relaxation of MC:
\[
\begin{array}{ccc}
     \mu^*_{MCSDP3} =
    &\max & \trace H_cY\\
  &\mbox{s.t.}& \Hcal_1^*(Y) = n\\
  &                 & \Hcal_2^*(Y) = 0\\
  &                 & \Hcal_3^*(Y) = 0\\
  &                 & \Hcal_4^*(Y) = 1\\
     && Y \succeq 0.
\end{array}
\]

Further: restrict $Y_{0j}=\diag(Y)_j=1$ corresponding to diagonal of
$X$.

The details of this derivation and numerical tests are contained in a
preliminary research report with URL:

http://orion.math.uwaterloo.ca:80/\~{ }hwolkowi\\
/henry/reports/ABSTRACTS.html\#strengthMC


\end{slide}
\begin{slide}{}

We now continue to look at various QQPs and the properties related to duality
gaps.

\end{slide}
\begin{slide}{}

{\bf Convex Quadratic Program}
\begin{eqnarray*}
\mbox{CQP}\qquad
\mu^*:=&\min& q_0(x)\\
&\mbox{s.t.}& q_k(x) \leq 0,\quad k=1, \ldots m,
\end{eqnarray*}
where all $q_i(x)$ are convex quadratic functions.
The dual is
\[ 
\mbox{DCQP}\qquad
\nu^*:= \max\limits_{\lambda \geq 0}\ \min\limits_x\ q_0(x)
           + \sum_{k=1}^m \lambda_k q_k(x).
\]

$\bullet$(KKT) conditions are sufficient for global optimality

$\bullet$if the primal value of CQP is bounded then it is
attained and there is no duality gap, (e.g. ref Peterson-Ecker
or  Terlaky).

$\bullet$ the dual may not be attained



\end{slide}
\begin{slide}{}
{\bf Nonconvex Cases}

{\bf 1. Rayleigh Quotient}

$A=A\tran \in \Sn$
\[
 \lambda_{\min} = \min \{x\tran Ax : x\tran  x = 1\}.
\]
tractable (nonconvex) problem

no (Lagrangian) duality gap even though this is a nonconvex problem
\[
\begin{array}{rcl}
 \mu^*&:=& \max\limits_{\lambda}\ \min\limits_x\ 
      x\tran Ax -\lambda (x\tran  x - 1)\\
 &=& \max\limits_{A - \lambda I \succeq 0}\ \min\limits_x\ 
               x\tran (A -\lambda I)x  + \lambda\\
 &=& \max\limits_{A - \lambda I \succeq 0}\ \lambda\\
 &=& \lambda_{\min}
\end{array}
\]


\end{slide}
\begin{slide}{}

{\bf 2. Trust Region Subproblem}
\begin{eqnarray*}
 &\mu^*:=\min& q_0(x)\\
&\mbox{s.t.}& x\tran x - \delta^2\leq 0 \mbox{ (or } =0). \\
\end{eqnarray*}
(more general nonconvex constraints $\alpha \leq q(x) \leq \beta.$)\\
for ``$\le$," the Lagrangian dual is:
\[ 
\mbox{DTRS}\qquad
 \nu^*:=\max\limits_{\lambda \geq 0}\ \min\limits_x\ q_0(x) + \lambda 
(x\tran x - \delta^2).
\]
strong duality holds and equivalent to (ref Stern-Wolkowicz/95) the
(concave) nonlinear semidefinite program 
\begin{eqnarray*}
\mbox{DTRS}\qquad
&\nu^*:=\max& g_0\tran  (Q+\lambda I)^{\dagger} g_0 - \lambda \delta^2\\
&\mbox{s.t.}& Q+\lambda I \succeq 0\\
&&\lambda \geq  0.
\end{eqnarray*}

Again our theme holds:
if we have a tractable problem  then strong duality holds.
(tractable:- ref e.g. More-Sorensen/83)



\end{slide}
\begin{slide}{}

short proof of strong duality (e.g. A. Lewis)

WLOG TRS is nonconvex; 
smallest eigenvalue of $Q_0,$ denoted $\gamma,$ is negative:
\[
\begin{array}{rccll}
 \mu^*& =& \min\limits_{x^Tx \leq \delta^2}
       & x^T(Q_0-\gamma I)x-2c_0^tx + \gamma x^Tx\\
 &= & \min\limits_{x^Tx = \delta^2}
       & x^T(Q_0-\gamma I)x-2c_0^tx + \gamma x^tx, 
                     & \mbox{($Q_0$ is indefinite)}\\
 &= & \min\limits_{x^Tx = \delta^2}
       & x^T(Q_0-\gamma I)x-2c_0^tx + \gamma \delta^2\\
 &= & \min\limits_{x^Tx \leq \delta^2}
       & x^T(Q_0-\gamma I)x-2c_0^tx + \gamma \delta^2, &\mbox{($Q_0-\gamma
                      I$ is singular)}\\
 &=&   \max\limits_{\lambda \geq 0} \min\limits_x
       & x^T(Q_0-\gamma I)x-2c_0^tx + \lambda(x^Tx-\delta^2) + \gamma \delta^2
                  & \mbox{(convex case)}\\
 &=&   \max\limits_{\lambda \geq 0} \min\limits_x
       & x^TQ_0x-2c_0^tx +(\lambda - \gamma) (x^Tx-\delta^2)\\
 &\leq &   \max\limits_{\lambda \geq \gamma} \min\limits_x
       & x^TQ_0x-2c_0^tx +(\lambda - \gamma) (x^Tx-\delta^2)
           & \mbox{($\gamma < 0$)}\\
 &=& \nu^* \leq   \mu^*.
\end{array}
\]



\end{slide}
\begin{slide}{}
{\bf 3. Two Trust Region Subproblem}
TTRS consists in minimizing a
(possibly nonconvex) quadratic function subject to a norm and a
least squares constraint.

ref in SQP methods by Celis-Dennis-Tapia.

TTRS can have a nonzero duality gap, ref Peng-Yuan.

if objective not convex,
then the primal may not be attained, ref Luo-Zhang.

TRS can have at most one local and nonglobal optimum, ref Martinez.

Still an open problem whether TTRS is an NP-hard or a polynomial time
problem.


\end{slide}
\begin{slide}{}

Note: a quadratic constraint can be written as
\[  y^tPy \leq \delta  \]
after the homogenization. This is lifted to
\[  \trace PY \leq \delta. \]
Second lifting:
\[   YPY \preceq \delta Y. \]
This strictly strengthens the SDP relaxation.


\end{slide}
\begin{slide}{}


{\bf Orthogonally Constrained Programs with Zero Duality Gaps}

permutation matrices are a subset of orthogonal matrices
\[ \Pi \subset {\cal O} := \{X: X X\tran =I\} \]
(Stiefel manifold ref e.g. Edelman,Arias,Smith)

$A$ and $B$ $n\times n$ symmetric matrices
\[
\begin{array}{rcl}
{\rm QQP_O}\qquad  \mu^*:=&\min& \tr AXBX\tran\\
&{\rm s.t.}& XX\tran=I.
\end{array}
\]


\end{slide}
\begin{slide}{}

Tractable problem; can be solved using
classical Hoffman-Wielandt inequality. Provides bounds for e.g. QAP.

Proof using first application of Lagrange multipliers:
\[L(X,S)= \tr AXBX\tran + S(XX^T-I)
\]
\[ 0= \left< \nabla L(X,S),h \right> = 2 \trace AXB h^T + SXIh^T
  \quad \forall h.
\]
Therefore $AXBX^T = -S=-S^T$, i.e. $A$ and $XBX^T$ are mutually
diagonalizable. The optimal value is then 
\[ \mu^* = \sum_i \lambda_i(A) \lambda_{n-i+1}(B)
\]

\end{slide}
\begin{slide}{}


But, Lagrangian dual can have a duality gap, ref Zhao,Karisch,Rendl,Wolkowicz

Lagrangian of $(P)$
$$
L(X,S) = \tr AXBX^t + \tr SXX^t - \tr S.
$$
Lagrangian dual is
\[
\nu^* = \max_S \min\limits_X  L(X,S).
\]
The hidden constraint (Hessian is psd) yields the dual
\[
(D)
\begin{array}{ccc}
\mu^D = &\max\limits_{\hat{S}=\hat{S}^t} & -\tr \hat{S} \\ 
&  \mbox{~subject to~}  &  (B \otimes A + I \otimes \hat{S}) \succeq 0. 
\end{array}
\]


\end{slide}
\begin{slide}{}

 {A simple Example}

Consider the following $2\times 2$ example
$$
A:= \left( 
\begin{array}{cc}
1 & 0 \\
0 & 2 
\end{array} 
\right) ~~~~~~~~
B:= \left( 
\begin{array}{cc}
3 & 0 \\
0 & 4 
\end{array} 
\right).
$$
$\mu^* = 10$
$$
B \otimes A = \left( 
\begin{array}{cccc}
3 & 0 & 0 & 0 \\
0 & 6 & 0 & 0 \\
0 & 0 & 4 & 0 \\
0 & 0 & 0 & 8 \\
\end{array} 
\right).
$$
But $s_{11}\geq -3$ and $s_{22}\geq -6$;
to maximize $(D)$, equality must hold, and therefore $-\tr \hat{S} = 
9$ in the optimum. 

However, add redundant constraint $X^TX=I$.
Get $T \otimes I$ in Hessian and $-\trace T$ in objective function.
$s_{11}\geq -3-t_{11}$ 
$s_{11}\geq -4-t_{22}$ 
$s_{22}\geq -6-t_{11}$
$s_{22}\geq -8-t_{22}$
So $t_{22}=-1.$ Duality gap is closed.



\end{slide}
\begin{slide}{}


Summary: constraints $XX\tran=I$ and
$X\tran X=I$ are equivalent. Add redundant constraints.
\begin{eqnarray*}
{\rm QQP_{OO}}\qquad  \mu^O:=&\min& \tr AXBX\tran\\
&{\rm s.t.}& XX\tran=I,\ X\tran X=I.
\end{eqnarray*}
dual problem is
\begin{eqnarray*}
{\rm DQQP_{OO}}\\
\mu^O \geq \mu^D:=&\max& \tr S+\tr T\\
&\mbox{s.t.}&
(I\Kprod S)+(T\Kprod I)\preceq (B\Kprod A)\\
&& S=S\tran,\ T=T\tran.
\end{eqnarray*}

{\bf Theorem (Anstreicher-Wolkowicz/98)}
Strong duality holds for $\rm QQP_{OO}$ and $\rm DQQP_{OO},$ 
i.e.  $\mu^D=\mu^O$ and both primal and dual are attained.
\QED

Theme again holds.

\end{slide}
\begin{slide}{}
Other applications:

Weighted Sums of Eigenvalues;

Graph Partitioning Problem;

TRS like constraints $\{X: XX\tran \preceq I\}$ (ref
Anstreicher-Wolkowicz-Xin-Yuan/99)
(extension of Hoffman-Wielandt inequality)




\end{slide}
\begin{slide}{}

Concluding Remarks:

In each case of a tractable bound for a nonconvex problem, the structure
allows for redundant constraints to be added to close the Lagrangian
duality gap.

What is the correct question about ``best''? Can we close or reduce the
duality gap in general? 
\end{slide}
\begin{slide}{}
\end{slide}
\begin{slide}{}
\end{slide}

\end{document}

