%\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, ~~~ \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- \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}