%\documentclass{slides}
\documentclass[landscape]{seminar}
\usepackage{amssymb}
\usepackage{latexsym}
\input epsf
\usepackage{psfig}
\pagestyle{plain}
\newtheorem{exam}{Example}
\newtheorem{prop}{Proposition}
\newtheorem{lem}{Lemma}
\newtheorem{thm}{Theorem}
\newtheorem{cor}{Corollary}
\newtheorem{alg}{Algorithm}
\newcommand{\cone}{{\rm cone\,}}
\newcommand{\NN}{{\mathcal N} }
\newcommand{\RR}{{\mathcal R} }
\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}{}
{\large{MOPTA 01}}
~~\\
~~\\
\fbox{
\begin{minipage}{3.5in}
\begin{center}
{\bf Semidefinite Programming\\
 and\\ Some Closest Matrix Approximation Problems}
\end{center}
\end{minipage}
}

\vspace{2mm}

{
Henry Wolkowicz \\
 }

\vspace{2mm}

Department of Combinatorics \& Optimization \\
University of Waterloo

\vspace{2mm}

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




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


\begin{center}OUTLINE
\end{center}

\begin{enumerate}
\item
SDP  - notation
\item
SDP and positive definite matrix completions
\item
Euclidean distance matrix (EDM) completions
\item
New characterization for EDM; (solving large sparse problems)
\item
Closest correlation matrix
\end{enumerate}

(Advantages of: using different forms of perturbed complementary
slackness , e.g.  $X-\mu Z^{-1}=0$; and using Gauss-Newton direction.)




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



\[ \begin{array}{cc}
  f(P):=||H \circ (A-P) ||_F^2 
\end{array}
\]
~~\\
~~\\
{\bf weighted, best approximation problem}
\fbox{
\begin{minipage}{4in}
\[
\begin{array}{ccc}
       \mu^*:=&\min &f(P) \\
 &  \mbox{~subject to~} &  P \in {\cal K}
    \end{array}
\]
\end{minipage}
}

~\\

$||A||_F = \sqrt{ \tr A^*A}$ {\em Frobenius norm},\\ 
$\circ$ denotes {\em Hadamard product},\\
${\cal K}$ is  a convex set (psd cone; EDM cone; correlation matrices).




\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^*=  & \min &\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 L{\"{o}}wner partial order
~~($A\preceq B$ if $B-A \succeq 0$)\\
${\cal S}^n$ --  $n \times n$ symmetric matrices

\begin{eqnarray*} 
{\cal A} &:& {\cal S}^n \rightarrow \Re^m \quad \mbox{linear operator} \\
({\cal A}X)_i &:=& \tr (A_iX),~
  \mbox{for given}~ A_i \in {\cal S}^n 
\end{eqnarray*} 

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

\hrulefill

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

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

Using Lagrangian
\[ L(X,y) :=  \tr (CX) +y^t(b-{\cal A}X)
\]
\[p^* = 
       \min_{X \succeq 0 } \max_{y }  L(X,y) 
\geq d^*:=\max_y \min_{X \succeq 0} L(X,y) 
\]
yields primal-dual pair of programs

\hrulefill

{\bf dual }
\[ {\bf (DSDP)}
\begin{array}{ccc}
    d^*=& \max &b^ty \\
 &  \mbox{s.t.} & {\cal A}^*y \preceq  C \\
    \end{array}
\]

for the {\bf primal}
\[ {\bf (PSDP)}
\begin{array}{ccc}
    p^*=  & \min &\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$~~($X\succeq 0, \mbox{ slack } Z \succeq 0$)
 \[ 
\begin{array}{cc} 
    \A^*y +Z = C  & \mbox{dual feasibility}\\
    \A X = b & \mbox{primal feasibility}\\
    ZX  = 0 & \mbox{complementary slackness}
\end{array}
\]
\[
    ZX = \mu I ~~~~~ \mbox{perturbed}
\]

Forms the basis for:\\ ~~\\
interior point methods\\
(primal simplex method,
dual simplex method)

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

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

{\bf given}:
\begin{quote}
 $H=H^t \geq 0$  {\bf real symmetric matrix of weights}\\
    \hspace*{.5in} (nonneg. els, $\diag (H) > 0)$\\
$A=A^*$ the {\bf given partial Hermitian matrix}
\end{quote}

\hrulefill

i.e. some elements (including diagonal) are approximately fixed; 
others are 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~} &  P \succeq 0.
    \end{array}
\]




