%\documentclass{slides}
\documentclass[landscape]{seminar}
%\documentclass[portrait]{seminar}
\usepackage{amssymb}
\usepackage{psfig}
%\pagestyle{empty}
\pagestyle{plain}
\newcommand{\F}{{\cal F}}
\newcommand{\A}{{\cal A}}
\newcommand{\p}{{\cal P}}
\newcommand{\Ocal}{{\mathcal O}}
\newcommand{\Kprod}{\otimes}
\newcommand{\Diag}{\rm Diag\,}
\newcommand{\tran}{^T}
\newcommand{\diag}{\rm diag\,}
\newcommand{\tr}{\rm trace\,}
\newcommand{\trace}{\rm trace\,}
\newcommand{\beq}{\begin{equation}}
\newcommand{\Sn}{{\cal S}^n}
\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{\eeq}{\end{equation}}
\newcommand{\nc}{\newcommand}
\nc{\Hcal}{{\cal H}}
\newcommand{\rank}{{\rm rank\,}}
\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 ~~}
\newcommand{\QED}{\hfill ~\rule[-1pt] {8pt}{8pt}\par\medskip ~~}

\begin{document}
%=======================
%=======================
\begin{slide}{}
\begin{center}
{\bf
Semidefinite Relaxations for Hard Combinatorial Problems
}
\end{center}

\vspace{5mm}

Henry Wolkowicz \\

\vspace{5mm}

Department of Combinatorics \& Optimization \\
University of Waterloo

\vspace{10mm}

\mbox{
\begin{figure}
\psfig{file=UWlogori.ps,height=20mm}
\end{figure}
}


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

{\bf 
\begin{center}
OUTLINE
\end{center}
}

$\bullet$ Introduction (short) to SDP \\
(geometry, duality, algorithms)

$\bullet$ Max-Cut Problem instance\\
 (quadratic boolean programming)\\
tractable relaxations versus Lagrangian duality \\
equivalence of various bounds

$\bullet$ Other instances, e.g. QAP, GP, ...\\
SDPs equivalent to min-max eigenvalue problems

$\bullet$ 
\underline{Theme:} - Tractable relaxation implies Lagrangian relaxation which 
can be solved efficiently using SDP. \\
       - Advantages of Lagrangian approach
(recipe for SDP relaxation).

\end{slide}
\begin{slide}{}
\begin{center}
INTRODUCTION
\end{center}
Semidefinite programming --  SDP\\
extension of linear programming  -- LP
\[ 
(P)\quad  \begin{array}{rc}
   \mu^*:=  \min        &  C \bullet X  \\
     \mbox{s.t.} & \A X = b \\
                 & X \succeq 0,
    \end{array}
\]
$C,X \in \Sn$, space of symmetric $n \times n$ matrices\\
inner product $C \bullet X = \tr CX$\\
$A\succeq B$ if $A-B \succeq 0$ positive semidefinite\\
$ \A  :\Sn \rightarrow \Re^m $,
linear operator: $(\A X)_i =\tr (A_iX)$
$A_i \in \Sn,~i=1, \ldots m.$


\end{slide}
\begin{slide}{}
Why use SDP?

Many applications: engineering, combinatorial optimization, statistics,
matrix completions, approximation theory, nonlinear programming, ...

\underline{\hspace{90mm}}\\

Many computationally  hard problems
can be modelled as quadratic programs.

These quadratic programs are themselves hard to solve numerically. 

But,
the Lagrangian relaxation can be solved {\em efficiently using SDP}.

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

\begin{center}
{\bf Properties of  SDP}
\end{center}

SDP is a special case of the cone programming problem
\[ 
 \begin{array}{cc}
     \min        &  f(x)  \\
     \mbox{s.t.} & g(x) \succeq_K 0,
    \end{array}
\]
$K$ is a convex cone \\
$g(x) \succeq_K 0$ is cone partial order, $g(x) \in K.$ 

very general mathematical program 

e.g.  standard equality and
inequality constraints when
 $K= \Re^n_+ \otimes \Sn_+ \otimes \{0\}.$


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


\begin{center}
{\bf GEOMETRY} 
\end{center}
Much of the elegant geometry of polyhedral sets
developed for LP can be extended to SDP.
(e.g.  Bohnenblust 1948, Barker-Carlson 1975 and more recently 
Lewis/98  and Pataki/98)

