\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{\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\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}
}
~~\\
~~\\
~~\\
~~\\
~~\\
~~\\
~~\\
\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
Outline of SDP, history
\item
SDP and combinatorics
\item
SDP and matrix completions
\item
Euclidean distance matrix completions
\item
graph embedding
\end{enumerate}




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



\begin{center}SDP: BACKGROUND and HISTORY
\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}
Direct SDP Relaxation
\end{center}
\begin{center}
Max-Cut Problem
\end{center}
\[
 \begin{array}{c}
    \max ~ \frac 12 \sum_{i<j} w_{ij}(1-x_ix_j),~~~x \in  \{ \pm 1 \}^n.
\end{array}
\]
Equate $x_i=1$ with $i \in \cal I$ and -1 otherwise.  \\
Let
\[ q(x) := x^tQx, \]
where $Q$ is an $n \times n$ symmetric matrix.
An equivalent problem is  the homogeneous
{\em $(\pm 1)$-quadratic programming problem}
\[
\mu^*:=\max ~ q(x),~~~x \in \{ \pm 1 \}^n.
\]
Replace $x \in \{ \pm 1 \}^n$ with constraints $x_i^2=1.$

Note that for
\[ X=xx^t,  \]
\[ X \succeq 0,~ \diag (X) = e, ~q(x)=\tr XQ.  \] 
Relax the rank-1 condition on $X$ to get SDP.


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

The SDP Relaxation:\\

\[ \begin{array}{ccc}
\max&               \tr XQ\\
\mbox{subject to} & \diag (X) = e  \\
&                   X \succeq 0
\end{array}
  \] 

If the weights are nonnegative:\\
Goemans-williamson randomized approximation algorithm with performance
guarantee of 0.87856, i.e.
\[ \mbox{opt MC} \geq \mbox{rand. value} \geq 0.87856 \mbox{(opt SDP)}
\]

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


How does SDP arise from general quadratic approximations?

Let 
\[q_i(y)=\frac 12 y^tQ_iy+y^tb_i + c_i,~y\in \Re^n \]
\[ {\bf (QQP)}
\begin{array}{ccc}
    q^*=  & \min &q_0(y) \\
 &  \mbox{s.t.} & q_i(y)\leq 0\\
     &&  i=1,\ldots m
    \end{array}
\]
Lagrangian:\\
\[ 
\begin{array}{ccc}
  L(y,x) &=& q_0(y) + \sum_{i=1}^m x_iq_i(y)
\end{array}
\]
or equivalently
\[ 
\begin{array}{ccc}
  L(y,x) &=& \frac 12 y^t (Q_0 +\sum_{i=1}^m x_iQ_i)y  \\
 &&   +y^t(b_0 +\sum_{i=1}^m x_ib_i)\\
   &&+ (c_0 +\sum_{i=1}^m x_ic_i)
\end{array}
\]
\end{slide}
\begin{slide}{}

Weak duality follows from ``hidden constraint''
\[d^*=\max_{x\geq 0} \min_y L(y,x) \leq q^* = \min_y \max_{x\geq 0} L(y,x).
\]

Now homogenize; multiply linear term by new variable $y_0$
\[ y_0y^t(b_0 +\sum_{i=1}^m x_ib_i), ~~ y_0^2=1.  \]

\end{slide}
\begin{slide}{}
\[
\begin{array}{cccc}
  d^*=\\
  =\max\limits_{x \geq 0} \min_y &L(y,x)\\
  = \max\limits_{x \geq 0} 
         \min\limits_{y_0^2=1}& \frac 12 y^t (Q_0 +\sum_{i=1}^m x_iQ_i)y 
                            ~~~~~+ty_0^2 \\
 &   +y_0y^t(b_0 +\sum_{i=1}^m x_ib_i)\\
 &+ (c_0 +\sum_{i=1}^m x_ic_i)
                            ~~~~~-t\\
  = \max\limits_{x \geq 0,t} 
         \min\limits_{y}& \frac 12 y^t (Q_0 +\sum_{i=1}^m x_iQ_i)y 
                            ~~~~~+ty_0^2 \\
 &   +y_0y^t(b_0 +\sum_{i=1}^m x_ib_i)\\
 &+ (c_0 +\sum_{i=1}^m x_ic_i)
                            ~~~~~-t\\
\end{array}
\]