\end{slide}
\begin{slide}{}
Current approach - use second order cone:

\[
(AC)~~
\begin{array}{ccl}
       \mu^*:=&\min &\alpha  \\
 &  \mbox{~subject to~} &  Y-H \circ (A-P)  =0 \\
  && ||Y ||_F \leq \alpha  \\
  &&P \succeq 0.
    \end{array}
\]



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


Direct approach - use Lagrangian:
\[
L(P,y,\Lambda) = f(P)   - \tr \Lambda P
\]
~~\\
Dual problem:
 \[
(DAC)
\begin{array}{ccc}
       \max &f(P) - \tr \Lambda P \\
   \mbox{~subject to~} &  \nabla f(P)  - \Lambda =  0\\
          &       \Lambda \succeq 0.
    \end{array}
\]

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

{\bf THEOREM} \label{thm:optcond}
The matrix $\bar{P}\succeq 0$ and matrix
$\bar{\Lambda} \succeq 0$ solve AC and DAC if and only if
\[
\begin{array}{cc}
 2H^{(2)} \circ (\bar{P}-A)
  -\bar{\Lambda} =  0 & \mbox{dual feas.}\\
\tr \bar{\Lambda} \bar{P} = 0 & \mbox{compl. slack.}\\
\end{array}
\]
\epr


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

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;\\
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 + \left( 2H^{(2)} \circ (P-A)
-\Lambda  \right)  \\
  & = &  2 H^{(2)} \circ  \left(\mu \Lambda^{-1} - 
 \mu \Lambda^{-1} l \Lambda^{-1}  -P \right) \\
   &&  ~~~~~~~  + ( 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}
\]

$l,\Lambda$ have same sparsity pattern as $H$,\\
order is number of nonzeros/2 in $H$.



\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  \\
\hline\hline
 dim& toler&$H$dens./infty&
           $A$psd &cond(A)&$H$pd&time/iter&iters\\ \hline
655   & $10^{-6}$& .0017/0  & no &$\infty$& no & 3.7 & 29.  \\
755   & $10^{-3}$& .0005/0  & no &$\infty$& no & 3.3 & 17.  \\
1755   & $10^{-6}$& .000001/0  & no &$\infty$& no & 7.39& 28.  \\
2755   & $10^{-6}$& .000005/0  & no &$\infty$& no & 16.8 & 29.  \\
3755   & $10^{-6}$& .000005/0  & no &$\infty$& no & 33.7 & 28.  \\
\hline
\end{tabular}
~~\\
~~\\
{\bf dual-step-first}\\
~~\\
20 problems per test for $n \leq 155$; 
using SUN SPARC 1\\
\hrulefill \\
1 problem per test for $n \geq 655$; using SUN ULTRA 10; \\
\hrulefill \\
(Getting the extra accuracy is expensive.)
\end{tiny}
\end{flushleft}

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

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

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

D is a (squared) {\bf Euclidean distance matrix} (EDM):\\
$\bullet$ if 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.
\]
\hrulefill  \\
The smallest value of $r$ is called {\bf the embedding dimension} of
$D$.
($r$ is always $\leq n-1$)

\end{slide}
\begin{slide}{}
{\bf approximate EDMCP}:\\
~\\
{\bf Given}: $A$ symmetric; and $H$ symmetric  weight matrix:
\[ f(D) := {\| H \circ (A - D) \|}^2_F,   \]
\fbox{
\begin{minipage}{4in}
\[
(CDM_0) \qquad
 \begin{array}{ccc}
          \mu^* := & \min   &   f(D)  \\
                  & \mbox{ subject to } & D \in {\cal E}, 
  \end{array}
\]
\end{minipage}
}