similarities to LP:\\
{\em self-polar}
\[
\p = \p^+:= \left\{Y: X \bullet Y \geq 0, \forall X \in  \p \right\};
\]
{\em homogeneous}\\
for any $X,Y \in \mbox{int}(\p)$,
there exists an invertible linear operator $\cal A$ that leaves $\p$
invariant and $\A (X)=Y.$



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

{\em faces}
\[ {\cal F} = \left\{Y: {\cal N}(Y) \supset {\cal N}(X) 
                \right\}, \quad X \in \mbox{ relint } {\cal F}
\]

faces are {\em exposed}\\
${\cal F} =  \p \cap \phi^{\perp}$, where $\phi \in
 \p \cap {\cal F}^{\perp}$ {\em conjugate face},
(Here $\cdot^{\perp}$ denote orthogonal complement.)

But difficulties in duality theory can arise due to:

 $\p + {\cal F}^{\perp}$ is always closed

 $\p + \mbox{span}({\cal F})$ is never closed.


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


\begin{center}
{\bf Duality Theory, Optimality Conditions} 
\end{center}
Extensions from LP to SDP, e.g.
Bellman and Fan 1963, but
strong duality theorems require
a Slater-type constraint qualification (strict feasibility). 

(Modified optimality conditions without CQ exit Borwein-Wolkowicz/81 and
Ramana/98.)


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

primal program
\[ 
(P)\quad  \begin{array}{rc}
   \mu^*:=  \min        &  C \bullet X  \\
     \mbox{s.t.} & \A X = b \\
                 & X \succeq 0,
    \end{array}
\]

dual program
\[ 
(D)\qquad \begin{array}{rc}
   \nu^*:=  \max &    b^T y \\
     \mbox{s.t.} & \A^*y \preceq  C 
    \end{array}
\]


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

weak duality (using hidden constraints)
\begin{eqnarray*}
 \mu^* &=& \min\limits_{X\succeq 0} \max_y C \bullet X + y^T(b-\A X)\\
       &\geq& \max_y \min\limits_{X\succeq 0}  y^Tb +\left(C -
                                  \A^*y\right) \bullet X\\
       &=& \nu^*,
\end{eqnarray*}
$\A^*$ adjoint operator of $\A$
\[  \A (X) \bullet y =
  X\bullet \A^* (y),  \quad  \forall  X, \forall y
\]


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


The duality theory gives rise to the
characterization of optimality
\begin{equation}
\label{eq:optcond}
\begin{array}{cccc}
           \A^{*}y +Z - C  &=&  0 & \mbox{dual feasibility} \\
          b - \A(X) &=&  0 & \mbox{primal feasibility} \\
          ZX &=&  0 & \mbox{complementary slackness} \\
       Z,X \succeq 0.
\end{array}
\end{equation}
$X,(y,Z)$ a primal-dual optimal pair. $Z$ is the (dual) slack
variable.

\underline{\hspace{90mm}}\\

  \[        ZX =  \mu I, \quad \mu >0   \]
 perturbed compl. slack. used for interior-point methods

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

First and second order optimality conditions e.g. Shapiro/94,99

Nondegeneracy and strict complementarity
(Theorem of Goldman and Tucker)
do not directly
follow through from LP to SDP though generic, 
e.g. Shapiro/99, Pataki-Tuncel/98,
Alizadeh-Haeberly-Overton/98.

(strict complementarity 
for SDP translates to $Z+X \succ 0$)

Complexity/algorithms:
SDP are convex programs and fall into the class of problems that can be
approximately solved in polynomial time by int-pt algorithms, 
Nesterov-Nemirovski/93.


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

\begin{center}
{\bf Tractable Relaxations of Max-Cut}\\
(quadratic boolean programming)
\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$\\
\underline{\hspace{90mm}}\\

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}
\]
where $e$ vector of ones.

\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}
\]
(adding tractable constraint -- equivalence to other bounds)