The hidden semidefinite constraint yields the semidefinite program. 
\end{slide}
\begin{slide}{}
We get
\[ 
B:=\left( \begin{array}{cc}
      0 & b_0^t \\ b_0 &Q_0
   \end{array}  \right),
\] 
 $A: \Re^{m+1} \rightarrow {\cal S}_{n+1}$
\[ 
A \left( \begin{array}{c}
      t \\ x
   \end{array}  \right)
   := -\left[ \begin{array}{cc}
        t &  \sum_{i=1}^m x_ib_i^t \\
      \sum_{i=1}^m x_ib_i  & \sum_{i=1}^m x_i Q_i
        \end{array}   \right]
\]
and the SDP constraint
\[
B-A \left( \begin{array}{c}
      t \\ x
   \end{array}  \right)
 \succeq 0.
\]

{\bf NOTE There is NO hidden constraint on the $Q_i$ 
if all $q_i$ are convex.} There is no need for SDP in the convex case.
Better algorithms exist, e.g. proximal methods, using quadratic cones,
...

\end{slide}
\begin{slide}{}
The dual program is equivalent to the SDP (with $c_0=0$)
\[ {\bf (D)}
\begin{array}{ccc}
    d^*=  & \mbox{sup} & -t +\sum_{i=1}^m x_ic_i \\
 &  \mbox{s.t.} & A\left( \begin{array}{c}
      t \\ x
   \end{array}  \right)
 \preceq B\\
  && x \in \Re^m, t \in \Re
    \end{array}
\]
As in linear programming, the dual of the dual is obtained from the optimal
strategy of the competing player:
\[ {\bf (DD)}
\begin{array}{ccc}
    d^*=& \inf &\tr BU \\
 &  \mbox{s.t.} & A^*U = \left( \begin{array}{c}
      -1 \\ c
   \end{array}  \right) \\
  && U \succeq 0.
    \end{array}
\]


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

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

Solve the perturbed
nonlinear system,
\[\tr \bar{\Lambda} \bar{P} = \mu I,\]
using Newton's method
i.e. take one Newton
step then update/decrease the barrier parameter $\mu$\\

Two algorithms: dual-step-first; primal-step-first

Exploit sparsity, i.e. depends on whether there are 
{\em many} elements fixed or
{\em many} elements free.





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

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