~\\
where $\cal E$ denotes the cone of EDMs.


\end{slide}
\begin{slide}{}
{\bf DISTANCE GEOMETRY}\\
A {\em 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.

\end{slide}
\begin{slide}{}
Define {\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 two linear operators
\[ \begin{array}{rcl} \label{KK} 
\KK(B)& := &  \mbox{diag}(B)\,e^t + e \, \mbox{diag}(B)^t - 2B,
\end{array} \] 
\[ \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}{}

$\bullet$ 
hollow matrix $D$ is EDM {\bf iff} $B=\TT(D) \succeq 0$ 

$\bullet$ 
$D$ is EDM {\bf iff} $D=\KK(B)$ with $Be=0$ and $B \succeq 0$   

{\bf Then}:\\
embedding dimension $r$ = rank $B$\\
for $B=XX^t$, the rows of X generate the coordinates of the points  
$x^1,x^2,\ldots,x^n$ that generate $D$

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

{\bf Projection onto Minimal Face of $\p$}\\ 
(since interior of EDM cone is empty)
\[ \label{eq:Vmp}
J := V V^{\dagger}= I- \frac{e e^t}{n}, 
\quad (V, n \times (n-1), \mbox{ full col rank, } V^te=0)
\]
orthogonal projection onto $M$,
$V^{\dagger}$ is Moore-Penrose gen. inv.\\

\hrulefill 

\[ V \cdot V : {\cal S}_{n-1}  \rightarrow {\cal S}_{n}  
\quad \mbox{ (and } {\cal P}_{n-1}  \rightarrow {\cal P}_{n}  )
\]
\[ \begin{array}{rcl} \label{KV} 
\KK_V(X)& := &  \KK( V X V^t),
\end{array} \] 
\[ \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_{n-1})  & = &  \E_n , \\
\TT_V(\E_{n}) & = &\p_{n-1}.
\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)

\fbox{
\begin{minipage}{4in}
\[
(CDM) \qquad
 \begin{tabular}{ccc}
          $\mu^*$ := & $\min$   &   $f(X)$  \\
                  &  subject to     &  $X \succeq 0.$
  \end{tabular}
\]
\end{minipage}
}


\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 two equations hold.
\[ \begin{array}{cc}
  2\KK^*_V( H^{(2)} \circ \KK_V( \bar{X}-B))  - \bar{\Lambda} =0 &
                                           \mbox{(dual feas.)}  \\
\trace \bar{ \Lambda} \bar{X}=0 & \mbox{(compl. slack.)}
\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

(current approach with SOC can be used.)
\end{slide}
\begin{slide}{}

Direct approach - use:

equate $\Lambda = \mu X^{-1}$; multiply through by $X$

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

\hrulefill

(an OVERDETERMINED nonlinear system since $\Lambda X$ not
symmetric; use Gauss-Newton method)

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


\end{slide}
\begin{slide}{}
\begin{flushleft}
\begin{tiny}
 \begin{tabular}{|c|c|c|c|c|c|c|c|}
\hline
 dim &  toler  & $H$  dens.  & $rank(X)$ & {avg. iter.} & 
      \multicolumn{2}{c|} {total lss cpu-time} \\ \cline{6-7} 
 &  &   & & &  GN& RGN\\ 
\hline
  8   & $10^{-13}$& .8  & 2 &  25&.16 &.1   \\
  9   & $10^{-13}$& .8  & 2 &  23 & .24 &.13   \\
  10   & $10^{-13}$& .8  & 3 &  25  &.34  &.18  \\
  12   & $10^{-9}$& .5  & 3 &  17  &.73 &.32   \\
  15   & $10^{-9}$& .5  & 2 &  20  &2.13 &.79   \\
  18   & $10^{-9}$& .5  & 4 &  20  &6.15 & 1.9   \\
  20   & $10^{-9}$& .3  & 2 &  20  & 11.35 &3.3   \\
  24   & $10^{-9}$& .3  & 2 &  20  &34.45 & 8.4   \\
  30   & $10^{-9}$& .3  & 4 &  20  & 138. & 31.5   \\
  35   & $10^{-9}$& .2  & 3 &  19  & 373. & 77.  \\
  38   & $10^{-9}$& .2  & 3 &  19  & 634. & 127   \\
  40   & $10^{-8}$& .1  & 2 &  20  & 845.9 & 181.7   \\
  42   & $10^{-8}$& .1  & 4 &  18  & 1118.& 232.02   \\
\hline\hline
 dim &  toler  & $H$  dens.  & $rank(X)$ & {avg. iter.} & 
      \multicolumn{2}{c|} {per iter lss cpu-time} \\ \cline{6-7} 
 &  &   & & &  GN& RGN\\ 
  32   & $10^{-9}$& .5  & 3 &  29  &22.3  & -  \\
  42   & $10^{-9}$& .5  & 3 &  25  &100.3  & -  \\
\hline
\hline
\end{tabular}

~~\\
{\bf 1st set: Gauss-Newton and Restricted Gauss-Newton} - using SUN SPARC 2\\
{\bf 2nd set: Gauss-Newton} - using SUN ULTRA 10\\
(Very robust. Least squares solution is ``total'' expense per iteration.)
\end{tiny}
\end{flushleft}

\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.5in}
%\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}
\psfig{figure=fig11513.ps,width=3.1in}
\end{center}


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