\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)
\]
\[
   \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, equivalence to bounds $B_0^c$
and other homogenized bounds.


\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 restriction $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)\\
%  \max_{||y||^2=n+1} q^c_u(y) = 
(n+1) \lambda_{\max} (Q^c + \Diag (u) ) - u^Te\\
&&~\\
\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 theme:
\begin{center}
\fbox{
{\bf Theorem }(PRW) $B_L$ equals all above bounds.
}
\end{center}
(proofs from -- strong Lagrangian duality of TRS.)\\
(question: which relaxation is best numerically, e.g. SDP in dense case,
eigenvalue in large sparse case)


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

\begin{center}
{\bf Strengthened SDP Bounds for MC}\\
\end{center}
(Anjos-Wolkowicz/99)\\
Illustration of recipe for SDP relaxation.\\
(some parts similar to S-procedure Yakubovich/71, Shor relaxation/87)\\
$\bullet$ replace $Ax=b$ by $||Ax-b||^2=0$ and homogenize\\
$\bullet$ add redundant quadratic constraints\\
$\bullet$ take Lagrangian dual\\
$\bullet$ take dual of Lagrangian dual (use hidden SDP constraint)\\
$\bullet$ eliminate redundant constraints\\


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


motivation for $||Ax-b||^2=0$:\\

$0=\max \{ x^2 : x=0\}$ primal optimal value \\
$0<\infty= \inf\limits_{\lambda} \max\limits_x x^2 + \lambda x$
Lagrangian dual optimal value

BUT:\\
replace linear constraint by $x^2 = 0$\\
Then: Lagrangian dual is
\[
0= \inf_\lambda \max_x x^2 + \lambda x^2
\]


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


the trick 
\[
\mbox{replace } Ax=b \mbox{ by } ||Ax-b||^2 = 0
\]
works in general for most applications\\

{\bf Theorem} (PRW)
Let $K \subset \Re^n$ be a {\bf finite set}.
Let $q(x) = x^TQx -2 c^Tx$, $A \in \Re^{m \times n}$ and $b \in \Re^n$.
Then there exists $\bar{\lambda} \in \Re$ such that
$\forall\ \lambda \geq \bar{\lambda}$
\[
\max_{x \in K} \{ q(x) :  ||Ax-b||^2 = 0 \} = 
\max_{x \in K} \{q(x) - \lambda ||Ax-b||^2\}.
\]
\QED
i.e. quadratic penalty function is exact in the case that $K$ is a finite set
(no need for e.g. augmented Lagrangian)

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


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

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

MCQ is equivalent to:
\begin{eqnarray*}
\mu^*:=&\max& \tr QX\\
&\mbox{s.t.}&\diag(X)=e\\
&&X \succeq 0\\
&& X \mbox{ is rank 1}.
\end{eqnarray*}
which is equivalent to
\begin{eqnarray*}
\mu^*:=&\max& \tr QX\\
&\mbox{s.t.}&\diag(X)=e\\
&&X^2-nX=0
\end{eqnarray*}
Since $X$ and $X^2$ can be mutually diagonalized.\\


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


Now add redundant constraints;\\
and replace $\diag(X)=e$ with $||\diag(X)-e||^2_F=0$
\begin{eqnarray*}
\mu^*:=&\max& \tr QX\\
&\mbox{s.t.}&||\diag(X)-e||^2_F=0\\
&&X^2-nX=0\\
&&X \circ X=E
\end{eqnarray*}
where $E$ is the matrix of ones.



\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)} \quad$ 
vector formed (columnwise) from $S$\\
   \hspace{20mm}(ignoring strictly lower triang.)\\
$\bullet$ $S=\sMat(s) \quad$ inverse of $\svec$\\
$\bullet$ $\hMat (v) \quad$ 
adjoint of $\svec$,
off-diagonal terms {\em divided} by 2\\
$\bullet$ $\dsvec (S) \quad$
adjoint of $\sMat$, off diagonal elements {\em multiplied} by 2\\
$\bullet$ $\sdiag(s):= \diag( \sMat(s))$\\
$\bullet$ $\vsMat(s):=\kvec(\sMat(s))$
\[ \bullet \quad 
  \vsMat^*(s)=\dsvec \left( \left(\kmat(v)+\kmat(v)^T\right)/2 \right).
\]


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

