\documentclass[pdf,blends,slideColor,colorBG]{prosper} \usepackage[latin1]{inputenc} \usepackage{pstricks,pst-node,pst-text,pst-3d} \usepackage{amsmath} \usepackage{epsfig} \usepackage{graphicx} % Definition of new colors \newrgbcolor{mag}{0.6 0 0.6} \newrgbcolor{dgreen}{0 0.5 0.5} \newcommand{\X}{{\cal X}} \newcommand{\diag}{{\rm diag\,}} \def\SDP{\mbox{\boldmath$SDP\,$}} \def\EDM{\mbox{\boldmath$EDM\,$}} \def\EDMC{\mbox{\boldmath$EDMC\,$}} \def\EDMCR{\mbox{\boldmath$EDMC-R\,$}} \def\EDMCD{\mbox{\boldmath$EDMC-D\,$}} \newcommand{\offDiag}{{\rm offDiag\,}} \newcommand{\Diag}{{\rm Diag\,}} \newcommand{\Ss}{{\mathcal S}} \newcommand{\Sn}{{\mathcal S}^n } \newcommand{\Snm}{{\mathcal S}^{n-1} } \newcommand{\hn}{{\mathcal H}^n } \newcommand{\D}{{\mathcal D_n} } \newcommand{\E}{{\mathcal E_n} } \newcommand{\Sd}{{\mathcal S}_d } \newcommand{\Sc}{{\mathcal S}_C } \newcommand{\Sh}{{\mathcal S}_H } \newcommand{\snn}{{\mathcal S}_{n-1} } \newcommand{\CC}{{\mathcal C} } \newcommand{\KK}{{\mathcal K} } \newcommand{\LL}{{\mathcal L} } \newcommand{\NN}{{\mathcal N} } \newcommand{\MM}{{\mathcal M} } \newcommand{\Mn}{{\MM^n} } \newcommand{\ZZ}{{\mathcal Z} } \newcommand{\YY}{{\mathcal Y} } \newcommand{\EE}{{\mathcal E} } \newcommand{\FF}{{\mathcal F} } \newcommand{\DD}{{\mathcal D} } \newcommand{\BB}{{\mathcal B} } \newcommand{\GG}{{\mathcal G} } \newcommand{\II}{{\mathcal I} } \newcommand{\RR}{{\mathcal R} } \newcommand{\PP}{{\mathcal P} } \newcommand{\TT}{{\mathcal T} } \newcommand{\UU}{{\mathcal U} } \newcommand{\A}{{\mathcal A} } \newcommand{\p}{{\mathcal P} } \newcommand{\n}{{\mathcal N} } \newcommand{\trace}{{\rm trace\,}} \newcommand{\relint}{{\rm relint\,}} \newcommand{\rank}{{\rm rank\,}} \newcommand{\cone}{{\rm cone\,}} \newcommand{\sspan}{{\rm span\,}} \newcommand{\tr}{{\rm trace\,}} \newcommand{\svec}{{\rm svec\,}} \newcommand{\sMat}{{\rm sMat\,}} \newcommand{\sblk}{{\rm sblk\,}} \newcommand{\sBlk}{{\rm sBlk\,}} \newcommand{\blk}{{\rm Blk\,}} \newcommand{\kvec}{{\rm vec\,}} \newcommand{\Mat}{{\rm Mat\,}} \newcommand{\bpr}{{\bf Proof.} \hspace{1 em}} \newcommand{\QED}{\hfill ~\rule[-1pt] {8pt}{8pt}\par\medskip ~~} \newcommand{\epr}{\QED} \newcommand{\ip}[2]{\left\langle #1, #2 \right\rangle} \title{ Anchored Graph Realization and Sensor Localization } %\subtitle{at: Dalhousie University, Faculty of Computer Science, May/06} \author{ {\red Nathan Krislock}, {\blue Veronica Piccialli}, {\red Jiawei Qian}, and \underline {\red Henry Wolkowicz}} \institution{ {\blue University of Rome} and %\blue University of Windsor and {\red University of Waterloo}} %\email{\blue ???? and {\red hwolkowicz@uwaterloo.ca}} \begin{document} \maketitle %---------------------------------------------------------------------- SLIDE - %\overlays{2}{ \begin{slide}{Outline} \tiny{ \begin{description} \blue \item %$\bullet$ Problem Formulation, \EDMC \item %$\bullet$ Matrix Reformulation, \EDMC \\ \quad - Semidefinite Programming connection \item %$\bullet$ SDP Relaxation of Hard Constraint $\bar Y =PP^T$ \item %$\bullet$ Facial Reduction - Reduced Problem Model \item %$\bullet$ Adjoints/Duality for \EDMCR \item %$\bullet$ Primal-Dual Bilinear Optimality Conditions (overdetermined) \item %$\bullet$ {\red \bf Robust Interior-Point algorithm}\\ \quad - Gauss-Newton Direction, crossover, exact p-d feasibility, preconditioning \item MATLAB demonstration \item Concluding Remarks \end{description} } \end{slide} \begin{slide}{Problem} \blue \begin{description} \blue \item $\bullet$ Ad hoc wireless sensor network \item $\bullet$ A few anchors (e.g. with GPS/bulky) have fixed, known locations \item $\bullet$ sensors within a given range have some known distance measurements (approximate) \item $\bullet$ {\red Problem}: Determine positions of all sensors \item $\bullet$ {\red Parameters}: Radio range, \# of anchors, noise level \item $\bullet$ Semidefinite Relaxations/Robust Algorithm \end{description} \end{slide} \begin{slide}{Problem Applications} \blue \begin{description} \blue \item $\bullet$ health, military, home \item $\bullet$ natural habitat monitoring, earthquake detection, weather/current monitoring \item $\bullet$ random deployment in inaccessible terrains or disaster relief operations \item $\bullet$ {\red Future ?}: bicycles (prevent theft); guns; ~~~~~~~ students/kids (prevent class absence :) ) \end{description} \end{slide} %\overlays{2}{ \begin{slide}{Problem Example - with Radio Range} \begin{figure}[htb] \epsfxsize=210pt \centerline{\epsfbox{plot4.eps}} \caption{Connected Graph} \end{figure} \end{slide} %\overlays{2}{ \begin{slide}{Problem Formulation} \begin{description} \blue \item $\bullet$ $\mag p^1, \ldots, p^n \in \Re^r$ \quad unknown (sensor) points\\ $\mag a^1, \ldots ,a^m \in \Re^r$ \quad known (anchor) points\\ $\mag r$ \quad embedding dimension (usually $\mag 2$ or $\mag 3$) \item $\bullet$ $\mag A^T := [a^1, a^2, \ldots ,a^m]$\quad $\mag X^T := [p^1, p^2, \ldots, p^n]$\\ \[ \mag P^T:= \left( p^1, p^2, \ldots, p^n, a^1, a^2, \ldots ,a^m \right) \] $\mag P= \begin{pmatrix} X \\ A \end{pmatrix}$ \quad rows are sensor/anchor points \end{description} \end{slide} \begin{slide}{Assumption (avoids some trivialities)} \begin{description} \blue \item $\bullet$ The number of sensors and anchors, and the embedding dimension satisfy \[ \mag n > m > r, ~ A^Te=0~ \mbox{\blue and } \mag A \mbox{ \blue is full rank}. \] \end{description} \end{slide} %} \begin{slide}{Definitions} \blue \begin{description} \item $\bullet$ \underline{\black index sets} of existing values of distances $\mag d_{ij}$ between pairs of sensors, $\mag \{p^i\}_1^n$:\\ \quad $\mag \NN_e$ distance values\\ \quad $\mag \NN_u$ upper bounds on distances \\ \quad $\mag \NN_l$ lower bounds on distances\\ Similarly, the index sets $\mag \left(\MM_e, \MM_u, \MM_l\right)$ are for pairs $\mag \{p^i\}_1^n$ (sensors) to/from $\mag \{a^k\}_1^m$ (anchors) \item $\bullet$ \underline{{\black partial}} EDM matrix $\mag E$ of \underline{\black squared} distances\\ $ \mag E_{ij}:= \left\{ \begin{array}{cl} d_{ij}^2 & \mbox{if }~~ ij \in \NN_e \cup \MM_e \\ 0 & \mbox{otherwise}. \end{array} \right. $ \end{description} \end{slide} \begin{slide}{Definitions} \blue Similarly, we define \begin{description} \item $\bullet$ the (partial) matrix of (squared distances) upper bounds\\ \quad $\mag U$, using $\mag ij \in \NN_u \cup \MM_u$ \item $\bullet$ and the (partial) matrix of (squared distances) lower bounds\\ \quad $\mag L$, using $\mag ij \in \NN_l \cup \MM_l$ \end{description} \end{slide} \begin{slide}{Weighted Least Squares Error} \blue \begin{description} \item In the case $\mag E_{ij}$ have errors:\\ Let $\mag W_p, W_a$ be weight matrices. We minimize the weighted least squares error. (\EDMC) \[ \mag \begin{array}{rcl} f_1(P) &:=& \displaystyle\sum_{(i,j) \in \mathcal{N}_e}(W_p)_{ij}(\|p^i-p^j\|^2 - E_{ij})^2 \\ && + \displaystyle\sum_{(i,k) \in \mathcal{M}_e}(W_a)_{ik}(\|p^i-a^k\|^2 - E_{ik})^2 \end{array} \] \end{description} \end{slide} \begin{slide}{HARD (nonconvex) Constrained LS} \blue \EDMC Problem: \[ \mag \begin{array}{ll} \mbox{\blue min } & f_1(P) \quad \mbox{\blue (weighted least squares)}\\ %\displaystyle\sum_{(i,j) \in %\mathcal{N}_e}(W_p)_{ij}(\|p^i-p^j\|^2 - E_{ij})^2 \\ % & + \displaystyle\sum_{(i,k) \in %\mathcal{M}_e}(W_a)_{ik}(\|p^i-a^k\|^2 - E_{ik})^2 \\ \mbox{\blue s.t.} &\mag \|p^i-p^j\|^2 \leq U_{ij} ~~ \forall (i,j) \in \mathcal{N}_u ~~ \left(n_u=\frac {|\mathcal{N}_u|}{2} \right)\\ & \|p^i-a^k\|^2 \leq U_{ik} ~~ \forall (i,k) \in \mathcal{M}_u ~~ \left(m_u=\frac {|\mathcal{M}_u|}{2} \right)\\ & \|p^i-p^j\|^2 \geq L_{ij} ~~ \forall (i,j) \in \mathcal{N}_l ~~ \left(n_l=\frac {|\mathcal{N}_l|}{2} \right)\\ & \|p^i-a^k\|^2 \geq L_{ik} ~~ \forall (i,k) \in \mathcal{M}_l ~~ \left(m_l=\frac {|\mathcal{M}_l|}{2}\right) \end{array} \] \end{slide} \begin{slide}{$\KK(\SDP)=\EDM$} \blue $\mag B=PP^T$ (\SDP). $\mag B_{ii}=(p^i)^Tp^i$; $\mag B_{ij}=(p^i)^Tp^j$\\ The squared distance \[ \mag \begin{array}{rcrclrcl} D_{ij} &=& \|p^i-p^j\|^2 && \mbox{\blue (\EDM)} \\&=& (p^i)^Tp^i &+& (p^j)^Tp^j &-& 2(p^i)^Tp^j \\&=& \updownarrow ~~~&& ~~~\updownarrow && \updownarrow \\&=& (\diag (B) e^T &+& e \diag(B)^T &-& 2B)_{ij} \\&=:& \left(\KK(B)\right)_{ij} \end{array} \] $\mag D=\KK(B)$ \quad change \EDM $\mag D$ $\mag \leftrightarrow$ \SDP $\mag B$ \end{slide} %} \begin{slide}{L\"owner Partial Order} \blue matrix inner-product \fbox{$\mag \left=\trace M^TN$} and Frobenius norm \fbox{$\mag \|M\|^2 = \trace M^TM$}.\\ In $\mag \Sn$, $\mag n \times n$ symmetric matrices: \[ \mag \begin{array}{c} B \succeq 0 \quad \mbox{\blue (is positive semidefinite)} \\ \iff \\ \exists P \mbox{ with } B=PP^T,~\rank (B)=\rank (P) \end{array} \] the positive semidefinite (L\"owner) partial order is: \[ \mag A \succeq B ~(A \succ B) \mbox{ if } A- B \succeq 0~(A- B\succ 0) \] \end{slide} \begin{slide}{Matrix Reformulation of \EDMC} \blue Let $\mag \bar Y:= PP^T = \begin{pmatrix} XX^T & XA^T \\ AX^T & AA^T \end{pmatrix}$ \\ We get the equivalent \EDMC \[ \mag \begin{array}{crcl} {\blue \min} & f_2(\bar Y) := \frac{1}{2}{\| W \circ (\KK(\bar Y) - E) \|}_F^2 \\ \mbox{\blue subject to } & g_u(\bar Y) :=H_u \circ (\KK(\bar Y) - U) &\leq& 0 \\ & g_l(\bar Y) :=H_l \circ (\KK(\bar Y) - L) & \geq& 0\\ & \mbox{\blue hard constraint } \fbox{$\bar Y-PP^T=0$} \end{array} \] \end{slide} \begin{slide}{SDP Relaxation of Hard Constraint} \blue \[ \mag \begin{array}{lcl} \bar Y=PP^T=\begin{pmatrix} XX^T & XA^T \\ AX^T & \fbox{$AA^T$} \end{pmatrix} \quad \mbox{holds} \\ \qquad \qquad \iff \\ \qquad \bar Y_{11}=XX^T \mbox{ and } \bar Y_{21} = AX^T, \fbox{$\bar Y_{22} = AA^T$}. \end{array} \] Relax $\mag \bar Y=PP^T$ to (L\"owner partial order) \[ \mag \fbox{$\bar Y_{22}=AA^T$}\quad PP^T-\bar Y \preceq 0 \quad \mbox{ \blue quadr convex constr} \] {\red (But .... why this relaxation?)} \end{slide} \begin{slide}{Convex wrt L\"owner Partial Order} \blue The constraint $ \mag g(P,Y)=PP^T -Y \preceq 0$ is $\mag \succeq$-convex, since each function \[ \mag \phi_Q(P,Y)=\trace Qg(P,Y)\quad \mbox{is convex } \forall Q\succeq 0. \] Note \[ \mag \begin{array}{rcl} \trace QPP^T &=& \trace QPIP^T \\&=& \kvec(P)^T \left( I \otimes Q \right) \kvec(P) \end{array} \] Hessian is $\mag I \otimes Q \succeq 0$;\\ and the cone {\mag \SDP} is self-polar. \end{slide} \begin{slide}{Linearization of SDP Relaxation} \blue $ \mag \begin{array}{lcl} PP^T-\bar Y \preceq 0, \qquad P= \begin{pmatrix} X \\ A \end{pmatrix}, \fbox{$\bar Y_{22}=AA^T$} \\ \qquad \qquad \iff \mbox{\blue (by Schur complement)} \\ Z = \begin{pmatrix} I & P^T \\ P & \bar Y \end{pmatrix} \succeq 0, \quad P= \begin{pmatrix} X \\ A \end{pmatrix}, \fbox{$\bar Y_{22}=AA^T$} \\ \qquad \qquad \iff \mbox{ \blue (ignore } \bar \cdot {\blue )} \\ Z = \begin{pmatrix} I & X^T &A^T \\ X & Y & Y_{21}^T \\ A & Y_{21}& \fbox{$AA^T$} \end{pmatrix} \succeq 0, \quad \left(\begin{array}{c} \mbox{\blue NOT! } \succ 0 \\ \Rightarrow Y_{21} = AX^T \end{array}\right) \end{array} $ \end{slide} \begin{slide}{Facial Reduction} \blue \[ \mag Z_s:=\begin{pmatrix}I & X^T \\ X & Y\end{pmatrix} \qquad \begin{array}{lcl} \mbox{ \blue (NE $2 \times 2$ block)}\\ \mbox{ \blue (Lin.Tr. but {\red \underline{NOT}} onto)} \end{array} \] {\bf THEOREM:} \[ \mag \begin{array}{lcl} Z = \begin{pmatrix} I & X^T &A^T \\ X & Y & Y_{21}^T \\ A & Y_{21}& \fbox{$AA^T$} \end{pmatrix} \succeq 0 \\ \qquad \qquad \iff \\ Z_s \succeq 0 \mbox{ and } Y_{21} = AX^T \end{array} \] \end{slide} \begin{slide}{Facial Reduction - Proof Outline} \blue (compact) singular value decomposition\\ $ \mag \fbox{$A = U \Sigma V^T$}~~ U {m\times r}, V r\times r$\\ \[ \mag Z=Z_1 := \begin{pmatrix} I & X^T & V\Sigma U^T \cr X & Y & Y_{21}^T\cr U \Sigma V^T & Y_{21} & U \Sigma^2 U^T\end{pmatrix} \succeq 0 \] choose $\mag \bar U$ so that $\mag \begin{pmatrix}U&\bar U\end{pmatrix}$ is orthogonal; \end{slide} \begin{slide}{Facial Reduction - Proof Outline cont...} \blue Nonsingular congruence (apply Sylvester Lemma on inertia) \[ \mag \begin{array}{lll} 0\preceq Z_2:=T^TZT=\\ = \begin{pmatrix}V^T & 0 & 0 \\ 0&I&0 \\ 0& 0 & \begin{pmatrix}U&\bar U\end{pmatrix}^T \end{pmatrix} Z \begin{pmatrix}V & 0 & 0 \\ 0&I&0 \\ 0& 0 & \begin{pmatrix}U&\bar U \end{pmatrix} \end{pmatrix} \end{array} \] \end{slide} \begin{slide}{Facial Reduction - Congruence cont...} \blue \[ \mag = \begin{pmatrix} I & V^TX^T & \begin{pmatrix} \Sigma & 0\end{pmatrix} \\ \vspace{.05in} XV & Y & \begin{pmatrix}Y_{21}^TU &Y_{21}^T \bar U\end{pmatrix}\\ \begin{pmatrix} \Sigma \cr 0\end{pmatrix} & \begin{pmatrix}U^TY_{21}\\ \bar U^TY_{21}\end{pmatrix} & \begin{pmatrix} \Sigma^2 & 0 \\ 0 & 0 \end{pmatrix} \end{pmatrix} \perp \begin{pmatrix} 0 & 0 \\ 0 & \fbox{\tiny{$I$}} \end{pmatrix} \] \[ \mag \Rightarrow Z \perp \left[T \begin{pmatrix} 0 & 0 \\ 0 & \fbox{\tiny{$I$}} \end{pmatrix} T^T \right] = \begin{pmatrix} 0 & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 0& \fbox{$\bar U \bar U^T$} \end{pmatrix} :=Q \] \end{slide} \begin{slide}{Minimal and Conjugate Faces} \blue Conjugate face to feasible set $\mag \FF_Z$ is \[ \mag \SDP \cap \left\{ \begin{pmatrix} 0 & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 0& \bar U \bar U^T \end{pmatrix} \right\} ^\perp \] Minimal face of \SDP containing $\mag \FF_Z=\cone \FF_Z$ is \[ \mag \begin{pmatrix} I & 0 & 0 \\ 0 & I & 0 \\ 0 & 0& U \end{pmatrix} \Ss^{2r+n}_+ \begin{pmatrix} I & 0 & 0 \\ 0 & I & 0 \\ 0 & 0& U \end{pmatrix}^T \] \end{slide} \begin{slide}{Minimal Face} \blue each given feasible $ \mag Z = \begin{pmatrix} I & X^T &A^T \cr X & Y & Y_{21}^T \cr A & Y_{21}& AA^T \end{pmatrix} \succeq 0, $ can be expressed as (using $\mag A=U\Sigma V^T$) \[ \mag =\begin{pmatrix} I & 0 & 0 \cr 0 & I & 0 \cr 0 & 0 & U \end{pmatrix} \begin{pmatrix} I & X^T &V\Sigma \cr X & Y & X V\Sigma \cr \Sigma V^T & \Sigma V^T X^T & \Sigma^2 \end{pmatrix} \begin{pmatrix} I & 0 & 0 \cr 0 & I & 0 \cr 0 & 0 & U \end{pmatrix}^T \] \end{slide} \begin{slide}{Matrix $\leftrightarrow$ Vector Notation I} \blue vector \fbox{$\mag v=\kvec V$} is matrix $\mag V$ taken columnwise\\ \fbox{ $ \mag \sblk_{21} \begin{pmatrix} 0 & X^T \\ X & 0 \end{pmatrix}= \sqrt{2} X $} pulls out the $\mag 21$ block - the $\mag \sqrt 2$ is for isometry in Frobenius norm \[ \mag \begin{array}{c} x:= \kvec\left( \sblk_{21} \begin{pmatrix} 0 & X^T \\ X & 0 \end{pmatrix}\right)= \sqrt{2} \kvec(X)\\ \fbox{$ y:=\svec(Y)$} \quad (Y=Y^T, \mbox{ \blue isometry}) \end{array} \] \end{slide} \begin{slide}{Matrix $\leftrightarrow$ Vector Notation II} \blue (adjoints: $\mag \sblk_{21}^*(X) =$) $\mag \sBlk_{21}(X)= \frac 1{\sqrt 2}\begin{pmatrix} 0 & X^T \\ X & 0 \end{pmatrix}$\\ $\mag \svec^{-1} (\cdot) =\svec^* (\cdot) = \sMat (\cdot)$ \[ \mag \begin{array}{rcl} {\ZZ}^x_s(x):=\sBlk_{21}(\Mat(x)), & {\ZZ}^y_s(y):=\sBlk_2(\sMat(y))\\ {\ZZ}_s(x,y):=\ZZ^x_s(x)+\ZZ^y_s(y), & Z_s := \sBlk_1(I)+{\ZZ}_s(x,y) \\ \end{array} \] $ \mbox{\blue to build } \quad \red \begin{array}{lcl} Z_s = \begin{pmatrix} I & X^T \\ X & Y \end{pmatrix} \in \Ss^{r+n} \end{array} $ \end{slide} \begin{slide}{Matrix $\leftrightarrow$ Vector Notation III} \blue \[ \mag \begin{array}{rcl} \YY^x(x)=\sBlk_{21}(A\Mat(x)^T),~ \YY^y(y)=\sBlk_1(\sMat(y))\\ \YY(x,y)= \YY^x(x)+ \YY^y(y),~ \fbox{${\red \bar Y=\sBlk_2(AA^T)+\YY(x,y)}$} \end{array} \] \[ \mag \begin{array}{rcl} \bar E:= W \circ \left[ E- \KK(\sBlk_2(AA^T))\right]\\ \bar U:= H_u \circ \left[\KK(\sBlk_2(AA^T)) - U\right]\\ \bar L:= H_l\circ \left[L-\KK(\sBlk_2(AA^T))\right] \end{array} \] The unknown matrix $\mag \bar Y$ is equal to $\mag \YY(x,y)$ (with additional constant $\mag 2,2$ block), i.e. unknowns are the vectors $\mag x,y$. \end{slide} \begin{slide}{Equivalent Reduced Problem Model} \blue \mbox{(\EDMC{\boldmath$-R\,$})} \[ \mag \begin{array}{crcl} \min & f_3(x,y) := \frac{1}{2}{\| W \circ (\KK(\YY(x,y))) - \bar E \|}_F^2 \\ \mbox{s.t.} & g_u(x,y):=H_u \circ \KK(\YY(x,y)) - \bar U &\leq& 0 \\ & g_l(x,y):=\bar L -H_l \circ \KK(\YY(x,y))& \leq& 0 \\ & \sBlk_1(I)+{\ZZ}_s(x,y)&\succeq& 0 \end{array} \] (objective is $\mag \ell_2$ rather than $\mag \ell_1$ in the literature, e.g. H. Jin(05), A. So, Y. Ye(05), P. Biswas, T. Liang, K. Toh, T. Wang, Y. Ye(06).) \end{slide} \begin{slide}{Problems with Relaxation} \blue \begin{enumerate} \item $ \mag \{(\bar Y, P): \bar Y= PP^T \} \subset \{(\bar Y, P): \bar PP^T- \bar Y \preceq 0 \} $ {\red (But, is Lagrangian relaxation stronger?)} \item linearization (using Schur complement) results in a constraint that is {\em NOT} onto, i.e.\\ {\red two relaxations {\em NOT} numerically equivalent} \item Least squares problem is (usually) {\red underdetermined}. \end{enumerate} \end{slide} \begin{slide}{Lagrangian of \EDMCR} \blue \[ \mag \begin{array}{lcl} L(x,y,\Lambda_u,\Lambda_l,\Lambda) =\\ \quad \frac{1}{2}{\| W \circ \KK(\YY(x,y) - \bar E \|}_F^2 \\ \qquad +\ip{\Lambda_u}{H_u \circ \KK(\YY(x,y))-\bar U} \\ \qquad\quad + \ip{\Lambda_l}{\bar L -H_l \circ \KK(\YY(x,y))} \\ \qquad\qquad - \ip{\Lambda}{\sBlk_1(I)+{\ZZ}_s(x,y)}, \end{array} \] where $\mag 0\leq \Lambda_u, 0\leq \Lambda_l \in \Ss^{m+n},$~~ $\mag 0\preceq \Lambda \in \Ss^{m+n}$ \[ \mag \Lambda =\begin{pmatrix}\Lambda_1 & \Lambda_{21}^T\\ \Lambda_{21} & \Lambda_{2}\end{pmatrix}, \qquad \ip{A}{B}=\trace A^TB. \] \end{slide} \begin{slide}{Matrix $\leftrightarrow$ Vector Dual Variable Notation} \blue \[ \mag \begin{array}{c} \lambda_u:=\svec(\Lambda_u), \quad \lambda_l:=\svec(\Lambda_l), \\ h_u:=\svec(H_u), \quad h_l:=\svec(H_l),\\ \lambda:=\svec(\Lambda), \quad \lambda_1:=\svec(\Lambda_1), \\ \lambda_2:=\svec(\Lambda_2), \quad \lambda_{21}:=\kvec \sblk_{21}(\Lambda). \end{array} \] \end{slide} \begin{slide}{Adjoints} \blue To differentiate the Lagrangian, we need the adjoints of the various linear transformations, e.g. part of $\KK$: \[ \mag \begin{array}{cclrcl} \DD_e(B) &=& \diag (B)\,e^T + e \, \diag (B)^T \\ \DD^*_e(D)&=& 2 \Diag(De)\\ \ip{\DD_e(B)}{D} &=& \trace (\diag(B) e^T D + e \diag(B)^T D) \\&=& \trace ( De (\diag B )^T + De (\diag B )^T) \\&=& 2\trace \left(\diag B \right)^T(De) \\&=& \ip{B}{\DD^*_e(D)}, \forall D,B \end{array} \] \end{slide} \begin{slide}{\underline{Primal}-Dual Optimal. Conditions 1} \blue {\bf THEOREM:} The primal-dual variables $\mag x,y,\Lambda,\lambda_u,\lambda_l$ are optimal for \EDMCR if and only if: \begin{description} \item[1.] \underline{Primal Feasibility}:\\ The slack variables satisfy $ \mag \begin{array}{lcl} S_u = \bar U - H_u \circ \left( \KK\left(\YY(x,y)\right)\right),~ s_u=\svec S_u \geq 0 \\ S_l = H_l \circ \left(\KK\left(\YY(x,y)\right)\right) -\bar L, ~~~ s_l=\svec S_l \geq 0 \end{array} $ and\\ $ \mag \begin{array}{rcl} \mag Z_s &=& \sBlk_1(I)+\sBlk_2\sMat (y) +\sBlk_{21}\Mat(x) \\& \succeq &0 \end{array} $ \end{description} \end{slide} \begin{slide}{Primal-\underline{Dual} Optimal. Conditions 2a} \blue \begin{description} \item[2a.] \underline{Dual Feasibility}:\\ The stationarity equations ($\mag \Rightarrow$ exact p-d feas.) $ \mag \begin{array}{rcl} (\ZZ_s^x)^*(\Lambda) &=& \lambda_{21} \quad \mbox{\blue (eliminated)} \\&=& \left[W\circ(\KK \YY^x)\right]^* \left( W \circ \KK(\YY(x,y)) - \bar E \right) \\&& \quad + \left[H_u\circ(\KK \YY^x)\right]^* (\Lambda_u) \\&& \qquad -\left[H_l\circ(\KK \YY^x)\right]^* (\Lambda_l) \end{array} $ $ \mag \begin{array}{rcl} (\ZZ_s^y)^*(\Lambda) &=& \lambda_{2} \quad \mbox{\blue (eliminated)} \\&=& \left[W\circ(\KK \YY^y)\right]^* \left( W \circ \KK(\YY(x,y)) - \bar E \right) \\&& \quad + \left[H_u\circ(\KK \YY^y)\right]^* (\Lambda_u) \\&& \qquad - \left[H_l\circ(\KK \YY^y)\right]^* (\Lambda_l) \end{array} $ \end{description} \end{slide} \begin{slide}{Primal-\underline{Dual} Optimal. Conditions 2b} \blue \begin{description} \item[2b.] \underline{Dual Feasibility}:\\ Nonnegativity $ \mag \begin{array}{rcl} \Lambda &=& \sBlk_1\sMat(\lambda_1)+\sBlk_2\sMat(\lambda_2) \\&& \quad +\sBlk_{21}\Mat(\lambda_{21}) \succeq 0; \end{array} $ \[ \mag \lambda_u\geq 0;\lambda_l\geq 0 \] \[ \mag \Lambda = \Lambda(\lambda_1,x,y,\lambda_u,\lambda_l) \qquad \mbox{\blue (from stationarity)} \] \end{description} \end{slide} \begin{slide}{Primal-Dual Optimal. Conditions 3 (\underline{C.S.})} \blue \begin{description} \item[3.] \underline{Complementary Slackness}:\\ \[ \mag \begin{array}{rcl} \lambda_u \circ s_u & = & 0 \\ \lambda_l \circ s_l & = & 0 \\ \Lambda Z_s & = & 0 \qquad \mbox{\blue (equivalently } \trace \Lambda Z_s = 0 \mbox{\blue )} \end{array} \] \end{description} \end{slide} \begin{slide}{Perturbed Compl. Slack. Conditions} \blue \[ \mag \begin{array}{rcl} F_\mu(x,y,\lambda_u,\lambda_l,\lambda_1):= \begin{pmatrix} \lambda_u \circ s_u - \mu_u e\\ \lambda_l \circ s_l - \mu_l e \\ \fbox{\mbox{ $\Lambda Z_s - \mu_c I $}} \end{pmatrix} = 0, \end{array} \] where $\mag s_u=s_u(x,y)$, $\mag s_l=s_l(x,y)$, $\mag \Lambda=\Lambda(\lambda_1,x,y,\lambda_u,\lambda_l)$, $\mag Z_s=Z_s(x,y)$\\ an \fbox{overdetermined} bilinear system with $\mag (m_u+n_u)+ (m_l+n_l)+(n+r)^2 \mbox{ equations}$ $\mag nr +t(n) + (m_u+n_u)+ (m_l+n_l)+t(r) \mbox{ variables}. $ \end{slide} \begin{slide}{Gauss-Newton Search Direction} \blue \[ \mag \Delta s := \left(\begin{array}{c} \Delta x \\\Delta y \\ \Delta \lambda_u \\ \Delta \lambda_l \\ \Delta \lambda_1 \end{array}\right) \] \underline{overdetermined} linearized system is: \[ \mag F^\prime_\mu(\Delta s) \cong F^\prime_\mu(x,y,\lambda_u,\lambda_l,\lambda_1) (\Delta s) =-F_\mu(x,y,\lambda_u,\lambda_l,\lambda_1) \] \end{slide} \begin{slide}{Notation - Compos. of Lin. Tr.} \blue \[ \mag \begin{array}{rcl} \KK^x_H (x)&:=& H\circ (\KK (\YY^x(x))),\\ \KK^y_H (y)&:=& H\circ (\KK (\YY^y(y))),\\ \KK_H (x,y)&:=& H\circ (\KK (\YY(x,y))). \end{array} \] \end{slide} \begin{slide}{GN: Three blocks of Equations} \blue 1. $ \mag \lambda_u \circ \svec \KK_{H_u} (\Delta x,\Delta y) + s_u \circ \Delta \lambda_u = \mu_u e - \lambda_u \circ s_u $ 2. $ \mag \lambda_l \circ \svec \KK_{H_l} (\Delta x,\Delta y) + s_l \circ \Delta \lambda_l = \mu_l e - \lambda_l \circ s_l $ 3. $ \mag \begin{array}{lcl} \Lambda \ZZ_s(\Delta x, \Delta y)+ \left[ \sBlk_1\left(\sMat(\Delta\lambda_1)\right)\right. \\ ~~+\left.\sBlk_2\left( \sMat\left\{(\KK_W^y)^*\KK_W(\Delta x,\Delta y)+\right.\right.\right. \\ ~~~~\left.\left.\left. (\KK^y_{H_u})^*\left(\sMat(\Delta\lambda_u)\right) -(\KK^y_{H_l})^*\left(\sMat(\Delta\lambda_l)\right)\right\}\right)\right. \\ ~~~~~~ \left.+\sBlk_{21}\left(\Mat\left\{(\KK_W^x)^*\KK_W(\Delta x,\Delta y) \right.\right.\right. \\ ~~~~~~~~ \left.\left.\left.+ (\KK^x_{H_u})^*\left(\sMat(\Delta\lambda_u)\right)-(\KK^x_{H_l})^*\left(\sMat(\Delta\lambda_l)\right)\right\}\right)\right]Z_s \\= \mu_cI-\Lambda Z_s \end{array} $ \end{slide} \begin{slide}{Initial Str. Feas. Start Heuristic} \blue If the graph is connected, we can use the stationarity equations and get a strictly feasible primal-dual starting point and {\em \red maintain exact numerical primal-dual feasibility} throughout the iterations. \end{slide} \begin{slide}{Diagonal Preconditioning} \blue Given $\mag A\in\MM^{m\times n}$, $\mag m\ge n$ full rank matrix; and using condition number of $\mag K \succ 0$: $\mag \omega(K)=\frac {\trace(K)/n}{\det(K)^{1/n}}$, the \underline{\red optimal diagonal scaling} \[ \mag \min_{D \succ 0}{\omega\left((AD)^T(AD)\right)}, \quad D^*=\Diag(1/\|A_{:,i}\|) \] \small{(cite Dennis-W.)} Therefore, need to evaluate columns of $\mag F_\mu^\prime(\cdot)$ (can be done explicitly/efficiently) ~~\\ ---------------------------------\\ (Partial block Cholesky precondioning) \end{slide} \begin{slide}{dens: W .75,L .8;\\ n 15, m 5, r 2} \blue \tiny{ \begin{table}[htbp] \centering \begin{tabular}{|c|c|c|c|c|c|} \hline nf & optvalue & relaxation & cond.number & sv($\ZZ_s$) & sv($F^\prime_\mu$) \\ \hline 0.0000e+000 & 3.9909e-009 & 1.1248e-005 & 3.8547e+006 & 15 & 19 \\ \hline 5.0000e-002 & 7.5156e-004 & 4.4637e-002 & 1.0244e+011 & 6 & 27 \\ \hline 1.0000e-001 & 3.7103e-003 & 1.1286e-001 & 1.9989e+010 & 5 & 25 \\ \hline 1.5000e-001 & 6.2623e-003 & 1.3125e-001 & 1.0065e+010 & 6 & 14 \\ \hline 2.0000e-001 & 1.3735e-002 & 1.3073e-001 & 6.8833e+009 & 7 & 12 \\ \hline 2.5000e-001 & 2.3426e-002 & 2.4828e-001 & 2.4823e+010 & 8 & 6 \\ \hline 3.0000e-001 & 6.0509e-002 & 2.3677e-001 & 3.4795e+010 & 7 & 7 \\ \hline 3.5000e-001 & 5.5367e-002 & 3.7260e-001 & 2.3340e+008 & 6 & 4 \\ \hline 4.0000e-001 & 7.6703e-002 & 3.6343e-001 & 8.9745e+010 & 8 & 3 \\ \hline 4.5000e-001 & 1.2493e-001 & 6.9625e-001 & 3.2590e+010 & 6 & 9 \\ \hline 5.0000e-001 & 1.3913e-001 & 3.9052e-001 & 2.2870e+005 & 8 & 0 \\ \hline 5.5000e-001 & 8.8552e-002 & 3.8742e-001 & 5.8879e+007 & 8 & 2 \\ \hline 6.0000e-001 & 4.2425e-001 & 4.1399e-001 & 4.9251e+012 & 8 & 4 \\ \hline \end{tabular} \end{table} } \end{slide} \begin{slide}{dens: W .75,L .8;\\ n 15, m 5, r 2} \blue \tiny{ \begin{table}[htbp] \centering \begin{tabular}{|c|c|c|c|c|c|} \hline nf & optvalue & relaxation & cond.number & sv($\ZZ_s$) & sv($F^\prime_\mu$) \\ \hline 0.0000e+000 & 3.9909e-009 & 1.1248e-005 & 3.8547e+006 & 15 & 19 \\ \hline 5.0000e-002 & 7.5156e-004 & 4.4637e-002 & 1.0244e+011 & 6 & 27 \\ \hline 5.5000e-001 & 8.8552e-002 & 3.8742e-001 & 5.8879e+007 & 8 & 2 \\ \hline 6.0000e-001 & 4.2425e-001 & 4.1399e-001 & 4.9251e+012 & 8 & 4 \\ \hline 6.5000e-001 & 2.0414e-001 & 6.6054e-001 & 2.4221e+010 & 7 & 4 \\ \hline 7.0000e-001 & 1.2028e-001 & 3.4328e-001 & 1.9402e+010 & 7 & 6 \\ \hline 7.5000e-001 & 2.6590e-001 & 7.9316e-001 & 1.3643e+011 & 7 & 4 \\ \hline 8.0000e-001 & 4.7155e-001 & 3.7822e-001 & 6.6910e+009 & 8 & 2 \\ \hline 8.5000e-001 & 1.8951e-001 & 5.8652e-001 & 1.4185e+011 & 6 & 7 \\ \hline 9.0000e-001 & 2.1741e-001 & 9.8757e-001 & 2.9077e+005 & 8 & 0 \\ \hline 9.5000e-001 & 4.4698e-001 & 4.6648e-001 & 2.7013e+006 & 9 & 2 \\ \hline \end{tabular} \caption{Robust Algorithm for Ill-posed Problem} \end{table} } \end{slide} \end{document}