REMARKS:
\begin{description}
\item
An initial stepsize of 1.5 was taken; tests were also done with 2 and
improved convergence was noted.
\item
A centering parameter $\sigma$ changes adaptively
depending on the length of the stepsize, i.e. it decreases if the
stepsize is large and increases to 1 if the stepsize is small.
\item
The barrier parameter $\mu$ also changes adaptively; there is an
aggressive decrease $\mu/4n$ if the stepsize is large; this decrease is
smaller when small stepsizes are chosen.
\end{description}
\end{slide}
\begin{slide}{}
\begin{description}
\item
Backtracking was initially
done with the value .95 to be conservative, as is
usually the case with SDP. However, tests were done with the aggressive
.997 as is done in LP. This did not result in faster convergence.
However, robustness was maintained.
\item
The upper part of $F^{\prime}$, i.e. $[ F^{\prime}_{u1}~ F^{\prime}_{u2}],$ 
need only be evaluated once
at the beginning; while the lower (simpler) part of the operator needs to be
evaluated at each iteration.
Both evaluations take very little time compared to the solution of the
least squares problem.
\end{description}
\end{slide}
\begin{slide}{}
\begin{description}
\item
No predictor-corrector approach was used. Rather, centering was used to
speed up convergence.
However, the step lengths were
consistently larger than 1 which suggests that no corrector step is
needed, i.e. centering keeps 
the steps very close to the central path.
\item
Though the initial starting points were feasible, dual feasibility was
lost after the first iteration, i.e. unlike Newton's method, the
Gauss-Newton direction does not maintain feasibility. However,
complementarity and dual feasibility converged together to 0, i.e. at a
similar rate. This might account for the strong convergence obtained
with this direction.
\end{description}
\end{slide}
\begin{slide}{}
\begin{description}
\item
The search direction was very robust, i.e. machine accuracy was
attainable whenever asked for. This was the case even when the
aggressive initial stepsize and reduction of $\mu$ were used.
\item
Problem dimension was restricted to $n \leq 42$. 
This was because of the high cost of the least squares solution
in MATLAB. (Done
using qls, Version 1.6, from Pontus Matstoms, Linkoping University.)
However, if one solves the
least squares problem using, for example, a Lanczos approach, then one
need never form the matrices which represent $F^{\prime}$ and thus
can exploit sparsity and solve much larger problems. These tests are
ongoing.
\end{description}
\end{slide}
\begin{slide}{}
\begin{description}
\item
We have assumed, without loss of generality, that the graph of the
matrix $H$ was connected, i.e. if this was not the case then we can
solve two smaller problems independently and more simply. In fact, one
should always solve the smaller problems independently. Note that
Slater's constraint qualification is always satisfied for the primal and
so there is no duality gap. However, if Slater's constraint
qualification fails for the dual (which is equivalent to the graph being
disconnected), then the set of optimal
solutions for the primal is unbounded and the algorithm has great
difficulty converging. Here is an example of a class of problems where
strong duality holds but interior-point methods have difficulty.
\end{description}



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



\begin{center}
{\bf A Heuristic for \\ Low Dimensional Realizations of Weighted Graphs}
\end{center}
\begin{flushright}with Abdo Alfakih\end{flushright}

$G=(V,E,\omega)$
edge-weighted connected graph,
$n$ nodes, $m$ edges\\
with  points $p^1,p^2,\ldots,p^n \in \Re^r$\\
\[
P := \left[ \begin{array}{c}
        {p^1} \quad {p^2} \quad \ldots \quad {p^n} \end{array} \right]^t,
\quad \mbox{$n \times r$ matrix}
\]
is called a {\em realization} of $G$ in $\Re^r$ if
\[ \|p^i-p^j\|= \omega_{ij} \;\;\;\; \mbox{ for all } (v_i,v_j) \in
E, \]


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

We assume:\\
$G$ is {\em $r$-realizable}, i.e.
there exists a realization of $G$ in $\Re^r$.\\
And, wlog that
$P^Te=0$, ($e \in \Re^n$ vector of ones) $\mbox{rank} P = r$

The\\
{\bf Euclidean distance matrix (EDM) associated with a realization $P$}\\
is the $n \times n$ matrix 
\[D_P = (d_{ij})= \|p^i-p^j\|^2.\]
($D_{P}$ is symmetric with zero diagonal and
$d_{ij}=\omega^2_{ij}$ for all $(v_i,v_j) \in E$)


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

again, with
$V$ $n \times (n-1)$ matrix
\[ V^Te=0\;, \;\;\;\;  V^TV=I_{n-1}; \]
~~\\
we get three equivalent representations for the realization:\\
{\bf THEOREM} Given a realization $P$ of a weighted graph 
$G =(V,E, \omega)$
such that ${P}^T e =0$, then $P$ can be equivalently
represented by the matrices $B$ or $X$
where $B := P P^T$ and $X := V^T B V$.
\epr


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

we use the $(n-1) \times (n-1)$
positive semidefinite matrix $X$ as the representation
of a given realization of a graph $G$ since:\\

it allows
a much simpler characterization of $\Omega$, the set of all
realizations
of graph $G$ in all dimensional Euclidean spaces;\\

the set $\Omega$
has the desired property of being full dimensional, whenever the
given
graph $G$ has a realization in $\Re^{(n-1)}$.



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