Summary:
\[
 \begin{array}{rcl}
 \diag^* &=& \Diag    \\
 \svec^* &=& \hMat    \\
 \svec^{-1} &=& \sMat    \\
 \dsvec^* &=& \sMat    \\
 \vsMat^* &=& \dsvec \left[ \frac 12 \left(\kmat(\cdot)+
                                 \kmat(\cdot)^T\right) \right].
 \end{array}
\]


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



homogenize $1-y_0^2=0.$\\
use: $X=\sMat(x)$ is  a symmetric matrix.
\[
\begin{array}{ccc}
    &\max &  \tr \left(Q\, \sMat(x)\right)y_0 \\
  &\mbox{s.t.}& \sdiag(x)^T \sdiag(x) - 2 e^T \sdiag(x)y_0 
                  + n=0\\
     &&\sMat(x) \circ \sMat(x)=E\\
     &&\sMat(x)^2-n\, \sMat(x)y_0=0\\
     &&1-y_0^2=0.
\end{array}
\]



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

take the Lagrangian dual;
Lagrange multipliers $t,w,T,S$
\[
 \begin{array}{rl}
     \mu^*\leq & \\
      \nu_2^*= &
    \min\limits_{t,w,T,S}
\max\limits_{x,y_0}   \tr \left(Q\sMat(x)\right)y_0 \\
 &~+w( \sdiag(x)^T \sdiag(x) - 2 e^T 
                  \sdiag(x)y_0 + n)\\
 &~~+\tr T(\sMat(x) \circ \sMat(x)-E)\\
 &~~+\tr S((\sMat(x))^2-n\, \sMat(x)y_0)\\
 &~~~+ t(1-y_0^2).
\end{array}
\]

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



constant part (no Lagrange multipliers) of Lagrangian Hessian:
\[
 2H_c:=2\pmatrix{
  0 & \frac 12 \dsvec(Q)^T\cr
 \frac 12 \dsvec(Q)  & 0\cr
}.
\]

~~\\
{\em negative} nonconstant part of Lagrangian Hessian
\[
   \begin{array}{lll}
 2\Hcal:= 2\Hcal_1(w) + 2\Hcal_2(T)+ 2\Hcal_3(S) + 2\Hcal_4(t) \\
  ~~:=2w\pmatrix{
  0 &  (\dsvec \Diag e )^T\cr
  (\dsvec \Diag e ) & -\sdiag^* \sdiag }\\
  ~~~~~+2\pmatrix{
  0 &  0 \cr
   0 & \dsvec \left( T \circ \sMat\right) }\\
  ~~~~~~~~+2\pmatrix{
  0 & \frac 1n\dsvec(S)^T\cr
   \frac 1n\dsvec(S)
        & -\dsvec S  \sMat }\\
  ~~~~~~~~~~~+2t\pmatrix{
  1 & 0\cr
   0 & 0 }.\\
\end{array}
\]



\end{slide}
\begin{slide}{}
Use {\bf hidden SDP constraint}\\

Lagrangian dual:

\[
{\rm MCDSDP2} \quad
  \begin{array}{ccc}
     \nu^*_2 =
    &\min & nw +\tr ET+\tr 0S  +t\\
  &\mbox{s.t.}& \Hcal(w,T,S,t) \succeq H_c\\
\end{array}
\]

Take $T$ sufficiently positive definite and $t$ sufficiently
large, then we can guarantee Slater's constraint qualification.


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

take dual  of this SDP  -- strengthened SDP relaxation of MC:
\[
 {\rm MCPSDP2} \begin{array}{ccc}
     \nu_2^* =
    &\max & \trace H_cY\\
  &\mbox{s.t.}& \Hcal_1^*(Y) = n\\
  &                 & \Hcal_2^*(Y) = E\\
  &                 & \Hcal_3^*(Y) = 0\\
  &                 & \Hcal_4^*(Y) = 1\\
     && Y \succeq 0.
\end{array}
\]
\end{slide}
\begin{slide}{}


we need to calculate the adjoint operators and remove redundant
constraints in MCPSDP2.

we use

\[  Y \cong \left( \begin{array}{c}y_0 \\ x \end{array}\right) 
                     \left( y_0 ~x^T\right), \quad
X = \sMat(x)
\]


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