\begin{center}
\psfig{figure=fig13513.ps,width=3.1in}
\end{center}
%\end{slide}
%\begin{slide}{}

%\begin{center}
%\psfig{figure=fig8513.ps,width=3.1in}
%\end{center}
%\end{slide}
%\begin{slide}{}


%\begin{center}
%\psfig{figure=fig9513.ps,width=3.1in}
%\end{center}



\end{slide}
\begin{slide}{}
Direct {\bf MATRIX} approach - use:


optimality conditions,
\[ \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} \]
substitute and solve:
\[ \begin{array}{llccl}
 \left( 2 \KK^*_V\left(H^{(2)} \circ \KK_V(X)\right) - C\right)X - \mu I =0
\end{array} \]

\hrulefill

an OVERDETERMINED nonlinear system again;\\
 use GN method with conjugate gradient (Krylov method);\\
never change to vector system!! Exploit sparsity directly.\\
Very Stable: high accuracy, low iteration count.


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


\begin{center}
{\em Larger} Models
\end{center}
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 \},\\
\end{array}
\]
Then
\beq  \label{eq:subsets}
  {\rm ri} \left(\FF \right) \subset
  \FF_0   \subset \FF \subset \overline{\FF_0}.
\eeq
\end{lem}

\hrulefill

up to closure:\\

 EDM = $ \overline{\left\{D \in \Sn:
      \diag(D)=0, ~ \alpha E - D \succeq 0, \mbox{ for some } \alpha \geq 0
                   \right\}}$

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

let: $E=ee^t$;
$f(D) := {\| H \circ (A - D) \|}^2_F$;\\
{\bf primal problem} is:
\[
({\rm CDM})
 \begin{array}{ccl}
          \mu^* := & \min   &   f(D)  \\
                  &  \mbox{subject to}   &  \diag(D)=0 \\
               & &  \alpha E-D \succeq 0
  \end{array}
\]
and {\bf dual problem (DCDM)} is (L is Lagrangian)
\[
\begin{array}{ccl}
   \nu^*:= 
 &\max &L=f(D) +\left<y,0-\diag(D)\right>- \tr \Lambda (\alpha E-D)\\
  &  \mbox{subject to} &  \nabla_D L =\nabla_D f(D)  -\Diag(y)+ \Lambda = 0\\
   &                   & \nabla_\alpha L =-\trace \Lambda E =  0\\
    &      &       \Lambda \succeq 0.
    \end{array}
\]
(Slater's holds for primal but fails for dual; both $E,\Lambda \succeq 0$.)
\end{slide}
\begin{slide}{}

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

\hrulefill

Again: solve for $\Delta P$ in terms of $\Delta \Lambda$
(or vice-versa). Exploit sparsity.


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


\end{slide}

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