\documentclass{slides}
\usepackage{latexsym}
\input epsf
\usepackage{psfig}
\newtheorem{exam}{Example}
\newtheorem{prop}{Proposition}
\newtheorem{lem}{Lemma}
\newtheorem{thm}{Theorem}
\newtheorem{cor}{Corollary}
\newtheorem{alg}{Algorithm}
\newcommand{\req}[1]{(\ref{#1})}
\newcommand{\svec}{{\rm svec\,}}
\newcommand{\sMat}{{\rm sMat\,}}
\newcommand{\sn}{{\cal S}^n }
\newcommand{\Sn}{{\cal S}^n }
\newcommand{\hn}{{\cal H}^n }
\newcommand{\p}{{\cal P} }
\newcommand{\g}{{\cal G} }
\newcommand{\kvec}{{\rm vec\,}}
\newcommand{\adj}{{\rm adj\,}}
\newcommand{\trace}{{\rm trace\,}}
\newcommand{\tr}{{\rm trace\,}}
\newcommand{\diag}{{\rm diag\,}}
\newcommand{\Diag}{{\rm Diag\,}}
\newcommand{\Se}{{\mathcal S}_e }
\newcommand{\Sd}{{\mathcal S}_d }
\newcommand{\Sc}{{\mathcal S}_C }
\newcommand{\Sh}{{\mathcal S}_H }
\newcommand{\snn}{{\mathcal S}_{n-1} }
\newcommand{\GG}{{\mathcal G} }
\newcommand{\KK}{{\mathcal K} }
\newcommand{\DD}{{\mathcal D} }
\newcommand{\BB}{{\mathcal B} }
\newcommand{\PP}{{\mathcal P} }
\newcommand{\TT}{{\mathcal T} }
\newcommand{\FF}{{\mathcal F} }
\newcommand{\EE}{{\mathcal E} }
\newcommand\T{{\mathcal T}}
\newcommand{\bt}{ \begin{tabular} }
\newcommand{\et}{ \end{tabular} }
\newcommand\A{{\mathcal A}}
\newcommand\E{{\mathcal E}}
\newcommand{\bpr}{{\bf Proof.} \hspace{1 em}}
\newcommand{\beq}{\begin{equation}}
\newcommand{\eeq}{\end{equation}}
%\newcommand{\epr}{\\ \hspace*{4.5in}  $\Box$}
\newcommand{\QED}{\hfill ~\rule[-1pt] {8pt}{8pt}\par\medskip ~~}
\newcommand{\epr}{\QED}
\begin{document}
%\bibliographystyle{plain}
\begin{slide}{}
\begin{center}
\large{
{\bf Semidefinite Programming\\
 and\\
 Matrix Completions}
}
~~\\
~~\\
~~\\
~~\\
Tutte Colloquium\\
Department of\\
 Combinatorics and Optimization\\
University of Waterloo\\
Friday, June 16, 2000
~~\\
\small{
\begin{flushleft}
        Henry Wolkowicz\\
~~\\
          Dept. of Combinatorics and Optimization\\
          University of Waterloo\\
~~\\
          Waterloo, Ontario N2L 3G1, Canada\\
hwolkowi@orion.math.uwaterloo.ca\\
http://orion.math.uwaterloo.ca/\~{ }hwolkowi
\end{flushleft}
}
\end{center}


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


\begin{center}OUTLINE
\end{center}

\begin{enumerate}
\item
Short intro. to SDP
\item
SDP and positive definite matrix completions
\item
Euclidean distance matrix completions
\item
New characterization for EDM;\\
solving large sparse problems
\end{enumerate}




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



\begin{center}SDP  BACKGROUND and NOTATION
\end{center}

~~\\
~~\\

\begin{center}
Semidefinite Programming\\
 looks just like\\
Linear Programming
\end{center}
\[ {\bf (PSDP)}
\begin{array}{cccc}
    p^*=  & \max &\tr CX & (\left< C,X \right>) \\
 &  \mbox{s.t.} & {\cal A}X = b & \mbox{(linear)}\\
  && X \succeq 0,~~(X \in \p)& \mbox{(nonneg)}
    \end{array}
\]


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

$\preceq$ denotes the L{\"{o}}wner partial order\\
$A\preceq B$ if $B-A \succeq 0$\\

${\cal S}^n$ denotes  $n \times n$ symmetric matrices

\[ {\cal A} :{\cal S}^n \rightarrow \Re^m
\]
\[({\cal A}X)_i =\tr (A_iX),~
  \mbox{for given}~ A_i \in {\cal S}^n 
\]

$\p$ - 
cone of positive semidefinite matrices
\begin{center}
replaces
\end{center}
$\Re^n_+$ - nonnegative orthant

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

\begin{description}
\item
SDP is arguably hottest area in Opt. during last 10 years.\\
\item
ISMP00 in Atlanta - at least 13 minisymposia on SDP.
Many conferences, papers, books, theses have been published recently, 
see e.g.

\begin{center}
{\bf Handbook of Semidefinite Programming: Theory, Algorithms, and
Applications}\\
 Kluwer Academic Publs. 2000.
\end{center}

\end{description}

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

Reasons for high interest:\\
      \begin{description}
      \item
      many interesting \underline{{\bf applications}} in many diverse areas
      \item
      SDPs are convex problems that can be\\
       \underline{{\bf solved
      very efficiently}}, both  in theory (with a polynomial worst-case
      complexity) and in practice\\
       (Nesterov and Nemirovski 1988,
       $\log \det A$  is a self-concordant barrier for the 
      positive semidefinite cone, apply p-d i-p methods)
      \end{description}



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



\begin{center}
{\bf APPLICATIONS}
\end{center}
\begin{description}
\item  [Engineering  (LMIs):]
 Lyapunov stability of ODEs, 1890's;
Yakubovitch 1960's; Boyd et al 1980's, Ricatti equations, ...
\item [matrix completion problems] 1980s, more below.
\item [combinatorial optimization] 1980s;
Lov\'{a}sz {\em theta function}  ({\em 
Lov\'{a}sz number of a graph});
strong approximation results for the max-cut
problem by Goemans-Williamson; boolean quadratic approximations
\end{description}




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

\begin{center}
{\bf OTHER APPLICATIONS}
\end{center}
\begin{description}
\item
e.g.
Complementarity Problems;
min-max eigenvalue problems;
Financial Applications;
Nonlinear Programming;
Statistics.

\end{description}

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


\begin{center}
{\bf MORE SIMILARITIES WITH LP}\\
~\\
~\\
~\\
~\\
~\\
DUALITY
\end{center}
payoff function, player $Y$ to player $X$ (Lagrangian)
\[ L(X,y) :=  \tr (CX) +y^t(b-{\cal A}X)
\]

Optimal (worst case) strategy for player $X$:
\[p^* = 
      \max_{X \succeq 0 }  \min_{y }  L(X,y) 
\]
Using the {\em hidden constraint} $b-{\cal A}X=0$, recovers primal problem.

\end{slide}
\begin{slide}{}
\[ 
\begin{array}{rcl}
L(X,y) &=&  \tr (CX) +y^t(b-{\cal A}X)\\
       &=&  b^ty + \tr \left(C -{\cal A}^*y \right) X
\end{array}
\]

~\\
~\\
adjoint operator,~~ ${\cal A}^*y= \sum_i y_i A_i $
\[
\left<{\cal A}^*y,X \right>= \left<y,{\cal A}X \right>, ~~~ \forall X,y
\]


\[p^* = 
       \max_{X \succeq 0 } \min_{y }  L(X,y) 
\leq d^*:=\min_y \max_{X \succeq 0} L(X,y) 
\]

The {\em hidden constraint} $C-{\cal A}^*y \preceq 0$
\end{slide}
\begin{slide}{}

\[p^* = 
       \max_{X \succeq 0 } \min_{y }  L(X,y) 
\leq d^*:=\min_y \max_{X \succeq 0} L(X,y) 
\]
The dual is obtained from the optimal strategy of the competing player,
Y. \\
The {\em hidden constraint} $C-{\cal A}^*y \preceq 0$\\
 yields the dual
\[ {\bf (DSDP)}
\begin{array}{ccc}
    d^*=& \min &b^ty \\
 &  \mbox{s.t.} & {\cal A}^*y \succeq  C \\
    \end{array}
\]

for the primal
\[ {\bf (PSDP)}
\begin{array}{ccc}
    p^*=  & \max &\tr CX \\
 &  \mbox{s.t.} & {\cal A}X = b\\
  && X \succeq 0
    \end{array}
\]
\end{slide}
\begin{slide}{}
Characterization of optimality for the\\
   dual pair $X,y$~~(slack $Z\succeq 0$)
 \[ 
\begin{array}{cc} 
    {\cal A}^*y -Z = C  & \mbox{dual feasibility}\\
~\\
    AX = b & \mbox{primal feasibility}\\
~\\
    ZX  = 0 & \mbox{complementary slackness}
\end{array}
\]
\[
    ZX = \mu I ~~~~~ \mbox{perturbed}
\]

Forms the basis for:\\ ~~\\
primal simplex method\\
dual simplex method\\
interior point methods
\end{slide}
\begin{slide}{}

\begin{center}
{\bf Positive Definite Completions\\
of\\
Partial Hermitian Matrices}
\end{center}
$\GG(V,E)$ finite undirected graph\\
~~\\
$A(\GG)$ is a $\GG$-partial matrix\\
($a_{ij}$ defined iff $\{i,j\} \in E$)\\
~~\\
$A(\GG)$ is a $\GG$-partial positive matrix if
$a_{ij}=\overline{a_{ji}}, \forall \{i,j\} \in E$ and all existing
principal minors are positive.\\
~~\\
with ${\mathcal J}=(V,\bar{E}), E \subset \bar{E}$ a 
$\mathcal J$-partial matrix
$B({\mathcal J})$ extends the $\GG$-partial matrix $A(\GG)$ if
$b_{ij}=a_{ij}, \forall \{i,j\} \in E$\\
~~\\
$\GG$ is positive
completable if every $\GG$-partial positive matrix can be
extended to a positive definite matrix.


\end{slide}
\begin{slide}{}
$\GG$ is {\bf chordal} if there are no minimal cycles of length $\geq
4$. (every cycle of length $\geq 4$ has a chord)

{\bf THEOREM}
(Grone, Johnson, Sa, Wolkowicz)\\
$\GG$ is positive completable iff $\GG$ is chordal.
\epr
~~\\
~~\\
equivalently - strict feasibility for SDP:\\
\[\begin{array}{cl}
\trace E_{ij}P=a_{ij}, & \forall \{i,j\} \in E\\
P \succ 0
\end{array}\]
~~\\
where $E_{ij}=e_ie_j^t+e_je_k^t$

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

\begin{center}
{\bf Approximate Positive Semidefinite Completions}
\end{center}
\begin{flushright}
\small{
(with Charlie Johnson\\
 and Brenda Kroschel)
}
\end{flushright}

given:\\
 $H=H^t \geq 0$ real, nonnegative (elementwise) {\bf symmetric
matrix of weights}\\
 with positive diagonal elements $ H_{ii} > 0,~ \forall i$;
~~\\
~~\\
and $A=A^*$ the\\
 {\bf given partial Hermitian matrix}\\
i.e. some elements approximately fixed;\\ 
others free (for notational purposes, assume
free elements set to 0 if not specified.)
~~\\

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


$||A||_F = \sqrt{ \tr A^*A}$
{\em Frobenius norm},
$\circ$ denotes {\em Hadamard product}.\\
\[ \begin{array}{cc}
  f(P):=||H \circ (A-P) ||_F^2 
\end{array}
\]
~~\\
~~\\
{\bf weighted, best approximate,\\ completion problem}
\[
(AC)~~
\begin{array}{ccc}
       \mu^*:=&\min &f(P) \\
 &  \mbox{~subject to~} & KP=b\\
  &  &  P \succeq 0,
    \end{array}
\]
where $K: \hn \rightarrow {\cal C}^m$ linear operator




\end{slide}
\begin{slide}{}
Lagrangian:
\[
L(P,y,\Lambda) = f(P)  + \left<y,b-KP\right> - \tr \Lambda P
\]
~~\\
Dual problem:
 \[
(DAC)
\begin{array}{ccc}
       \max &f(P) +\left<y,b-KP\right>- \tr \Lambda P \\
   \mbox{~subject to~} &  \nabla f(P)  -K^*y- \Lambda =  0\\
          &       \Lambda \succeq 0.
    \end{array}
\]
~~\\
{\bf THEOREM} \label{thm:optcond}
The matrix $\bar{P}\succeq 0$ and vector-matrix
$\bar{y},\bar{\Lambda} \succeq 0$ solve AC and DAC if and only if
\[
\begin{array}{cc}
 K\bar{P}  = b & \mbox{primal feas.}\\
 2H^{(2)} \circ (\bar{P}-A)-K^*\bar{y}
  -\bar{\Lambda} =  0 & \mbox{dual feas.}\\
\tr \bar{\Lambda} \bar{P} = 0 & \mbox{compl. slack.}\\
\end{array}
\]
\epr


\end{slide}
\begin{slide}{}
Discard linear operator $K$ and replace with appropriate
weights in $H$.

Use {\em square} perturbed optimality conditions.

\[
\begin{array}{cc}
 2H^{(2)} \circ (P-A) -\Lambda =  0 & \mbox{dual
feasibility}\\
-P + \mu \Lambda^{-1}  = 0 & \mbox{perturbed C.S.}\\
\end{array}
\]

Linearization of second equation\\
and solve for $h$ and $l$

\[
h= \mu \Lambda^{-1} - \mu \Lambda^{-1} l \Lambda^{-1}-P
\]
\[
l= \frac 1{\mu}\left\{
     - \Lambda (P+h) \Lambda
 \right\}+\Lambda
\]



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

Dual Step First:\\
(if many elements of $P$ are free)

We can eliminate the primal step $h$ and solve for the dual
step $l$.
\[
\begin{array}{ccl}
l & = &  2 H^{(2)} \circ h + ( 2H^{(2)} \circ (P-A)
-\Lambda)\\
  & = &  2 H^{(2)} \circ  (\mu \Lambda^{-1} - \mu \Lambda^{-1}\\
&& ~~~~~~~~ l \Lambda^{-1}  -P)+ ( 2H^{(2)} \circ (P-A)
-\Lambda).
\end{array}
\]
Equivalently, we get the Newton equation
\[
\begin{array}{ccl}
 2 H^{(2)} \circ (\mu \Lambda^{-1} l \Lambda^{-1}  ) + l =
 2 H^{(2)} \circ (\mu \Lambda^{-1} -A  ) -\Lambda.
\end{array}
\]

This shows that $l,\Lambda$ have the same sparsity pattern as
$H$, i.e. this is a square system;\\
order is number of nonzeros/2 in $H$.


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


{\bf Each test appears on one line and includes 20 test problems.}\\

~~\\
\begin{tiny}
\begin{flushleft}
\begin{tabular}{|c|c|c|c|c|c|c|c|c|}\hline
 dim &  toler  &$H$dens./infty&$A$psd&cond(A)&$H$pd&min/max&iters\\ 
\hline
  15 &   $10^{-5}$& .0751/.02  & yes & 222.5& no & 8/17 & 10.3  \\
  15 &   $10^{-6}$& .1/.95  & yes & 19.6 & no & 10/23 & 15.6 \\
  15 &   $10^{-6}$& .01/.95  & yes & 21. & no & 10/20 & 13.2 \\
  19 &   $10^{-6}$& .005/.1  & yes & 14.8 & no & 10/18 & 12.9 \\
  21 &   $10^{-6}$& .005/.1  & yes & 20.3 & no & 8/24 & 15 \\
  38 &   $10^{-6}$&    1/.99  & yes & 49.6 & yes & 14/24 & 16. \\
  45 &   $10^{-6}$&    1/.99  & yes & 46.8 & yes & 15/22 & 17. \\
  55 &   $10^{-6}$&    1/.99  & yes & 37.2 & yes & 15/30 & 17.5 \\
  85 &   $10^{-5}$& .0219/.02  & yes & 1374.5& no & 16/23 & 18.9  \\
  95 &   $10^{-5}$& .0206/.02  & yes & 2.7 & no & 8/14 & 11.1  \\
  95 &   $10^{-6}$& 1/.999 & yes & 196. & yes & 14/18 & 16.8  \\
 145 &   $10^{-6}$& .01/.997 & yes &  658.5 & yes & 13/17 & 14.9 \\
\hline
\end{tabular}
~~\\
data for primal-step-first (20 problems per test): \\
dimension;  tolerance for duality gap;\\
 density of nonzeros in $H$/ density of infinite values in $H$;\\
positive semidefiniteness of $A$; condition number of $A$; 
positive definiteness of $H$;\\
min and max number of iterations; average number of iterations.

\end{flushleft}
\end{tiny}



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


\begin{flushleft}
\begin{tiny}
\begin{tabular}{|c|c|c|c|c|c|c|c|c|}\hline
 dim& toler&$H$dens./infty&
           $A$psd &cond(A)&$H$pd&min/max&iters\\ \hline
  60   & $10^{-6}$& .01/.001  & yes & 79.7& no & 15/23 & 16.8  \\
 65   & $10^{-6}$& .015/.001  & yes & 49.9& yes & 18/24 & 21.3  \\
 83   & $10^{-6}$& .007/.001  & no & 235.1 & no & 24/29 & 25.5 \\
 85   & $10^{-5}$& .008/.001  & yes & 94.7 & no & 11/17 & 13.1 \\
 85   & $10^{-6}$& .0075/.001  & no & 299.9 & no & 23/27 & 25.2 \\
 87   & $10^{-6}$& .006/.001  & yes & 74.2 & yes & 14/19 & 16.9 \\
 89   & $10^{-6}$& .006/.001  & no & 179.3 & no & 23/28 & 15.2 \\
110   & $10^{-6}$& .007/.001  & yes & 172.3& yes & 15/20 & 17.8  \\
155   & $10^{-6}$& .01/0  & yes &643.9& yes & 14/18 & 15.3  \\
655   & $10^{-6}$& .017/0  & yes &1.4& no & 14/14 & 14.  \\
755   & $10^{-6}$& .002/0  & yes &1.5& no & 15/15 & 15.  \\
\hline
\end{tabular}
~~\\
data for dual-step-first (20 problems per test): 
dimension;  tolerance for duality gap;\\
 density of nonzeros in $H$/ density of infinite values in $H$;\\
positive semidefiniteness of $A$; condition number of $A$; 
positive definiteness of $H$;\\
(only one test for: 655,755)
\end{tiny}
\end{flushleft}

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

\begin{center}
{\bf Euclidean Distance Matrix Completion Problem}
\end{center}

\begin{flushright}
\small{
(with Abdo Alfakih)
}
\end{flushright}

{\bf What are EDMs?}\\
-----\\
A {\bf pre-distance matrix} (or dissimilarity matrix):\\
$\bullet$ an $n \times n$ symmetric
matrix $D=(d_{ij})$ with nonnegative elements and zero
diagonal
~~\\
-----\\
A (squared) {\bf Euclidean distance matrix} (EDM):\\
$\bullet$ a pre-distance matrix such that there
exists points $x^1,x^2,\ldots,x^n$ in $\Re^r$ such that
\[
d_{ij} = {\| x^i- x^j\|}^2, ~~~ i,j=1,2,\ldots,n.
\]
-----\\
The smallest value of $r$ is called {\bf the embedding dimension} of
$D$.
($r$ is always $\leq n-1$)

\end{slide}
\begin{slide}{}
{\bf EDM problem:}\\
 Given a partial symmetric matrix $A$ with certain elements specified,
the Euclidean distance matrix completion problem
(EDMCP) consists in finding the unspecified elements
of $A$ that make $A$ a EDM. 

{\bf WHY?}\\
e.g.: \\
$\bullet$ 
The shape of an enzyme determines it chemical function. Once the
shape is known, then the proper drug can be designed.\\
~~\\
$\bullet$ 
distance geometry on molecules: Atoms are points in space with pairwise
distances; find a set of points which yield those distances.
\end{slide}
\begin{slide}{}
For the approximate EDMCP,
let $A$ be a pre-distance matrix,
$H$ be an $n \times n$ symmetric  matrix with nonnegative elements, and
let $\|A\|_F= \sqrt{
     \trace A^tA}$ denote the {\em Frobenius norm} of $A.$ Consider
the objective function
\[ f(D) := {\| H \circ (A - D) \|}^2_F,   \]
where $\circ$ denotes {\em Hadamard product}.
The {\bf weighted, closest Euclidean distance matrix problem} is
\[
(CDM_0)
 \begin{array}{ccc}
          \mu^* := & \min   &   f(D)  \\
                  & \mbox{ subject to } & D \in {\cal E}, 
  \end{array}
\]
where $\cal E$ denotes the cone of EDMs.
\end{slide}
\begin{slide}{}
{\bf DISTANCE GEOMETRY}

A pre-distance matrix 
$D$ is a EDM if and only if $D$ is negative semidefinite on 
\[ M:=\left\{ x \in \Re^n : x^t e = 0 \right\},
\]
where $e$ is the vector of all ones.

Define $V$ $n \times (n-1),$ full column rank such that $V^te=0.$
Then
\[ \label{eq:Vmp}
J := V V^{\dagger}= I- \frac{e e^t}{n}
\]
is the orthogonal projection onto $M$,
where $V^{\dagger}$ denotes Moore-Penrose generalized inverse.

\end{slide}
\begin{slide}{}
Define the {\bf centered} and {\bf hollow} subspaces
\[ \begin{array}{rcl}
\Sc &:=&  \{ B \in \Sn :  Be = 0 \}, \\ 
\Sh& := & \{ D \in \Sn :  \diag(D) = 0 \}. 
\end{array}
\] 
Define the two linear operators
\[ \begin{array}{rcl} \label{KK} 
\KK(B)& := &  \mbox{diag}(B)\,e^t + e \, \mbox{diag}(B)^t - 2B,
\end{array} \] 
and
\[ \begin{array}{rcl} \label{T} 
\TT(D)& := &  -\frac 12 JDJ.
\end{array} \]
The operator $- 2 \TT$ is an orthogonal projection onto $\Sc.$ 

{\bf THEOREM}
The linear operators satisfy
\begin{eqnarray*}
\KK (  \Sc) = \Sh, \\
\TT (  \Sh) = \Sc, 
\end{eqnarray*} 
and $\KK_{|\Sc}$ and $\TT_{|\Sh}$ are inverses of each other.
\epr
\end{slide}
\begin{slide}{}

A hollow matrix $D$ is EDM \\
if and only if\\
 $B=\TT(D) \succeq 0$ (positive semidefinite)

$D$ is EDM\\
 if and only if\\
 $D=\KK(B),$ for some $B$ with $Be=0$ and $B \succeq 0$.   

In this case the embedding dimension $r$ is given
by the rank of $B$. Moreover if $B=XX^t$, then
the coordinates of the points  $x^1,x^2,\ldots,x^n$ that generate $D$ are
given by the rows of $X$ and, since $Be=0,$
it follows that the origin coincides with the  centroid
of these points.
\end{slide}
\begin{slide}{}

The cone of EDMs, $\cal E$, has empty interior. This can cause problems
for interior-point methods.

\[ V \cdot V : {\cal S}_{n-1}  \rightarrow {\cal S}_{n}  
\]
\[ V \cdot V : {\cal P}_{n-1}  \rightarrow {\cal P}_{n}  
\]

Define the composite operators
\[ \begin{array}{rcl} \label{KV} 
\KK_V(X)& := &  \KK( V X V^t),
\end{array} \] 
and
\[ \begin{array}{rcl} \label{TV} 
\TT_V(D)& := &  V^{\dagger}\TT( D)(V^{\dagger})^t= 
                     - \frac 12 V^{\dagger} D (V^{\dagger})^t.
\end{array} \] 

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


{\bf LEMMA}
\begin{eqnarray*} 
\KK_V ( \snn) =\Sh, \\
\TT_V ( \Sh) =\snn, 
\end{eqnarray*} 
and $\KK_V$ and $\TT_V$ are inverses of each other on these two spaces.
\epr

{\bf COROLLARY}
\begin{eqnarray*} 
\KK_V(\p)  & = &  \E , \\
\TT_V(\E) & = &\p.
\end{eqnarray*} 
\epr
\end{slide}
\begin{slide}{}

\begin{center}
Summary
\end{center}

(Re)Define the closest EDM problem:
\begin{eqnarray*}
 f(X) := {\| H \circ (A - \KK_V ( X)) \|}^2_F\\
          = {\| H \circ \KK_V(B - X) \|}^2_F, 
\end{eqnarray*}
where $B = \TT_V(A)$.\\
($\KK_V$ and $\TT_V$ are both linear operators)

{\bf
\[
(CDM)
 \begin{tabular}{ccc}
          $\mu^*$ := & $\min$   &   $f(X)$  \\
                  &  subject to  & $\A X=b $ \\ 
               &   &  $X \succeq 0.$
  \end{tabular}
\]
}

~\\

~\\
The additional constraint
using $\A : \snn \longrightarrow \Re^m$, 
could represent some of the fixed
elements in the given matrix $A$.
\end{slide}
\begin{slide}{}

{\bf Primal-Dual Interior-Point Framework:}

\begin{enumerate}
\item[Step 1]
derive a dual program

\item[Step 2]
state optimality conditions for log-barrier problem (perturbed
primal-dual optimality conditions)

\item[Step 3]
find a search direction for solving the perturbed optimality conditions

\item[Step 4]
take a step and backtrack to stay strictly feasible (positive definite)

\item[Step 5]
Update and go to Step 3
(adaptive update of log-barrier parameter)
\end{enumerate}

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

{\bf Step 1.  derive a dual program:}

$\Lambda \in \snn, \Lambda \succeq 0$ and $y \in R^m$, \\
Lagrangian is
\[
L(X,y,\Lambda) = f(X) + \langle y, b - \A(X) \rangle - 
   \langle \Lambda, X  \rangle
\]

primal program (CDM) is
\[
       =  \min_{X} \max_{\stackrel{y}{\Lambda 
                    \succeq 0}}  L(X,y,\Lambda).   
\]

dual program is:
\[
         = \max_{\stackrel{y}{\Lambda \succeq 0}} \min_{X}  
          L(X,y,\Lambda),  
\]
\end{slide}
\begin{slide}{}

The inner minimization of the convex, in $X$, Lagrangian is unconstrained
so we add the hidden constraint which makes the minimization redundant.

dual program (DCDM)
\[
 \max_{\stackrel{\nabla f(X) - \A^*y=\Lambda}{\Lambda \succeq 0}}
                f(X) + \langle y, b - \A(X) \rangle - \mbox{trace} \Lambda X.
\]
or
\[
\begin{array}{cccc} 
 & & \max & f(X)+\langle y, b - \A(X) \rangle -
      \trace  \Lambda X \\  
       &           & \mbox{subject to} & \nabla f(X) - \A^*y- \Lambda = 0  \\
       &           &             &   \Lambda \succeq 0, (X \succeq 0).   
\end{array}  \]


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

the duality gap,\\
 $  f(X)-\left(f(X)+\langle y, b - \A(X) \rangle - \trace  \Lambda X
           \right),$\\
in the case of primal and dual
feasibility, is given by the complementary slackness condition:
\[
\mbox{ trace } X (\KK^*_V( H^{(2)} \circ \KK_V( {X}-B))- \A^*{y}) = 0,
\]
or equivalently 
\[
 X (\KK^*_V( H^{(2)} \circ \KK_V( {X}-B))- \A^* {y}) = 0 ,
\]
where $H^{(2)}=H \circ H.$
\end{slide}
\begin{slide}{}


{\bf THEOREM}
Suppose that Slater's condition holds. Then
$\bar{X} \succeq 0$, and $\bar{y}$, $\bar{ \Lambda} 
      \succeq 0$ solve (CDM) and (DCDM),
respectively, if and only if the following three equations hold.
\[ \begin{array}{cc}
 \A (\bar{X}) = b  & \mbox{prim. feas.}  \\
  2\KK^*_V( H^{(2)} \circ \KK_V( \bar{X}-B)) - \A^* \bar{y} - 
                          \bar{\Lambda} =0 &
                                           \mbox{dual feas.}  \\
\trace \bar{ \Lambda} \bar{X}=0 & \mbox{C.S.}
\end{array} \]  
\epr


{\bf LEMMA}
Let $H$ be an $n \times n$ symmetric matrix with nonnegative elements
and 0 diagonal such that the graph of $H$ is connected.  Then 
\[ \KK_V^*(H^{(2)} \circ \KK_V(I)) \succ 0 ,  \]
where $I \in \snn$ is the identity matrix.
\epr


i.e. when ${\cal A}=0,$ we have a Slater point for the dual (and
primal)



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

{\bf Step 2.  
state optimality conditions for log-barrier problem (perturbed
primal-dual optimality conditions):}


 The log-barrier problem for (CDM) is
\[ \min_{X \succ 0} B_{\mu}(X) := f(X) - \mu \log \det(X),  \]
where $\mu \downarrow 0$. 

For each $\mu > 0$ we take one Newton step
for solving the stationarity condition
\[
\nabla B_{\mu}(X) = 2 \KK^*_V(H^{(2)} \circ \KK_V(X - B)) - \mu
X^{-1}=0.
\]

Let
\[
C := 2 \KK^*_V(H^{(2)} \circ \KK_V( B))
= 2 \KK^*_V(H^{(2)} \circ A).
\]

Then the stationarity condition is equivalent to
\[
\nabla B_{\mu}(X) = 2 \KK^*_V\left(H^{(2)} \circ \KK_V(X)\right)
            - C - \mu X^{-1}=0.
\]



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

equating $\Lambda = \mu X^{-1}$ and multiplying through by $X$

optimality conditions,
$F:=\left( \begin{array}{c} F_d \\ F_c  \end{array} \right)=0,$
\[ \begin{array}{llccl}
 2 \KK^*_V\left(H^{(2)} \circ \KK_V(X)\right) - C
- \Lambda &=&0 &  \mbox{dual feas.} \\
 \Lambda X - \mu I&=&0  &  \mbox{pert. C.S.},
\end{array} \]
(an OVERDETERMINED nonlinear system since $\Lambda X$ not
symmetric)

estimate of the barrier parameter
\[  \mu = \frac{1}{n-1} \mbox{ trace }\Lambda X    \]


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

$\sigma_k$ centering parameter \\
${\cal F}^0$ set of strictly feasible primal-dual
points\\
 $F^\prime$ derivative of $F$

\begin{alg}
 (p-d i-p framework:)\\
{\bf Given} $(X^0,\Lambda^0) \in {\cal F}^0$\\
{\bf for} $k=0,1,2 \ldots $\\
\hspace{.5in}{\bf solve} for the search direction\\
     \[
  ~~~~F^{\prime}(X^k,\Lambda^k)
\left(
\begin{array}{ccc}
\delta X^k \\  \delta \Lambda^k
\end{array}
\right)
= 
\left(
\begin{array}{ccc}
-F_d \\ -\Lambda^k X^k+ \sigma_k \mu_k I
\end{array}
\right)
\]
\hspace{.5in}where $\sigma_k$ centering,
 $\mu_k=\frac {\trace X^k\Lambda^k}{(n-1)}$

\[ (X^{k+1},\Lambda^{k+1}) = (X^k,\Lambda^k) +
\alpha_k
(\delta X^k,    \delta \Lambda^k)
\]
\hspace{.5in}so that $(X^{k+1},\Lambda^{k+1}) \succ 0$\\
{\bf end (for)}.
\end{alg}




\end{slide}
\begin{slide}{}
For the EDM:

search direction (Gauss-Newton direction)
is the Frobenius norm lss of
\[ F^{\prime} s = - F,\]
i.e.
\[ \begin{array}{rcll}
 2 \KK^*_V\left(H^{(2)} \circ \KK_V (h)\right) - l&=&-F_d    \\ 
  \Lambda h + l X&=&-F_c.
\end{array} \]
$t(n)=\frac {(n+1)n}2$ be dimension of $\Sn.$
\[
F^{\prime} s=
\left[  \begin{array}{cc}
F^{\prime}_{u1}& F^{\prime}_{u2}\\
F^{\prime}_{l1} & F^{\prime}_{l2}
\end{array} \right]
\left(  \begin{array}{cc}
h \\
l
\end{array} \right)
=
rhs=
\left(  \begin{array}{cc}
rhs_1 \\
rhs_2
\end{array} \right).
\]
Operator $F^{\prime}$ maps $\Re^{2(t(n-1))}$ to $\Re^{t(n-1)+(n-1)^2}.$ 




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


%%    \begin{figure}[htb]
%     \centering
%     \centerline{\
%\psfig{figure=fig11513.ps,width=5.3in}
%%      \label{fig2}
%%   \caption{Approximate Completion Problem}
%%    \end{figure}



\psfig{figure=fig11513.ps,width=5.3in}
\end{slide}
\begin{slide}{}

\psfig{figure=fig13513.ps,width=5.3in}
\end{slide}
\begin{slide}{}

\psfig{figure=fig8513.ps,width=5.3in}
\end{slide}
\begin{slide}{}

\psfig{figure=fig9513.ps,width=5.3in}


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

\begin{center}
{\em Larger} Models
\end{center}
often result in improved numerical complexity.
Instead of projecting and reducing the dimension to get
Slater's condition, add a variable and increase the dimension.

\begin{lem}
\label{lem:newcharact}
Let
\[
\begin{array}{rcl}
\FF &:=& \{X \in \Sn : v^Te=0 \quad \Rightarrow \quad v^TXv
\leq 0
           \},\\
\FF_0 &:=&\{ X \in \Sn :
       X - \alpha ee^t \preceq 0, \quad \mbox{for some } \alpha
\geq 0
        \},\\
\FF_1 &:=&\{ X \in \Sn :
X - \alpha ee^t \preceq 0, \quad \forall ~ \alpha \geq
\bar{\alpha},\\
&& ~~~~~~~~~\mbox{ for some } \bar{\alpha} \geq 0 \}.
\end{array}
\]
Then
\beq  \label{eq:subsets}
  {\rm ri} \left(\FF \right) \subset
  \FF_0  = \FF_1 \subset \FF \subset \overline{\FF_0}.
\eeq
\end{lem}


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


\bpr
Suppose that $\bar{X} \in {\rm ri} \left(\FF \right)$ (i.e.
$v^Te=0, v \neq 0 \Rightarrow v^T\bar{X}v < 0$) but
$\bar{X} \notin  \FF_0$.
Then, for each $\alpha \geq 0$,
there exists $w_{\alpha}$ with $||w_{\alpha}||=1$, such that
$w_{\alpha} \rightarrow \bar{w}$, as $\alpha \rightarrow
\infty$ and
\[
w_{\alpha}^T(\bar{X} - \alpha  ee^t)w_{\alpha} > 0, \quad
\forall ~
            \alpha\geq 0,
\]
i.e.
\[
w_{\alpha}^T\bar{X}w_{\alpha} >
\alpha w_{\alpha}^T  ee^tw_{\alpha} , \quad \forall ~
            \alpha\geq 0.
\]
Since $w_{\alpha}$ converges and the left-hand-side of the
above
inequality must be finite, this implies that $e^t \bar{w} =
\bar{w}^T\bar{X}\bar{w} = 0$, a contradiction. Therefore,
  ${\rm ri} \left(\FF \right) \subset \FF_0$.
That $\FF_0 = \FF_1$ is clear.

Now suppose that $\bar{X} - \alpha ee^t \preceq 0, ~ \alpha
\geq 0$. Let $v^T
e
= 0$. Then $0 \geq v^T(\bar{X} - \alpha ee^t)v=v^T\bar{X}v$,
i.e.
$\FF_0 \subset \FF$. The final inclusion comes from the first
and
the fact that $\FF$ is closed.
\epr


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

\begin{cor}
\label{cor:newcharacthollow}
Let
\[
\begin{array}{rcl}
\EE &:=& \{X \in \Sh : v^Te=0 \quad \Rightarrow \quad v^TXv
\leq 0
           \},\\
\EE_0 &:=&\{ X \in \Sh :
       X - \alpha ee^t \preceq 0, \quad \mbox{for some } \alpha
        \},\\
\EE_1 &:=&\{ X \in \Sh :
X - \alpha ee^t \preceq 0, \quad \forall ~ \alpha \geq
\bar{\alpha},\\
&& ~~~~~~~~~~~~ \mbox{ for some } \bar{\alpha} \}.
\end{array}
\]
Then
\beq  \label{eq:subsetsE}
  \EE = \EE_0  = \EE_1.
\eeq
\end{cor}
\bpr
The proof is similar to that in the above Lemma
\ref{lem:newcharact}.
We only include the details about the closure.

Suppose that $0 \neq X_k \in \EE_0$, i.e.
$\diag(X_k)=0, X_k \preceq \alpha_k E$, for some $\alpha_k$;
and, suppose that
$X_k \rightarrow \bar{X}$. Since $X_k$ is hollow it has exactly
one positive eigenvalue and this must be smaller than
$\alpha_k$.
However, since $X_k$ converges to $\bar{X}$, we conclude that
$\bar{X} \leq \lambda_{\max}(\bar{X}) E$, where
$\lambda_{\max}(\bar{X})$ is the largest eigenvalue of
$\bar{X}$.
\epr



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

let: $E=ee^t$;
$f(P) := {\| H \circ (A - P) \|}^2_F$;\\
$\KK$ lin. operator with constraint $\diag (P)=0$.\\
{\bf primal problem} is:
\[
({\rm CDM})
 \begin{tabular}{ccc}
          $\mu^*$ := & $\min$   &   $f(P)$  \\
                  &  subject to  & $\KK P=b $ \\
               &   &  $\alpha E-P \succeq 0$
  \end{tabular}
\]
and {\bf dual problem (DCDM)} is
\[
\begin{array}{lcc}
   \nu^*:=\\
 ~~~\max &f(P) +\left<y,b-KP\right>- \tr \Lambda (\alpha
E-P)\\
 ~~~  \mbox{s.t.} &  \nabla_P f(P)  -\KK^*y+ \Lambda =
0\\
 ~~~                      & -\trace \Lambda E =  0\\
          ~~~&       \Lambda \succeq 0.
    \end{array}
\]

(Slater's holds for primal but fails for dual.)

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

(perturbed) Optimality Conditions are:
\[
\begin{array}{cl}
  \diag (P) = 0  & \mbox{primal feas.}\\
 2H^{(2)} \circ (P-A)-\Diag(y) +\Lambda =  0, \\
  ~~~  -\trace \Lambda E= 0  & \mbox{dual feas.}\\
-(\alpha E -P) + \mu \Lambda^{-1}  = 0, ~
                  & \mbox{pert. C.S.}\\
\end{array}
\]



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

 \[  \begin{array}{rcl}
h & \mbox{denotes the step for}&  P\\
w & \mbox{denotes the step for}&  \alpha\\
l & \mbox{denotes the step for}&  \Lambda\\
s & \mbox{denotes the step for}&  y.
\end{array}
\]

maintain
\[
\diag(h)=\diag(P)=0
\]



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

linearization of complementary slackness
\[
\begin{array}{rcl}
-(\alpha + w)E+(P+h)+ \mu \Lambda^{-1} -
                     \mu \Lambda^{-1} l \Lambda^{-1}&=&0,
\end{array}
\]


solve for $h$
\[
\begin{array}{rcl}
h &=& -\mu \Lambda^{-1} + \mu \Lambda^{-1}
           l \Lambda^{-1}-P +(\alpha  +w)E.
\end{array}
\]
(or solve for $l$)

linearization dual feasibility
\[
\begin{array}{rcl}
2 H^{(2)} \circ h -\Diag(s) +l &=& -( 2H^{(2)} \circ (P-A)\\
               && ~~~ -\Diag(y)+\Lambda)\\
-\trace  l E   &=& \trace \Lambda E
\end{array}
\]







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

substitute for $h,s$\\
Newton equation is
\[
\begin{array}{rcl}
 2 H^{(2)} \circ \left(
wE +\mu \Lambda^{-1} l \Lambda^{-1}  \right) -\Diag\diag (l)+ l \\
 ~~~~~ = 2 H^{(2)} \circ \left\{\mu \Lambda^{-1} +A  -\alpha E \right\}
          +\Diag(y) -\Lambda\\
\diag\left( \mu \Lambda^{-1} l \Lambda^{-1}\right)  + we \\
  ~~~~~ = \diag\left(\mu \Lambda^{-1}\right) - \alpha e\\
\trace(lE)  = -\trace(\Lambda E).
\end{array}
\]
square system, order $1+nnz$ where $nnz$ are the number of
nonzeros in the upper triangular part of $H$, ($\diag(H)=0$).



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

$F$ denotes $(nnz+n) \times 2$ matrix\\
row $p$ contains indices of the $p$-th nonzero, 
upper triangular, element of $H+I$ ordered by columns,
\[
\begin{array}{lcc}
\left\{ (F_{p1},F_{p2})_{p=1, \ldots nnz+n} \right\}\\
  ~~~~~~~~~~  = \left\{ ij : H_{ij} \neq 0, i \leq j, \mbox{ ordered
                by columns} \right\}.
\end{array}
\]
$\delta_{ij}$ is {\em Kronecker delta function}\\
 $\delta_{(ij)(kl)}$  is 1 if $(ij)=(kl)$, 0 otherwise.

$E_{ij} = \left( e_ie_j^t+e_j^te_i\right)/\sqrt{2}$,
$ij$ unit matrix in $\Sn$, where 
$E_{ij} = \left(e_ie_j^t+e_j^te_i\right)/2$ if $i=j$.\\
(orthonormal basis of $\Sn$)



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


operator equation:\\
\[
\begin{array}{lcl}
{\bf \mbox{$k\neq l, i\neq j$ LHS}} = \\
= \tr E_{kl} \left\{ 2 H^{(2)} \circ 
\left( \mu\Lambda^{-1} E_{ij} \Lambda^{-1} \right) 
   -\Diag \diag (E_{ij}) \right.\\
   ~~~~~~~~~~~~~~~~~~ \left. + E_{ij}\right\} \\
= \mu\tr (e_ke_l^t+e_le_k^t) \left(H^{(2)} \circ \Lambda^{-1}
    (e_ie_j^t+e_je_i^t)\Lambda^{-1} \right)\\
      ~~~~~~~~~~~~~~~~ + \delta_{(ij)(kl)}\\
=  \mu   \left[
     2e_{l}^t \left(H^{(2)} \circ \Lambda^{-1}_{:,i}
                   \Lambda^{-1}_{j:} \right)e_k+
     2e_{k}^t \left(H^{(2)} \circ \Lambda^{-1}_{:,i}
                   \Lambda^{-1}_{j:} \right)e_l \right] \\
   ~~~~~~~~~~~~    + \delta_{(ij)(kl)};\\
{\bf \mbox{$k\neq l, i\neq j$ LHS}}=\\
=  2 \mu H^{(2)}_{kl} \left(
     \Lambda^{-1}_{li} \Lambda^{-1}_{jk}+
  \Lambda^{-1}_{ki} \Lambda^{-1}_{jl} \right)  + \delta_{(ij)(kl)};\\
{\bf \mbox{$k\neq l, i= j$ LHS}}=\\
= \tr E_{kl} \left\{ 2\mu H^{(2)} \circ 
\left[ \Lambda^{-1} E_{jj} \Lambda^{-1} \right]
   -\Diag \diag (E_{jj}) \right.
     ~~~~~~~~~~~~~~~~\left.  + E_{jj}\right\} \\
= 2\sqrt{2}\mu\tr e_ke_l^t \left(H^{(2)} \circ \Lambda^{-1}
     e_je_j^t \Lambda^{-1} \right) \\
=  2\sqrt{2} \mu H^{(2)}_{kl} \left(
     \Lambda^{-1}_{lj} \Lambda^{-1}_{jk} \right);\\
{\bf \mbox{$k =  l, i\neq j$ LHS}}=\\
~~~ =  \sqrt{2}\mu \Lambda^{-1}_{ki} \Lambda^{-1}_{jk},
              \quad k= 1, \ldots n;\\
{\bf \mbox{$k =  l, i= j$ LHS}}=\\
=  \mu \Lambda^{-1}_{ki} \Lambda^{-1}_{ik},
                  \quad k= 1, \ldots n.
\end{array}
\]


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


last column of LHS, matrix $l=0$ and $w=1$:
\[
\begin{array}{rcl}
{\bf \mbox{$w=1, k \neq l$ LHS}} =\\
~~~ \tr  \left(E_{kl} ( 2H^{(2)} \circ E)\right);\\
{\bf \mbox{$w=1, k=l$ LHS}} = 1.
\end{array}
\]
last row of LHS:
\[
\begin{array}{rcl}
{\bf \mbox{$ i \neq j$ LHS}}=
               &=& \tr  \left(E_{ij} E)\right) =   \sqrt{2};\\
{\bf \mbox{$ i = j$ LHS}}=
               &=&   1.
\end{array}
\]


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


Newton system is:
\[
 \sMat\left[ L (\svec (l))\right] = \sMat\left[ \svec (RHS) \right],
\]
$\svec(S)$ vector formed from 
nonzero elements of columns of
upper triangular part, where
strict upper triangular part is multiplied by
$\sqrt{2}$. ($\trace XY = \svec(X)^t
\svec(Y)$, i.e. isometry)
$\sMat$ is inverse

Solve for $\svec(l)$:
\[
  L (\svec (l)) =  \svec (RHS).
\]


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

$ L_{pq}= $
\[
  \left\{  \begin{array}{ll}
     2 \mu H^{(2)}_{F_{p_2},F_{p_1}}
  \left(
      \Lambda^{-1}_{F_{p_2},F_{q_1}} 
       \Lambda^{-1}_{F_{q_2},F_{p_1}}  +
      \Lambda^{-1}_{F_{p_1},F_{q_1}} 
       \Lambda^{-1}_{F_{q_2},F_{p_2}}  \right) \\
   ~~~~~~~~~~~~~~~~~~~~ \mbox{if } p \neq q, ~  k \neq l, ~ i \neq j;\\
     2\sqrt{2} \mu H^{(2)}_{F_{p_2},F_{p_1}}
  \left(\Lambda^{-1}_{F_{p_2},F_{q_2}} 
       \Lambda^{-1}_{F_{q_2},F_{p_1}}  \right) \\
   ~~~~~~~~~~~~~~~~~~~~~~ \mbox{if } p \neq q, ~  k \neq l, ~ i = j;\\
     2\sqrt{2} \mu H^{(2)}_{F_{p_2},F_{p_1}}\left(\Lambda^{-1}_{F_{p_2},F_{q_2}} 
       \Lambda^{-1}_{F_{q_2},F_{p_1}}  \right) \\
   ~~~~~~~~~~~~~~~~~~~~~~ \mbox{if } p = q, ~ k \neq l, ~  i = j;\\
     2 \mu H^{(2)}_{F_{p_2},F_{p_1}}
  \left(
      \Lambda^{-1}_{F_{p_2},F_{q_1}} 
       \Lambda^{-1}_{F_{q_2},F_{p_1}}  +
      \Lambda^{-1}_{F_{p_1},F_{q_1}} 
       \Lambda^{-1}_{F_{q_2},F_{p_2}}  \right) +1\\
   ~~~~~~~~~~~~~~~~~~~~~~~~~ \mbox{if } p = q, k \neq l, ~  i \neq j;\\
     \sqrt{2}\mu \Lambda^{-1}_{F_{p_1},F_{q_1}} \Lambda^{-1}_{F_{q_2},F_{p_1}} \\
   ~~~~~~~~~~~~~~~~~~~~~~~~~~~ \mbox{if }   k=l, ~ i \neq j;\\
     \mu \Lambda^{-1}_{F_{p_1},F_{q_1}} \Lambda^{-1}_{F_{q_1},F_{p_1}}
   & \mbox{if }   k=l, ~ i=j\\
     2\sqrt(2) H^{(2)}_{F_{p_2},F_{p_1}}
   & \mbox{if }   w=1,~k \neq l\\
  1
   & \mbox{if }   w=1,~k = l.
\end{array}  \right.
\]
The $p$-th row
calculated using Hadamard product of pairs of columns of
$\Lambda^{-1}$,
\[
  \Lambda^{-1}_{F_{p_2},F_{:,1}} \circ
       \Lambda^{-1}_{F_{p_1},F_{:,2}}.
\]
complete vectorization



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

$p=kl, k\leq l$, and last row, 
component of the right-hand-side of the system is\\
$RHS_p =$
\[
 \left\{
\begin{array}{lcl}
\sqrt{2}\left(  2H^{(2)}_{p} \circ
     \left\{\mu \Lambda^{-1}_p +A_p  
     -\alpha \right\} -\Lambda_p \right), 
                   & \mbox{if }k \neq l\\
      \mu \Lambda^{-1}_{kk} - \alpha & \mbox{if } k=l\\
     -\trace (\Lambda E)   & \mbox{last row } \\
\end{array}  \right.
\]

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


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


\end{slide}

%\bibliography{.psd,.master,.publs}
\end{document}