simplified SDP relaxation MCPSDP2
\[
 \begin{array}{clc}
     \nu_2^* =\\
    \max & \trace H_c Y\\
  \mbox{s.t.}& \diag(Y) = e\\
      & Y_{0,t(i)}=1, i=1, \ldots , n\\
     & Y_{0,T(i,j)} = \frac{1}{n} \sum\limits_{k=1}^n Y_{T(i,k),T(k,j)},
                        \,\,\,\forall\, i,j \:{\rm s.t.}\: 1\leq i<j\leq n\\
      & Y \succeq 0, Y \in {\cal S}^{t(n)+1},
\end{array}
\]
where
\[
T(i,j) := \left\{
\begin{array}{l}
t(j-1)+i, \,\mbox{if}\,\, i \leq j \\ t(i-1)+j,\,\,\mbox{otherwise}.
\end{array} \right.
\]
This problem has $2t(n)-1$ constraints; but very sparse.



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

if dual program is
\[ 
(D)\qquad \begin{array}{rc}
   \nu^*:=  \min &    b^T y \\
     \mbox{s.t.} & \A^*y \succeq  C 
    \end{array}
\]

Helmberg-Rendl/2000: if $\trace X = \mbox{const}$ 
(is constant) for all primal feasible $X$, 
\[
\A X = b \quad  \mbox{ {\bf implies} } \quad  \trace X = \mbox{const}  
                          \qquad (*)
\]
then
\[
\nu^* = \min b^T y + \mbox{const} \lambda_{\max} (C-\A^*y)
\]
Moreover, (*) holds iff $I=\A^*w$, for some $w$.
But, this holds if original QQP is bounded;
 add redundant constraint $||x||^2\leq K$.\\
So -- apply min-max eigenvalue approach in large sparse case.



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

surprise result

{\bf LEMMA}\\
Suppose that $Y$ is feasible in MCPSDP2. Then the first row
\[  \sMat \left( Y_{0,1:t(n)} \right) \succeq 0.  \]
\underline{\hspace{90mm}}\\
Proof:
Let $x=Y_{0,2:t(n)}$.
$X^2=nX$ constraint:
\[ n \sMat (x) = \sMat (x) \sMat (x) 
      =\sMat (x) x^T \sMat^*. 
\]
identify $xx^T$ with lower
right block of $Y$; get congruence of a positive
semidefinite matrix.
Alternatively: using ${\cal H}_3^*,$  and
$\dsvec (\cdot) \sMat$ is self-adjoint operator
\[ n\dsvec^* (x)
= \dsvec \bar{Y} \sMat 
= \left( \dsvec \bar{Y} \sMat \right)^*,
\]
where $\bar{Y}$ is the bottom
right block of $Y.$ Again congruence.
\QED

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

{\bf Theorem}
The optimal values satisfy
\[
 \nu_2^* \leq  \nu^* \quad \mbox{and} \quad
\nu_2^* = \nu^* \Rightarrow \nu_2^* =  \mu^*.
\]
(Unless MC optimum if sound, the new bound is strictly better.)

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

\oddsidemargin -.35in
\evensidemargin -.35in
{\tiny
%\begin{table}[b]
%\begin{center}
\begin{tabular}{||c|c|c|c|c|c|c|c|c||}\hline
 $n$ & Wt & MCSDP& MCPSDP2&
 Num. \\
     & opt.& (\% rel. err) &
 (\% rel. err) & rank \\
\hline \hline
5 & 4 & 4.5225 (13.06\%) & 4.2890 (7.22\%) & 2 \\
\hline
7 & 56 & 56.4055 (0.72\%) & 56.0954 (0.17\%) & 3 \\
\hline
8 & 30 & 30.2015 (0.67\%) & 30. (e-10\%) & 1 \\
\hline
9 & 58 & 58.9361 (1.61\%) & 58.1182 (0.20\%) & 3 \\
\hline
 10&     64&  64.08 (0.1268\%) &   64 (e-08\%) &  3 \\
\hline
12 & 88 & 90.3919 (2.72\%) & 89.5733 (1.79\%) & 4 \\
\hline
\end{tabular}
%\end{center}
%\end{table}


The first line of results corresponds to
solving both MC relaxations for a 5-cycle with unit edge-weights;
the others come from randomly generated weighted graphs.

}

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

From
\[Y_{0,T(i,j)} = \frac{1}{n} \sum\limits_{k=1}^n Y_{T(i,k),T(k,j)},
  \,\,\,\forall\,  1\leq i<j\leq n,
\]
average = 1 implies each = 1

\[
(\mbox{MCPSDP3}) \quad \begin{array}{clc}
     \nu_3^* =\\
    \max & \trace H_c Z\\
  \mbox{s.t.}& \diag(Z) = e\\
      & Z_{0,t(i)}=1, i=1, \ldots , n\\
      & Z_{0,T(i,j)} = Z_{T(i,k),T(k,j)},
        \,\,\,\forall\, k, \forall\,1\leq i < j \leq n\\
      & Z \succeq 0, Z \in {\cal S}^{t(n)+1}.
\end{array}
\]
SDP3 has $(n-1) \cdot t(n-1) + 2n + 1$ equality constraints.

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

\oddsidemargin -.45in
\evensidemargin -.45in
{\tiny
\begin{center}
\begin{tabular}{|c|c|c|c|c|c|c|}\hline
 $n$ & MC & SDP1 & SDP2 & SDP1 plus  & SDP3 & Graph \\
     & opt & bound & bound &  all triangle & bound & \\
     & value & & & inequalities & & \\
\hline \hline
5 & 4 & 4.5225 & 4.2889 & 4.0000 & 4.0000 & 5-cycle \\
  &   & $\rho$ = 0.8845 & $\rho$ = 0.9326 & $\rho$ = 1.0000 & $\rho$ = 1.0000
  & with unit \\
  &   & R.E.: 13.06\% & R.E.: 7.22\% & R.E.: 0\% & R.E.: 0\% 
  & edge weights \\
\hline
5 & 6 & 6.2500 & 6.1160 & 6.0000 & 6.0000 & $K_5 \backslash e$ \\
  &   & $\rho$ = 0.9600 & $\rho$ = 0.9810 & $\rho$ = 1.0000 & $\rho$ = 1.0000
  & with unit \\
  &   & R.E.: 4.17\% & R.E.: 1.93\% & R.E.: 0\% & R.E.: 0\% & edge weights \\
\hline
5 & 6 & 6.2500 & 6.2500 & 6.2500 & 6.2500 & $K_5$ \\
  &   & $\rho$ = 0.9600 & $\rho$ = 0.9600 & $\rho$ = 0.9600 & $\rho$ = 0.9600
  & with unit \\
  &   & R.E.: 4.17\% & R.E.: 4.17\% & R.E.: 4.17\% & R.E.: 4.17\% 
  & edge weights \\
\hline
5 & 9.28 & 9.6040 & 9.4056 & 9.2961 & 9.2800 & Given by \\
& & $\rho$ = 0.9663 & $\rho$ = 0.9866 & $\rho$ = 0.9983 & $\rho$ = 1.0000
  & $A(G)$ \\
  &   & R.E.: 3.49\% & R.E.: 1.35\% & R.E.: 0.17\% & R.E.: 0\% 
  & below \\
\hline
10 & 12 & 12.5  & 12.3781 & 12.0000 & 12.0000 & Petersen \\
  &   & $\rho$ = 0.9600 & $\rho$ = 0.9695 & $\rho$ = 1.0000 & $\rho$ = 1.0000
  & with unit \\
  &   & R.E.: 4.17\% & R.E.: 3.15\% & R.E.: 0\% & R.E.: 0\%
  & edge weights \\
\hline
12 & 88 & 90.3919 & 89.5733 & 88.0029 & 88.0000 & Randomly \\
  &   & $\rho$ = 0.9735 & $\rho$ = 0.9824 & $\rho$ = 1.0000 & $\rho$ = 1.0000
  & generated \\
  &   & R.E.: 2.72\% & R.E.: 1.79\% & R.E.: $3.3e-5$ 
  & R.E.: $9.9e-7$ & \\
\hline
\end{tabular}
\end{center}
}


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


Other illustration of Lagrangian duality strength:

{\bf 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.$)
\[ 
\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:
{\em tractable implies  strong duality}


\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  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}{}

 {\bf A simple $2\times 2$ Example}
$\mu^* = 10$
\[
A:= \left( 
\begin{array}{cc}
1 & 0 \\
0 & 2 
\end{array} 
\right) \quad
B:= \left( 
\begin{array}{cc}
3 & 0 \\
0 & 4 
\end{array} 
\right) \quad
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}{}


Add redundant constraints $X^TX=I$.
\begin{eqnarray*}
{\rm QQP_{OO}}\qquad  \mu^O:=&\min& \tr AXBX\tran\\
&{\rm s.t.}& XX\tran=I,\ X\tran X=I.
\end{eqnarray*}
\begin{eqnarray*}
{\rm DQQP_{OO}} \qquad
\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}{}

