%======================= main.tex ===========================================
\documentstyle{slides}
\newtheorem{exam}{Example}
\newtheorem{prop}{Proposition}
\newtheorem{lem}{Lemma}
\newtheorem{thm}{Theorem}
\newtheorem{cor}{Corollary}
\newcommand{\Diag}{{\rm Diag\,}}
\newcommand{\diag}{{\rm diag\,}}
\newcommand{\tr}{{\rm trace\,}}
\newcommand{\trace}{{\rm trace\,}}
\newcommand{\rank}{{\rm rank\,}}
\newcommand{\p}{{\cal P}}
\newcommand{\hn}{{\cal H}_n }
\newcommand{\g}{{\cal G}}
\newcommand{\kvec}{{\rm vec\,}}
\newcommand{\trian}{{\rm trian\,}}
\newcommand{\Trian}{{\rm Trian\,}}
\newcommand{\BoDiag}{{\rm B^0Diag\,}}
\newcommand{\OoDiag}{{\rm O^0Diag\,}}
\newcommand{\arrow}{{\rm arrow\,}}
\newcommand{\Arrow}{{\rm Arrow\,}}
\newcommand{\bodiag}{{\rm b^0diag\,}}
\newcommand{\oodiag}{{\rm o^0diag\,}}
\newcommand{\ck}{{\cal C}_k}
\newcommand{\dk}{{\cal D}_k}
\newcommand{\uu}{{\cal U}}
\newcommand{\uk}{{\cal U}_k}
\newcommand{\vk}{{\cal V}_k}
\newcommand{\wk}{{\cal W}_k}
\newcommand{\wm}{{\cal W}_m}
\newcommand{\w}{{\cal W}}
\newcommand{\wks}{{\cal W}^s_k}
\newcommand{\wms}{{\cal W}^s_m}
\newcommand{\zk}{{\cal Z}_k}
\newcommand{\zks}{{\cal Z}^s_k}
\newcommand{\z}{{\cal Z}}
\newcommand{\n}{{\cal N}}
\newcommand{\ra}{{\cal R}}
\newcommand{\q}{{\cal Q}}
\newcommand{\s}{{\cal S}_n}
\newcommand{\m}{{\cal M}_{n}}
\newcommand{\req}[1]{(\ref{#1})}
\newcommand{\adj}{{\rm adj\,}}
\newcommand{\relint}{{\rm relint\,}}
\newcommand{\epr}{\\ \hspace*{4.5in}  $\Box$}
\pagestyle{plain}
\begin{document}
\blackandwhite{example}
%======================= example.tex
%  the file example.tex must exist - it is empty though
%======================= 
%======================= 
\begin{slide}{}
\begin{center}
{\bf AN INTERIOR-POINT METHOD FOR
APPROXIMATE POSITIVE SEMIDEFINITE COMPLETIONS}
\end{center}
 

~~\\
~~\\
~~\\
~~\\
~~\\
~~\\
\begin{center}
Henry Wolkowicz\\
University of Waterloo
\end{center}

\end{slide}
\begin{slide}{}
Suppose that 
\[ A=A^* \succeq 0,\]
i.e. $A$ is Hermitian positive semidefinite.

Suppose that the diagonal elements $a_{ii} >0, ~\forall i,$
i.e. $\diag(A) > 0.$ Consider

\[
\max \left\{ \det (B) : B \succeq 0, ~\diag(B)=\diag(A) \right\}.
\]

Then (Hadamard's Inequality) the maximum occurs when $B^{-1},$ and
so $B,$ is diagonal.

\end{slide}
\begin{slide}{}
Proof? Optimum is interior! Differentiate log-det !! 
\begin{eqnarray*}
  0&=&\nabla \left( \log \det (B) + \sum_i \lambda_i (B_{ii}-A_{ii}) E_{ii} 
  \right)\\
  &=& B^{-1} +\sum_i \lambda_i E_{ii}
\end{eqnarray*}
I.e., $B^{-1}$ must be diagonal. \epr

\end{slide}
\begin{slide}{}
Suppose that $2k+1$ bands are specified in $A$, i.e. $a_{ij}$ is fixed
for $|i-j| \leq k.$ And, suppose that any principal $k+1 \times k+1$
submatrix contained within the $2k+1$ bands is positive definite. Then:
\begin{thm} (Dym and Gohberg, 1981)
\begin{enumerate}
\item
If 
\[{\cal D}_k = \left\{ B : B \succeq 0, ~b_{ij}=a_{ij}, \forall |i-j|
                \leq k \right\},
\]
 then ${\cal D}_k \neq \emptyset.$
\item
$\max \left\{ \det (B) :B \in {\cal D}_k \right\}$ occurs at the unique
matrix $B \in {\cal D}_k$ having the property that for all $|i-j| \geq
k+1$, the $(i,j)$-entry of $B^{-1}$ equals 0.
\end{enumerate}
\end{thm}

\end{slide}
\begin{slide}{}
Suppose that we are given the {\em partial Hermitian} matrix 
\[A=A^*,\] 
i.e.  the components $A_{ij}, ij \in {\cal E}$ are specified (fixed), 
while the others are unspecified (free). 

Denoted 
\[A=A({\cal G}),\]
for the undirected graph ${\cal G} = ({\cal N,E}).$

The {\em positive semidefinite completion problem} consists in finding
components $A_{ij}, ij \notin {\cal E},$ such that the resulting matrix
$A \succeq 0,$ is positive semidefinite.
\end{slide}
\begin{slide}{}
A graph is {\em chordal} if there are no minimal cycles of length $\geq
4.$

A graph $\cal G$ is {\em  completable} if and only if any
${\cal G}$-partial positive definite matrix has a positive definite completion.

\begin{thm} (GJSW, 1984)
$\g$ is completable if and only if $\g$ is chordal.
\end{thm}
\begin{thm} (GJSW, 1984)
Suppose that $\diag(A)$ is fixed and
$A(\g)$ has a positive definite completion.
Then there is a unique such completion, $B$, with maximum
determinant; and it is characterized by $B^{-1}$ having 0 components in
positions corresponding to all $kl \notin {\cal E}.$
\end{thm}
\end{slide}
\begin{slide}{}
Let $H=H^t \geq 0$ be a  symmetric
{\em matrix of weights} with nonzero diagonal elements
and let $A=A^*$ be
another given Hermitian matrix.

Let
\[ f(P):=||H \circ (A-P) ||_F^2, \]
(Hadamard product, Frobenius norm)

{\em Best Approximate Completion Problem}
\[
(AC)
\begin{array}{ccc}
       \mu^*:=&\min &f(P) \\
 &  \mbox{~subject to~} & KP=b\\
  &  &  P \succeq 0,
    \end{array}
\]
\end{slide}
\begin{slide}{}
{\bf DUALITY and OPTIMALITY}\\
(Unconstrained Case)

characterization of an optimal solution
$\bar{P}$ of AC:
\[
\nabla f(\bar{P}) \in ({\cal P} - \bar{P})^+,
\]
where ${\cal P}$ denotes the {\em cone of positive semidefinite
matrices} and
\[  S^+ = \{P: \tr QP \geq 0,~ \forall Q \in S\}
\]
{\em polar cone}.

\begin{thm}
The matrix $\bar{P} \succeq 0$ solves AC if and only if
\[
\tr (H^{(2)} \circ (\bar{P}-A))(P-\bar{P}) \geq 0, ~ \forall P \succeq
0,
\]
where $H^{(2)}=H \circ H$ is the Hadamard squared term.
\end{thm}
\end{slide}
\begin{slide}{}
\begin{cor}
If $H=E,$ the matrix of ones, then the (unique)
optimal solution of AC is $\bar{P} = A_{\succ} ,$ where $A_{\succ} $ is
the positive part of $A$.
\end{cor}

\begin{cor}
If $H \succ 0$, then the (unique) optimal
solution $\bar{P}$ of AC is the solution of
\[
H \circ \bar{P} = (H \circ A)_{\succ}.
\]
\end{cor}

\end{slide}
\begin{slide}{}
{\bf General Constrained Case}

For $\Lambda \in \hn$ and $y \in {\cal C}^m$, let
\[
L(P,y,\Lambda) = f(P)  + \left<y,b-KP\right> - \tr \Lambda P
\]
denote the {\em Lagrangian} of AC.

primal program AC is equivalent to
\[
\mu^* = \min_P \max_{\stackrel{y}{\Lambda \succeq 0}} L(P,y,\Lambda).
\]

Assume that the generalized Slater's constraint qualification,
\[ \exists ~  P \succ  0~ \mbox{with}~ KP=b~,
\]
holds  for AC.
\end{slide}
\begin{slide}{}
Then
\[
\mu^* =  \max_{\stackrel{y}{\Lambda \succeq 0}} \min_P L(P,y,\Lambda)
\]
We can differentiate and get the Wolfe dual: denoted
(DAC)
\[
\begin{array}{ccc}
       \mu^*:=&\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}
\]
\end{slide}
\begin{slide}{}
 \begin{thm}
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}
\]
\end{thm}

\bf Primal-Dual Framework!!

compl slack = duality gap
\end{slide}
\begin{slide}{}
\begin{cor}
The optimal solution of AC is the solution of the two equations
\[
\bar{P} - (\bar{P} - 2H^{(2)} \circ (\bar{P}-A)+K^*y)_{\succ}=0
\]
and
\[
K\left(\bar{P}- 2H^{(2)} \circ (\bar{P}-A)+K^*y\right)_{\succ} = b.
\]
\end{cor}

\begin{cor}
Suppose that $A=0$ and $H=\frac 1{\sqrt{2}}E.$ Then
the optimal solution of AC is:
\[
\bar{P} = (K^*y)_{\succ},
\]
where
\[
K\left(K^*y\right)_{\succ} = b.
\]
\end{cor}
\end{slide}
\begin{slide}{}
{$K=0$ case}

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

Note
\[ H_{ii}=0 ~(P_{ii}~ \mbox{free~})~ \Rightarrow \Lambda_{ii}=0
\]
(dual variable $\Lambda$ takes role of $P^{-1}$ )
\end{slide}
\begin{slide}{}
{\bf Primal-Dual Interior-Point Algorithms}

Linearization of the second equation yields
\[
-(P+h)+ \mu \Lambda^{-1} - \mu \Lambda^{-1} l \Lambda^{-1}=0
\]
We get
\[
h= \mu \Lambda^{-1} - \mu \Lambda^{-1} l \Lambda^{-1}-P.
\]
and
\[
l= \frac 1{\mu}\left\{
     - \Lambda (P+h) \Lambda
 \right\}+\Lambda
\]

Linearization of the dual feasibility equation yields
\[
2 H^{(2)} \circ h -l = -( 2H^{(2)} \circ (P-A) -\Lambda).
\]
\end{slide}
\begin{slide}{}
{\bf Dual-Step-First}

Eliminate the primal step $h$ and solve for the dual step $l$.
\[
\begin{array}{ccl}
l & = &  2 H^{(2)} \circ h + ( 2H^{(2)} \circ (P-A) -\Lambda)\\
&= &  2 H^{(2)} \circ  (\mu \Lambda^{-1} - \mu \Lambda^{-1}l \Lambda^{-1}-P)\\
   &   &  ~~~~~     + ( 2H^{(2)} \circ (P-A) -\Lambda).
\end{array}
\]
We get the Newton equation
\[
 2 H^{(2)} \circ (\mu \Lambda^{-1} l \Lambda^{-1}  ) + l =
 2 H^{(2)} \circ (\mu \Lambda^{-1} -A  ) -\Lambda.
\]
or equivalently
\[
\begin{array}{c}
\left[2\Diag (\kvec (H^{(2)})  \mu (\Lambda^{-1} \otimes \Lambda^{-1})
     + I \right] \kvec (l) \\
  ~~=
       \kvec\left( 2 H^{(2)} \circ (\mu \Lambda^{-1} -A) -\Lambda
\right).
\end{array}
\]
\end{slide}
\begin{slide}{}
Let $F$ denote the $k \times 2$ matrix with row $s$
denoting the $s$-th nonzero element of $H$, i.e. for $s = 1, \ldots, k,$
\[
 (F_{s1},F_{s2})_{s=1, \ldots k} = \left\{ ij : H_{ij} \neq 0
       \right\}.
\]

Note that  the $(kl,ij)$ component of the Hadamard-Kronecker
product $2 H^{(2)} \circ (\mu \Lambda^{-1} l \Lambda^{-1})  $ is found
from
\begin{eqnarray*}
   ~&&2\mu \tr E_{kl} \left(H^{(2)}
          \circ \Lambda^{-1} E_{ij} \Lambda^{-1} \right)\\
   ~   &&~~~= 2 \mu\tr e_ke_{l}^t \left(H^{(2)} \circ \Lambda^{-1}
                   e_ie_j^t \Lambda^{-1} \right)\\
   ~    &&~~~= 2 \mu\tr e_{l}^t \left(H^{(2)} \circ \Lambda^{-1}_{:,i}
                   \Lambda^{-1}_{j:} \right)e_k\\
   ~ &&~~~= 2 \mu H^{(2)}_{lk}\Lambda^{-1}_{li} \Lambda^{-1}_{jk}.
\end{eqnarray*}

This can be ``vectorized'' in MATLAB. The ``sparsity'' (free variables
of $A$) of $H$ can be exploited.

\end{slide}
\begin{slide}{}
{\bf Primal-Step-First}

Alternatively, if many elements of $H$ are sufficiently large, i.e. if
we fix (or specify) elements of $A$;
eliminate $l$ and solve for $h$ first.
\[
 2 H^{(2)} \circ h + \frac 1{\mu} \Lambda h \Lambda   =
        \Lambda -\frac 1{\mu}\Lambda P \Lambda
 -\left( 2H^{(2)} \circ (P-A) -\Lambda \right)
\]
or equivalently
\[
\begin{array}{c}
\left[2 \Diag (\kvec (H^{(2)}) + \frac 1{\mu}(\Lambda \otimes \Lambda)
      \right] \kvec (h) \\
  ~~~=
       \kvec\left( \Lambda -\frac 1{\mu}\Lambda P \Lambda
 -( 2H^{(2)} \circ (P-A) -\Lambda) \right).
\end{array}
\]

The $(kl,ij)$ component of the Kronecker
product $\Lambda \otimes \Lambda$ is found from
\[ \tr E_{kl} \Lambda E_{ij} \Lambda = \tr e_ke_{l}^t \Lambda
   e_ie_j^t \Lambda
= \Lambda_{li} \Lambda_{jk}.
\]


This can be ``vectorized'' in MATLAB. The ``infinities'' (fixed variables
of $A$) of $H$ can be exploited.
\end{slide}
\begin{slide}{}
{\bf The Diagonal of $P$ and $H$}

dual feasibility
\[
2H^{(2)} \circ (P-A)
  -\Lambda =  0 
\]

For $\Lambda \succ 0,$ we cannot fix 
($P_{ii}= A_{ii}$) or free 
($H_{ii}= 0$) the diagonal of $A$
\end{slide}
\begin{slide}{}
\end{slide}
\begin{slide}{}
\end{slide}
\begin{slide}{}
\end{slide}
\begin{slide}{}
\end{slide}
\begin{slide}{}
\end{slide}
\end{document}