$H=(h_{ij})$ adjacency matrix of graph $G$ 

\[  \A(X) := H \circ \KK_V(X), \quad \mbox{linear operator}  \]
($\circ$ Hadamard product)

\[  
\begin{array}{rcl}
\KK_V(X)& := & \mbox{diag}(V X V^T)\,e^T + 
                   e \, \mbox{diag}(V X V^T)^T\\
          &&~~~~~~~~~~~ -2 V X V^T
\end{array} \]

$\bar{m}$ number of  missing edges of $G$ \\
 $\bar{m}= n(n-1)/2 - m$

$E^{ij} \in \Sn$ matrix with ones in $(i,j)$th and $(j,i)$th entries

if $h_{ij}=0$ and $i < j$, let
\[  M^k := -\frac{1}{2} V^T E^{ij} V, ~k=1,\ldots,\bar{m} \]
 



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


Then
\{ $M^k$ : $k=1,\ldots, \bar{m}$ \}
is  linearly independent set; forms a basis for ${\cal N}(\A)$
\[ 
{\cal N}(\A) = \{ B \in \snn : B= \sum_{k=1}^{\bar{m}} 
  y_k M^k,  \mbox{some } y \in \Re^{\bar{m}} \}. \]

Recall that $X^*$ = $V^T B^* V$ = $V^T P^* {P^*}^T V$ and
that $X^* \in \snn $ is positive semidefinite with rank $r$. 


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

Let $\Omega_r$ be the subset of 
$\Re^{\bar{m}}$ defined by   
\[
\begin{array}{rcll}
\Omega_r &:= &\{ y \in \Re^{\bar{m}}:& X(y)= X^* + 
      \sum_{k=1}^{\bar{m}} y_k M^k \succeq 0,\\
           &&&  \mbox{and rank }X(y)=r\}.   
\end{array}
\]


{\bf THEOREM} Given a framework $(G,X^*)$ in $\Re^r$, then    
$\{ X(y) : y \in \Omega_r \}$ is the set of all realizations of $G$ 
in $\Re^r$.
\epr



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


By relaxing the rank condition on $X(y)$,   we get
the following closed, convex, and generally non-polyhedral  set.  
 
\[
\Omega := \{ y \in \Re^{\bar{m}} \; : \; X(y)= X^* + \sum_{k=1}^{\bar{m}} 
  y_k M^k \; \succeq 0 \}.
\]
It readily follows that  $\{ X(y) : y \in \Omega \}$ is the set
of all realizations of $G$ in all finite-dimensional Euclidean spaces. 
Since $X^* \succeq 0$, the origin is always contained in $\Omega$. 
Furthermore, $\Omega$ is bounded if and only if 
the given graph $G$ is connected.



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


{\bf Heuristic}

{\bf Step 1}

Given $G=(V,E,\omega)$, let 
\[
D =(d_{ij}) := \left\{ \begin{array}{cl} 
        \omega_{ij}^2  & \mbox{ if $(v_i, v_j) \in E$ } \\ 
         0             & \mbox{ otherwise } \end{array} \right\}. 
\]
Then solve the following SDP:

\[
 \bt{ccc}
          $\mu^*$ := & $\min$   &   ${\| H \circ (D - \KK_V(X) \; \|}^2_F $  \\
               &   &  $X \succeq 0.$
  \et
\]
$\mu^* = 0$ iff $G$ is realizable. Assume $G$ is realizable and let
$X^*$ be the optimal solution of the above SDP.




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


Also let  
\[
\Omega := \{ y \in \Re^{\bar{m}} \; : \; X(y)= X^* + \sum_{k=1}^{\bar{m}} 
  y_k M^k \; \succeq 0 \}.
\]

Then
\[\{ X(y) : y \in \Omega \}\] 
is the set
of all realizations of $G$ in all finite-dimensional Euclidean spaces. 
Furthermore, $\Omega$ is a nonpolyhedral convex closed set and it 
is bounded iff $G$ is connected.   

Note that the origin belongs to $\Omega$ since $X^* \succeq 0$.




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

Now it is easy to show that if $\hat{y}$ is an extreme point of
$\Omega$, then rank $X(\hat{y}) \leq r^*$. $r^*$ is Barvinok bound.    
Thus by moving to an extreme point of $\Omega$ we are guaranteed
a realization of $G$ in a Euclidean space of dimension $\leq r^*$. 
Obviously our goal is not to move to just any extreme point of $\Omega$
but rather to an extreme point $y$  such that rank of $X(y)$ is
as small as possible. That is done in step 2. 


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

{\bf Step 2}

Now chose a vector $c$ randomly and solve the following SDP. 

\[
 \bt{cl}
        $\max$   &   $c^T y $ \\
         $\mbox{ subject to }$ & $y \in \Omega. $ 
  \et
\]
It can be proved that if $\hat{y}$ is a vertex of $\Omega$. i.e.,
the normal cone $N(\Omega, \hat{y})$ is full dimensional, then
rank of $X(\hat{y})$ is {\em small}. Then since $c$ is random, we
have more chances of obtaining such a point $\hat{y}$ as a solution
of the above SDP.


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

Following is a derivation of optimality conditions for the SDP pair:

\[
 \bt{cl}
        $\max$   &   $c^T y $ \\
         $\mbox{ subject to }$ & $X^* + \sum_{k=1}^{\bar{m}} y_k M^k \succeq 0 $ 
  \et
\]
and
\[
 \bt{cll}
           $\min$   &   $\left< X^* Y \right> $ & \\
        $\mbox{ subject to }$ & $ \left<  Y M^k \right> = \; - \; c_k $ & for $k=1,\ldots,\bar{m}$, \\ 
                & $Y \succeq 0. $ & 
  \et
\]




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


 the perturbed optimality conditions are : 

\[
 \bt{clcll} \label {op}
     $Z$ & = & $ X^* + \sum_{k=1}^{\bar{m}} y_k \; M^k $  & \\ 
     $c_k$ &= & $ - \; \left<  Y M^k \right> $ & for $k=1,\ldots,\bar{m}$ \\ 
    $ ZY $ & = & $ \mu I \;, \quad Z \succeq 0$, $Y \succeq 0$ & \et
\]
~~\\
Linearizing yields:
\[
 \bt{rcll}
       $\delta Z -   \sum_{k=1}^{\bar{m}} \delta y_k \; M^k $  & = & $- F_d$ &  \\ 
      $ \left<  \delta Y M^k \right> $ &= & $ - F_p^k$ & for $k=1,\ldots,\bar{m}$ \\ 
      $ Z \; \delta Y + \delta Z \; Y $ & = & $ -Z Y + \mu I $ &   
  \et
\]

where
\[
 \bt{lcll}  
       $F_d$ & = & $ - X^* + Z - \sum_{k=1}^{\bar{m}} y_k \; M^k $  & \\ 
       $F_p^k$ &= & $ c_k + \; \left<  Y M^k \right> $ & for $k=1,\ldots,\bar{m}$  
  \et
\]


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

Solving for the search direction yields
\[
 \begin{array}{rcll} 
       \delta y & = &  A^{-1} b   & \\ 
       \delta Z  &= &  - F_d + \sum_{k=1}^{\bar{m}} \delta y_k \; M^k  \\ 
       \delta Y  & = &  - Y + \mu Z^{-1} + Z^{-1} F_d Y - 
    \sum_{k=1}^{\bar{m}} \delta y_k Z^{-1} M^k Y  
  \end{array}
\]
where 

\[
 \begin{array}{ccll} 
       A =(a_{ij})  & = & \left( \left<  Z^{-1} M^j Y M^i \right>\right) \\ 
b=(b_i) &=& \left( F_p^i - \left<  Y M^i \right> + \right.\\
     &&~~\mu\left.\left<  Z^{-1} M^i \right> + \left<  Z^{-1}F_d Y M^i \right>  
          \right)
  \end{array}
\]



\end{slide}

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