add linear constraint to QAP ????
Use equivalence to min-max eig problem after homogenization to get zero
duality gap?

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

{\bf Linear Case} $A=B=0.$
\begin{equation}
\begin{array}{rcl}
{\rm QQPL_{\Ocal}}\qquad  \mu_L^\Ocal:=&\min& \tr -2CX^T\\
&{\rm s.t.}& XX^T=I.
\end{array}
\label{QAPL}
\end{equation}
Characterize the optimal solution using singular values:\\
{\bf Proposition}
Suppose we have the singular value decomposition
$C=U\Sigma V^T,$
where the singular values, $\sigma_i,$ 
are in the diagonal matrix $\Sigma,$
and $U,V$ are orthogonal matrices.
Then the optimal value of ${\rm QQPL_{\Ocal}}$
is $\mu_L^\Ocal=-2\tr \Sigma =-2\sum\limits_{i=1}^n \sigma_i.$
The optimal solution is obtained using the orthogonal matrices that
yield the decomposition, i.e. $X^*=UV^T.$
\QED



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

dual of pure linear case:
(can assume $S,T$ are diagonal)
\begin{eqnarray*}
{\rm LD}\qquad&\max&  e^Ts+e^Tt+w\\
&\mbox{s.t.}&s_j+t_i\leq   
        - \frac 1{|w|} |c_{(j-1)n+i}|^2,
                        \quad i,j=1,\ldots, n.
\end{eqnarray*}
notice independence of the sign of the
individual elements of $C.$

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


But:\\
{\bf Example}
\beq
\label{eq:exampC}
\begin{array}{ccc}
\mu^*:=
&\min & \tr -2CX^T\\
 &  \mbox{~s.t.~} &XX^T = I,~X^TX = I,
    \end{array}
\end{equation}
with  $2\times 2$ matrix
$$
C= \left( 
\begin{array}{rr}
1 & -1 \\
1 & 1 
\end{array} 
\right).
$$
We then solve this example with the sign changed on -1, i.e. 
$$
C= \left( 
\begin{array}{rr}
1 & 1 \\
1 & 1 
\end{array} 
\right).
$$



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


The dual problem in the second case is
\[
(D_{\mathcal O})~~
\begin{array}{cl}
\max &    \tr S + \tr T +w\\
\mbox{s.t.}&  \BoDiag(S) + \OoDiag(T) + wE_{00} \preceq L_Q,
    \end{array}
\]
where 
\beq \label{eq:lq0}
L_Q := \left[ \begin{array}{cc}
0 & \begin{array}{rrrr} -1&-1&-1&-1 \end{array} \\
\begin{array}{r} -1\\-1\\-1\\-1 \end{array} 
                                                & \mbox{\huge{0}}
\end{array} \right].
\end{equation}
Dual optimal value does not change. 
But primal does, since the sum of the singular
values of the two matrices are: $2\sqrt 2$ in the first instance
and just $2$ for the symmetric $C,$ i.e. the optimal values are
$-4(\sqrt 2)$ and $-4,$ respectively.
(Implies duality gap in second case.)


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


Add redundant variables:\\

{\bf Theorem}
Strong duality holds between the pure linear case 
and its Lagrangian dual if the following equivalent problem for the sum
of the singular values is used.
\[
{\rm SVD}\qquad
\begin{array}{rcl}
  \sum_i \sigma_i (C) =\max& 2\tr YCX^T  \\
{\rm s.t.}& 
XX^T+YY^T=I.
\end{array}
\]


\end{slide}


\end{document}
